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


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

Анализ агломеративных иерархических методов кластеризации. Выводы




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

Так, ROCK на основе матрицы сходства конструирует граф, используя пороговое значение сходства и принцип общих соседей. По схожей схеме действует метод, основанный на значении взаимного соседства (mnv). CURE также неявно использует в своем алгоритме надстройку над матрицей сходства в виде специального графа, содержащего только представительные точки для каждого кластера. В этом графе присутствуют только ребра, соединяющие точки разных кластеров, после чего выбирается ребро с наибольшим весом, и кластеры, которые оно соединяет, объединяются. Алгоритм CHAMELEON при первоначальной обработке также строит граф по принципу k ближайших соседей и потом использует понятие связи на основе этого графа. Все эти методы безусловно имеют преимущества по сравнению с методами кластеризации, основанными на других мерах близости кластеров. Однако, и у них в той или иной степени встречаются серьезные недостатки.

Несмотря на то, что была доказана наибольшая перспективность агломеративных методов, использующих в той или иной степени принцип попарного среднего, следовало обратить внимание на алгоритм CURE, поскольку он решает проблемы остальных методов в определении различных форм и размеров кластеров, не используя этот принцип. Тем не менее, основанный только на сходстве отдельных точек в кластерах, он, очевидно, может давать положительные результаты, только в случае достаточно равномерного распределения объектов в пространстве, поскольку не учитывает плотности объединяемых кластеров. Так, на Рисунке 7 и 8 изображены по две группы объектов. Вторая пара – лучший кандидат в объединение, исходя из требования к однородности объектов в кластере, а первая, хоть и характеризуется большой взаимной близостью и может быть объединена, на данном этапе должна остаться без изменений.

Алгоритм CURE провел бы верное объединение, только если бы использовал параметр сокращения расстояния представительных точек от центра a=0, то есть объединял бы по методу ближайшего соседа. Однако, тогда исчезали бы его преимущества в определении формы кластеров. В остальных случаях, поскольку CURE не учитывает разницу в плотности (связности) и основан только на взаимном сходстве, данный алгоритм выбрал бы первое, неверное объединение. Если бы сравнивались пары кластеров на Рисунках 8 и 9, то опять же, CURE выбрал бы пару 9, что неверно, вследствие большей взаимной однородности, плотности пары на рисунке 8.




Рисунок 7 – Распределение объектов 1

Рисунок 8 – Распределение объектов 2

Рисунок 9 – Распределение объектов 3

Рисунок 10 – Распределение объектов 4

Рисунок 11 – Распределение объектов 5

Алгоритм ROCK при выборе между парой 7 и парой 8, скорее отдаст предпочтение второй паре, поскольку, плотность создаваемых кластеров ведется с учетом размера кластеров (ожидаемого числа связей в новом кластере). Однако и в этой ситуации ROCK может дать сбой, когда число объектов будет одинаково, а плотность различна. Алгоритм ROCK основан на заданном пользователем пороге близости, то есть, фактически не может учитываться разница во внутренней плотности кластеров. Если распределение объектов в пространстве не равномерное, и плотности на разных его участках различны, алгоритм будет стремиться объединить наиболее плотные кластеры, потому что количество общих соседей для объектов из этих кластеров больше, чем в более разреженных кластерах. Также, ROCK в определенных ситуациях, таких как на рисунках 10 и 11, может совершить неверное объединение (выбрать пару 11), потому что, будучи основан на неверной модели связности (слишком большом пороге близости), не будет учитывать большую силу сходства отдельных объектов, а возьмет в рассмотрение лишь количество связей. Причем метод, основанный на простом попарном среднем в любом случае даст неверный результат.



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

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

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

Во-первых, количество общих соседей точек, что позволит ввести понятие связи и рассматривать только сходства превышающие некий порог (объекты, достаточно далекие друг от друга будут обладать нулевыми значениями связи, у них не будет общих соседей). Причем, как было доказано выделение соседей на основе заданного порогового значения сходства является неэффективным, поскольку может не учитывать различия в плотности кластеров. Такой порог можно устанавливать неявно для каждого объекта или кластера (при объединении), если использовать принципы значения взаимного соседства (mnv) или k ближайших соседей. Первый подход – более динамический, независимый, второй – более производительный, но опирается на заданное статически число k. Использование динамических параметров при определении глобального сходства объектов позволит находить кластеры различной плотности в одном наборе данных.

Во-вторых, непосредственное сходство объектов, что позволит избежать проблем с заданной априорно моделью связности и соседства.

В-третьих, при вычислении близости кластеров, необходимо учитывать их внутреннюю связность и сходство. В этом смысле наиболее перспективным является подход, предложенный в алгоритме CHAMELEON. Соответствующие значения взаимной связности и сходства следует разделять на средние между двумя рассматриваемыми кластерами значения внутренней связности и сходства. Этот подход несколько отличается от используемого в ROCK, поскольку основан не на ожидаемом количестве связей (функция от размера), то есть определяется не статически.

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

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

Последний подход, очевидно, понизит производительность метода, хоть и позволит полностью отказаться от заданных параметров. Если, все-таки, как утверждается многими специалистами, подобный «динамический» порог не будет оказывать отрицательного влияния на результаты анализа и его можно будет подбирать оптимально для конкретного набора данных, то данное ограничение в виду его незначительности можно ввести в окончательный вариант алгоритма кластерного анализа.

В зависимости от используемой модели можно определить оптимальное соотношение глобального и локального сходства в определении близости кластеров (параметр a а произведении относительных сходств).





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


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

Лучшие изречения: Учись учиться, не учась! 10835 - | 8102 - или читать все...

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

 

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


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