Дисперсия жизни... ;Регистрационный код (если есть)  ; Открывать в новом окне?  ;Имя нового окна  ; Разрешение (1-8)  ; Скорость смены (1-255)  ; Задержка (миллисекунд)  ; Смена рисунков со спецэффектами ("YES" или "NO")  ;Произвольный рисунок поверх апплета  ;X смещение наложенного рисунка  ;Y смещение наложенного рисунка  ;Задержка освобождения памяти  ;Приоритет задачи (1..10)  ; Мин. время синхр. кадра (мс); Sorry, your browser doesn't support Java ; Сообщение для браузеров без поддержки Java (tm)  Кликните по фотографии, и вы сможете ...

ОСНОВНЫЕ ПОНЯТИЯ И ТЕРМИНЫ

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

Признак (синонимы - свойство, переменная, характеристика; англ. - variable - переменная.) - представляет собой конкретное свойство объекта. Эти свойства могут выражаться как числовыми, так и не числовыми значениями. Например, артериальное давление (систолическое или диастолическое) измеряют в миллиметрах ртутного столба, вес - в килограммах, рост в сантиметрах и т.д. Далее такие признаки мы будем называть количественными признаками [5]. В отличие от этих непрерывных числовых характеристик (шкал), ряд признаков может иметь дискретные, прерывистые значения. В свою очередь такие дискретные признаки принято делить на две группы. Первая группа - ранговые, или как их еще называют порядковые переменные (шкалы). Таким признакам присуще свойство упорядоченности этих значений. К ним можно отнести стадии того или иного заболевания, возрастные группы, балльные оценки знаний учащихся, 12-балльную шкалу магнитуд землетрясений по Рихтеру и т.д. Вторая же группа дискретных признаков не имеет такой упорядоченности и носит название номинальных (от слова "номинал" - образец ) или классификационных признаков. Примером таких признаков может быть состояние пациента - "здоров" или "болен", пол пациента, период наблюдения - "до лечения" и "после лечения" и т.д. В этих случаях принято говорить, что такие признаки относятся к шкале наименований. Строго говоря, не вполне корректно в таких случаях будет использование выражения "измерение в шкале наименований", поскольку процедура измерения предполагает наличие некоторых средств измерения для нахождения численного значения измеряемой величины. Эти две группы дискретных признаков условимся далее именовать качественными признаками.[5] 

Используя понятия объекта и признака, условимся впредь называть матрицей "Объект-свойство" или "Объект-признак" прямоугольную таблицу, состоящую из значений признаков описывающих свойства исследуемой выборки наблюдений. В данном контексте одно наблюдение будет записываться в виде отдельной строки состоящей из значений используемых признаков. Отдельный же признак в такой матрице данных будет представлен столбцом, состоящим из значений этого признака по всем объектам выборки. Ниже приведена такая матрица, содержащая небольшую часть данных реального исследования свойств эритроцитов крови и ряда биохимических показателей у детей с больной щитовидной железой. В первом столбце матрицы размещен порядковый номер наблюдения, Х1-Х7 - количественные переменные представляющие собой электронномикроскопические характеристики эритроцитов крови, качественный признак Х8 - характер группы пациентов (здоровые, больные до лечения и больные после лечения) и качественный признак Х9 - вид заболевания щитовидной железы.

Таблица 1
 

N п/п	X1	X2	X3	X4	X5	X6	X7	X8	X9
1	80,93	0,605	0,303	4,94	1,21	5,85	0,2	1	1
2	80,3	0,5	0,7	5,1	1,3	5,7	0,1	1	1
3	80,22	0,599	0,599	5,59	1,09	5,29	0,2	2	1
4	80,8	0,3	0,6	4,9	1,2	5,9	0,1	2	1
5	80	0,5	0,9	5,2	1,1	5,8	0,1	1	1
6	80,6	0,7	0,3	5,1	1,2	5,9	0,2	2	1
7	79,9	0,2	1	4,7	1,9	5,7	0,2	1	1
8	81,4	0,6	0,5	5,3	1,8	3,9	0,2	2	2
9	80	0,3	0,8	4,9	1,8	5,1	0,3	3	2
10	80,3	0,5	0,4	5,4	1,9	5,1	0,2	2	2
11	79,8	0,8	0,2	5,3	2	5,2	0,3	3	2
12	80,7	0,6	0,3	5,7	2,1	4,7	0,2	2	1
13	80,9	0,3	0,6	4,1	2	5,7	0,3	1	1
14	80,5	0,5	0,5	4,9	1,9	5,1	0,2	2	1
15	79,5	0,5	0,6	5,3	2	5,3	0,1	3	1
16	80,2	0,7	0,2	5,1	2,2	5	0,2	1	1
17	80,5	0,6	0,3	5,1	2,1	4,7	0,2	2	2
18	80,42	0,499	0,399	4,89	1,89	5,09	0,3	2	2
19	80,3	0,7	0,3	5,3	2	5,2	0,2	1	2
20	80,5	0,5	0,5	5,1	1,9	4,9	0,2	3	2

Весь массив данных включал 8 групп количественных признаков: общий анализ крови, биохимия крови, содержание гормонов, характеристики эритроцитов крови, полученные с помощью электронной микроскопии и т.д. и 4 группы качественных признаков: жалобы, анамнез заболевания, наследственность, и пункция щитовидной железы. Общее количество исследуемых признаков равнялось 85. Выборка включала наблюдений за 105 детьми. Таким образом, вся матрица данных для анализа представляла собой таблицу, состоящую из 105 строк и 86 столбцов: 85 признаков плюс еще один столбец - идентификатор наблюдения, в качестве которого выступали фамилия и имя ребенка. 

2. РАССТОЯНИЕ МЕЖДУ ОБЪЕКТАМИ (МЕТРИКА)

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

1. d_ij > 0 (неотрицательность расстояния)
2. d_ij = d_ji (симметрия)
3. d_ij + d_jk > d_ik (неравенство треугольника)
4. Если d_ij не равно 0, то i не равно  j (различимость нетождественных объектов)
5. Если d_ij = 0, то i = j (неразличимость тождественных объектов)

В данной формуле использованы следующие обозначения:

• d_ij - расстояние между i-тым и j-тым объектами; 
• x_ik - численное значение k-той переменной для i-того объекта;
• x_jk - численное значение k-той переменной для j-того объекта;
• v - количество переменных, которыми описываются объекты.

Используя евклидову метрику, вычислим матрицу межобъектных расстояний, состоящую из величин d_ij - расстояние между i-тым и j-тым объектами. В нашем случае i и j - номер объекта, наблюдения. Поскольку объем выборки равен 5, то соответственно i и j могут принимать значения от 1 до 5. Очевидно также, что количество всех возможных по парных расстояний будет равно 5*5=25. Действительно, для первого объекта это будут следующие расстояния: 1-1; 1-2; 1-3; 1-4; 1-5. Для объекта 2 также будет 5 возможных расстояний: 2-1; 2-2; 2-3; 2-4; 2-5 и т.д. Однако число различных расстояний будет меньше 25, поскольку необходимо учесть свойство неразличимости тождественных объектов - d_ij = 0 при i = j. Это означает, что расстояние между объектом №1 и тем же самым объектом №1 будет равно нулю. Такие же нулевые расстояния будут и для всех остальных случаев i = j. Кроме того, из свойства симметрии следует, что d_ij = d_ji для любых i и j. Т.е. расстояние между объектами №1 и №2 равно расстоянию между объектами №2 и №1. Ниже приведена симметричная (d_ij = d_ji) квадратная матрица с нулевой (d_ij = 0 при i = j) диагональю. 
 

Вспомнив школьную алгебру, нетрудно вычислить количество расстояний d_ij в одном из треугольников матрицы (верхнем или нижнем). Всего в матрице количество элементов (чисел) равно N*N (в нашем случае 5*5=25). Вычтем из этого числа количество элементов находящихся на диагонали, равно объему выборки N. Далее разделим количество элементов находящихся над диагональю и под диагональю на два. В результате этого получим следующее выражение: (N*N - N)/2= N*(N-1)/2. Итак, для нашего случая всего будет 5*(5-1)/2=10 разных расстояний. 

А теперь попытаемся вычислить некоторые их этих расстояний самостоятельно, например, между объектом №1 и №2. Вначале вычислим квадрат этого расстояния, а потом извлечем из него квадратный корень. d²₁₂ = [(5-6)² + (11-11)² ]= 1² + 0² =1. Отсюда получаем, что d₁₂ =1. Аналогично вычислим величину d²₁₃ а затем и d₁₃ : d²₁₃ =[(5-6)² + (11-12)² ] = 1² + 1² = 2. Откуда находим, что корень квадратный из двух с точностью до второго знака после запятой равен 1,41. Запомним, что минимальная величина в данной матрице равна 1 и отвечает расстоянию d₁₂. Чуть ниже мы увидим, что процесс кластеризации этих 5 наблюдений начнется именно с объектов №1 и №2. Рекомендуем нашим читателям самостоятельно вычислить расстояние между 4 и 5 объектами, убедившись, что оно действительно равно 1,41.

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

При р = 2 мы получаем обычное Евклидово расстояние. Ниже приводится выражение для обобщенной метрики Минковского.

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

Частным случаем расстояния Минковского является так называемое манхэттенское расстояние, или "расстояние городских кварталов" (city-block), соответствующее р=1:

Таким образом, манхеттенское расстояние является суммой модулей разностей соответствующих признаков объектов. Устремив p к бесконечности, мы получаем метрику "доминирования", или Sup-метрику: 

которую можно представить также в виде d_ij = max| x_ik - x_jk|.

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

Здесь через X_i и X_j обозначены вектор-столбцы значений переменных для i-того и j-того объектов. Символ Т в выражении (X_i - X_j)^Т обозначает так называемую операцию транспонирования вектора. Символом S обозначена общая внутригрупповая дисперсионно-ковариационная матрица. А символ ^-1 над S означает, что необходимо обратить матрицу S (желающих более детально разобраться с этими математическими тонкостями отправляем к вполне доступным для медиков и биологов книгам [6-10]). В отличие от метрики Минковского и евклидовой метрики, расстояние Махаланобиса через матрицу дисперсий-ковариаций S связано с корреляциями переменных. Когда корреляции между переменными равны нулю, расстояние Махаланобиса эквивалентно квадрату евклидового расстояния. 

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

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

Кроме этих достаточно известных и популярных метрик используются и такие метрики, как коэффициенты Рао, Хемминга, Роджерса-Танимото, Жаккара, Гауэра, меры близости Журавлева, Воронина, Миркина, метрики Брея-Кертиса, Канберровская и многие другие [5, 11-33]. 

3. ПЛОТНОСТЬ И ЛОКАЛЬНОСТЬ КЛАСТЕРОВ

Как уже говорилось выше, главной целью кластерного анализа является нахождение в выборке групп объектов схожих между собой. Предположим, что каким-то из возможных методов мы получили такие группы - кластеры. Теперь имеет смысл обсудить наиболее важные свойства кластеров. Одно из таких свойств - это плотность распределения точек, наблюдений внутри кластера. Это свойство дает нам возможность определить кластер в виде скопления точек в многомерном пространстве, относительно плотное по сравнению с иными областями этого пространства, которые либо вообще не содержат точек, либо содержат малое количество наблюдений. Иными словами, насколько данный кластер является компактным, или же наоборот - достаточно разреженным. Несмотря на достаточную очевидность этого свойства, однозначного способа вычисления такого показателя (плотности) не существует. Наиболее удачным показателем, характеризующим компактность, плотность "упаковки" многомерных наблюдений в данном кластере, является дисперсия расстояния от центра кластера до отдельных точек кластера. Чем меньше дисперсия этого расстояния, тем ближе к центру кластера находятся наблюдения, тем больше плотность кластера. И наоборот, чем больше дисперсия расстояния, тем более разрежен данный кластер, и, следовательно, есть точки находящиеся как вблизи центра кластера, так и достаточно удаленные от центра кластера. 

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

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

Мы видим, что минимальный размер имеет кластер 1, а кластеры 2 и 3 имеют примерно равные размеры. В то же время, можно говорить о том, что минимальная плотность, а стало быть, и максимальная дисперсия расстояния, характерна для кластера 3. Кроме того, кластер 1 отделяется достаточно большими участками пустого пространства как от кластера 2, так и от кластера 3. Тогда как кластеры 2 и 3 частично перекрываются друг с другом. Представляет интерес и тот факт, что кластер 1 имеет гораздо большее различие от 2-го и 3-го кластеров по оси 1, нежели по оси 2. Напротив, кластеры 2 и 3 примерно одинаково различаются между собой как по оси 1, так и по оси 2. Очевидно, что для такого визуального анализа необходимо иметь все наблюдения выборки проецировать на специальные оси, подобные использованным нами, в которых проекции элементов кластеров будут видны как отдельные скопления. 

4. РАССТОЯНИЕ МЕЖДУ КЛАСТЕРАМИ 

В более широком смысле под объектами можно понимать не только исходные предметы исследования, представленные в матрице "объект-свойство" в виде отдельной строки, или отдельными точками в многомерном признаковом пространстве, но и отдельные группы таких точек, объединенные тем или иным алгоритмом в кластер. В этом случае возникает вопрос о том, каким образом понимать расстояние между такими скоплениями точек (кластерами) и как его вычислять. Отметим, что в этом случае разнообразных возможностей еще больше, нежели в случае вычисления расстояния между двумя наблюдениями в многомерном пространстве. Эта процедура осложняется тем, что в отличие от точек кластеры занимают определенный объем многомерного пространства и состоят из многих точек. Как, например, можно определить расстояние от Новосибирска до Академгородка, от Хабаровска до Владивостока, или от Москвы до Санкт-Петербурга? Можно принять за это расстояние протяженность прямой линии соединяющей главпочтамты этих городов. А можно измерить расстояние между главпочтамтами по автомобильной дороге или по железной дороге. Но эти методы не единственные из возможных. Учитывая протяженность самих объектов, можно понять, что эти расстояния будут различаться, если их измерять между ближними окраинами этих городов, или между дальними окраинами. Не лишено смысла и измерение расстояния между геометрическими центрами этих городов. Вопрос только в том, что при этом считать геометрическим центром города?

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

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

Краткий обзор методов