Интеллектуальный анализ данных
 Скачать 7.76 Mb.
|
|
4. Неиерархические алгоритмы кластеризации Неиерархические алгоритмы кластеризации ориентированы на построе- ние разбиений. Ввиду значительного разнообразия подходов рассмотрим только некоторые из алгоритмов. Достаточно простым и понятным является алгоритм кратчайшего незамк- нутого пути, основанный на удалении самых длинных ребер в кратчайшем не- замкнутом пути, построенном на полносвязном графе. Построение кратчайшего незамкнутого пути можно представить следующим алгоритмом: // Дано: матрица смежности полносвязного графа // Найти: разбиение графа на n кластеров // Построение кратчайшего незамкнутого пути: Начало: Найти пару элементов с минимальным расстоянием; Соединить их; Повторять пока есть свободные элементы Найти элемент, ближайший к одной из конечных точек связанного пути; Соединить их; // Конец построения КНП Повторять n-1 раз Найти самое длинное ребро КНП; Удалить его; Конец. // Получили n кластеров Другой распространенный алгоритм носит название k-средних (k-means). Он обеспечивает построение заданного числа (k) кластеров с минимальным квадра- тичным отклонением их членов от центров этих кластеров. Динамика алгоритма k-means показана на рис. 9. Достоинствами алгоритма k-means полагают высокую скорость работы и простоту использования. Недостатков у данного алгоритма гораздо больше: - чувствительность к выбору начальных условий (первичных центров кла- стеров); - чувствительность к выбросам данных (аномальным значениям); - существенное замедление по мере роста данных 136 Тем не менее, этот алгоритм используется как предварительный фильтр для нейросети, обеспечивающий обработку изображений. 5. Качество кластеризации Основной проблемой, возникающей при оценивании качества кластериза- ции является сложность математической формулировки задачи улучшения пони- мания структуры данных. Эта проблема обуславливает наличие широкого спек- тра процедур формирования оценки качества кластеризации. Интуитивно понятно, что качество кластеризации тем выше, чем меньше внутрикластерное расстояние и, соответственно, больше межкластерное. Что Вам напоминает это выражение? Как вариант, для сравнения двух кластерных струк- тур критерием качества может служить минимальная дисперсия объектов в кла- стере или внутригрупповая функция квадратов отклонения: n i i ) x x ( 1 2 , где x i – значение i-й характеристики объекта. NB! Эти способы применимы только при известном количестве кластеров! Рис. 9. Динамика алгоритма k-means 137 Еще один возможный критерий – это стабильность кластерной структу- ры при добавлении в выборку новых объектов. При незначительных отклонениях значений характеристик новых объектов от уже имеющихся кластерная структура должна либо сохраняться, либо меняться незначительно. Стабильность кластерной структуры может быть оценена и другим спосо- бом: применением других алгоритмов и способов кластеризации. Схожесть кла- стерных структур, полученных при использовании различных подходов, указывает на «объективность» кластеризации. Заканчивая обзор методов кластеризации, следует, хотя бы, упомянуть те, которые получили достаточно широкое распространение в науке об обработке данных, но не рассматриваются в лекции в силу невозможности объять необъят- ное. К ним относятся: алгоритмы нечеткой кластеризации (fuzzy c-means), нейро- сетевые технологии – самоорганизующиеся карты Кохонена, (Self-Organized Maps) и т.п. Вопросы: 1. Приведите формализованную постановку задачи кластеризации. 2. Где используется кластер-анализ? 3. Приведите общее правило объединения двух кластеров. 4. Что называется разбиением? Иерархией? 5. В чем состоит метод «ближайшего соседа»? «Дальнего соседа»? 6. Что называется методом средней связи? 7. Назовите особенности реализации центроидного метода. 8. Чем отличаются агломеративные и дивизимные алгоритмы кластериза- ции? 9. Назовите достоинства алгоритмов иерархической кластеризации. 10. В чем состоит алгоритм кратчайшего незамкнутого пути? 11. В чем состоит алгоритм k-средних? Его достоинства и недостатки? 12. Что называется внутрикластерным расстоянием? Межкластерным рас- стоянием? 13. Как определяется стабильность кластерной структуры? Литература: . Классификация и снижение размерности/Айвaзян С.А., Бухштабер В.М., Енюков И.С., Мешалкин Л.Д. Под ред. С.А.Айвазяна.- М.: Финансы и статистика, 1989.- 607с. . Вентцель Е.С. Теория вероятностей. - М.: Физматгиз, 1962. - 564с. . Прикладная статистика. Исследование зависимостей/// Айвaзян С.А., Енюков И.С., Мешалкин Л.Д. /Под ред. С.А.Айвазяна.- М.: Финансы и статистика, 1989.- 607с. . Кендалл М., Стьюарт А. Статистические выводы и связи// Пер. с англ. под ред. А.Н.Колмогорова.- М.: Наука, 1973.- 900с. 138 ЛЕКЦИЯ 17 СОКРАЩЕНИЕ РАЗМЕРНОСТИ И ВИЗУАЛИЗАЦИЯ Вопросы: 1.Главные компоненты и факторный анализ 2. Нелинейные главные компоненты (проектирование с контрастировани- ем) 1. Главные компоненты и факторный анализ Пусть случайный вектор X = ( x 1 , ... , x k ) T N k (a, ). Первой главной компонентой вектора X называется линейная комбинация k i i T k k i T i i c C c c C X C x c z 1 2 1 2 1 1 11 1 1 1 1 1 , 1 , ) ,..., ( ; где коэффициенты с 1i выбираются так, чтобы величина z 1 имела наи- большую дисперсию среди всех нормированных линейных комбинаций компо- нент x i . Дисперсия случайной величины X C z T , )] ( [ ) ( ] ) )( [( ) ( C C C XX M C C XX C M X C X C M X C D T T T T T T T T T поэтому вектор C 1 является решением оптимизационной задачи max C C T с ог- раничением 1 2 C C C T Составим для этой задачи функцию Лагранжа ) , (C L ) 1 ( C C C C T T , затем приравняем нулю ее производные по векторному аргументу C и ска- лярному аргументу λ : 0 ) 1 ( 0 2 2 C C L C C C L T Первое уравнение приводится к виду 0 ) ( C I : точками, подозрительны- ми на экстремум, являются пары собственных чисел и соответствующих собст- венных векторов матрицы Σ. Второе уравнение показывает, что собственные векторы должны иметь единичную длину. Подставим найденные варианты значений вектора C в исходную целевую функцию: ) ( C C C C C C T T T Таким образом, максимальное значение дисперсии z, равное λ max (Σ), дости- гается, если вектор C – нормированный собственный вектор ковариационной мат- рицы Σ, соответствующий ее максимальному собственному числу λ max (Σ). Геометрически это означает, что вектор С 1 параллелен наибольшей оси эллипсоида рассеяния вектора Х. Поскольку суммарная дисперсия всех компонент вектора X k i i k i k i ii i tr Dx 1 1 1 2 , ) ( говорят, что доля суммарной дисперсии, объясняемая первой главной ком- понентой z 1 , равна 139 ) ( 1 1 1 tr k Аналогично, с использованием второго по величине собственного числа 2 и соответствующего собственного вектора С 2 , ортогонального, как извест- но, С 1 , определяется вторая главная компонента и т.д. Векторы С 1 , С 2 и т.д. можно получать также непосредственно из решения оптимизационных задач: ; 1 , ) ( max arg 1 1 C Dx X C D C k i i T 1 1 1 2 , 1 , ) ( max arg C C C Dx X C D C k i i T и т.д. Геометрически переход от вектора Х к его первым двум главным ком- понентам означает его проектирование на плоскость, параллельную главным осям эллипсоида рассеяния. На практике матрица обычно неизвестна, и ее заменяют матрицей ˆ , полученной на основе обучающей выборки Х 1 , ... , Х n Пример 1. Определение линейной главной компоненты для двумерного вектора. Пусть X = (x , y) T N 2 (0 , ); 2 5 0 5 0 1 . Прежде всего, находятся собственные числа матрицы : 79 0 , 21 2 : 0 2 5 0 5 0 1 det 2 1 Далее определяется собственный вектор С = (с 1 , с 2 ) Т , соответствующий наибольшему собственному числу 1 = 2.21 , из системы уравнений 92 0 38 0 C : 1 c c 0 c 5 0 c 21 1 2 2 2 1 2 1 Этот вектор C задает направление главной оси х 1 . Ось у 1 ей перпендику- лярна; ее направление можно также определить как собственный вектор, соответ- ствующий второму собственному числу λ 2 . Ортогональность этих осей обеспечи- вается симметрией матрицы Σ. На рис. 1 приведен эллипс рассеяния для вектора Х. Направление его главной оси задается найденным вектором С. В осях х 1 , у 1 этот эллипс описывается уравнением 1 ) ( x ) ( x 2 2 2 2 2 1 2 1 Доля дисперсии, объясняемой первой главной компонентой , 1 /( 1 + 2 ) = 74% . Таким образом, размерность вектора уменьшается в два раза, а эффективность представления - только на 26%. 140 Рис. 1. Семейство эллипсов рассеяния в примере 1 Данную технику, как правило, применяют при анализе k-мерной совокупно- сти однотипных измерений – k-мерного облака точек X 1 ,…, X n , которые трактуют как независимые измерения случайного вектора X. Для параметров a, исполь- зуют их выборочные оценки. Если компоненты вектора Х имеют различную физическую природу и измерены с помощью качественно различных технических средств, то ре- зультат не имеет, как правило, ясного физического смысла и существенно зависит от выбора масштаба. В этих случаях вместо ковариационной матри- цы или ее оценки используют корреляционную матрицу с элементами r i j = i j ( i i jj ) -1/2 , которые являются безразмерными величинами (диагональные элементы r ii = 1). Главные компоненты, построенные по корреляционной матрице – безраз- мерные случайные величины – называют главными факторами, объясняющими рассеяние компонент вектора X. Традиционный факторный анализ использует несколько иную технику вы- числений коэффициентов c ij – факторных нагрузок, основанную на методе наи- меньших квадратов. Его результаты обычно очень близки к результатам ана- лиза главных компонент по корреляционной матрице, однако в факторный анализ органически входит специальный метод вращений, призванный облег- чить содержательную интерпретацию получающихся факторов. Пример 2. Для данной k-мерной выборки X = [ X 1 , X 2 ,…, X n ] ( 2 k ) найти коэффициенты двух главных факторов и определить долю информации, объяс- няемую этими факторами. Процедура вычисления коэффициентов двух главных факторов function [c,d,r]=factor1(X); %Анализ главных компонент [n,m]=size(X); [P,Q]=eig(corrcoef(X)); %главные компоненты по корреляционной матрице c1=P(:,m); с2=P(:,m-1); q=diag(Q); r=(q(m)+q(m-1))/sum(q); % контроль объясняемой дисперсии 141 Есть два пути для выявления физического смысла найденных факторов. Во-первых, можно проанализировать веса c ij . Во-вторых, можно просто располо- жить исходные объекты, описываемые измерениями X, в порядке возрастания i-го фактора и попытаться понять, какому физическому свойству соответствует такое упорядочение. Линейные главные компоненты обладают целым рядом других опти- мальных свойств, которые в некоторых случаях можно использовать даже в качестве их начального определения. Пусть X 1 , ... , X n , X i = (x i1 , ... , x ik ) T - не- зависимая выборка из распределения N k (a, ) , a z 1 , ... , z n - их образы при линейном проектировании в некоторое q - мерное пространство (q < k): k j i T ij lj il T iq i i i X C x c z z z Z X 1 1 , ) ,..., ( Пусть d i j - расстояние между X i и X j в евклидовом пространстве R k , ij - расстояние между их образами в R q . В качестве меры искажения мат- рицы попарных расстояний используется величина n j i ij ij r d 1 , 2 2 ) ( (1) Имеет место следующее важное свойство: q 2 минимально, если в качестве Z i взяты первые q главных компонент векторов X 1 , ... , X n . На этом свойстве, в частности, основаны различные нелинейные аналоги метода главных компонент, которые получаются, если рассматривать меры искаже- ния, отличные от (1) . Пример 3. Несколько лет назад в одном из российских НИИ решалась следующая задача. Имелось около 300 образцов смазочных материалов, отечественных и импортных. Каждый образец анализировался по 9 парамет- рам. Таким образом, исходная информация представляла собой облако то- чек в 9-мерном пространстве. При проектировании этого облака на плос- кость двух первых главных факторов величина 9 1 2 1 i i оказалась равной 0.64, т.е. потери информации при проектировании составили около 36% . Анализ выявленных факторов позволил выделить 14 сгустков (кластеров), в каждый из которых вошли материалы с достаточно близкими свойствами, что дало основания для рекомендаций по замене им- портных материалов их отечественными аналогами. 32 точки при этом ока- зались изолированными - это материалы, не имеющие аналогов и не допус- кающие замены. 2. Нелинейные главные компоненты (Проектирование с контрастированием) Пусть в k-мерном пространстве имеется облако точек X 1 , ... , X n , d i j - расстояние между точками X i и X j . Пусть эти точки каким-то образом про- ектируются в пространство R q , q i Z i R q , i j - расстояние между Z i и Z j . В качестве меры искажения геометрической структуры данных при пере- ходе от {X i }к{Z j } вводится функция 142 j i ij j i ij ij ij n d d d z z Q 2 1 ) ( ) ,..., ( Образы z 1 , ... , z n ищутся из условия Q (z 1 , ... , z n ) = min . При < 0 метод более чувствителен к искажению малых расстояний , при > 0 - больших. Рекомендуется использовать значение = -1 . Такое проектирование приводит к контрастному выделению неоднородностей (сгустков) в множестве {X i } , а также выявлению среди них аномальных значений (выбросов). Зада- ча решается итерационным градиентным методом: i n j ij k i k i z Q d z z 1 1 ) ( ) 1 ( 2 В качестве начального приближения используются линейные главные компоненты. Можно рассматривать и другие конструкции мер искажения. Подобные задачи называют задачами редукции размерности или ви- зуализации. Результаты рационального снижения размерности часто интер- претируют как нахождение основополагающих скрытых характеристик (факто- ров) имеющегося массива данных. В наибольшей степени эта тенденция на- шла свое выражение в концепции факторного анализа. Действительно, мож- но доказать, что если такие скрытые переменные в данных действительно есть и они независимы между собой, то в результате осуществления опера- ций по рациональному снижению размерности они, как правило, обнаружи- ваются. |