Алгоритмы кластерного анализа

Алгоритмы выделения кластеров делятся на три класса: адаптивные, агломеративные и с оптимизацией критерия.

Адаптивные алгоритмы основаны на использовании простых настраивающихся эвристических правил классификации, агломеративные (от англ. слова agglomerate – собирать) – на последовательном слиянии двух «наиболее близких» кластеров в один.

Примером адаптивного алгоритма является алгоритм гиперсфер. При применении данного алгоритма число кластеров заранее не фиксируется, но задается радиус гиперсферы – R*.

1-й шаг. Формируется первый кластер. Берется гиперсфера радиуса R*с центром в произвольной точке (первый объект), и все объекты, которые попали внутрь гиперсферы, относятся к кластеру № 1.

2-й шаг. Вычисляется новый центр кластера № 1 как центр тяжести всех точек (объектов), входящих в кластер. Центр гиперсферы радиуса R* переносится в новый центр кластера № 1.

3-й шаг. Уточняется состав точек, входящих в новую гиперсферу.

Если состав точек не изменился, то формирование 1-го кластера завершается, в противном случае повторяются шаги 2 и 3.

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

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

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

D = || ρ ( i, j) ||.

При применении этого алгоритма задаются произвольным порогом U0и формируют матрицу близости U следующим образом:

Uij= 1, если ρ(i; j) £ U0;

Uij= 0, если ρ(i; j) > U0.

Матрица U порождает некоторый граф (рисунок), на котором "близкие" объекты ( Uij= 1 ) соединяются дугами. В результате применения такого подхода все множество объектов разбивается на несвязанные друг с другом дугами кластеры.

Количество выделенных кластеров зависит от принятой величины U0:

– если U0< min ρ (i; j),

i,j

выделится n кластеров (каждый объект будет образовывать самостоятельный кластер);

- если U0> max ρ (i; j) ,

ij

все объекты попадут в один кластер.

Поэтому величина U0должна лежать в следующем диапазоне:

min ρ (i; j) < U0< max ρ (i; j).

i,j i,j

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

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

Для решения проблемы выхода из процедуры кластеризации воспользуемся критерием

Алгоритмы кластерного анализа - student2.ru

где Алгоритмы кластерного анализа - student2.ru = Алгоритмы кластерного анализа - student2.ru – мера близости объектов i и j;

Алгоритмы кластерного анализа - student2.ru – число сочетаний из Алгоритмы кластерного анализа - student2.ru элементов по 2;

n – общее количество рассматриваемых объектов.

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

К алгоритмам с оптимизацией критерия относится алгоритм ISODATA и ряд других алгоритмов. Их основной недостаток – зависимость результата от начального разбиения объектов. Кроме того, оптимизационные алгоритмы предполагают априорное задание количества классов – k, так как меры качества разбиения объектов на кластеры (2.11) и (2.12) являются убывающими функциями числа классов.

Приведем пример агломеративного иерархического алгоритма. На первом шаге каждое наблюдение Xi (i = 1, 2,...,n) рассматривается как от­дельный кластер. В дальнейшем на каждом шаге работы алгоритма проис­ходит объединение двух самых близких кластеров, и, с учетом принятого расстояния, по формуле пересчитывается матрица расстояний, размер­ность которой, очевидно, снижается на единицу. Работа алгоритма закан­чивается, когда все наблюдения объединены в один класс. Большинство программ, реализующих алгоритм иерархической классификации, преду­сматривает графическое представление классификации в виде дендро-граммы.

Пример 1

Провести классификацию n=6 объектов, каждый их которых харак­теризуется двумя признаками (табл.1).

Т а б л и ц а 1. Значения признаков

Номер объекта i
xi1
xi2

Расположение объектов в виде точек на плоскости показано на рис.1.

15 X2

13 *

12 *

10 *

9 * *

7 *

6 X1

1 2 3 4 5 6 7 8 9 10 11 12

Рис.1. Расположение объектов

Решение

Воспользуемся агломеративным иерархическим алгоритмом классифи­кации. В качестве расстояния между объектами возьмем обычное евклидо­во расстояние. Тогда согласно формуле (2.2) расстояние между первым и вторым объектами

𝛒12 = Алгоритмы кластерного анализа - student2.ru = 2,24, а между первым и третьим объектами

𝛒13= Алгоритмы кластерного анализа - student2.ru = 3.

Очевидно, что

𝛒11=0.

Аналогично находим остальные расстояния между шестью объектами и строим матрицу расстояний.

Алгоритмы кластерного анализа - student2.ru

Из матрицы расстояний следует, что четвертый и пятый объекты наи­более близки ρ4,5 =1,00 и поэтому объединяются в один кластер. После объединения объектов имеем пять кластеров (табл.2).

Т а б л и ц а 2. Состав кластеров

Номер кластера
Состав кластера (1) (2) (3) (4,5) (6)

Расстояние между кластерами определим по принципу "ближайшего соседа".

Расстояние 𝛒1,(4,5) равно расстоянию от объекта 1 до ближайшего к нему объекта, входящего в кластер S(4,5) т. е. 𝛒1,(4,5) = 𝛒1,4 =5,10. Тогда матрица расстояний

Алгоритмы кластерного анализа - student2.ru

Объединим второй и третий объекты, имеющие наименьшее расстоя­ние 𝛒23 = 1,41. После объединения объектов имеем четыре кластера:

S(1), S(2,3), S(4,5), S(6)

Вновь найдем матрицу расстояний. Для того чтобы рассчитать рас­стояние до кластера S(2,3) воспользуемся матрицей расстояний R2. На­пример, расстояние между кластерами S(4,5) и S( 2, 3) равно 5.

Проведя аналогичные расчеты, получим

Алгоритмы кластерного анализа - student2.ru

Объединим кластеры S(4,5) и S(6), расстояние между которыми согласно матрице R3 наименьшее ρ(4,5),6=2,00. В результате получим три кластера S(1), S(2,3), S(4,5,6). Матрица расстояний будет иметь вид

Алгоритмы кластерного анализа - student2.ru

Объединим теперь кластеры S(1) и S(2,3), расстояние между которыми 𝛒1,(2,3)= 2,24. В результате получим два кластера: S(1,2,3) и S(4,5,6), расстоя­ние между которыми, найденное по принципу "ближайшего соседа",

𝛒 (1,2,3), (4.5.6) =5,00.

Результаты иерархической классификации объектов представлены на рис. 2 в виде дендрограммы.

На рис. 2 приводятся расстояния между объединяемыми на данном этапе кластерами (объектами). В нашем примере предпочтение следует отдать предпоследнему этапу классификации, когда все объекты объеди­нены в два кластера S(1,2,3) и S(4,5,6).

5,00

2,24 2,00

1,41

1 1,00

0 1 2 3 4 5 6

Рис. 2. Результаты классификации объектов

Пример 2. Автомагазином были опрошены следующие группы покупа­телей: молодые и пожилые бизнесмены, люди среднего и пожилого возраста с высоким и средним уровнем доходов.

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

Ответы обследуемых групп в кодированной записи (0 или 1) приведены в табл. 3.

Т а б л и ц а 3. Результаты опроса покупателей

Номер Уровень Состав Характеристика
группы дохода группы  
      Высок Ино- Экст.   Комфорта- Экономич- Безо-
      скор. марка вид бельность ность пасность
Высокий Молодые бизнесмены
               
-//- Пожилые бизнесмены
               
    Люди среднего возраста            
-//-
               
-//- Люди пожилого возраста
               
               
Средний Молодые
    бизнесмены            
  -//- Пожилые бизнесмены
    Люди среднего возраста            
-//-
             
-//- Люди
    пожилого            
    возраста            

Матрица расстояний между группами покупателей, рассчитанная по формуле (2.6), приведена в табл. 4.

Т а б л и ц а 4. Матрица расстояний

Группа
-
  -
    -
      -
        -
          -
            -
              -

Задаваясь пороговым значением Т=1 (т. е. не более одного несовпадающего требования), получим следующую матрицу близости (табл. 5).

Т а б л и ц а 5. Матрица близости

Группы
-
  -
    -
      -
        -
          -
            - 1 .
              -

Исходя из табл. 5, построим граф взаимосвязи покупателей (рис. 3).



Алгоритмы кластерного анализа - student2.ru

Рис. 3. Граф взаимосвязи покупателей

Таким образом, в результате использования алгоритма получено 3 кластера (S1 ¸ S3):

– 1-й кластер — молодые бизнесмены, независимо от уровня
дохода;

– 2-й кластер — пожилые бизнесмены и люди среднего и
пожилого возраста с высокими доходами;

– 3-й кластер — люди среднего и пожилого возраста со средними доходами.

3. ДИСКРИМИНАНТНЫЙ АНАЛИЗ

3.1. Теоретические основы дискриминантного анализа

Дискриминантный анализ как раздел многомерного статистического анализа включает в себя статистические методы классификации много­мерных наблюдений в ситуации, когда исследователь обладает так назы­ваемыми обучающими выборками ("классификация с учителем").

В общем случае задача различения (дискриминации) формулируется следующим образом. Пусть результатом наблюдения над объектом явля­ется реализация k-мерного случайного вектора x=(x1,x2,...,xk)T. Требуется установить правило, согласно которому по наблюденному значению век­тора x объект относят к одной из возможных совокупностей Алгоритмы кластерного анализа - student2.ru (i=1,2,...,m). Для построения правила дискриминации все выборочное пространство Rn значений вектора х разбивается на области Xi (i=1,2,...,m) так, что при попадании х в Xi, объект относят к совокупности pi.

Правило дискриминации выбирается в соответствии с определенным принципом оптимальности на основе априорной информации о совокуп­ности pi вероятностей извлечения объекта из pi. При этом следует учитывать размер убытка от неправильной дискриминации. Априорная информация может быть представлена как в виде некоторых сведений о функции k-мерного распределения признаков в каждой совокупности, так и в виде выборок из этих совокупностей. Априорные вероятности рi могут быть либо заданы, либо нет. Очевидно, что рекомендации будут тем точнее, чем полнее ис­ходная информация.

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

Пусть Алгоритмы кластерного анализа - student2.ru выборка из совокупности Алгоритмы кластерного анализа - student2.ru , i=1,2,...,m; причем каждый j-й объект выборки представлен k-мерным век­тором параметров

Алгоритмы кластерного анализа - student2.ru .

Произведено дополнительное наблюдение x=(x1,...,xk)T над объектом, принадлежащим одной из совокуп­ностей Алгоритмы кластерного анализа - student2.ru . Требуется построить правило отнесения наблюдения х к одной из этих совокупностей.

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

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

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

1) имеются разные классы объектов;

2) каждый класс имеет нормальную функцию плотности от к перемен­ных

Алгоритмы кластерного анализа - student2.ru

Алгоритмы кластерного анализа - student2.ru (x- Алгоритмы кластерного анализа - student2.ru

где Алгоритмы кластерного анализа - student2.ru – вектор математических ожиданий переменных размерности k;

Алгоритмы кластерного анализа - student2.ru – ковариационная матрица размерности k*k;

Алгоритмы кластерного анализа - student2.ru – обратная матрица.

В случае если параметры известны, дискриминацию можно провести, например, следующим образом.

Имеются функции плотности Алгоритмы кластерного анализа - student2.ru нормально рас­пределенных классов. Задана точка х в пространстве к измерений. Предпо­лагая, что fi(x) имеет наибольшую плотность, отнесем точку х к i-му классу. Существует доказательство, что если априорные вероятности для определяемых точек каждого класса одинаковы и потери при неправиль­ной классификации i-й группы в качестве j-й не зависят от i и j, то решаю­щая процедура минимизирует ожидаемые потери при неправильной клас­сификации.

Приведем пример оценки параметра многомерного нормального рас­пределения μ и Σ..

μ и Σ могут быть оценены по выборочным данным: Алгоритмы кластерного анализа - student2.ru и Алгоритмы кластерного анализа - student2.ru для клаcсов. Задано l выборок

Алгоритмы кластерного анализа - student2.ru ; (i=1,…,m)

из некоторых классов. Математические ожидания Алгоритмы кластерного анализа - student2.ru могут быть оценены средними значениями

Алгоритмы кластерного анализа - student2.ru . (3.1)

Несмещенные оценки элементов ковариационной матрицы Σ есть

Алгоритмы кластерного анализа - student2.ru . (3.2)

Следовательно, можно определить Алгоритмы кластерного анализа - student2.ru и Алгоритмы кластерного анализа - student2.ru по l выборкам в каждом классе при помощи (3.1), (3.2). Получив оценки, точку х отнесем к клас­су, для которой функция f(х) максимальна. Класс, к которому должна принадлежать точка х, можно определить на основе неравенства

fi(x)>fj(x).

3.2. Метод потенциальных функций

Будем рассматривать детерминистическую постановку. Пусть Алгоритмы кластерного анализа - student2.ru . Через K(x,y) будем обозначать потенциал, создаваемый точкой Алгоритмы кластерного анализа - student2.ru в точке Алгоритмы кластерного анализа - student2.ru . Функция K(x,y) должна удовлетворять следующим условиям:

а) K(x,y) >0 для всех Алгоритмы кластерного анализа - student2.ru ;

б) Алгоритмы кластерного анализа - student2.ru ;

в) если точка Алгоритмы кластерного анализа - student2.ru удаляется от Алгоритмы кластерного анализа - student2.ru , то значение K(x,y) убывает.

Приведем пример функции K(x,y). Пусть Алгоритмы кластерного анализа - student2.ru . Тогда можно, например, положить Алгоритмы кластерного анализа - student2.ru , где Алгоритмы кластерного анализа - student2.ru . График функции K(x,y) при фиксированном Алгоритмы кластерного анализа - student2.ru представляет собой холм с вершиной над точкой Алгоритмы кластерного анализа - student2.ru .

Пусть Алгоритмы кластерного анализа - student2.ru . Определим Алгоритмы кластерного анализа - student2.ru – сумму холмов над точками из А; Алгоритмы кластерного анализа - student2.ru – сумму холмов над точками из В. Тогда функцию Алгоритмы кластерного анализа - student2.ru можно интерпретировать как разделяющую два множества А и В.

3.3. Статистический подход в теории распознавания образов

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

Основными вероятностными характеристиками являются:

– плотность распределения вероятностей появления образа f(x);

–условные вероятностипринадлежности некоторого образа заданным классам Алгоритмы кластерного анализа - student2.ru ;

– вероятности появления классов Алгоритмы кластерного анализа - student2.ru ;

– условные плотности распределения вероятностей внутри классов Алгоритмы кластерного анализа - student2.ru ,

Будем предполагать, что события появления классов Алгоритмы кластерного анализа - student2.ru образуют полную группу событий. Тогда справедлива формула полной вероятности

Алгоритмы кластерного анализа - student2.ru

и формула Байеса

Алгоритмы кластерного анализа - student2.ru .

Наши рекомендации