Параметрическая чуствительность метода кластеризации, основанного на анализе плотности распределения объектов

Введение

Целью кластеризации является разбиение исходного множества объектов на группы, которые можно было бы интерпретировать. Группы формируются таким образом, чтобы объекты одной группы были максимально похожи, а разных групп максимально отличались. Основную часть применяемых для этого методов можно разделить на две группы, а именно иерархические и итеративные. В итеративных методах происходит перераспределение объектов между различными кластерами для достижения оптимума характерной для данного метода функции цели [1, 2]. В иерархических методах, строят не одно разбиение выборки на непересекающиеся кластеры, а систему вложенных разбиений.

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

Отрицательная черта применяемых методов заключается в необходимости внесения человеком различных корректирующих параметров, влияющих на результаты и качество проводимого анализа. Примером такого параметра может служить число кластеров, на которое необходимо разбить выборку. Построенное таким образом разбиение может совершенно не совпадать  с тем естественным разбиением, которое бы сделал человек на данной выборке; к таким методам относится метод k-means [6]. Для решения этой проблемы разработаны методы, такие как X-means [3], являющиеся модификациями метода k-means, которые ищут наилучшее разбиение в заданном диапазоне числа кластеров, но это приводит к слишком большим вычислительным затратам. Еще одна группа параметров сильно влияющих на результаты, это различные меры расстояний, задаваемые человеком, например ширина окна в ЕМ-методе [7], длина удаляемых ребер в графовых методах.

Появляются методы, которые пытаются избавить нас от этих сложностей, примером может служить метод, предлагаемый в работе [4], в ней авторы пытаются определить приблизительное число кластеров через поиск их центров. Еще один метод [5], который сами авторы называют G-Algorithm, использует идею о взаимном притяжении объектов. В этом методе объекты под действием силы взаимного притяжения совершают серию перемещений, после чего некоторые из них сливаются, образуя группы, далее отсекаются все группы, состоящие из малого числа объектов. В данном методе делается попытка автоматически определять число кластеров, однако в нем присутствует много задаваемых параметров, которые очень сильно влияют на результаты кластеризации.

Предлагаемый в данной работе метод [8] избавляет нас от этих проблем и позволяет проводить анализ данных подобно тому, как это делает человек, а именно анализируя изменение плотности распределения объектов по пространству, при этом строится единственное разбиение выборки, которое является наилучшим. Также будет рассмотрен вопрос влияния различных параметров на результаты кластеризации, в частности параметра a. Данный параметр в значительной степени влияет на получаемое изменение плотности распределения объектов по пространству, которое в свою очередь напрямую отражается на результатах кластеризации.

Кластеризация объектов через анализ плотности и расстояний

Имеется множество объектов X={x1,x2,…,xn}, которые описывают нашу выборку. Каждый объект xiÎX определяется набором из p параметров, то есть наши объекты представляют собой точки в p-мерном пространстве. В каждой точке этого пространства мы можем вычислить величину, которая будет соответствовать изменению плотности распределения объектов по пространству. Первоначально величина плотности по всему p-мерному пространству при отсутствии в нем объектов равна нулю. Когда мы помещаем в пространство объект, он начинает оказывать влияние на значение плотности по всему пространству, это влияние удобно задавать с помощью функции влияния. Функция влияния должна обладать следующим свойством, величина ее влияния на плотность пространства должна убывать при удалении от объекта. А именно в точке, где располагается сам объект, величина плотности должна равняться единице, при удалении от нее плотность должна опускаться до нуля. Мы можем построить функцию влияния, если представим ее как функцию распределения, которая будет убывать с ростом расстояния, в частности функцию целесообразно представить в следующем виде:

p111

где r — расстояние от объекта до точки, на которую он оказывает свое влияние, a — параметр, влияющий на расстояния в пространстве. При этом предполагается, что чем меньше расстояние между объектами, тем больше они похожи друг на друга. Таким образом, учитывая влияние всех объектов из множества X на пространство, у нас появляется возможность получить плотность распределения объектов по всему пространству. Для дальнейшего анализа нам достаточно иметь значения плотности в точках, где располагаются наши объекты.

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

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

Значения функции P(r) быстро убывают с ростом r, поэтому необходимо, чтобы для областей находящихся внутри кластеров, данный процесс происходил медленнее, чем за их пределами. Данному требованию можно удовлетворить, если правильно задать параметр a, который по своему смыслу аналогичен дисперсии в функциях распределения. Одним из возможных способов задания a может быть его представление в следующем виде:

p112

где n — число объектов составляющих выборку.

Итоговое значение плотности для точек, в которых расположены объекты из множества X, вычисляется следующим образом:

p113

где rij расстояние между объектами  i и j. Функция F(i) выражает величину влияния, оказываемую каждым объектом из множества X на значение плотности в точке, совпадающей с расположением i-го объекта.

После того как вычислены значения функции F(i) для каждого объекта из множества X, можно перейти к распределению объектов по группам. Для осуществления процедуры распределения объектов по группам предлагается использовать следующую функцию:

p114

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

Изначально каждый объект принадлежит группе, которая состоит только из него самого. Далее для каждого объекта i из множества X необходимо определить объект j, на котором достигается максимум функции S(i, j) и провести объединение групп, к которым принадлежат объекты i и j.

После объединения могут появиться группы, состоящие из малого числа объектов, находящиеся на некотором удалении от основных групп с большей численностью. Полученные малые группы необходимо расформировать, а объекты их образующие присоединить к основным группам. В этом случае возникает вопрос, как определять малые и большие группы. Критерием оценки является ли группа малой или большой может быть порог числа элементов, которыми она образована. Такой величиной может быть p115. По сути, малые группы можно рассматривать как шум “noise”. В этом случае группы, число объектов в которых меньше данной величины необходимо расформировать, а объекты их образующие распределить по группам, число объектов в которых превосходит данную величину. Распределение по группам осуществляется с применением функции S(i, j), где объект i будет принадлежать малой группе, а объект j большой группе.

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

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

После того как выполнено распределение по группам для каждого объекта из множества X и проведена повторная кластеризация, мы получим несколько групп объектов, которые теперь мы можем рассматривать как кластеры. В каждом из таких кластеров будет присутствовать объект, для которого значение функция F(i) будет максимальным, он и будет являться центром данного кластера.

Параметрическая чувствительность

Проведенный анализ показал, что качество кластеризации предлагаемого метода в значительной степени зависит от правильности задания параметра a. Если значения a слишком большие, то это может приводить к слиянию нескольких кластеров в один, если слишком малые, то это приводит к дроблению кластеров. Однако было выявлено, что результаты кластеризации практически не будут отличаться, если a будет лежать в широком диапазоне значений. Данный диапазон можно приближенно задать двумя функциями. Нижняя граница значений задается функцией p116. Верхняя граница значений задается функцией p124 . Данные функции были получены экспериментально и носят условный характер. Предлагаемая для вычисления a функция находится внутри данного диапазона. Помимо этого для задания a можно использовать и ряд других функций, например

p117 или p118

где k – отношение максимального расстояния к среднему расстоянию между всеми объектами в нашей выборке.

На рисунке 1 представлены кривые, используемые для задания a. Верхняя и нижняя кривые соответствуют функциям, задающим диапазон значений a. Нижняя кривая из внутренней области это основная функция, предлагаемая для вычисления a, выше нее расположены кривые дополнительных функций приведенных ранее.

p119

Рисунок 1 – Зависимость a от n при k = 3

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

Как можно видеть задать значения параметра a можно и с помощью величины k, которая характеризует анализируемые данные, остальные же величины зависят лишь от числа объектов и постоянны для различных выборок. По значениям k можно косвенно судить о том, чем является анализируемая выборка. Если значения k лежат в районе двух с половиной и ниже то, скорее всего выборка является шумом и никаких четко выраженных скоплений в ней не присутствует. Значения k лежащие в районе трех говорят о том, что в выборке присутствует несколько скоплений объектов, но об их численности ничего сказать нельзя. Значения k лежащие в районе четырех с половиной и больше говорят о том, что выборка состоит либо из одного скопления, либо из группы скоплений, центры которых расположены очень близко. Из этого следует, что при малых значениях k кластеры удалены друг от друга и для их выявления значения a должны быть больше. При больших значениях k кластеры расположены близко друг к другу и для их выявления значения a должны быть меньше. Функции, предлагаемые для вычисления a, удовлетворяют данным требованиям.

На рисунке 2 приведен пример, на котором построена кривая распределения плотности для группы объектов, сами объекты представлены в виде точек в основании графика. Первоначальные расстояния между объектами были увеличены в 1.36 раза, то есть было проведено растяжение пространства, на рисунке представлены новые положения объектов. Для одного из объектов, помеченного вертикальной линией, построен график функции квадратный корень из S. Как видно наибольшие значения функция S для выделенного объекта достигаются на объектах из той же группы, к которой он принадлежит. То есть внутри группы основной вклад в значения функции S вносит плотность, а за пределами расстояние.

p110

Рисунок 2 – Пример кривой распределения плотности объектов и функции S при n = 100 и k = 3.18

Осуществление сжатия или растяжения пространства вызвано необходимостью добиться желаемого поведения функции S. Так при расстояниях больших, чем число объектов, мы будем получать множество групп состоящих из двух трех объектов. Это говорит о том, что основной вклад в значения функции S вносит расстояние. При расстояниях меньших, чем число объектов, мы будем получать одну группу, состоящую из всех объектов. Это говорит о том, что основной вклад в значения функции S вносит плотность. Таким образом, осуществляя сжатие или растяжение пространства, мы устанавливаем связь между плотностью и расстоянием, выравнивая их вклады в значения функции S. На рисунке 2 эту взаимосвязь можно представить тем, что высоты пиков то есть максимальные плотности кластеров примерно соответствуют радиусам самих кластеров.

Примеры

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

p120

Рисунок 3 – Девять кластеров

На рисунке 4 представлен еще один тестовый набор данных, на котором некоторые кластеры расположены близко, помимо этого данные сильно зашумлены. Как видно из рисунка без применения повторной кластеризации метод выявляет только 3 кластера, но при этом устраняет значительную часть шума присутствующего в данных.

p121

Рисунок 4 – Без повторной кластеризации выявлено три кластера

На рисунке 5 представлен тот же тестовый набор данных, что и на рисунке 4, но при анализе была проведена повторная кластеризация, которая позволила выявить семь кластеров.

p122

Рисунок 5 – Повторная кластеризация выявила семь кластеров

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

p123

Рисунок 6 –Три близко расположенных кластера

Заключение

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

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

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

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

Список литературы

[1] Frigui H., Krishnapuram R. Clustering by competitive agglomeration // Pattern recognition, Vol. 30. 1997. — P. 1109-1119.
[2] Pedrycz W. Clustering and Fuzzy Clustering in Knowledge-Based Clustering: From Data to Information Granules // Wiley InterScience, 2005.
[3] Pelleg D., Moore A. X-means: Extending K-means with Efficient Estimation of the Number of Clusters // Seventeenth International Conference on Machine Learning, 2000, -P. 727-734.
[4] Weng L., Xu Y., Li Y., Nayak R. A Novel Cluster Center Estimation Algorithm with Hybrid Partitional Clustering // Conference on Data Mining, 2007. — P. 104-110.
[5] Gomez J., Dasgupta D., Nasraoui O. A New Gravitational Clustering Algorithm // http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.4622.
[6] Stuart P. Lloyd. Least squares quantization in pcm // IEEE Transactions on Information Theory, 1982, 28(2):129–136.
[7] Dempster A., Laird N., Rubin D. Maximum likelihood from incomplete data via the EM algorithm // Journal of the Royal Statistical Society: Series B, November 1977, 39(1):1–38.
[8] Заякин Д.И. Кластеризация объектов на основе анализа плотности их распределения в пространстве признаков // Проблемы управления и моделирования в сложных системах: Труды Х международной конференции. Самара. 2008.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *