Кластерный анализ

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

Анализ отечественных  и зарубежных публикаций показывает, что кластерный анализ находит применение в самых разнообразных научных  направлениях: биология, медицина, археология, история, география, экономика, филология  и т.д. В прекрасной книге В.В.Налимова "Вероятностная модель языка" [42] описано применение кластерного анализа при исследовании восприятия живописи. В. Власов. Эпидемиология.Большая часть литературы по кластерному анализу появилась в течение последних трех десятилетий, хотя первые работы, в которых упоминались кластерные методы, появились достаточно давно [1]. Польский антрополог К.Чекановский выдвинул идею "структурной классификации" [1], содержавшую основную идею кластерного анализа - выделение компактных групп объектов. 

В 1925 г. советский  гидробиолог П.В. Терентьев разработал так называемый "метод корреляционных плеяд" [22], предназначенный для  группировки коррелирующих признаков. Этот метод дал толчок развитию методов группировки с помощью графов. Термин "кластерный анализ" впервые был предложен Трионом [2-3]. Слово "cluster" переводится с английского языка как "гроздь, кисть, пучок, группа". По этой причине первоначальное время этот вид анализа называли "гроздевым анализом". В начале 50-х годов появились публикации Р.Люиса, Е.Фикса и Дж. Ходжеса по иерархическим алгоритмам кластерного анализа. Заметный толчок развитие работ по кластерному анализу дали работы Р.Розенблатта по распознающему устройству (персептрону), положившие начало развитию теории "распознавания образов без учителя".

Толчком к разработке методов кластеризации явилась  книга "Принципы численной таксономии"[4], опубликованная в 1963г. двумя биологами - Робертом Сокэлом и Питером Снитом. Авторы этой книги исходили из того, что для создания эффективных биологических классификаций процедура кластеризации должна обеспечивать использование всевозможных показателей характеризующих исследуемые организмы, производить оценку степени сходства между этими организмами и обеспечивать размещение схожих организмов в одну и ту же группу. При этом сформированные группы должны быть достаточно "локальны", т.е. сходство объектов (организмов) внутри групп должно превосходить сходство групп между собой. Последующий анализ выделенных группировок, по мнению авторов, может выяснить, отвечают ли эти группы разным биологическим видам. Иными словами, Сокэл и Снит предполагали, что выявление структуры распределения объектов в группы, помогает установить процесс образования этих структур. А различие и сходство организмов разных кластеров (групп) могут служить базой для осмысления происходившего эволюционного процесса и выяснения его механизма.

В эти же годы было предложено множество алгоритмов таких  авторов, как Дж. Мак-Кин, Г. Болл и Д. Холл по методам k-средних; Г. Ланса и У. Уильямса, Н. Джардайна и др. - по иерархическим методам. Заметный вклад в развитие методов кластерного анализа внесли и отечественные ученые - Э.М.Браверман, А.А.Дорофеюк, И.Б.Мучник, Л.А,Растригин, Ю.И.Журавлев, И.И.Елисеева и др. В частности, в 60-70 гг. большой популярностью пользовались многочисленные алгоритмы разработанные новосибирскими математиками Н.Г.Загоруйко, В.Н.Елкиной и Г.С.Лбовым. Это такие широко известные алгоритмы, как FOREL, BIGFOR, KRAB, NTTP, DRET, TRF и др. На основе этих пакетов был создан специализированный пакет программ ОТЭКС [26]. Не менее интересные программные продукты ППСА и Класс-Мастер были созданы московскими математиками С.А.Айвазяном, И.С.Енюковым и Б.Г.Миркиным[27].

В том или ином объеме методы кластерного анализа  имеются в большинстве наиболее известных отечественных и зарубежных статистических пакетах: SIGAMD, DataScope, STADIA, СОМИ, ПНП-БИМ, СОРРА-2, СИТО, SAS, SPSS, STATISTICA, BMDP, STATGRAPHICS, GENSTAT, S-PLUS и т.д. Достаточно подробный сравнительный анализ многочисленный статистических пакетов заинтересованный читатель найдет в [28]. Конечно, спустя 10 лет после выхода этого обзора, изменилось достаточно много, появились новые версии многих статистических программ, появились и абсолютно новые программы, использующие как новые алгоритмы, так и сильно возросшие мощности вычислительной техники. Однако большинство статистических пакетов используют алгоритмы предложенные и разработанные в 60-70 гг.

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

Третья причина - углубление специальных знаний неизбежно  приводит к увеличению количества переменных, учитываемых при анализе тех  или иных объектов и явлений. Вследствие этого субъективная классификация, которая ранее опиралась на достаточно малое количество учитываемых признаков, часто оказывается уже ненадежной. А объективная классификация, с все возрастающим набором характеристик объекта, требует использования сложных алгоритмов кластеризации, которые могут быть реализованы только на базе современных компьютеров. Именно эти причины и породили "кластерный бум"[12-47]. К сожалению, в среде медиков и биологов кластерный анализ еще не стал достаточно популярным и обыденным методом исследования. Причины этого мы уже рассматривали в своих предыдущих публикациях [48-50] и в статьях раздела "Биометрика" :

1. Леонов В.П. Долгое прощание с лысенковщиной.
2. Леонов В.П. Общие проблемы применения статистики в биомедицине, или что разумнее: ДДПП или ДППД?

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

1. ОБЪЕКТ  И ПРИЗНАК

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

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

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

Таблица 1  
 

Весь массив данных включал 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 (неразличимость тождественных объектов)

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

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

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