Шалымов Д.С. - Алгоритмы устойчивой кластеризации на основе индексных функций и функций устойчивости (1027382), страница 2
Текст из файла (страница 2)
Для этого определяют функциюs(i) =b(i) − a(i),max (a(i), b(i))где a(i) — среднее расстояние между i-ой точкой и всеми остальными наблюдениями, попавшими в тот же кластер, b(i) — среднеерасстояние до точек в ближайшем кластере, где под ближайшимкластером понимается тот, который минимизирует b(i). Количествокластеров считается верным, если оно максимизирует среднее значение s(i).Другой, более редкий, метод использует статистику расхождений [5], вычисляя1 Xlog Wb∗ (K) − log W (K).GAP (K) =BbМетод использует B различных унифицированных множеств, каждое из которых состоит из того же количества элементов, что и оригинальное множество. Строится внутренняя сумма квадратов дляразличного количества кластеров.
Требуется подобрать K, максимизирующее GAP (K).Существуют методы, основанные на использовании ядер длявероятностных распределений элементов внутри кластеров [6], которые оперируют с двумя выборками элементов. Выборки производятся согласно двум распределениям. Первое — это исходное распределение данных, второе построено таким образом, что оно представляет ядра кластеров. Качество кластера считается по мере схожести его со своим ядром.241Известен эффективный непараметрический метод, предложенный Sugar and James [7].
Он основан на использовании “искажений”, которые по своей сути являются оценками дисперсии внутрикласса. Для иллюстрации эффективности алгоритма строится специальный функционал зависимости минимального “искажения” отколичества кластеров, который убывает с ростом количества кластеров. Минимальное “искажение” определяется следующим образом: на множестве данных с учетом текущего количества кластеровзапускается какой-либо алгоритм кластеризации. Как правило, этоk-means.
Множество разбивается на отдельные кластеры, для каждого из которых подсчитывается внутренняя дисперсия. Из множества значений дисперсий выбирается наименьшее, которое принимается за минимальное “искажение” и становится значением функционала при данном количестве кластеров. Теоретически и эмпирически доказывается, что, при определенном выборе параметраY (степень трансформации), построенная для функционала кривая будет иметь резкий скачок в том месте, которое соответствуетдействительному количеству кластеров.Процедура определения количества кластеров состоит из следующих шагов:1. Запускается k-means алгоритм для K кластеров и определяется соответствующее “искажение” dbk . Для различных значений Kстроится набор dbk .2.
Выбирается степень трансформации Y > 0 (обычно принимается Y = p/2).3. Вычисляются скачки по формуле Jk = db−Y− db−Ykk−1 .4. За итоговое количество кластеров выбирается то, которое соответствует наибольшему скачку K ∗ = arg maxk Jk .На рис. 1 изображены зависимости “искажений” от количествакластеров.
В данном случае использовано Гауссово распределение,однако метод был апробирован также на негауссовых данных.4.Подходы на основе функций устойчивостиФункции устойчивости, как правило, основаны на подсчете количества различий в метках, задаваемых элементам множества на242Рис. 1: a) Набор из девяти кластеров (Гауссово распределение) b) Кривая функционала (внутренняя дисперсия - количество кластеров) c)Преобразованная кривая, показывыающая количество кластеров, равноедевяти.
d) Кривая скачков.каждой итерации алгоритма. Рассмотрим некоторые из них.Основная идея метода, предложенного в [8], заключается в использовании вычислительной процедуры разбиения на группы, которая работает эффективно, когда она идентифицирует схожие структуры за счет многократного применения алгоритмов кластеризации. Выборки производятся за счет произвольного выбора элементов исходного множества.
Первая выборка, Y , считается обучающим множеством. На основе этой выборки анализируется тестовоеподмножество. Пусть αk,Y (z) и αk (z) определяют метки элементовz ∈ Z на основе анализа выборки Y и на основе непосредственногоприменения алгоритма кластеризации соответственно.Например, αk,Y (z) может быть реализован с помощью определения каждого элемента из Z к ближайшему центру кластера в Y .Разница между метками используется функцией устойчивости длявычисления структуры кластеров. Так как не используется заранееизвестных меток для кластеров, значения меток могут быть перемешаны от одной реализации к другой.
Таким образом, вводитсяфункция перестановки ψ. Эта функция соотносит индексы междуметками так, что соотношение между метками максимально. Длярешения этой задачи используется Венгерский метод [9], сложностькоторого O(k 3 ). В данном случае устойчивость определяется сле-243дующим образом:S(αk ) = maxψXI(αk,Y 6= ψ(αk (z))).z∈ZФункция устойчивости зависит от k.
За результирующее количество кластеров принимаетсяk∗ = min S(αk ).kАлгоритм в общем виде можно описать следующим образом.1) Из исходного множество производятся две независимые выборки, в результате чего формируются множества O1n и O2n , равномощные исходному.2) Применяется алгоритм α1 к первому множеству O1n , результатом чего является разбиение множества на k кластеров.3) Применяется алгоритм α2 ко второму множеству O2n .
Алгоритм α2 используется для предсказания кластерной принадлежности всех элементов первого множества O1n4) Каждый элемент множества O1n теперь имеет две маркировки. С помощью Венгерского метода [9] определяется корректнаямаркировка всех элементов множества O1n . В качестве стоимостиидентификации меток i и j принимается количество несовпадений по сравнению с маркировкой, произведенной в ходе алгоритмаα1 (O1n ), которая считается корректной.5) Подсчитывается среднее значение “нестабильности” при заданном количестве кластеров k на основе стоимости идентификации меток.6) За итоговое количество кластеров принимается такое k, которое минимизирует “нестабильность”.Алгоритмы α1 , α2 и множества O1n , O2n могут быть различны.Но, как правило, используется один алгоритм кластеризации α имножества O1n , O2n содержат все элементы исходного множества иравномощны ему.244Используя два независимых множества из одного и того же источника данных, задача кластеризации переформулируется как задача обучения с учителем, где в качестве учителя выступает разбиение на кластеры первого множества.Следующий алгоритм [10] применяется для данных, которыесодержат в себе помехи.
Может применяться для сравнения различных алгоритмов. Помехи обрезаются за счет передискретизацииисходного множества данных.Используются матрицы кластерной связности(1 i, j ∈ SameCluster,Ti,j =0 otherwise.Функция устойчивости основана на сравнении матриц связности всех выбранных подмножеств и исходного множества. Производится следующее: сперва выделяются для одного разбиения все такие элементы, которые попали в один кластер как в данном разбиении, так и в исходном множестве. Далее производится выделениетаких элементов по всем разбиениям и выбираются те элементы,которые находились в одном кластере в большей части разбиений.По сути функция устойчивости измеряет, насколько предложенноев ходе передискретизации разбиение на кластеры совпадает с кластерами в исходном наборе данных.Многие алгоритмы используют параметры, которые определяют разрешение, с которым производится идентификация кластеров.
Например, в агломеративных (объединительных) методах кластеризации такие параметры определяют высоту дерева, по которому осуществляется кластеризация. В неиерархических методахтакими параметрами может определяться количество допустимыхсоседей для элемента в кластере.В данном алгоритме важным является предположение, что параметры алгоритма, влияющие на качество результата, не зависятот размера исходных данных.
Суть алгоритма заключается в следующем.1) Выбираются значения параметров алгоритма кластеризации.2) Производится кластеризация для всего набора данных.2453) Произвольным образом набор данных разбивается на подмножества.4) Для каждого подмножества запускается алгоритм кластеризации.5) На основе шага 1 и 3 с помощью матриц связности вычисляется значение кривой качества.6) Изменяются параметры алгоритма. Стабильными кластерами считаются те, при которых кривая качества достигает наибольших значений.Другой робастный алгоритм кластерной устойчивости [11] подсчитывает количество одинаковых меток у элементов, общих длянескольких выборок. Предполагается эффективным для любых алгоритмов кластеризации, однако авторами апробировался на иерархических алгоритмах.
В ходе работы алгоритма используются искусственные возмущения исходных данных и строятся дендрограммы. Используются подмножества исходного множества. Для общихточек подмножеств вычисляются схожести кластеризации. Плюсомявляется то, что для корректной работы не делается никаких предположений о распределении данных или о форме кластеров. Алгоритм позволяет также определить наличие или отсутствие какойлибо структурированности в наборе данных.5.ЗаключениеВ статье описаны основные алгоритмы устойчивой кластеризации на основе индексов и на основе функций устойчивости. Кластеризация имеет большое количество приложений.
Исследованиеи апробация существующих алгоритмов на реальных данных позволяет узнать их сильные и слабые стороны. На основе этой информации впоследствии могут быть предложены новые алгоритмы,которые будут обладать полезными свойствами. Например, будуттребовать небольших вычислительных затрат, будут помехоустойчивыми и способными давать адекватные оценки на множестве данных различной природы.В качестве возможного решения могут быть предложены, например, алгоритмы многомерной оптимизации, эффективность которых была продемонстрирована в целом ряде прикладных задач.246Поскольку данные методы оптимизации хорошо описаны математически, новые методы также удастся строго описать.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
