Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Кластеризация на основе нечетких отношений

Автор: over 16.2.2010, 11:15

Стоит задача реализации алгоритма кластеризации на основе нечетких отношений (необходимо для кластеризации торговых точек на карте).  Реализовывал алгоритм методом К-средних, но заказчика не совсем устроило. Короче основная проблема в том что я не могу нигде найти нормального описания этого алгоритма, возможно кто нибудь сталкивался и сможет объяснить нормальным языком принцип его работы. Тута есть описалово: http://www.spellabs.ru/FuzzyRelationClastering.htm , но, честно говоря, ничего не понятно. P.S. Особенно пугают такие фразы:  "... На основании метрики определяется нечеткое отношение, обладающее свойствами четкой рефлексивности и нормальной -симметричности. Строится транзитивное замыкание отношения, позволяющее определить для каждого значения в диапазоне от 0 до 1 отношение эквивалентности на исходном множестве ..."    Заранее спасибо!

Автор: Earnest 16.2.2010, 20:11

Честно сказать, особо в математических основах я не копалась (подзабыла этот птичий язык), да и желания особого не было после фразы Цитата Существенным недостатком алгоритма является большое время выполнения, характеризуемое порядком n^4  от числа элементов Но зацепила фраза: Цитата Т.е. два элемента входят в один класс эквивалентности тогда и только тогда, когда между ними есть последовательность попарно близких друг к другу элементов. И тогда я не поняла, причем тут нечеткая логика и n^4, если для решения этой задачи можно использовать так называемые методы "выращивания" (точно не помню). Короче, начинаем с какого-то элемента и присоединяем всех, кто близко лежит хоть к одному из элементов множества. "Близко лежит" тоже как-то определить надо. А дальше осматриваем окружающее текущий кластер пространство на предмет возможных кандидатов на включение. И это будет сильно не n в четвертой, если, конечно, не вычислять каждый раз расстояние кандидатом и между всеми точками кластера.

Автор: W4FhLF 19.2.2010, 08:03

Цитата(over @  16.2.2010,  11:15 ) Реализовывал алгоритм методом К-средних, но заказчика не совсем устроило Что именно не устроило? Вы использовали k-means++ и евклидову метрику?

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)