Подскажите как сделать из одного множества 2 подмножества? как их разбить?
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > метод к средних (к=2) |
| Автор: Reptor 5.3.2008, 21:02 |
| Я читал про этот метод k средних (в моём случае K=2) но понятного для себя так и не увидел. Подскажите как сделать из одного множества 2 подмножества? как их разбить? |
| Автор: podval 5.3.2008, 21:45 |
| 1. Начальное приближение: первые К наблюдений объявляются принадлежащими К кластерам. Каждое новое наблюдение приписываются к тому кластеру, к которому оно ближе всех. После этого вычисляются центроиды всех кластеров. 2. Итеративный процесс. Каждое из наблюдений проверяется на предмет того, нет ли среди центроидов других кластеров такого, который был бы ближе, чем его собственный центроид. Если да, то данное наблюдение переносится в другой кластер. После прогона всех наблюдений снова вычисляем центроиды. Повторяем до сходимости. Для K = 2 - элементарно. |
| Автор: sergejzr 5.3.2008, 22:44 |
А вот и игрушка соотв  http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/AppletKM.html |
| Автор: Reptor 6.3.2008, 17:46 |
| podval, можеш мне помочь бо я что то не могу понять этот метод? Добавлено через 6 минут и 2 секунды вот у меня есть например вот несколько векторов которые в матрице содержатся 2 3 1 2 3 4 4 3 6 5 9 5 4 2 7 4 1 1 1 1 тут 2 это вектор x1 ну потом идёт х2 х3 и х4 3 6 4 1 так вот как их разбить на 2 класса и найти те самые центройды. |
| Автор: podval 7.3.2008, 14:46 |
| Всё то же самое, только в матричной (векторной) форме. 1. Объявляем х1 и х2 кластерами 1 и 2 соответственно. Берем х3 и вычисляем, к примеру, евклидово расстояние между х1 и х3, а также между х2 и х3. Где это расстояние меньше, в тот кластер и относим х3. Квадрат евклидова расстояние (х1, х3) равен (2 - 1)^2 + (3 - 4)^2 + (6 - 9)^2 + (4 - 7)^2 + (1 - 1)^2 = 1 + 1 + 9 + 9 = 20 Квадрат евклидова расстояние (х2, х3) равен (3 - 1)^2 + (4 - 4)^2 + (5 - 9)^2 + (2 - 7)^2 + (1 - 1)^2 = 4 + 16 + 25 = 45 Выходит, х3 относим к кластеру 1. Аналогично делаем для х4. Вычисляем центроиды. Центроид - это просто вектор средних. Т.е. его компоненты - средние арифметические соотв. компонент всех векторов. Для кластера 1 это Ц1 = (1.5, 3.5, и т.д) 2. Прогоняем теперь векторы по той же схеме, но меряем расстояния между векторами х и найденными центроидами. После того, как раскидаем по новой на кластеры, опять вычисляем центроиды. Повторяем до сходимости. |
| Автор: Reptor 7.3.2008, 16:49 | ||
podval, огромное спасибо. Буду делать программку  Добавлено через 1 минуту и 21 секунду да метод не сложный. По тем формулам что у меня были я его не догонял. Добавлено через 5 минут и 5 секунд podval, да ещё вопросик
что значит в этом алгоритме сходимость и как определить что она была? |
| Автор: podval 12.3.2008, 20:29 |
| Ну, к примеру, если разбивка на кластеры на очередной итерации не отличается от предыдущей итерации, то алгоритм сошёлся. Вообще у этого алгоритма нет строгого доказательства сходимости, но он сходится |
| Автор: sergejzr 12.3.2008, 20:46 |
| Максимальную дельту (разница между координатами центроида до и после итерации) самому надо выбрать. Чем меньше дельта - тем дольше будет алг отрабатывать и тем точнее будет результат. На практике недо смотреть. Если например здания в своём квартале кластеруешь, то дельта в 100 метров будет ОК, а если континенты на глобусе, то , возможно, 100 километров. |
| Автор: Reptor 13.3.2008, 16:42 |
| podval, спасибо я понял. Когда запрограмировал алгоритм стало ясно. И вот сразу по этому вопрос дело в том что это на второй итерации сходимость отработало тоесть кластеры заново не распределились. Вот может это из зи того что я неверно выбрал центроиды для первой итерации? как то не точно мне кажется работает так как сразу решение. sergejzr, не совсем понял что это зп дельта? я такого ничего не делал. |
| Автор: sergejzr 13.3.2008, 16:50 | ||||
|
| Автор: Reptor 17.3.2008, 16:57 |
| как правильно назначить центроиды на первой итерации? Я просто взял точку первую и вторую и всё. |
| Автор: Reptor 19.3.2008, 11:47 | ||
ну неужели нет правил по которым нужно выбрать 2 центроида на 1-ой итерации? |
| Автор: maxim1000 26.10.2010, 22:45 |
| Модератор: новый вопрос выделен в отдельную тему: http://forum.vingrad.ru/forum/topic-313575.html |
| Автор: neutrino 4.11.2010, 15:11 | ||
неа  maxim1000, Что-то там вопрос не так звучит. топикстартер спросил каким образом выбрать начальные центроиды. Ответ: В большинстве случаев делают несколько итераций того же k-means и статистически выбирают центроиды (считают средние для каждого центроида). Метод 2: анализ распределения данных. ИМХО, метод k-means хорош далеко не всегда. Две его большие проблемы: 1) На сколько кластеров разбить множество (если количество кластеров выбрано неправильно, то кластеризация и выеденного яйца не стоит) 2) Как выбрать начальные кластеры (результат алгоритма сильно зависит от начального разделения на кластеры) Чаще небольшой анализ данных может выявить лучший метод для кластеризации. А вот k-means использовать как оптимизирующий алгоритм. |
| Автор: maxim1000 4.11.2010, 20:56 | ||
на всякий случай уточню - новая тема не для какого-то из сообщений в этой теме, а для сообщения, которое я отсюда перенёс |
