Здравоохранение, медицина

Кластеризация

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

Методы автоматического разбиения на кластеры редко используются сами по себе, просто для получения групп схожих объектов. Анализ только начинается с разбиения на кластеры. Коли уж кластеры обнаружены, естественно использовать другие методы data mining, чтобы попытаться установить, а что означает такое разбиение на кластеры, чем оно вызвано.

Существует большое число методов кластеризации. В data mining наиболее популярны методы расщепления, непосредственно разбивающие всю совокупность записей на несколько кластеров. Из них наибольшее распространение получили различные модификации метода K-средних.

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

На первом шаге разобьем все записи на K групп, наиболее близких к одному из центров. Мерой близости может быть расстояние в пространстве всех переменных (если переменным приписать геометрический смысл). Проиллюстрирует разбиение на три кластера в плоскости двух переменных, обобщение на случай нескольких переменных несложно. Выбранные центры помечены крестиком. Множество точек, равноудаленных от двух заданных центров на плоскости – прямая (в пространстве n

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

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

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

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