Лекция (4), страница 3

Keim (KDD’98) CLIQUE: Agrawal, et al. (SIGMOD’98)Основные положенияВажные параметры:Eps: радиус области поиска ближайших соседейMinPts: минимальное число ближайших соседей в Eps-областиМножество ближайших соседей:Непосредственно достижимые точки:NEps(p):{q | dist(p,q) <= Eps}Точка p непосредственно достижима из q с учетом. Eps, MinPts, еслиp принадлежит NEps(q)Ядровая точка:|NEps (q)| >= MinPtspqMinPts = 5Eps = 1 cmОсновные положенияДостижимость:pТочка p достижима из q с учетом Eps,MinPts, если существует путь p1, …, pn, p1 =q, pn = p такой, что pi+1 непосредственнодостижима из pip1qСвязность:Точка p связана с q с учетом Eps, MinPts,если существует точка o такая, что обеточки p и q достижимы из o с учетом Eps иMinPts.pqoDBSCAN: Density Based SpatialClustering of Applications with NoiseОснован на понятии связного кластера:Кластер определен как максимальное множество связных точекПозволяет находить кластеры произвольной формы в условияхшумаПроцедура:Произвольный выбор точки pВыбор всех достижимых из pOutlierточек с учетом Eps и MinPts.Если p – ядровая, то кластерсформированЕсли p граничная или выброс,Borderто обработка следующей точкиПродолжать пока не будут выбранывсе точкиCoreEps = 1cmMinPts = 5DENCLUE: использование функцийплотности распределенияDENsity-based CLUstEring by Hinneburg & Keim (KDD’98)В SAS есть реализация, но в виде процедурыОсновная идея:Аппроксимация плотности распределения по методу Parzen window Функция влияния (Influence function), а на самом деле - ядровая илипотенциальная функция, определяет влияние точки на окружение:f Gaussian ( x , y )  efd ( x , y )22 2Плотность в точке есть сумма всех функцийокружения2Df Gaussian( x)  i 1 eNd ( x , xi )Центры кластеров – локальныемаксимумы плотности (ищутсяградиентным методом):( x, xi )  i 1 ( xi  x)  eDGaussianN22d ( x , xi ) 22 2Кластеры DENCLUEОсновные достоинства:Работает с шумом и большими объемами данных, достаточнобыстрый методНО:нужно задавать критические параметры (ширину ядра)только числовые данные, проблемы с интерпретируемостьюSelf-Organizing Maps (SOM)Общая идея нейросетевого подхода (сети Кохонена):Базируется на моделировании процесса обучения/запоминания в мозгеКаждый кластер (нейрон) определяется своим «прототипом» (число кластеровзадается априори)Прототипы (нейроны) объединены в виде 2D (реже 3D) решетки (сети) сквадратными (или шестигранными) ячейкамиСтруктура решетки определяет понятие «окрестности» каждого прототипа(дискретное расстояние по решетке)У прототипа кластера (нейрона) есть векторный «вес» – соответствует точке висходном пространствеПроцесс активации – реакция на образ входного пространства, определяетсямерой сходства между «весом» нейрона и входным образом (или расстояниеммежду прототипом кластера и объектом)Конкурентное обучение: нейроны соревнуются за право активации (winnertakes-all, всегда один ближайший - победитель)Основная задача SOMЗадача:формирование топографической карты входных образов, в которойпространственное расположение нейронов решетки (прототиповкластеров) в некотором смысле отражает статистическиезакономерности во входных параметрах.Или:построение отображения многомерного исходного пространства на 2х(или 3х) мерную решетку с сохранением топологических зависимостей(близкие объекты исходного пространства будут рядом и на решетке).Процедура работы SOM(неформально)Неформально:Есть решетка нейронов r x s, с каждым узлом которой связан центркластера исходного пространства 1,1,… r,s Алгоритм SOM двигает центры кластеров в исходном многомерномпространстве, сохраняя топологию решетки Точка исходного пространства относится к тому кластеру, чей весближе (расстояние до центра меньше) При обработке новой точки центр кластера-победителяи всех его соседей по решеткесдвигается в сторону этой точкиУпрощенный пример:Добавляя точки из картинок,решетка «обтягивает» их контур Небольшой обман, ибо тутразмерность решетки и исходногопространства совпадаютПроцедура работы SOMШаг 0.

Инициализация:структура решетки и число кластеров (нейронов) инициализация «весов» прототипов wj(0) (полностью случайно илислучайной выборкой из данных) начальные параметры (скорость обучения и размер окрестности)Шаг 1. Выборка (итерация t):Выбираем случайный x(t) из исходного пространстваШаг 2. Конкуренция:i ( x )  arg min x(t )  w j (t )jШаг 3. Коррекция весов с учетом кооперации:Находим «лучший» нейрон для активации:Для победителя и соседей по решетке пересчитываем их «вес» –двигаем их центры к точке x в исходном пространстве Уменьшаем скорость обучения и размер окрестностиШаг 4. Проверка условий остановки и переход на Шаг 1.Стабилизация структуры либо превышение числа выполненныхитерации установленного значенияКоррекция весов с учетомкооперацииПерерасчет весов победителя и соседей:Стохастический градиентный спуск:w j (t  1)  w j (t )   (t )hij ( x ) (t )( x  w j (t ))скорость обученияразмер топологическойокрестности (на решетке!!!!)t    (t  1)   0 exp  t  (t  1)  0 exp    2 d grid(i , j ) hij ( x ) (t )  exp 22(t)ПримерВходные данные:продуктбелкиуглеводыжирыApples0.411.80.1Avocado1.91.919.5Bananas1.223.20.3Beef Steak20.90.07.9Big Mac13.019.011.0Brazil Nuts15.52.968.3Bread10.537.03.2Butter1.00.081.0Cheese25.00.134.4Cheesecake6.428.222.7Cookies5.758.729.3Cornflakes7.084.00.9Eggs12.50.010.8Fried Chicken17.07.020.0Fries3.036.013.0Hot Chocolate3.819.410.2Pepperoni20.95.138.3Pizza12.530.011.0Pork Pie10.127.324.2Potatoes1.716.10.3Rice6.974.02.8Roast Chicken26.10.35.8Sugar0.095.10.0Tuna Steak25.60.00.5SOM(10Х10):Визуализация и интерпретацияSOMКогерентные области:Близкие кластеры в исходном пространстве – рядом на решетке(свойство SOM) и одним (или спектрально близким) цветом Группы кластеров – категории, областиСвойства SOMАпроксимация входного пространства признаковТопологический порядокОбласти исходного пространства с высокой плотностьюотображаются в большие области на решетке и наоборотВыбор признаков:Рядом в исходном пространстве => рядом на решетке и наоборотСоответствие плотности«Сжатие» информации, связь с методом LVQ (кластеризация наоснове теории информации, задача - выбрать кодовые словакластеры так, чтобы минимизировать возможное искажение)осуществляет нелинейную дискретную аппроксимацию главныхкомпонент (точнее главных кривых и плоскостей)Недостатки:Алгоритм простой, но мат.

анализу поддается плохо, в общемслучае не доказана ни сходимость, ни даже устойчивость Много неочевидных, но важных параметров, задаваемых априори,включая структуру решеткиИспользование в SAS EMРассмотрим ту же задачу с рекомендательными системами, но безотбора переменных (для SOM это не так важно):Распределение переменной(карта интенсивности)Размеры кластеров(карта интенсивности)В результирующие данные добавляется и номер кластера (ячейка решетки) икоординаты на решетке (нелинейные главные компоненты):ВизуализацияРезультаты кластеризации можно оценить с точки зрения:Выделения важных переменных для каждого кластераРазличия распределения переменных внутри каждого кластера и по всейвыборкеРеализовано в узле Segment Profile (раздел Assess) для любых алгоритмовкластеризации и группировки.