Размещено на http://www.allbest.ru/

Курсовая работа

Анализ медико-биологической информации методом иерархической классификации



Содержание

Вступление

1. Математическая формулировка задачи

2. Выбор метода решения и постановки задачи

3. Описание алгоритма решения задачи

4. Описание программы

5. Описание методики решения задачи по разработанной программе на основе контрольного примера

6. Контрольный пример решения задачи

Выводы

Литература



Вступление

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

Кластерный анализ наиболее ярко отражает черты многомерного анализа в классификации, факторный анализ - в исследовании связи.

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

Первое применение кластерный анализ нашел в социологии. Впервые в 1939 был определен предмет кластерного анализа и сделано его описание исследователем Трионом. Главное назначение кластерного анализа - разбиение множества исследуемых объектов и признаков на однородные в соответствующем понимании группы или кластеры. Это означает, что решается задача классификации данных и выявления соответствующей структуры в ней. Методы кластерного анализа можно применять в самых различных случаях, даже в тех случаях, когда речь идет о простой группировке, в которой все сводится к образованию групп по количественному сходству.

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

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

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

В задачах социально-экономического прогнозирования весьма перспективно сочетание кластерного анализа с другими количественными методами (например, с регрессионным анализом).

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

В кластерном анализе считается, что:

а) выбранные характеристики допускают в принципе желательное разбиение на кластеры;

б) единицы измерения (масштаб) выбраны правильно.

Выбор масштаба играет большую роль. Как правило, данные нормализуют вычитанием среднего и делением на стандартное отклонение, так что дисперсия оказывается равной единице.

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

кластерный таксономия биологический



1. Математическая формулировка задачи

Задача кластерного анализа заключается в том, чтобы на основании данных, содержащихся во множестве Х, разбить множество объектов G на m (m - целое) кластеров (подмножеств) Q1, Q2, …, Qm, так, чтобы каждый объект Gj принадлежал одному и только одному подмножеству разбиения и чтобы объекты, принадлежащие одному и тому же кластеру, были сходными, в то время, как объекты, принадлежащие разным кластерам были разнородными.[1]

Например, пусть G включает n стран, любая из которых характеризуется ВНП на душу населения (F1), числом М автомашин на 1 тысячу человек (F2), душевым потреблением электроэнергии (F3), душевым потреблением стали (F4) и т.д. Тогда Х1 (вектор измерений) представляет собой набор указанных характеристик для первой страны, Х2 - для второй, Х3 для третьей, и т.д. Задача заключается в том, чтобы разбить страны по уровню развития.

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

Для решения задачи кластерного анализа необходимо определить понятие сходства и разнородности.

Понятно то, что объекты -ый и j-ый попадали бы в один кластер, когда расстояние (отдаленность) между точками Х и Хj было бы достаточно маленьким и попадали бы в разные кластеры, когда это расстояние было бы достаточно большим. Таким образом, попадание в один или разные кластеры объектов определяется понятием расстояния между Х и Хj из Ер, где Ер - р-мерное евклидово пространство. Неотрицательная функция d(Х , Хj) называется функцией расстояния (метрикой), если:

а) d(Хi , Хj) 0, для всех Х и Хj из Ер

б) d(Хi, Хj) = 0, тогда и только тогда, когда Х = Хj

в) d(Хi, Хj) = d(Хj, Х)

г) d(Хi, Хj) d(Хi, Хk) + d(Хk, Хj), где Хj; Хi и Хk - любые три вектора из Ер.

Значение d(Хi, Хj) для Хi и Хj называется расстоянием между Хi и Хj и эквивалентно расстоянию между Gi и Gj соответственно выбранным характеристикам (F1, F2, F3, ..., Fр).

Наиболее часто употребляются следующие функции расстояний:

Евклидова метрика является наиболее популярной. Метрика l1 наиболее легкая для вычислений. Сюпремум-норма легко считается и включает в себя процедуру упорядочения, а lp - норма охватывает функции расстояний 1, 2, 3.

Понятием, противоположным расстоянию, является понятие сходства между объектами G. и Gj. Неотрицательная вещественная функция S(Х ; Хj) = Sj называется мерой сходства, если :

1) 0 S(Хi , Хj)1 для Х Хj

2) S(Хi , Хi) = 1

3) S(Хi , Хj) = S(Хj , Х)

Величину Sij называют коэффициентом сходства.

1.1 Методы кластерного анализа

Сегодня существует достаточно много методов кластерного анализа. Остановимся на некоторых из них (ниже приводимые методы принято называть методами минимальной дисперсии).

Пусть Х - матрица наблюдений: Х = (Х1, Х2,..., Хu) и квадрат евклидова расстояния между Х и Хj определяется по формуле:

1) Метод полных связей.

Суть данного метода в том, что два объекта, принадлежащих одной и той же группе (кластеру), имеют коэффициент сходства, который меньше некоторого порогового значения S. В терминах евклидова расстояния d это означает, что расстояние между двумя точками (объектами) кластера не должно превышать некоторого порогового значения h. Таким образом, h определяет максимально допустимый диаметр подмножества, образующего кластер.

2) Метод максимального локального расстояния.

Каждый объект рассматривается как одноточечный кластер. Объекты группируются по следующему правилу: два кластера объединяются, если максимальное расстояние между точками одного кластера и точками другого минимально. Процедура состоит из n - 1 шагов и результатом являются разбиения, которые совпадают со всевозможными разбиениями в предыдущем методе для любых пороговых значений.

3) Метод Ворда.

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

4) Центроидный метод.

Расстояние между двумя кластерами определяется как евклидово расстояние между центрами (средними) этих кластеров:

d2 ij = (X -Y)Т(X -Y) Кластеризация идет поэтапно на каждом из n-1 шагов объединяют два кластера G и , имеющие минимальное значение d2ij Если n1 много больше n2, то центры объединения двух кластеров близки друг к другу и характеристики второго кластера при объединении кластеров практически игнорируются. Иногда этот метод иногда называют еще методом взвешенных групп.

1.2 Алгоритм последовательной кластеризации

Рассмотрим Й = (Й1, Й2, … Йn) как множество кластеров {Й1}, {Й2},…{Йn}. Выберем два из них, например, Й и Й j, которые в некотором смысле более близки друг к другу и объединим их в один кластер. Новое множество кластеров, состоящее уже из n-1 кластеров, будет:

{Й1}, {Й2}…, {Й , Й j}, …, {Йn}.

Повторяя процесс, получим последовательные множества кластеров, состоящие из (n-2), (n-3), (n-4) и т.д. кластеров. В конце процедуры можно получить кластер, состоящий из n объектов и совпадающий с первоначальным множеством Й = (Й1, Й2, … Йn).

В качестве меры расстояния возьмем квадрат евклидовой метрики d j2. и вычислим матрицу D = {di j2}, где di j2 - квадрат расстояния между Й и Й j(рис.1.1):

	Й1	Й2	Й3	….	Йn
Й1	0	d122	d132	….	D1n2
Й2		0	d232	….	D2n2
Й3			0	….	D3n2
….				….	….
Йn					0

Рис.1.1

Пусть расстояние между Й i и Й j будет минимальным:

d j2 = min {di j2, i j}. Образуем с помощью Й i и Й j новый кластер

{Й i , Й j}. Построим новую ((n-1), (n-1)) матрицу расстояния(рис.1.2)

	{Й i , Й j}	Й1	Й2	Й3	….	Йn
{Й i ; Й j}	0	di j21	di j22	di j23	….	Di j2n
Й1		0	d122	d13	….	D12n
Й2			0	di j21	….	D2n
Й3				0	….	D3n
Йn						0

Рис.1.2 Матрица ((n-1),(n-1))

(n-2) строки для последней матрицы взяты из предыдущей, а первая строка вычислена заново. Вычисления могут быть сведены к минимуму, если удастся выразить di j2k,k = 1, 2,…, n; (k i j) через элементы первоначальной матрицы.

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

di+j,k = ? (di k + dj k).

Но можно также определить di+j,k как минимальное из этих двух расстояний:

di+j,k = min (di k + dj k).

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

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

di+j,k = A(w) min(dik djk) + B(w) max(dik djk), где

где ni и nj - число элементов в кластерах i и j, а w - свободный параметр, выбор которого определяет конкретный алгоритм. Например, при w = 1 мы получаем, так называемый, алгоритм «средней связи», для которого формула перерасчета расстояний принимает вид:

В данном случае расстояние между двумя кластерами на каждом шаге работы алгоритма оказывается равным среднему арифметическому из расстояний между всеми такими парами элементов, что один элемент пары принадлежит к одному кластеру, другой - к другому.

Наглядный смысл параметра w становится понятным, если положить w . Формула пересчета расстояний принимает вид:

Di+j,k = min (d,k djk)

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

Метод наиболее удаленных соседей - расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями"). Этот метод обычно работает очень хорошо, когда объекты происходят на самом деле из реально различных "рощ". Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является "цепочечным", то этот метод непригоден.

Di+j,k = max (d,k djk)

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

В случае кластер анализа объектов наиболее часто мерой различия служит либо квадрат евклидова расстояния

Если признакам приписывается разный вес, то эти веса можно учесть при вычислении расстояния.

Естественной мерой сходства характеристик объектов во многих задачах является коэффициент корреляции между ними.

1.3 Число кластеров

Очень важным вопросом является проблема выбора необходимого числа кластеров. Иногда можно m число кластеров выбирать априорно. Однако в общем случае это число определяется в процессе разбиения множества на кластеры.

Проводились исследования Фортьером и Соломоном, и было установлено, что число кластеров должно быть принято для достижения вероятности того, что найдено наилучшее разбиение. Таким образом, оптимальное число разбиений является функцией заданной доли наилучших или в некотором смысле допустимых разбиений во множестве всех возможных. Общее рассеяние будет тем больше, чем выше доля допустимых разбиений. Фортьер и Соломон разработали таблицу, по которой можно найти число необходимых разбиений. S( в зависимости от и (где - вероятность того, что найдено наилучшее разбиение, - доля наилучших разбиений в общем числе разбиений) Причем в качестве меры разнородности используется не мера рассеяния, а мера принадлежности, введенная Хользенгером и Харманом. Таблица значений S( ) приводится ниже.

Таблица значений S( ) Табл.1.

\	0.20	0.10	0.05	0.01	0.001	0.0001
0.20	8	11	14	21	31	42
0.10	16	22	29	44	66	88
0.05	32	45	59	90	135	180
0.01	161	230	299	459	689	918
0.001	1626	2326	3026	4652	6977	9303
0.0001	17475	25000	32526	55000	75000	100000

Довольно часто критерием объединения (числа кластеров) становится изменение соответствующей функции. Например, суммы квадратов отклонений:

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

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



1.4 Дендограммы

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

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

На рисунке 1 показан один из примеров дендограммы. Рис 1 соответствует случаю шести объектов (n=6) и k характеристик (признаков). Объекты А и С наиболее близки и поэтому объединяются в один кластер на уровне близости, равном 0,85. Объекты D и Е объединяются при уровне 0,8. Теперь имеем 4 кластера: (А, С), (F), (D, E), (B).

Далее образуются кластеры (А, С, F) и (E, D, B), соответствующие уровню близости, равному 0,7 и 0,6. Окончательно все объекты группируются в один кластер при уровне 0,5.

Вид дендограммы зависит от выбора меры сходства или расстояния между объектом и кластером и метода кластеризации. Наиболее важным моментом является выбор меры сходства или меры расстояния между объектом и кластером.

Число алгоритмов кластерного анализа слишком велико. Все их можно подразделить на иерархические и неиерархические.

Иерархические алгоритмы связаны с построением дендограмм и делятся на:

а) агломеративные, характеризуемые последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров;

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

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

1.5 Данные

Кластерный анализ можно применять к интервальным данным, частотам, бинарными данным. Важно, чтобы переменные изменялись в сравнимых шкалах.

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

Z-вклад показывает, сколько стандартных отклонений отделяет данное наблюдение от среднего значения:

Среднее для Z-вкладов является нулевым и стандартное отклонение равно 1.

Стандартизация позволяет сравнивать наблюдения из различных распределений. Если распределение переменной является нормальным (или близким к нормальному), и средняя и дисперсия известны или оцениваются по большим выборным, то Z-вклад для наблюдения обеспечивает более специфическую информацию о его расположении.



2. Выбор метода решения и постановка задачи.

В данном случае при решении задачи будем использовать такую функцию расстояния, как Евклидово расстояние; правило объединения кластеров - метод ближайшего соседа.

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



3. Описание алгоритма решения задачи

Алгоритм представлен в дополнениях на рис.1-3.

На рис. 1 алгоритма изображена схема алгоритма проведения иерархической классификации с формированием протокола. Эта схема состоит с 16 блоков:

Блок 1: начало программы;

Блок 2-6: ввод начальных данных. Координаты объектов хранятся в строках матрицы dat, а вектор c содержит для каждого объекта номер кластера, к которому он относится. При этом вначале, до объединения, каждый объект считается отдельным кластером, поэтому ci = I;

Блок 7: основной цикл поиска пары кластеров, расстояние между которыми минимально;

Блок 8: присвоение переменной dist значения MAXDIST, которое означает некоторую константу, которая принимает наибольшее значение для типа данных, представляющего расстояние;

Блок 9-10: «подцикл» определения пары кластеров, расстояние между которыми минимально;

Блок 11: обращение к функции nearest и присвоение переменной t её значения;

Блок 12-13: сравнение значения переменной t с значением переменной dist. Если t < dist, то dist=t; a=i; b=j;

Блок 14-17: вывод протокола программы в файл и сохранение его в массиве;

Блок 18: конец.

На рис. 2 алгоритма представлен алгоритм функции nearest, т.е. схема алгоритма вычисления расстояния между кластерами по методу «ближайшего соседа». Этот алгоритм состоит из 10 блоков:

Блок 1: начало программы;

Блок 2: присвоение переменной r значения MAXDIST, которое означает некоторую константу, которая принимает наибольшее значение для типа данных, представляющего расстояние;

Блок 3-9: в соответствии с правилом «ближайшего соседа», при определении расстояния просматривается весь список объектов, находится два объекта, относящихся к интересующим нас кластерам (с номерами a и b), и вычисляется расстояние между ними. Среди таких расстояний мы ищем минимальное;

Блок 10: конец.

На рис. 3 представлена схема алгоритма функции D, с помощью которой вычисляется евклидова мера расстояния. Данная схема состоит из 6 блоков:

Блок 1: начало программы;

Блок 2: присвоение переменной s значения 0;

Блок 3-4: вычисление суммы квадратов расстояний между объектами а и b;

Блок 5: вычисление корня рассчитанной выше суммы;

Блок 6: конец.

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



4.Описание программы

Эта программа написана на языке программирования BORLAND PASCAL. Исходный текст программы - dendro.pas занимает 12 Кб на диске.

Разработанная программа считывает данные об объектах из текстового файла, который должен называться `objects.txt'

В результате обработки данных программа создает на диске (в том же каталоге, в котором располагается сама) текстовый файл “protocol.txt”, содержащий протокол иерархической классификации. Программа содержит две функции:

1. function d: тип real; атрибуты функции - переменные a, b относящиеся к массиву vector. Также функция использует переменные s: real; i: byte. Используется в программе для расчета евклидового расстояния между объектами a и b.

2. function nearest: тип real; атрибуты функции - переменные a, b типа byte. Также функция использует переменные r, t: real; i, j: byte. Используется в программе для расчета расстояния между кластерами a и b методом ближайшего соседа.

Таблица переменных

Переменная	Тип	Назначение
k	byte	Объекты
n	byte	Признаки
A	Byte	Объект а
b	byte	Объект б
c	byte	Номер кластера
d	Real	Евклидово расстояние
f	text	Текст
other	byte	Коэффициент
step	byte	Шаг
Dat	array[1..Nmax-1] of obj	Данные об объектах
pro	array[1..Nmax-1] of protocol	Данные Протокола
clust	array[1..Nmax,1..2] of integer	Координаты кластеров
p	vector	Признаки
skip	set of 1..Nmax	Пропущенные объекты
j	integer	Параметр цикла
lasty	integer	промежная
Ya	Integer	Промежная
yb	integer	Промежная
stop	byte	Ограничитель
dist	Real	Расстояние
t	real	Промежная
s	real	Расстояние между объектами
I	integer	Параметр цикла
e	byte	промежная
Gd	Integer	Параметр цикла
gm	integer	Параметр цикла
stack	Array[1..Nmax] of byte	Вспом.стек
vector	Array[1..kmax] of real	Признаки объекта
mx	Real	Данные протокола
r	real	промежная
Nmax	30	Постоянная
Kmax	50	Постоянная
Maxdist	1е38	Постоянная



5. Описание методики решения задачи по разработанным программам на основе контрольного примера

Разработанная программа считывает данные об объектах из текстового файла, который должен называться `objects.txt' и иметь следующую структуру:

в первой строке файла должны располагаться два целых числа, первое из которых означает количество объектов (назовем его N), а второе (назовем его K) -- количество признаков;

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

Если в строке будет больше чисел, чем задано параметром K, «лишние» числа будут проигнорированы. То же самое касается и «лишних» строк в файле. В результате обработки данных программа создает на диске (в том же каталоге, в котором располагается сама) текстовый файл “protocol.txt”, содержащий протокол иерархической классификации.

По окончании вывода протокола на экран в графическом режиме выводится дендрограмма, построенная в соответствии с этим протоколом. Дендрограмма отображается на экране до тех пор, пока пользователь не нажмет клавишу ENTER; после этого программа завершает свою работу.



6. Контрольный пример решения задачи

Результаты расчетов

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

Объектов 10

Параметров 5

6 9 4 7 6

6 3 5 2 1

6 2 5 4 7

6 3 4 1 3

9 5 4 7 1

5 6 3 2 5

9 5 8 7 4

6 5 2 3 4

6 3 5 2 4

6 7 8 5 9

Результат:



Выводы

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

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



Литература

1. Гельфанд И.М., Розенфельд Б.И., Шифрин М.А. Структурная организация данных в задачах медицинской диагностики и прогнозирования. М.: Методика, 1984. - 437с.

2. Миркин Б.Г. Задачи классификации в смешанной системе признаков. Многомерный статистический анализ и вероятностное моделирование реальных процессов. М.:ИНФРА-М, 1991. - 532с.

3. Дюран Б., Оделл П. Кластерный анализ. М.: Статистика, 1977, стр.181-190

Размещено на Allbest.ru