Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

Динамическая иерархическая агломеративная кластеризация по принципу взаимного соседства




Основная особенность алгоритм, предложенного в [14], состоит в определении «соседей» для каждого объекта (каждого вектора) в пространстве. На входе алгоритма – матрица сходства документов, на выходе – иерархия кластеров.

Состав «соседей» данного объекта зависит от так называемого значения взаимного соседства (mutual neighborhood value – сокр. mnv) между двумя точками, взятого из теории распознавания образов. Пусть P и Q – две точки многомерного пространства. Если P – m-ый ближайший сосед (по степени сходства) Q и Q – n-ый ближайший сосед P, то для точек P и Q: mnv = m + n.

Смысл этой величины заключен в том, что две точки P и Q имеют высокую вероятность нахождения в одном и том же кластере, если не только P близко к Q, но и наоборот. Таким образом, mnv является псевдометрикой и не удовлетворяет аксиоме треугольника.

Параметр MT используется для отражения степени «соседства» объекта в пространстве с использованием mnv. Данная точка Q считается принадлежащей окрестностям точки P (является «соседом» P) , если выполняются следующие условия:

- mnv(P,Q) < MT ;

- не существует точки K, такой, что mnv(Q,K) < mnv(Q,P), но sim(Q,K) ³ sim(Q,P) (sim – мера сходства), а точка P, нарушающая это ограничение становится невалидной по отношению к Q;

- точка Q не невалидная по отношению к P.

Такой подход позволяет на начальном этапе алгоритма получить мелкие кластеры –скопления точек пространства (поскольку никогда ни одна точка не будет по отношению к другой невалидной, если обе эти точки являются ближайщими соседями).

В то же время это позволяет определить те кластеры, которые имеют тенденцию к объединению, но обладают несколько различным внутренним сходством (плотностью). Делается это с помощью ослабления последних двух условий. Для каждого меньшего кластера проверяется, какие точки, ему принадлежащие, принадлежали бы другому, большему кластеру, если бы последние два условия ослабили свое влияние. Более крупный кластер, получивший наибольшее число таких причислений склеивается с этим меньшим кластером.

Необходимо заметить, что последние два условия не игнорируются, а лишь ослабляются, поскольку в противном случае может появиться несколько больших кластеров, которые притянут все более мелкие и затем объединятся сами.

Заключительное разбиение зависит от параметра MT. Если этот параметр увеличивается, то усиливается тенденция к объединению кластеров. Опыты показали [14], что если увеличивать MT , то обнаруживаются промежутки, на которых не наблюдается изменения заключительного разбиения. Очевидно, что разбиения на данных промежутках – оптимальные и при прочих равных требованиях к кластерному разбиению выбираются именно они.




Алгоритм.

Шаг 1. Сортировка матрицы сходства.

Пусть S – матрица сходства и m = MT – 1. Поскольку MT – максимальное разрешенное значение mnv между двумя «соседями», необходимо брать в расчет только m ближайших соседей данной точки. Далее необходимо отсортировать матрицу S, для получения для каждой точки m ближайших соседей. Таким образом, матрица будет представлена как R = [rij], где i – от 0 до N – 1, j – от 0 до m – 1, где rij – j-ый ближайший сосед i.

Шаг 2. Нахождение значений mnv.

Полученная матрица содержит пары N ´ m значений. Необходимо использовать матрицу R, чтобы построить новую матрицу, содержащую значения mnv для каждой из таких пар точек.

Шаг 3. Сортировка полученных значений mnv.

Отсортируем матрицу, полученную на шаге 2 и обозначим ее за V = [vij], где i – от 0 до N – 1, j – от 0 до m – 1, где vij – точка, которая j-ая по близости к i исходя из значения mnv.

Шаг 4. Выделение «соседних точек».

Пусть i=0, j=1 и r=0.

Если mnv(i, vij) £ MT и сходство sim(i, vij) > r, то пометить vij как соседнюю точку i.

r = sim(i, vij). j = j + 1.

Если j ³ m или mnv(i, vij) > MT, то i = i +1.

Если i ³ N, то остановиться, иначе повторить сначала этот шаг.

Можно отметить, что на этом шаге взяты в расчет только 1-ое и 2-ое условие. 3-е условие будет выполнено после удаления отношений соседства тех пар, которые не симметричны.

Шаг 5. Нахождение компонент связности.

Найти на графе окрестностей, составленном ранее, компоненты связности и выделить их как небольшие кластеры.

Шаг 6. Заключительная обработка.

Если есть мелкие кластеры, определить, объединяться ли они с каким-нибудь более крупным, если ослабить условия 2 и 3, и если да, то объединить их.





Дата добавления: 2015-04-01; просмотров: 457; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше... 9286 - | 7362 - или читать все...

Читайте также:

  1. Аэродинамическая компоновка самолета
  2. Базы данных. Модели данных (иерархическая, сетевая, реляционная), их преимущества и недостатки
  3. Взаимного страхования
  4. Взаимного страхования. Для этого необходимо смоделировать возможные последствия на стандартном примере договора факультативного пропорционального перестрахования
  5. Взаимное расположение двух плоскостей. Для двух плоскостей возможны следующие варианты взаимного расположения: они параллельны или пересекаются по прямой линии
  6. Вопрос 6. Организация производства по принципу «точно - вовремя»
  7. Государственное регулирование взаимного страхования в России
  8. Дать определение и назвать характеристики следующих видов остойчивости «поперечная», «начальная», «при больших углах крена», «статическая», «динамическая», «аварийная»
  9. Диафрагменные насосы. Диафрагменные насосы имеют вместо поршня гибкую диафрагму (мембрану) из кожи, прорезиненной ткани или из синтетического ма­териала и работают по принципу
  10. Дивизивиная иерархическая кластеризация. Графо-ориентированные методы кластерного анализа
  11. ДИНАМИЧЕСКАЯ АФАЗИЯ
  12. Динамическая выходная характеристика транзистора. Работа транзистора в ключевом режиме. h-параметры транзисторов


 

3.234.208.66 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.002 сек.