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

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

Примечание. Для этой статьи требуется знание концепций машинного обучения.

Введение

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

Итоги этой статьи:

  1. Определение кластеризации
  2. Описание алгоритмов кластеризации, таких как K-средние и смешанные модели Гаусса.
  3. Описать масштабируемый алгоритм кластеризации для обработки больших наборов данных.
  4. Предварительный просмотр приложений здравоохранения для работы с большими данными для кластеризации.

Приложения для здравоохранения

Существует множество приложений и вариантов использования кластеризации в здравоохранении.

  1. Стратификация пациентов заключается в группировании пациентов в кластеры таким образом, чтобы пациенты в одном кластере имели общие характеристики.
  2. Исследование иерархии болезней — это изучение иерархической структуры болезней и того, как они связаны друг с другом.
  3. Фенотипирование — это преобразование необработанных данных в осмысленные клинические концепции или фенотипы.

Что такое кластеризация?

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

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

Алгоритмы кластеризации

Мы обсудим два типа алгоритмов кластеризации; классический и масштабируемый. Для классической кластеризации мы обсудим (1) K-средние (2) иерархическую кластеризацию (3) модель смеси Гаусса. Для масштабируемости мы обсудим (1) мини-пакетные k-средние и (2) DBScans.

Классические алгоритмы кластеризации

К-означает

Входные данные представляют собой набор точек данных (x1, x2 … xn) и параметр k, указывающий количество кластеров, которые мы хотим создать.

Результатом являются K кластеров (s1, s2, … sk) с подмножеством точек данных. Объединение этих кластеров — это все точки данных.

Цель кластеризации K-средних состоит в том, чтобы минимизировать сумму всех точек данных x, соответствующих соответствующим центрам ui, которые являются центром кластера si. Это оптимизирует назначение каждой точки данных в каждый из k кластеров.

Алгоритм К-средних

  1. Сначала укажите k
  2. Инициализировать центры K
  3. Назначьте каждую точку данных x ближайшему центру
  4. Получив все назначения, мы обновляем центр K, усредняя все точки в группе и переназначая K новому обновленному значению.
  5. Наконец, мы проверяем, сошелся алгоритм или нет — это означает, что мы больше не можем обновлять k или мы достигли максимального количества итераций.
  6. Затем мы можем вывести кластер.

Наглядная иллюстрация K-средних с k = 2. В приведенном ниже примере вы можете видеть, что (a) устанавливает две случайные точки для k. (b) точки теперь сгруппированы (c) центры k обновляются в (d и e) до сходимости в (f)

Иерархическая кластеризация

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

Есть два популярных подхода к этому

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

Агломерационная кластеризация начинается с вычисления расстояния между каждой точкой данных для создания матрицы расстояний. Это будет матрица размера n x n.

Затем мы инициализируем каждое расстояние как кластер, поэтому кластеров будет n. После этого мы объединяем два ближайших кластера. Как только это будет завершено, обновите матрицу расстояний и итеративно (матрица расстояний будет иметь размер n-1 x n-1. Слияние двух ближайших кластеров и создание новой матрицы расстояний выполняется итеративно, пока не останется только один кластер.

Мы рассмотрели методы KMeans и Hierarchial Clustering. Это жесткие методы кластеризации, поскольку каждая точка данных принадлежит только одному кластеру.

Модель гауссовой смеси

Это метод мягкой кластеризации. Что это значит? Каждая точка данных может принадлежать множеству кластеров с разной степенью.

Распределение Гаусса является наиболее популярным непрерывным распределением вероятностей и также известно как нормальное распределение. Гауссиана имеет форму колоколообразной кривой.

Распределение Гаусса имеет две переменные мю и сигма. Mu — это центр кривой нормального распределения, то есть среднее значение, а сигма — это дисперсия, отражающая разброс данных.

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

Модель смеси Гаусса математически представлена ​​как вероятность того, что точка данных x является взвешенной суммой более чем k гауссовских распределений. Подумайте о наличии нескольких распределений Гаусса, как на графике выше.

Это достигается путем умножения коэффициента смешивания a на среднее значение и дисперсию для кластера k. Коэффициент смешивания представлен как pi k на изображении ниже, и это говорит нам, насколько велик кластер k.

Мю и сигма теперь должны быть вам более знакомы. Mu k на изображении ниже — это среднее значение кластера k/центра кластера k. Sigma k - это дисперсия для кластера k

Цель GMM состоит в том, чтобы выяснить параметры, то есть pi k, mu k и sigma k, учитывая все точки данных X.

Максимизация ожиданий GMM (EM)

Для вычисления GMM мы используем популярную стратегию, называемую максимизацией ожидания или алгоритмом EM.

Сначала инициализируйте все параметры, включая pi k, mu k и sigma k. После этого выполните шаг ожидания, назначив каждой точке X в данных оценку для каждого кластера. Эта оценка будет = gamma n k для каждого кластера k. То есть точка данных Xn будет иметь k баллов, по одному для каждого кластера. Эта оценка покажет нам, насколько вероятно, что точка данных Xn была сгенерирована из кластера k.

Когда у нас есть все назначения, мы максимизируем назначения, обновляя эти параметры модели, pi k, mu k и sigma k, используя оценки, которые мы узнали из заданий на предыдущем шаге.

После этого вы проверяете, соблюдаются ли критерии сходимости. Например, вероятность больше не меняется.

Как только сходимость достигнута, мы возвращаем все параметры модели для смешанной модели Гаусса.

Шаги GMM более подробно:

Инициализация GMM: чтобы запустить алгоритмы EM для смешанных моделей Гаусса, мы должны найти коэффициент смешивания (пи), среднее значение (мю) и дисперсию (сигма) для каждого кластера. Этот первый шаг важно сделать правильно.

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

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

Есть несколько советов, которые могут помочь вам получить хорошую отправную точку при инициализации. То есть mu k можно установить на выходе запущенных k средств для определения центров. Ковариационная матрица сигма k может быть вычислена с использованием всех точек данных из соответствующих кластеров. Коэффициент смешивания pi k может быть рассчитан путем деления размера кластера k на общую численность населения n.

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

Шаг GMM E: на этом шаге мы назначаем каждой точке данных в X n оценку gamma nk для каждого кластера k.
Способ, которым мы можем вычислить это значение, показан на изображении ниже. Уравнение ниже показывает, что gamma nk имеет числитель из двух членов.
Один из них — это коэффициент смешивания для кластера k, а другой — вероятность появления X n в кластере k. Знаменатель должен нормализовать этот показатель между [0,1]

В приведенном выше примере мы видим результат создания оценки для каждого из оранжевых и синих гауссианов. Формула обеспечивает оценку для каждого кластера.

В примере мы видим одну точку внизу, оценка которой равна [0,5, 0,5], что означает, что эта точка может принадлежать синему гауссу на 50% и тому же самому оранжевому.
Другой вектор оценки в верхней части диаграммы имеет значения оценки ожидания [0,8, 0,2] для соответствующего распределения синего и оранжевого цветов.

Шаг E создает эту оценку для каждой точки данных.

Шаг GMM M. Этот шаг включает в себя обновление параметров модели pi k, mu k и sigma k с использованием всех оценок задания, которые мы узнали на предыдущем шаге. Это делается для каждого кластера k.

Сначала мы определяем вспомогательную сумму N k, которая равна сумме всех gamma n для конкретного k. Интуитивно N k является размером кластера k.

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

Сигма ковариации k вычисляется с использованием взвешенных точек данных, умноженных на ковариацию точки данных X n. Ковариация вычисляется путем взятия точки данных, а затем вычитания mu k (центральная точка/среднее значение кластера k), транспонированного, умноженного на ту же точку данных, вычитающую mu k. Все делится на Nk, который является размером кластера. Интуитивно сигма k – это ковариация всех точек данных в кластере k.

Коэффициент смешения pi k пропорционален размеру кластера N k. Другими словами, pi k — это априорная вероятность для точек данных, принадлежащих кластеру k.

Визуализация GMM. На изображениях ниже показан ряд обновлений гауссовых моделей (красный и синий). Начнем с инициализации двух моделей. на первом изображении вверху слева.

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

Там, после того как мы обновим параметры модели гауссовой смеси на основе оценок присвоения, на третьем рисунке мы можем увидеть, как красные и синие круги удлиняются в соответствии с данными. На этом изображении мы обновляем mu k (среднее значение/центры кластера), sigma k и pi k.

После этого мы повторяем шаг M и шаг E до сходимости.
На изображении выше мы видим L = 20 для окончательного графика. Это означает, что для сходимости потребовалось 20 итераций.

K-средние и гауссовская смешанная модель

Кластеризация: K означает, что каждая точка данных принадлежит одному кластеру и только одному кластеру. Модель гауссовой смеси - каждая точка данных принадлежит нескольким кластерам с разными весами.

Параметр: K означает — у нас есть только центр кластера в качестве параметра. Модель гауссовой смеси учитывает центр кластера, коэффициент смеси и ковариацию.

Алгоритмы: K означает и Модель смеси Гаусса используют алгоритм EM. Были ли они итеративно обновлены назначение кластеризации и параметры модели.

Алгоритмы масштабируемой кластеризации

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

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

Мини-пакет K-средних

Это алгоритм K-средних, но вместо использования всего набора данных мы работаем с меньшими партиями данных.

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

На высоком уровне мы начинаем с инициализации k центров как c. Это можно сделать путем случайного выбора этих центров.

Затем мы хотим обновить центры, мы делаем это, повторяя t раз и для каждого раза:

  • выборка b точек данных для формирования мини-партии, назовем ее M
  • назначьте точки данных (M) ближайшему кластеру c.
  • обновить центры на основе заданий в M.

На изображении выше мы видим псевдоалгоритм для мини-пакета K означает.

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

С. Обновите центр на основе назначений M.(1) На этом шаге мы просматриваем все точки данных x в мини-пакете и извлекаем соответствующий центр из предыдущего шага. (2) Затем мы увеличиваем соответствующий счетчик центров на единицу.
(3) Затем мы устанавливаем размер шага как обратную величину числа центров. (4) Наконец, мы обновляем центр c на 1-eta * old_centre + eta * x, как показано ниже. Интуитивно мы перемещаем старый центр обработки данных в сторону точек данных по eta.

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

Большой О:

t = t итераций по времени
b = размер пакета
K = количество кластеров
d = размер точек данных

O (t * b * K * d) - это большая нотация O для этого алгоритма. Самый затратный шаг в алгоритме — присвоить точки данных ближайшему центру. Поскольку у нас есть b точек данных в каждой партии и K центров. Нам нужно вычислить K * b сравнений, и каждая точка данных имеет размерность d.

Сканирование БД

Сканирование БД расшифровывается как пространственная кластеризация приложений с шумом на основе плотности.

Основная интуиция DB Scan состоит в том, чтобы определить кластер как области с высокой плотностью, разделенные областями с низкой плотностью. Это приводит к тому, что кластеры имеют любую форму

Ключевые понятия DBScan

Прежде чем мы объясним алгоритм, нам нужно ввести некоторые ключевые понятия.

Во-первых, как мы измеряем плотность? Плотность точки p определяется как количество точек в пределах абсолютного расстояния от p. Например, предположим, что точка p имеет 3 другие точки в пределах абсолютного расстояния 1, поэтому плотность этой точки p = 3.

Для одного и того же абсолютного расстояния каждая точка в наборе данных может иметь значение плотности. Теперь, чтобы понять, как интерпретировать плотность p, нам нужно понять, что считается плотной областью? Точка данных p является плотной, если плотность p ≥ некоторого порога минимальных точек данных.

Ядро: это точки в плотной области.

Граница: точки в радиусе эпсилон до центральной точки.

Шум: все остальные точки за пределами эпсилон-расстояния являются шумом.

Алгоритм DBScan

После того, как мы определили эпсилон и минимальный порог точки данных, а также основные точки.

  1. Для каждой центральной точки c создайте ребра к точкам с расстоянием в эпсилон.
    Пример для точек c1 -> [ ребро 1 = n3, ребро 2 = n50, ребро 3 = n20 ….]
  2. Определите N, это набор узлов на графике (который представляет собой все точки данных в наборе данных)
  3. Если в множестве N нет основных точек, то мы закончили.
  4. Если в наборе N все еще есть основные точки, то мы выбираем случайную основную точку c.
    4.1. Затем находим связную компоненту X из c, имеем ребра для c, ищем узлы, из которых состоит X.
    4.2. Теперь, когда мы сформировали кластер X с ядром c, мы удаляем все узлы X из N, чтобы получить оставшееся население. N = N \ X (установленная разница)
  5. Затем вернитесь к шагу 3 и продолжите итерацию.

Кластеризация показателей оценки

До сих пор мы рассматривали алгоритмы кластеризации, затем мы представим набор оценочных показателей для кластеризации. К ним относятся индекс Рэнда, взаимная информация и коэффициент силуэта.

Индекс Рэнда и взаимная информация требуют результатов кластеризации достоверности. Коэффициент силуэта не требует достоверности.

Индекс Рэнда

Также упоминается как РИ.

n будет использоваться для описания точки данных, X будет назначениями кластеризации, а Y - основными истинами. Мы определяем узлы, принадлежащие X1, и узлы, исходящие из Y1.

После этого мы вычисляем терм a, а a — это количество пар, принадлежащих как X1, так и Y1. Пересечение двух множеств. Затем мы вычисляем количество пар, принадлежащих разным кластерам в X и Y — давайте назовем этот термин b.

Чтобы вычислить RI, мы добавляем a к b и делим на количество пар. Количество пар n(n-1)/2

RI находится между [0, 1], где 0 — плохая оценка, а 1 — идеальная кластеризация.

Взаимная информация

Это понятие из теории информации. МИ измеряет, насколько одна случайная величина говорит нам о другой.

В нашем случае две случайные переменные представляют собой кластерное задание x {x1, x2, … xk} и истинное назначение y {y1, y2, … yk}.

Энтропия используется для измерения неопределенности переменной, поэтому энтропия x -> H(x) определяется как сумма вероятности p (x), умноженная на логарифм p (x). Для каждого x мы получаем значение от 0 до 1, где значения ближе к 0 означают, что переменная является детерминированной, а 1 означает, что переменная является случайной.

МИ x и y представляет собой сумму по x и y совместной вероятности p (x, y), умноженной на логарифм p (x, y), деленной на предельную вероятность p (x), умноженную на предельную вероятность p (y). .

Диапазон MI находится между 0 и энтропией x, которая равна [0, H(x)]. Когда M1 ближе к 0, это означает, что x и y независимы, а когда M1 ближе к энтропии x, это означает, что y полностью определяется x.

Если мы применим MI для интерпретации результата, чем выше значение, тем лучше назначение кластеризации.

Иногда используется нормализованное значение MI (как показано на изображении выше)
Чтобы вычислить это, мы берем MI x и y, деленное на квадратный корень из энтропии x, умноженный на энтропию y.

Резюме RI и MI

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

Коэффициент силуэта

Это еще одна популярная оценочная метрика, для которой нам не требуется никакой достоверной информации.

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

Мы делаем это, определяя x как точку данных, c как кластер, содержащий x и c` как ближайший к c кластер.

Затем мы вычисляем два значения a и b. a определяется как среднее расстояние от x до всех точек данных в кластере c. b — среднее расстояние от x до всех точек данных в кластере c`.

Наконец, мы можем рассчитать коэффициент силуэта как b -a, деленное на максимальное значение b и a. Как показано на изображении выше.

Интуиция подсказывает, что если назначение x правильное, разница между b и s должна быть большой. Это означает, что это хорошее задание кластеризации.

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

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

Краткое напоминание: полное резюме курса можно найти на курсе Большие данные для информатики здравоохранения

Надеюсь, вы чему-то научились.

-R