Материал: Мясников В.В. Основы статистической
Ml- (г) = M l (г - 1) {jc = 0 , K - 1) является условием сходимости алгоритма и при его достижении выполнение алгоритма заканчивается. В противном случае алгоритм повторяется с шага 2 с новым номером итерации г := г +1.
Комментарии Качество работы алгоритма К внутригрупповых средних зависит от числа
выбираемых центров кластеров К, от выбора центров кластеров на первой итерации и, естественно, от геометрических особенностей данных. От последовательности просмотра данных результаты не зависят.
Хотя для этого алгоритма общее доказательство сходимости не известно, получения приемлемых результатов можно ожидать в тех случаях, когда данные образуют характерные гроздья, отстоящие друг от друга достаточно далеко. В большинстве случаев практическое применение этого алгоритма потребует проведения экспериментов, связанных с выбором различных значений параметра К, и расположения первоначальных центров кластеров.
4.2 Реализация алгоритмов кластеризации в среде Mathcad
4.2.1 |
Генерация исходных данных |
|
|
|
|
|||
Описание алгоритма дано в разделе 1 текста настоящей работы. |
||||||||
Основными соотношениями являются: |
|
|
|
|
|
|||
Х = А ^ + М |
, А = |
«00 |
0 ■ |
- I d |
„ - |
BQI „ |
_ |
------^01 |
«10 |
•«00 |
V'°00^«10 |
1— — ^«11 |
1 R |
||||
|
|
«11_ |
|
|
VAo |
V |
Д'00 |
|
4.2.2 Основные функции кластеризации
Большинство алгоритмов кластеризации состоит из трех блоков: блока задания начальных центров кластеров, блока отнесения вектора к некоторому кластеру/классу и блока пересчета центров кластеров по данным векторам признаков и их номерам классов. Для этой цели удобно использовать следующий код в системе MathCad.
|
|
|
Инициирование |
4 := 2 |
/:= 0 .. 4 - 1 |
/:=0..74-1 |
счетчиков и |
Мо,1 ■■=xoj M ij := xyi |
|
первоначальных |
|
|
|
|
центров кластеров |
60
di,i |
-JikPoj - ^ o j f |
|
|
ClassNum, := min_ind{GetVector{d,i, L), L) |
|||
ki .—0 |
k(2lassNum,■) •“ k(ciassNum |
^ |
|
M Q J |
:= 0 |
MQ^ciassNum i)'-= ^ 0 ,{C la ssN u m ) + ^0,i |
|
M i j |
:= 0 |
M iY lassN u m i ) - = ^ \,{C la ssN u m ) + 4 ,i |
|
Получение массива, содержащего номера классов для каждого вектора признаков
Пересчет центров кластеров
M,0,1 |
M, , |
XI01 |
Щ1 |
k, |
ki |
Описание дополнительных функций и способ визуализации результатов кластеризации приведены в п.4.2.3.
4.2.3Вспомогательные функции, используемые для кластеризации
Среда математического программирования MathCAD предназначена для математического программирования. Поэтому реализацию подпрограммы в ней удобно выполнить в виде функции, объявление которой должно предшествовать ее первому вызову. Для кластеризации удобно использовать следующие функции.
Функпия поиска и отбора |
|
|
|
|
|
Функция |
|
ind<^0 |
|
нахождения |
|
i-^l |
|
некоторого |
|
AnylndexOjValue(array, value, Len) := while i < Len |
(последнего) |
||
ind <— i if arrayI = value |
индекса |
элемента |
|
i < - г |
+ 1 |
value в |
массиве |
return |
ind |
array длины Len |
|
|
|
||
ind<^0 |
|
|
|
min < - X-0 |
|
Функция вьщачи |
|
-1 |
|
||
while i < Len |
|
индекса |
|
min_ind(x,Len)-.= if Xj < min |
|
минимального |
|
min <— Xj |
|
элемента в |
|
ind <-i |
|
массиве х |
|
i +l |
|
размером Len |
|
return ind
61
J M I |
|
while j <Len |
|
GetVector{x,i,Len) := |
У ] ^ ^ 1,J |
|
J M j + l |
return у |
|
|
incl <- 0 |
|
max <—XQ |
|
/ ^ 1 |
|
while i < Len |
M a x in d (x, Len) := |
if Xj >max |
|
max <—Xj |
|
ind <—i |
|
i +l |
|
return ind |
Функция вьщачи вектора, сформированного из элементов /-й строки матрицы х размером Len элементов по горизонтали
Функция вьщачи индекса максимального элемента в массиве х размером Len.
Отображение результатов кластеризапии
Результатом кластеризации является массив ClassNum, элементы которого содержат номер класса/кластера, к которому отнесен соответствующий вектор из набора векторов х. Для отображения векторов, отнесенных к различным классам, следует распределить весь набор векторов на два набора с векторами, принадлежащими только какому-либо одному классу. Для формирования списка векторов, отнесенных к некоторому классу, нагфимер к классу «О», следует использовать следующий код MathCad:
indl := AnyIndexOfValue{ClassNum,\,N)
'■=if[ciassNum - 1, |
, xl,. j^ j ) |
При таком формировании списка вектора, отнесенные к необходимому классу, переносятся в новый вектор, а на место остальных векторов записывается некоторый наперед заданный вектор нужного класса.
62
4.3Порядок выполнения лабораторной работы
4.3.1Исходные данные
•Математические ожидания для пяти случайных векторов признаков, задаются по номеру варианта учащегося (см. раздел 7, часть 2);
4.3.2Общий план выполнения работы
1.Смоделировать и изобразить графически обучающие выборки обьема 7V=50 для пяти нормально распределенных двумерных случайных векторов с заданными математическими ожиданиями и самостоятельно подобранными корреляционными матрицами, которые обеспечивают линейную разделимость классов.
2.Обьединить пять выборок в одну. Общее количество векторов в обьединенной выборке должно быть 250. Полученная обьединенная выборка используется для выполнения пунктов 3 и 4 настоящего плана.
3.Разработать программу кластеризации данных с использованием минимаксного алгоритма. В качестве типичного расстояния взять половину среднего расстояния между существующими кластерами. Построить отображение результатов кластеризации для числа кластеров, начиная с двух. Построить график зависимости максимального (из минимальных) и типичного расстояний от числа кластеров.
4.Разработать программу кластеризации данных с использованием алгоритма К внутригрупповых средних для числа кластеров равного 3 и
5.Для ситуации 5 кластеров подобрать начальные условия так, чтобы получить два результата: а) чтобы кластеризация максимально соответствовала первоначальному разбиению на классы («правильная» кластеризация); б) чтобы кластеризация максимально не соответствовала первоначальному разбиению на классы («неправильная» кластеризация). Для всех случаев построить графики зависимости числа векторов признаков, сменивших номер кластера, от номера итерации алгоритма.
4.3.3Содержание отчета
Отчет по работе должен содержать:
•исходные данные генерируемых векторов признаков - средние и ковариационные матрицы;
•для минимаксного алгоритма: полученное число классов, график зависимости максимального и типичного расстояний от числа кластеров;
•для алгоритма Л'-внутригрупповых средних: график зависимости числа векторов признаков, сменивших номер кластера, от итерации алгоритма.
64