АЛГОРИТМ ОСРЕДНЕНИЯ В КЛАСТЕРИЗАЦИИ ДАННЫХ*

Abstract

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

Aidagulov R.R., Glavatsky S.T.

ALGORITHM OF AVERAGING IN DATA CLUSTERING

Принято считать, что термин «кластеризация» (сгусток, пучок), был предложен математи Р. Трионом. Впоследствии возник целый ряд терминов, которые рассматриваются как синонимы тер «кластерный анализ» или «автоматическая клиаксасциифя». У кластерного анализа очень широкий спектр применения, его методы используются в медицине, химии, археологии, маркетинге, геоло других дисциплинах.

Кластеризация состоит в объединении в группы схожих объектов, и эта задача является фундаментальных в области анализа данных. Обычно под кластеризацией понимается разбие заданного множества точек некоторого метрического пространства на подмножества таким образ чтобы близкие точки попали в одну группу, —ав драалзьнныие. Как мыажепмок ниже, это требование является достаточно противоречивым. Интуитивное разбиение «на глаз» использует соображен связности получаемых групп, исходя из плотности распределения точек. В данной работе предл алгоритм, основанный на этой идее. Постановка задачи

Согласно [ 1 ], кластеризац—ияэто процесс аналитического рассмотрения заданного множества точек и дальнейшей группировки точек в кластеры согласно некоторой метрике. При этом предполагае точки, попадающие в один кластер, должныспоблыотжьеныра недалеко друг от друга, а попадающие в разные кластеры— далеко. Подчас исследователи под кластеризацией набора точек понимают разбиен этого множества (набора) на подмножества таким образом, чтобы близкие точки попали в одну дальние — в разные. Несложно понять, что такое требование противоречиво.

Действительно, пусть самые удаленные друг от друxг,аy (тоzч,кtи (x, y)   (z,t)) могут быть соединены -путем x0  x,..., xn  y так, что (xi , xi1)   . Наличие такой связи наз-осввеямзностью. В многомерном (не одномерном) пространс-тсввеязность самых удаленных точек не дает однозначного ответа, попадут они в один кластер или нет. Это будет зависеть от геометрического располож набора точек. В случае попадания самых дальних точек в один кластер не будет выполнен близости точек из одного кластера, а в случае их попадания в разные кластер1ыi длnя некоторо близкие

точки (xi , xi1)   попадут в разные кластеры. Таким образом, приведенное выше требован является противоречивым.

Пример. В конфигурации точек, приведенной на Рисуонвкеек 1р,азчоебльет множество точек на 2 кластера, проведя разделительную границу около D.точВки то же время большинство алгоритмов кластеризации включат точCк,иD, C' в один кластер, используя при-нсцвиязпности. Такое применение -связности напоминает иг"рИуз мухи сделать слона":

МУХА-МУНА-МИНА-ЛИНА-ЛИНН-ЛИОН-СИОН-СЛОН, и почти неприменимо к произвольному расположению точек.

Человек интуитивно группирует точки согласно плотности их распределения. Когда наблюдают дальние галактики в телескопн,е овниидят отдельные звезды, и относят их к галактикам согласно распределению яркости (плотности).

Лишь в одномерном слу-чсавеязность характеризует плотность расположения точек на заданном отрезке. Уже в двумерном пространстве (как вид2н)о эитзо Рниес. так. В метрическом пространстве неравенство треугольника в свойствах метрики озкнлаочсатеьт выпу Плотность распределения существенно зависит от реальной Реальная размерность определяется из матрицы расстояний:

R  ( ij ),  ij   (xi , x j ), i, j  1,2,...,n.

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

Понятие выпуклости и вогнутости в метрических пространствах связаны с преобразовани Лежандра, с вариационным исчислением. В частности, значение расстояния между двумя точ удовлетворяет вариационному принципу:  (x, y)  inf il  (xi , xi1 ), x0  x, xl  y.

i0 Здесь inf берется по всем путlязмвенсьями, соединяющим точxки y, приl= 1,2,...

Это соотношение может быть использовано для определения метрики по нечетко заданным о экспертов. Например, пусть на множестве картин эксперты определили оценки всхеохжепстаир для картин (xi, xj), гдiе, j = 1,2,...,n, сопоставляя этим парам числа из [0о,1тр].еОзцкаенка 1 ставится в случае полной идентичности и— в0 случае полного несходства (бесконечной удаленности)S.(xi,Пxуj)ст—ь некоторое среднее значение (пмо вэскеспертам) выставленных оценок. Это симметричная функция от двух переменных. Определим вначале фунsк(цxiи, юxj )  log c S(xi , x j ), 0  c  1.

Эта функция близка к определению расстояния, однако может не удовлетворять нераве треугольника. Среднее значение (за исключением среднеготричгеесокмоего) может нарушить выполнение этого неравенства. Однако мы можем (как выше) определить расстояние по вариаци принципу:

il  (x, y)  inf  s(xi , xi1 ), x0  x, xl  y.

i0 Теперь все условия метричности выполнены.

Далее мы построим алгоритм кластеризации на принципах плотностной соввяозкиупнмоесжтядмуи с точек. Плотность расположения зависит от реальной размерности набора точек. Величина размерности — положительное, но не обязательно целое число (наподобие размерности Хаусдорфа), будет определена ниже. Отличие реальной размернорстаизмеронтости вмещающего Евклидова пространства хорошо видно на следующем пnртиомчеерке на кривой Веронезе.

Пусть заданыn точек на кривойd-мверном Евклидовом пространстxвiе (xi1,...,xid ), i 1,...,n, где xij  j ( yi ),  j ( yi ) C . Кривая

Веронезе определяется вложенj (иxе)м x j , x  0, и тем, чтоn > d точек на кривой не могут быть изометрично размерности меньшdе. Этиn точек образуют конфигурацию с реальной то же время не вложимы изометрично в пространство размернdо.сти характеризуется вложены в Евклидово простра размерностью близкой к 1, меньше Одномерный случай Как узнать по заданной матрице расстaоijяни й(xi , x j ) , находятся точки в одномерном пространстве или в пространстве большей размерности?

Для статистической значимости ответа будем полагать, что количnес—твдоостаотчоечкно большое число. ПустьD   (x1,...,xn) — диаметр множества точек. Если точки можно пронумеровать так, чтоб сумма длинL  nl  (xi, xi1) совпала сD, то мы можем утверждать, что точки находятся на одномер i1 прямой. Действительно, в этом случае существует изометрия (отображение сохраняющее взаим расстояния) точек номжества на точки прямой линии. В случLане,енакмонгдоаго (например, не более чем в 2 раза) превосDхо,дитто также можно утверждать, что точки множества лежат на одноме кривой. При этом сама кривая изометрически может быть вложена в Евакнлстивдоовотолпьркоостр очень большой размерности.

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

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

Для определения от,ог какие расстояния между соседними точками следует считать большим рассмотрим задачу случайного равномерного разделения отрезкаL ндалиnнычастей. Для этого с помощью генератора случайных чисел, распределённых равномеортнроезкена [ 0,1 ]в, ыработаем n-1 чисел yi и разрежемотрезок [L0], в точках с координатxаiм=иLyi. Вычислим теперь математическое ожидание длины самого большого l1к,ускслаедующего по дл—инl2еи т.дk.,-го по дли—неlk. Пустьl= L/n — средняя длина полученных кусков. Велиliчвиынрыазим в безразмерных величинах, относя их к средней длинlе.

При n = 2 задача решается несложно. С вероятн0о,с5тьиюмеем y1 < 0,5, и средняя длина меньшего 3 1 1 куска (при масштабе длинl)ы естьl1  2  1 , длина следующего отр—езка . В общем случае имеет 2 2 место следующее утверждение.

Теорема. Математические ожидания длин отрезков при случайном равномерном делении отрезка L] нnа частей выражаются формулами: покрытия нашего множества при0 . Так как у нас конечное чиnс,лототопчреки олмюбнеобходимое количество шаров не превосхоnд.итТем не менее, нужную размерность можно определить через танг угла в линейной аппроксимации логарифма от количества точек в зависимости от (при увел логарифма радиуса. Для этого упорядnо(чnим1) / 2 ненулевых расстояний междnу точками по возрастанию: r1  r2  ... rn(n1)/2 . На расстоянии не rбiоолтее некоторой точки в среднем нах2оi/дnится точек без учета самой точки. yПiусloтgь(2i / n), xi  log(ri ) .

Находим наилучшее приближение (аппроксимацию) yi = dxi+c или xi  yi  c . На значениdене влияет ни оаснниоев логарифма, ни d постоянный коэффициентlog (2/n) (уходит в определение величиc)н.ы Для уменьшения влияния граничных элементов в вычислении корреляции оставим только определен1нуmю nчазснтаьчений — только тех, гдriе rmax / 2, 1 i  m . Вычисляя наилучшую линейную аппмраоцкисюи, получим коэффициент пропорциональностeиxp(c).

Размерность

пространствdа d  i(log i)2  1 (ilog i)2 m 1 ilog (ri ) log i  m ilog(i) log( ri )

. Здесь m — длина суммирования (в сумме участвуют птеорлвьыкеоm членов Размерность множества точек, подобно разсмтиерноХаусдорфа, можно способами. Они все задают примерно одинаковую функцию плотности

Здесь, для простоты, мы ограничимся рассмотрением данных (точек) из Евклидова простр Зададим оператор осредниеян на функциях распределеaн(иx)я, x  Rn по формулеa:(x)   P(x  x)a(x)dx .

Взяв в качестPв(еx) бесконечно дифференцируемую функцию, получим, что функция распределения после осреднения станет бесконечно дифференцируемой. Взяв неотрицательнуюP(xф)у,нкицнитюеграл от которой равен по1л,учим, что оператор осреднения, как операLт1орв L1и,з имеет норму 1, и неотрицательное распределение переводит в неотрицательное. Оператор осреднения перестановочен трансляциями (сдвигами аргумента). Если фунPк(цxи)ясферически симметрична, то аотпоерр осреднения коммутирует с вращениями распределений. В задачах механики вращения включаютс группу симметрий, для сохранения симметрии для осредненных уравнений мы будем также исполь сферически симметричные ядPр(аx).

Пусть P(x) — ядро осредненяи (неотрицательно и интеграл от него равен 1d1P),( x )тотгадкаже a a является ядром осреднения. Такое ядро назовем подобным. Было бы желательно, чтобы осре осредненной функции ничего не меняло. Однако такое невозможно, кроме случая тождестве оператора, соответствующего ядруP(x) = (x). Достижимым является такое свойство, когда двойное осреднение эквивалентно одному осреднению с подобным ядром. Т—акоединясдтрвоенное с точностью до подобия. Это осреднение Гаусса P(сx) ядeрxpо(мx2) . Для этого ядра радиус еноисяредн 1 x2 положим равным 1. Подобные осреднRеdнeиxяp( R2 ) имеют радиус осреднениRя, случаюR = 0 (точнее, пределу прRи 0 ) соответствует тривиальное осреднение сP(яx)д=ром(x). Чем меньRш, е тем более осциллирующей получается осредненная функция плотности, быовсшреедйнендиоя функцией  (x  xi ) . Заметим, что если сделать осреднение Гаусса с радиусомR1, осаредпноет—ноимоясреднение i полученного осредненного распределения с радиусом осреRд2н,ентиоя получим в точности результат однократного осреднения с радиусом

осреяднеRн12и R22 .

Радиус осреднения d-вмерном пространстве Nитзочек следует выбирать так, чтобы, с одной стороны, среднее количество точnекв одном шаре такого радиуса было намного б(оlnльNш)dе,, а, чесм другой стороны, — намного меньше, чNем. Это свойство овлыняпется для часто встречающейся функции [2]: n  L(N)  exp( ln N ln ln N ) .

Метод осреднения заключается в осреднении плотности (тxочеxкi ) . Выбирая далее срезы i множества точек по определенному уровню плотности, мы получим разбиение на кластеры. Этот свободен от таких отмеченныхше в недостатков, как зависимость от нумерации точек, и к существенное изменение разбиения на кластеры при малом изменении позиции даже одной точк Алгоритм Dbscan и сравнение его с методом осреднения

Хорошо известен алгоритм Dbscan, также позиционйирунеамы плотности распределения точек. В этом алгоритме достаточными для создания групп связности по плотности выделяются точки, у в -окрестности имеетсmя точек. При этом результат кластеризации сильно зависит от (mп,ар)а.метров Рекомендуемые знчаения этих параметров не учитывают ни размерность множества, ни соответств росту количества точNе.кВ этом алгоритмиеграет роль радиуRса(в нашем представлении), параметр m определяет пороговую плотность с точностью до постоянного множитщеелгяо, зоатвискяоличества точек N и размерностиd. Вычисление плотности соответствует методу осреднения с ядром 1, x   , P(x)    .

0, x    Тогда одинаковый вес при вычислении плотности точек вплоть до приводит к ложному объединению всех точек в одвинсиктлуасцтиеир на Рис. 2.

удаления R н=а расстояни В случае Гауссовского ядра веса точек, находящихся на Rр/а2с,стобяундиуит меньш0.е46 от максимального веса, а у точек на раRсс—тояужниеи только0.043, и они вносят совсем малый вклад. А вот алгоритм Dbscan может неелятрьаздмножество точек на два кластера даже в ситуации на Рис.1, длина CD будет порядкаR/2. В нашем же алгоритме плотность D впадтаоетчкеболее существенно, и происходит разбиение на два кластера (на— чнеатыРриес. 2). Об авторах: Айдагулов Рустем Римович, кандидат физи-мкаотематических наук, старший научный сотрудник кафедры теоретической информатики меха-нмиактоематического факультета, Московский государственный университет имени ЛМо.мВо.носова, [e-mail] Главацкий Сергей Тимофеевич, кандидат физи-мкаотематических наук, доцент, доцент кафедры теоретической информатики механ и-мкаотематического факультета, Московский государственный университет имени ЛМо.мВо.носова, [e-mail]

References

1. Лесковец Ю. , Раадржаман А. , Ульман Дж . Анализ больших данных . Москва, ДМК , 2016 . 2. Крендалл Р. , Померанс К . Простые числа. Криптографические и вычислительные аспекты , УРСС , 2011 . 1. Leskovec J. , Rajaraman A. , Ullman J.D. Analiz bol'shikh dannyh . Moskva, DMK , 2016 . 2. Crandall R. , Pomerance C. Prostye chisla. Cryptographicheskie i vychislitel'nye aspekty . URSS , 2011 .