Хостинг Портала RusFAQ.ru:
MosHoster.ru - Профессиональный хостинг на Windows 2008

РАССЫЛКИ ПОРТАЛА RUSFAQ.RU

Чемпионы рейтинга экспертов в этой рассылке

Micren Статус: Студент Рейтинг: 129 ∙ повысить рейтинг >>

Ross Статус: Практикант Рейтинг: 15 ∙ повысить рейтинг >>

Бородин Константин Игоревич Статус: 2-й класс Рейтинг: 10 ∙ повысить рейтинг >>

/ КОМПЬЮТЕРЫ И ПО / Языки программирования / .NET

Выпуск № 113
от 17.02.2009, 14:35

Вопрос № 160240: помогите реализовать такой алгоритм кластеризации k-середных для матрицы на С# или С++Builder алгоритм представляет собой итерационную процедуру, в которой выполняються следующие шаги. 1.Выбирается число кластеров k Из исходного множе...

Вопрос № 160.240

помогите реализовать такой алгоритм кластеризации k-середных для матрицы на С# или С++Builder алгоритм представляет собой итерационную процедуру, в которой выполняються следующие шаги. 1.Выбирается число кластеров k Из исходного множества данных случайным образом выбираются k записей,которые будут служить начальными центрами кластером 2.ля каждой записи исходной выборки определяется ближайший к ней центр кластера. При етом записи, "притянутые"определенным центром образуют начальные кластеры 3.Вычисляются центроиды - центры тяжести кластеров. Каждый центроид - это вектор, элементы которого представлят собой средние значения признаков, вычисленные по всем записям кластера. 4.Затем центр кластера смещается в его центроид. затем 3-й и 4-й шаги итеративно повторяются. Очевидно,что на каждой итерации происходит изменение границ кластеров и смещение их центров.В результате минимизируется расстояние между элементами внутри кластеров. Остан овка алгоритма производится тогда, когда границы кластеров и расположения центроидов не перестанут изменятся отитерации к итерации, т.е.на каждой итерации в каждом кластере будет оставаться один и тот же набор записей. алгоритм реализовать в процедуре(функции), входные данные -матриця, результат - число кластеров(и содержание кластеров)

Отправлен: 11.02.2009, 21:53 Вопрос задала: Иванка (статус: Посетитель) Всего ответов: 1 Мини-форум вопроса >>> (сообщений: 3)

Отвечает: Micren Здравствуйте, Иванка! Сразу разъясню некоторые моменты: 1)В программе матрица генерируется автоматически при помощи System.Random. Т.е. это самый тяжелый случай для кластеризации. На кореллирующихся данных результат будет соответственно лучше. 2)Заранее число кластеров неизвестно и выбирать его случайным образом смысла нет. Это не соответствует практике. Вместо этого вводится допустимое максимальное отклонение записи от центра кластера и начинается перебор кластеров от 1 и до того момента пока максимальное отклонение не станет меньше заданного. 3)Начальные значения для центроидов выбираются не совсем случайно. Для упорядоченных матриц случайный выбор это плохой вариант, а для неупорядоченных разницы нет никакой. Но если же Вам нужно именно случайный выбор то измените функцию InitialCentroids() на свое усмотрение. 4)Результат работы метода кластеризации эт о класс с определенными полями, а именно:Size-к-во кластеров;AverageDeviation,MaxDeviation-среднее и максимальное отклонение от записей от центра кластера. Кроме этого добавлен индексатор аргументом которого является номер кластера, а результат список номеров записей в матрице(чтоб постоянно не копировать всю матрицу) 5)Элементом кластера является запись(строка) матрицы, а не отдельный элемент. Иначе нет смысла в матрице вообще. Можно обойтись одномерным массивом. Малый объем допустимого приложения не позволяет здесь выложить код. Поэтому Вы можете скачать весь проект на http://rapidshare.com/files/198745652/160240.rar Желаю удачи! Добавлена информация из мини-форума по просьбе эксперта: Исправил некоторые ошибки. Пожалуй, это можно считать окончательны м вариантом. Кроме того. Если к примеру начальные центроиды расположены близко друг к другу или совсем равны(например все строки матрицы одинаковые), а Вы пытаетесь разбить на много кластеров то реально используется только один центроид, но расчет в первой программе шел все равно по всем центроидам. Это не влияло на результат, но было совершенно излишне. Здесь ситуация исправлена. Проверялась на .NET 3.5 Код: using System; using System.Collections; using System.Collections.Generic; using System.Linq; using ClusterAnalyze; namespace _160240 { class Program { static void Main(string[] args) { uint rows, cols; rows = InputUInt("Введите количество строк матр ицы:"); cols = InputUInt("Введите количество столбцов матрицы:"); double[,] matrix; try { matrix = new double[rows, cols]; Random rndGen = new Random(); for (uint i = 0; i < rows; i++) { for (uint j = 0; j < cols; j++) { matrix[i, j] = rndGen.NextDouble() * 100 - 50; } } Console.WriteLine("Исходная матрица:"); for (uint i = 0; i < rows; i++) { for (uint j = 0; j < cols; j++) { Console.Write("{0,7:F3} ", matrix[i, j]); } Console.WriteLine(); } double deviation = InputDouble ("Введите желаемую погрешность:"); try { ClusterAnalyze.ClusterResult result = KMeans.Solve(matrix, rows, deviation); uint clusterNo = 0; foreach (ClusterAnalyze.ListOfRecords cluster in result) { Console.WriteLine("Кластер {0}", ++clusterNo); foreach (uint line in cluster) { for (uint i = 0; i < cols; i++) { Console.Write("{0,7:F3} ", matrix[line, i]); } Console.WriteLine(); } } Console.WriteLine("Среднее отклонение:{0}", result.AverageDeviation); Console.WriteLine("Мак симальное отклонение:{0}", result.MaxDeviation); } catch (ClusterAnalyze.ClusterAnalyzeException ex) { ErrorMsg(ex.Message); } } catch (OutOfMemoryException) { ErrorMsg("Не могу выделить память для матрицы"); } Console.WriteLine("Нажмите любую клавишу для выхода"); Console.ReadKey(); } /// <summary> /// Ввод числа типа double /// </summary> /// <param name="msg">Сообщение</param> /// <returns>Число</returns> static double InputDouble(string msg) { while (true) { Console.Write(msg); try { double val = Conver t.ToDouble(Console.ReadLine()); return val; } catch (FormatException) { } catch (OverflowException) { } ErrorMsg("Неверный ввод: ожидается действительное число"); } } /// <summary> /// Ввод числа типа uint /// </summary> /// <param name="msg">Сообщение</param> /// <returns>Число</returns> static uint InputUInt(string msg) { while (true) { Console.Write(msg); try { uint val = Convert.ToUInt32(Console.ReadLine()); return val; } catch (FormatException) { } catch (OverflowException)< br> { } ErrorMsg("Неверный ввод: ожидается целое положительное число"); } } /// <summary> /// Ввод числа типа uint в заданном диапазоне /// </summary> /// <param name="msg">Сообщение</param> /// <param name="lo">Нижняя граница</param> /// <param name="high">Верхняя граница</param> /// <returns>Число</returns> static uint InputUInt(string msg, uint lo, uint high) { while (true) { uint val = InputUInt(msg); if (val >= lo && val <= high) return val; ErrorMsg(String.Format("Неверный ввод: ожидается значение в интервале {0}..{1}", lo, high)); } } /// <summary> /// Выводит сообщение об ошибке /// </summary> /// <param name="msg">Сообщение</param> static void ErrorMsg(string msg) { ConsoleColor color = Console.ForegroundColor; Console.ForegroundColor = ConsoleColor.Red; Console.WriteLine(msg); Console.ForegroundColor = color; } } } namespace ClusterAnalyze { /// <summary> /// Класс для кластерного анализа /// </summary> static class KMeans { /// <summary> /// Решает задачу кластеризации /// </summary> /// <param name="matrix">Исходная матрица</param> /// <param name="numCluster">Количество кластеров</param> /// <returns>Результат анализа</returns> public static ClusterResult Solve(double[,] matr ix, uint numCluster) { return Clustering(Matrix2JadMatrix(matrix), numCluster); } /// <summary> /// Решает задачу кластеризации /// </summary> /// <param name="matrix">Исходная матрица</param> /// <param name="maxNumCluster">Ограничение на количество кластеров сверху</param> /// <param name="deviation">Допустимое отклонение записи от центроида</param> /// <returns>Результат анализа</returns> public static ClusterResult Solve(double[,] matrix, uint maxNumCluster, double deviation) { if (deviation == 0) deviation = 1e-10; else deviation = deviation < 0 ? -deviation : deviation; ClusterResult res; double[][] jadMatrix = Matrix2JadMatrix(matrix); uint clusters = 0; do { res = Clustering(jadMatrix, ++clusters); } while ((clusters < maxNumCluster) && (res.MaxDeviation > deviation)); GC.Collect(); return res; } /// <summary> /// Собственно решение здесь /// </summary> /// <param name="matrix">Матрица</param> /// <param name="numCluster">Количество кластеров</param> /// <returns>Результат анализа</returns> private static ClusterResult Clustering(double[][] matrix, uint numCluster) { uint rows = (uint)matrix.Length; // Количество кластеров должно быть не менее 1х и не более чем записей if (numCluster > rows || numCluster < 1) throw new ClusterAnalyzeException("ClusterResult Clustering(double[][] matrix, uint numCluster) : " + "Количество кластеров меньше 1 или больше чем число строк в матрице"); uint cols = (uint)matrix[0].Length; // Задаем центроиды для начала double[][] centroids = InitialCentroids(matrix, numCluster); bool isCont; // Словарь ключями которого являются номера центроидов, а значениями списки записей в матрице Dictionary<uint, ListOfRecords> clustersDict; double averageDeviation, maxDeviation; do { clustersDict = new Dictionary<uint, ListOfRecords>(); // Отклонения от центроидов averageDeviation = 0; maxDeviation = 0; // Для заданных центроидов определяем к какому кластеру относятся записи for (uint i = 0; i < rows; i++) { // Индекс ближайш его uint nearest = 0; // Минимальная дистанция double minDistance = Range(centroids[0], matrix[i]); // Перебор центроидов for (uint j = 1; j < numCluster; j++) { double distance = Range(centroids[j], matrix[i]); if (distance < minDistance) { minDistance = distance; nearest = j; } } averageDeviation += minDistance / rows; maxDeviation = maxDeviation < minDistance ? minDistance : maxDeviation; // Добавляем в словарь if (!clustersDict.ContainsKey(nearest)) { clustersDict.Add(nearest, new ListOfRecords()); } clustersDict[nearest].Add(i); } // Если есть не рабочие центроиды то избавимся от них if (clustersDict.Count != numCluster) { numCluster = (uint)clustersDict.Count; double[][] tmpCentroids = new double[numCluster][]; Dictionary<uint, ListOfRecords> tmpClusterDict = new Dictionary<uint, ListOfRecords>(); uint newNo = 0; foreach (uint oldNo in clustersDict.Keys) { tmpCentroids[newNo] = centroids[oldNo]; tmpClusterDict.Add(newNo, clustersDict[oldNo]); newNo++; } centroids = tmpCentroids; clustersDict = tmpClusterDict; } // Флаг продолжения итераций isCont = false; // Считаем новые центроиды double[][] newCentroids = new double[numCluster][]; foreach (uint i in clustersDict.Keys) { newCentroids[i] = new double[cols]; uint itemsInCluster = (uint)clustersDict[i].Count; foreach (uint line in clustersDict[i]) { for (uint j = 0; j < cols; j++) { newCentroids[i][j] += matrix[line][j] / itemsInCluster; } } // Сравниваем со старым центроидом и копируем в него, если есть различие for (uint j = 0; j < cols; j++) { if (centroids[i][j] != newCentroids[i][j]) { centroids[i][j] = newCentroids[i][j]; isCont = true; } } } } while (isCont); return new ClusterResult(clustersDict, averageDeviation, maxDeviation); } /// <summary> /// Возвращает начальные значения для центроидов /// </summary> /// <param name="matrix">Матрица</param> /// <param name="numCluster">Количество кластеров</param> /// <returns>Двухмерный массив центроидов</returns> private static double[][] InitialCentroids(double[][] matrix, uint numCluster) { uint rows = (uint)matrix.Length, cols = (uint)matrix[0].Length; double[][] centroids = new double[numCluster][]; for (uint i = 0; i < n umCluster; i++) { centroids[i] = new double[cols]; uint line = i * rows / numCluster; for (uint j = 0; j < cols; j++) { centroids[i][j] = matrix[line][j]; } } return centroids; } /// <summary> /// Вычисляет среднеквадратичное отклонение между двумя векторами /// </summary> /// <param name="array1">1й вектор</param> /// <param name="array2">2й вектор</param> /// <returns>Отклонение</returns> private static double Range(double[] array1, double[] array2) { uint len; if ((len = (uint)array1.Length) != array2.Length) throw new ClusterAnalyzeException("double Range(double[] array1, double[] array2): " + "Массивы имеют разную длину"); double sum = 0; for (uint i = 0; i < len; i++) sum += Math.Pow(array1[i] - array2[i], 2); return Math.Sqrt(sum / len); } /// <summary> /// Преобразует массив вида [,] к [][] /// </summary> /// <param name="matrix"></param> /// <returns></returns> private static double[][] Matrix2JadMatrix(double[,] matrix) { uint rows = (uint)matrix.GetLength(0), cols = (uint)matrix.GetLength(1); double[][] jadMatrix = new double[rows][]; for (uint i = 0; i < rows; i++) { jadMatrix[i] = new double[cols]; for (uint j = 0; j < cols; j++) { jadMatrix[i][j] = matrix[i, j]; } } return jadMatrix; } } /// <summary> /// Результат анализа возвращается в виде этого класса /// </summary> public class ClusterResult : IEnumerable { /// <summary> /// Конструктор класса /// </summary> /// <param name="dict"></param> /// <param name="averageDeviation">Среднее отклонение</param> /// <param name="maxDeviation">Максимальное отклонение</param> public ClusterResult(Dictionary<uint, ListOfRecords> dict, double averageDeviation, double maxDeviation) { AverageDeviation = averageDeviation; MaxDeviation = maxDeviation; data = dict.Values.ToArray(); } /// <summary> /// Список индексов записей в кластере /// </summary> /// <param name="Index">Номер кластера</param> /// <returns>Список индексов записей</returns> public ListOfRecords this[uint Index] { get { return data[Index]; } } /// <summary> /// Количество кластеров /// </summary> public uint Size { get { return (uint)data.Length; } } /// <summary> /// Возвращает тип перечислителя /// </summary> /// <returns>Перечислитель</returns> public IEnumerator GetEnumerator() { return data.GetEnumerator(); } /// <summary> /// Средне отклонение записей от центроидов кластеров /// < /summary> public readonly double AverageDeviation; /// <summary> /// Максимальное отклонение от центроидов кластеров /// </summary> public readonly double MaxDeviation; private readonly ListOfRecords[] data; } /// <summary> /// Класс-исключение для перехвата ошибок возникающих в классе ClusterAnalyze /// </summary> public class ClusterAnalyzeException : ApplicationException { /// <summary> /// Конструктор /// </summary> /// <param name="msg">Сообщение об ошибке</param> public ClusterAnalyzeException(string msg) : base(msg) { } } /// <summary> /// Класс список номеров записей в файле. Служит исключительно как синоним базового класса /// </summary> public class ListOfRecords : List< uint> { } } http://rapidshare.com/files/198909615/160240-2.rar Редактирование - удалено несколько обращений. Добавлена информация из мини-форума по просьбе эксперта. -------- ∙ Отредактировал: deepTeNk, Академик ∙ Дата редактирования: 17.02.2009, 00:49 (время московское)

Ответ отправил: Micren (статус: Студент) Ответ отправлен: 16.02.2009, 15:26 Как сказать этому эксперту "спасибо"? Отправить SMS #thank 243776 на номер 1151 (Россия) | Еще номера >> Отправить WebMoney: Неплохо (10 руб.) Хорошо (15 руб.) Отлично (20 руб.) БЛЕСТЯЩЕ! (30 руб.) Вам помогли? Пожалуйста, поблагодарите эксперта за это! Оценка за ответ: 5 Комментарий оценки: очень красиво и качественно написано!

© 2001-2009, Портал RusFAQ.ru, Россия, Москва. Авторское право: ООО "Мастер-Эксперт Про" Техподдержка портала, тел.: +7 (926) 535-23-31 Хостинг: "Московский хостер" Поддержка: "Московский дизайнер" Авторские права | Реклама на портале ∙ Версия системы: 5.13 от 01.12.2008
RusFAQ.ru | MosHoster.ru | MosDesigner.ru RusIRC.ru | Kalashnikoff.ru | RadioLeader.ru