Разработка системы для оценки качества кластеризации электрокардиограммы

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

Аннотация

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

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

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

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



Abstract

The object of development of this final qualifying work is a system for assessing the quality of ECG clustering.

The purpose of the work is to obtain an assessment of the quality of the results of clustering of ECGs for their further improvement based on this assessment.

As a result of the workwas selected a metric to assess the quality of clustering results of ECGs and developeda system that automates the process of assessing the quality of clustering results of ECGs using this metric to obtain optimal clustering results of any sample of ECGs.

Final qualifying work consists of a list of definitions, designations and abbreviations, introduction, three sections, conclusion, list of references.



Содержание

Введение

1. Аналитическая часть

1.1 Постановка задачи

1.2 Анализ предметной области

1.3 Постановка задачи на разработку системы

2. Теоретическое решение задачи

2.1 Анализ метрик оценки качества результатов кластеризации

2.2 Тестирование метрик оценки качества результатов кластеризации

3. Практическое решение задачи

3.1 Система для оценки качества кластеризации ЭКГ

3.1.1 Выбор инструментальных средств для разработки

3.1.2 Описание работысистемы

3.1.3 Структура системы

3.2 Результаты работы системы

Заключение

Список использованных источников

Приложение А

Приложение Б

Приложение В

Приложение Г

Приложение Д



Определения, обозначения и сокращения

ЭКГ - электрокардиограмма.

ВСР - вариабельность сердечного ритма: характеристика человеческого организма, рассчитываемая на основе ЭКГ.

dRR - вариационный размах RR-интервалов: характеристика человеческого организма, рассчитываемая на основе ВСР.

RRNN - средняя длительность RR-интервалов: характеристика человеческого организма, рассчитываемая на основе ВСР.

SDNN - стандартное отклонение RR-интервалов: характеристика человеческого организма, рассчитываемая на основе ВСР.

ИБС - ишемическая болезнь сердца: состояние организма человека.

КНП - метод кратчайшего незамкнутого пути: алгоритм кластеризации.

DBSCAN-Density-based spatial clustering of applications with noise: алгоритм кластеризации.

OPTICS-Ordering pointstoidentify the clustering structure: алгоритм кластеризации.

BIRCH -Balance diterative reducing and clustering using hier archies: алгоритм кластеризации.

ПКИ - подсистема кластеризации системы обработки и анализа ЭКГ.

БД - база данных.

СУБД - система управления БД.

RMSSTD-Root-mean-square standard deviation: метрика оценки качества результатов кластеризации.

Г - ModifiedHubertГStatistic:метрика оценки качества результатов кластеризации.

DB - Davies-Bouldinindex: метрика оценки качества результатов кластеризации.

RS - R-squared: метрика оценки качества результатов кластеризации.

CH - Calinski-Harabaszindex: метрика оценки качества результатов кластеризации.

BH - Ball-Hallindex: метрика оценки качества результатов кластеризации.

KL- Krzanowski-Laiindex: метрика оценки качества результатов кластеризации.

H - Hartiganindex: метрика оценки качества результатов кластеризации.

S - Silhouetteindex: метрика оценки качества результатов кластеризации.

VNND - VarianceoftheNearestNeighborDistance:метрикаоценкикачестварезультатов кластеризации.

RL- Ratkowsky-Lanceindex: метрика оценки качества результатов кластеризации.

RT - Ray-Turiindex: метрика оценки качества результатов кластеризации.

TrW - TraceWindex: метрика оценки качества результатов кластеризации.

WG - Wemmert-Ganзarskiindex: метрика оценки качества результатов кластеризации.

M - Marriotindex: метрика оценки качества результатов кластеризации.

TrCW - TraceCovWindex: метрика оценки качества результатов кластеризации.

SS - Scott-Symonsindex: метрика оценки качества результатов кластеризации.

TrW-1B - TraceW-1Bindex:метрикаоценкикачестварезультатов кластеризации.

XB - Xie-Beniindex: метрика оценки качества результатов кластеризации.

BIC - Bayesianin formation criterion: метрика оценки качества результатов кластеризации.

JS -JavaScript: язык программирования.

CHWOS - Calinski-Harabasz with outsingle clusters, модернизированная оценки качества результатов кластеризации CH.

NF - разработанная в ходе выполнения работы метрика оценки качества результатов кластеризации ЭКГ.

SQL - Structured Query Language: язык запросов кБД.

UML - Unified Modeling Language: язык графического описания моделей программного обеспечения.

ПОК - подсистема оценки качества кластеризации системы обработки и анализа ЭКГ: «Система для оценки качества результатов кластеризации электрокардиограмм»;

ПК - персональный компьютер.



Введение

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

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

статистические параметры вариабельности сердечного ритма (ВСР) и индексы, рассчитанные на их основе. Например, вариационный размах (dRR), средняя длительность (RRNN), стандартное отклонение RR-интервалов (SDNN), индекс напряжения регуляторных систем Баевскогои т.п. Эти параметры вычисляются в ходе обработки кардиоинтервалов (RR-интервалов) - интервалов между последовательными ударами сердца (R-зубцами) [3].;

параметры усредненного кардиоцикла (электросигнала, описывающего набор процессов, происходящих в сердце в период времени, за который происходит его сокращение и расслабление). Например, пульс, PQ интервал, QT интервал, ширина QRS-комплекса, форма зубцов и т.п.;

спектральные показатели ВСР пациента[4]: распределение мощностей спектра кардиоинтервалограммы, отношение мощностей низких и высоких частот, частоту дыхания и т.п.;

и ряд других показателей.

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



1. Аналитическая часть

1.1 Постановка задачи

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

Кластеризация, и в том числе применительно к ЭКГ, позволяет выявлять различные неочевидные зависимости. Например, предрасположенность к каким-либо болезням - туберкулезу, ишемической болезни сердца (ИБС) и прочим[5].

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

Задачей данной работы является разработка системы для автоматизации процесса оценки качества результатов кластеризации ЭКГ. Решение этой задачи можно разделить на пять этапов (рис. 1):

Обоснование выбора метода кластеризации ЭКГ, для которого будет производиться оценка качества;

Определение характеристик человеческого организма, по которым можно разделить ЭКГ на типы (далее - типы выборок ЭКГ), для которых будет производиться оценка качества. Для каждой из выборок определено свое пространство признаков - алгебраическое многомерное пространство, каждая точка которого соответствует фиксированному упорядоченному набору признаков одного из элементов анализируемой выборки - ЭКГ;

Анализ метрик для вычисления оценки качества результатов кластеризации;

Тестирование и выбор метрики для вычисления оценки качества результатов кластеризации выборки ЭКГ. Результирующая оценка должна учитывать количество полученных кластеров, поскольку их значение определяется в процессе кластеризации, а не задается изначально как параметр алгоритма кластеризации;

Рис. 1 - Схема решения поставленной задачи



Разработка системы, которая позволит вычислять оценку результата кластеризации как показатель качества - «Системы для оценки качества кластеризации электрокардиограмм». Система должна среди множествазначений входного параметра алгоритма кластеризации ЭКГ (X), найти такой элемент rmax, при котором функция оценки качества результатов кластеризации будет принимать минимальное (или максимальное, в зависимости от метрики) значение. То есть решение задачи

(в зависимости от метрики), где f(rmax) -функция, значением которой является оценка качества результатов кластеризации выборки ЭКГ c параметром rmax, позволит найти оптимальное значение параметра кластеризации для данной выборки. Это, в свою очередь, позволит получить наиболее качественные результаты кластеризации данной выборки ЭКГ.

Это даст возможность определить оптимальные входные параметры алгоритма кластеризации для каждого из типов выборок ЭКГ.

1.2 Анализ предметной области

Кластерный анализ (или кластеризация) - это процедура, решающая задачу, которая заключается в том, что определенную выборку данных необходимо разбить на кластеры - непересекающиеся (или слабо пересекающиеся, при нечеткой кластеризации) подмножества этой выборки. Результаты кластеризации (ее качество, то есть степень готовности данных к дальнейшей обработке) должны отвечать следующим условиям [6]:

расстояние между элементам одного кластера (среднее внутрикластерное расстояние) и сумма этих расстояний должны быть как можно меньше;

расстояние между разными кластерами (среднее межкластерное расстояние) и сумма этих расстояний должны быть как можно больше;

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

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

Расстояние ближайшего соседа - вычисляется расстояние между двумя ближайшими элементами разных кластеров;

Расстояние дальнего соседа - за расстояние между кластерами принимается расстояние между двумя элементами разных кластеров, которые максимально отдалены друг от друга;

Метод Уорда - два кластера объединяются между собой и рассчитывается расстояние между ними, равное увеличению суммы квадратов расстояний элементов до центра кластера, получаемого в результате этого объединения;

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

Центроидное расстояние - вычисляется расстояние между центрами масс двух кластеров. Центр масс кластера - это вектор, состоящий из средних значений каждой из характеристик всех элементов кластера. Для центроидного метода также существуют взвешенная и невзвешенная модификации.

Существует множество методов кластеризации. И несмотря на то, что общепринятой классификации не существует, зачастую методы кластеризации можно разделить на следующие примерные группы [8]:

Иерархические методы (таксономии);

Графовые методы;

Вероятностные методы;

Нечеткие методы;

Методы, основанные на нейронных сетях;

Генетические (эволюционные) методы;

Плотностные методы.

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

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

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

Примером агломеративного метода является кластеризация Ланса-Уильямса. Для всех элементов выборки, которые изначально являются кластерами, состоящими из одного элемента, определяется формула для расчета расстояния между ними-R(A, B). На каждом этапе объединения кластеры, расстояние между которыми является самым маленьким, сливаются в один новый кластер С. Расстояние между кластером С и любым другим кластером D вычисляется по формуле

,

где бA, бB, в и г - числовые коэффициенты. В качестве метода определения расстояния могут применяться практически любые меры, в том числе, и из перечисленных ранее [9].

Графовые методы кластеризации базируются на том, что выборка представляется в виде графа. Элементы выборки выступают в качестве вершин графа, а расстояния между элементами в качестве ребер. К этому семейству можно отнести такие эвристические методы, как [10]:

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

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

Эти методы также можно привести в пример дивизимных иерархических алгоритмов.

В вероятностных или статистических методах выдвигается гипотеза о том, что любой элемент выборки является элементом одного из K кластеров. Число K задается изначально. Для каждого элемента существует параметр вероятностного распределение по кластерам. Необходимо определить наиболее близкое к реальности значение этого параметра [8]. Среди самых популярных методов этого типа можно выделить:

EM-алгоритм (англ. Expectation-maximization (EM) algorithm). Он состоит из двух повторяющихся друг за другом шагов:

E-шаг (Expectation). Определяются вероятности принадлежности элемента кластеру X;

M-шаг (Maximization). Уточняются параметры всех кластеров с использованием полученных на прошлом шаге вероятностей.

Также в этом алгоритме настраивается форма кластеров.

Метод k-средних. Этот метод является упрощенной версией EM-алгоритма и имеет два основных отличия:

Каждый элемент приписывается лишь одному из K кластеров. Алгоритм очень чувствителен к начальному распределению элементов по кластерам;

Форма кластеров не настраивается.

Также существуют модернизации метода, такие как K-медиан и K-пространственных медиан, где для определения центра масс кластера вычисляется медиана или пространственная медиана вместо среднего значения, соответственно.

В методах нечеткой кластеризации каждый кластер представляет собой нечеткое множество объектов. Наиболее известным примером такого подхода является метод c-средних - модификация метода k-средних[11]:

Составляется матрица принадлежности Nэлементов к K кластерам (N * K);

Находится значение критерия нечеткой ошибки с учетом центра масс нечеткого кластера;

Матрица изменяется с учетом вычисленных критериев с целью их уменьшения.

Шаги б) и в) повторяются, пока матрица изменяется значительно.

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

Генетические методы основываются на том, что:

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

На основе предыдущей популяции создается новая с помощью эволюционных операторов:

выбора - выбирает хорошие решения;

рекомбинации - создает новое решения с помощью рекомбинации имеющихся;

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

Итерация б) повторяется до тех пор, пока не получится удовлетворительное решение[11].

К плотностным методам кластеризации можно отнести, например, Density-based spatial clustering of applications with noise (DBSCAN) и Ordering point stoidentify the clustering structure (OPTICS), основанные на плотности элементов выборки. DBSCAN объединяет в кластеры элементы, количество близких соседей у которых значительно, а остальные исключает как выбросы[12].Алгоритм OPTICS является модификацией DBSCAN и устраняет его главный недостаток - некорректную кластеризацию в случае, если кластеры имеют разную плотность. Для этого элементы выборки упорядочиваются так, что соседними становятся точки, которые находятся близко в пространстве [13].

Также существую методы, которые нельзя отнести к одному из типов приведенной классификации, например, комбинированный метод Balance diterative reducing and clustering using hier archies (BIRCH). Процесс кластеризации в нем проходит в два этапа[14]:

Определяются предварительные кластеры путем построения дерева;

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

В ЗАО «ЕС-лизинг» разработана и эксплуатируется система, осуществляющая разностороннюю обработку и анализ ЭКГ. Входными параметрами данной системы являются необработанные (полученные напрямую из электрокардиографа) ЭКГ и фотоплетизмограммы. Она позволяет осуществлять расчет параметров ВСР, различные показатели на основе кардиоцикла пациента, амплитудно-частотных характеристик ЭКГ, а также имеет набор тестовых параметров. В результате расчета таких параметров появляется возможность диагностики состояния как в конкретный момент времени, так и на протяжении периодов различной длительности.

Одним из модулей этой системы является подсистема кластеризации ЭКГ (ПКИ), позволяющая автоматизировать процесс разделения выборок ЭКГ на кластеры по какому-либо признаку. Метод кластеризации, используемый в ПКИ, является модифицированным методом выделения связных компонент. Также в него внесены правки для работы в подсистеме с сохраненным состоянием [5].

Работу метода можно описать следующим образом (рис. 2):на вход поступает массив ЭКГ, каждая из которых описывается:

массивом показателей- n (размерность пространства признаков)точек верхней огибающей амплитудного спектра Фурье ЭКГ, пример которой приведен на рис. 3;

параметр кластеризации - максимально возможное расстояние между элементами кластеров.

Если происходит добавление новых ЭКГ к уже кластеризованным, то в параметрах, поступающих на вход, содержатся ранее рассчитанные кластеры. Для каждой новой точки из массива:

рассчитывается ее нормальная форма;

рассчитывается количество существующих кластеров, которые находятся на расстоянии меньшем, чем максимально допустимое. Назовем их связанными с точкой;

в зависимости от количества связанных с ЭКГ кластеров алгоритм выполняет один из трех вариантов последовательностей действий:

Если связанных с точкой кластеров 0, то ЭКГ становится новым кластером и обработка переходит к следующей ЭКГ;

Если с ЭКГ связан 1 кластер, то эта ЭКГ добавляется в него;

Если с ЭКГ связано несколько кластеров, то они попарно объединяются между собой, а потом в один новообразованный кластер добавляется ЭКГ.

Сравнение характеристик, достоинств и недостатков описанных методов кластеризации приведено в табл. 1. Поля табл. 1, помеченные звездой (*), могут являться как достоинством, так и недостатком в зависимости от цели кластеризации.

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

количество кластеров изначально неизвестно и является разным для каждой выборки данных (по пациентам, типам пациентов, типам заболеваний и т.п.), поэтому необходимо определять количество кластеров и распределение ЭКГ по ним;

возможность добавления новых ЭКГ к уже кластеризованным без полного пересчета кластеризации всей выборки, которая не подразумевает использование ранее рассчитанных кластеров, их количество и принадлежность к ним отдельных ЭКГ;

работа в многомерном пространстве признаков;

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

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

По пациенту - выборка ЭКГ одного пациента;

По возрасту - выборка ЭКГ всех пациентов определенного возраста или диапазона возрастов;

По полу - выборка ЭКГ только мужчин или только женщин;

Больные ИБС - пациенты с диагностированной ИБС;

Больные туберкулезом - пациенты с диагностированным туберкулезом;

Спортсмены - пациенты, профессионально занимающиеся спортом.

Типы выборок могу пересекаться друг с другом (например, женщины от 25 до 35 лет). Все указанные выборки определены в 400-мерном пространстве признаков.



Рис. 2 - Алгоритм кластеризации ЭКГ



Рис. 3 - Амплитудный спектр Фурье ЭКГ (синяя кривая) и его верхняя огибающая (зеленая кривая)

Таблица 1 - Характеристики, достоинства и недостатки методов кластеризации

	Временная сложность	Входные параметры	Достоинства	Недостатки
Ланса-Уильямса	O(n3)	Функция вычисления расстояния d	Возможность применить различные методы вычисления расстояния между кластерами	Зависимость от метода вычисления расстояний
Модифицированный метод выделения связных компонент	O(3nlog n)	Максимальное расстояние между элементами кластера R	Возможность добавления новых элементов к уже кластеризованным без полного пересчета кластеризации	Недостаточная точность
Выделение связных компонент	Зависит от реализации		Возможность модернизации на основе теории графов	Плохие результаты при узких перемычках между кластерами или разреженном фоне
КНП	O(n2 log n)	Количество кластеров k
EM-алгоритм	O(nkl), l - количество итераций		Устойчивость к выбросам	Необходимо задавать число кластеров, зависимость от начального выбор центров масс
k-средних
c-средних			Вычисляется вероятность принадлежности элемента к кластеру*
Нейронные сети	Зависит от числа нейронов (и типов нейронов) и итераций обучения	Количество нейронов в различных слоях	Эффективная параллелизация	Долгое время обучения
	Временная сложность	Входные параметры	Достоинства	Недостатки
Нейронные сети	Зависит от числа нейронов (и типов нейронов) и итераций обучения	Количество нейронов в различных слоях	Эффективная параллелизация	Долгое время обучения
Генетические	O(nl), l - количество итераций	-	Поиск глобального оптимума	Отсутствует учет контекста
DBSCAN	O(n2)	Максимальный радиус для вычисления соседних элементов е, минимальное количество элементов для создания области mP	Устойчивость к выбросам, возможность строить кластеры различной формы, оптимизация для работы с базами данных	Зависимость от метода вычисления расстояний, чувствительность к плотности
			Вычисляется вероятность принадлежности элемента к кластеру*
OPTICS			Устойчивость к выбросам, возможность строить кластеры различной формы, оптимизация для работы с базами данных	Зависимость от метода вычисления расстояний
BIRCH	O(n)	-	Работает на ограниченном объеме памяти	Хорошо определяет только кластеры выпуклой формы

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

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

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

Тестирование метрик оценки качества результатов кластеризации производится, в зависимости от источника, на некоторых распространенных алгоритмах кластеризации, таких как k-средних, DBSCAN и тому подобные[16, 19].Различие в методах оценки, используемых в разных индексах, обуславливает то, что не все метрики дают одинаково качественный результат для любого алгоритма или типа алгоритма кластеризации. Также различные метрики обладают разной точностью оценки[15].

Исходя из описанных особенностей метрик оценки качества результатов кластеризациии их применения, а также из того, что:

используемый метод выявления связных компонент модифицирован для обработки ЭКГ;

тестирование метрик оценки качества результатов кластеризации на основе результатов кластеризации ЭКГ, полученных с помощью модифицированного метода выявления связных компонент, никем ранее не производилось;

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

1.3 Постановка задачи на разработку системы

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

прием данных из базы данных (БД):

данные ПКИ;

набор кластеров ЭКГ;

текущие настройки алгоритма кластеризации;

вычисление оценки качества результатов кластеризации ЭКГ с помощью метрики;

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

возможность выгрузки вычисленных оценок качества результатов кластеризации в БД.

Требования к надежности системы:

Система должна обеспечивать сохранность входных данных, поступающих из ПКИ;

В системе должен быть реализован механизм контроля доступа к данным;

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

Система должна исполняться на программной платформе Node.js 8 и выше, а также быть совместимой с системой управления БД(СУБД)PostgreSQL 10 и выше.



2. Теоретическое решение задачи

2.1 Анализ метрик оценки качества результатов кластеризации

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

В случае применения модернизированного метода выявления связных компонент к данным в виде ЭКГ необходимо рассчитывать качество результатов кластеризации на основе двух типов метрик - внутренних и относительных. Это обусловлено следующим:

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

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

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

вычислительная сложность метрики. Необходимо минимизировать это значение с целью максимизации скорости работы системы оценки качества результатов кластеризации ЭКГ;

точность результатов метрики;

свойства метрик. Например, ограниченная область применения. Примерами таких метрик могут служить среднеквадратичное стандартное отклонение (Root-mean-squarestand arddeviation, RMSSTD)или улучшенная Г статистика Хьюберта (ModifiedHubert Г Statistic, Г). В первом случае метрика предназначена исключительно для иерархических алгоритмов, а во втором для работы с малыми объемами данных[15];

учет характеристик качества (степени готовности данных к дальнейшей обработке) результатов кластеризации:

среднего внутрикластерного расстояния каждого кластера и суммы этих расстояний;

среднего межкластерного расстояния каждой пары кластеров и сумма этих расстояний;

наличие типов выборок ЭКГ;

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

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

К метрикам внутреннего и относительного типов можно отнести следующие:

Улучшенная Г статистика Хьюберта[21]:



где,N-количество элементов выборки, D - матрица, содержащая расстояния между указанными элементами выборки, а DV-матрица, содержащая расстояние между центрами кластеров, к которым принадлежат эти элементы. Чем больше значение Г, тем лучше результаты кластеризации;

Индекс Данна(Dunn index) [15]:

где с - количество кластеров в выборке, d(ci, cj) -дистанция между кластерами ci и cj, рассчитываемая тем или иным способом. Диаметр кластера C также рассчитывается разными способами, например:

Также существуют различные улучшенные варианты метода, где для измерения расстояния между кластерами используются относительный граф ближайших соседей, минимальное остовное дерево или граф Габриэля. Чем больше значение D, тем лучше результаты кластеризации;

Индекс Дэвиса-Болдина (Davies-Bouldinindex, DB) [17]:

где nc- количество кластеров в выборке, мера схожести между двумя кластерами:



Rij должен отвечать следующим требованиям:

Rij ? 0;

Rij = Rjij

Еслиsi = 0 иsj = 0, тогдаRij = 0;

Еслиsj>skиdij = dik, тогдаRij>Rik

Если sj = skиdij<dik, тогдаRij>Rik.

si - мераразброса кластераi, dij- мера различия между кластерами iи j. Обе эти меры могут рассчитываться различными способами, а сам индекс, также как и индекс Данна, имеет модификации, базирующиеся на построении относительного графа ближайших соседей, минимального остовного дерева и графа Габриэля. Сами авторы предлагают следующую формулу для Rij:.Чем меньше значение DB, тем лучше результаты кластеризации;

Семейство метрик, применяющихся для иерархических методов кластеризации на каждом их шагу - RMSSTD, полу-частичный R-квадрат (Semi-partial R-squared), R-квадрат(R-squared, RS) и расстояние между двумя кластерами (Distance between two clusters) [15].Из-за ориентированности метрик на иерархические методы кластеризации, их применение к модифицированному методу выявления связных компонент нецелесообразно;

Индекс SD [22]:

гдеб= Dis(cmax) - весовой коэффициент (cmax - максимальное количество кластеров, подаваемых на вход), вводимый при проверке нескольких выборок кластеров на количество кластеров в них с целью сбалансировать Scatи Dis, c- количество кластеров. Внутрикластерная дисперсия:

Где дисперсия выборки Х для p-го измерения

дисперсия i-го кластера выборки

центр кластера

ci- i-й кластер, n - количество элементов в выборке (ni - в i-ом кластере). Общая отделимость кластеров:



Где максимальное расстояние между центрами кластеров

минимальное расстояние между центрами кластеров

Чем меньше значение SD, тем лучше результаты кластеризации;

Индекс S_Dbw[23]:

где, c- количество кластеров. Внутрикластерная дисперсия:

Где дисперсия выборки Х для p-го измерения

дисперсия i-го кластера выборки



центр кластера

ci - i-й кластер, n - количество элементов в выборке (ni - в i-ом кластере). Плотность между кластерами:

Где vi и vj - центры соответствующих кластеров, uij-средняя точка линии между центрами кластеров vi и vj,

Чем меньше значение S_Dbw, тем лучше результаты кластеризации.

Индекс Калински-Харабаза (Calinski-Harabaszindex, CH)[24]:



Где k - количество кластеров,, - средний внутригрупповой квадрат расстояний,- средний внутригрупповой квадрат расстояний, средневзвешенная разница между общим и внутригрупповым средним квадратом расстояний

где N - количество элементов выборки, M-количество кластеров в выборке, сумма квадратов в кластере (СКВ, sum-of-squareswithin (SSW)cluster)

- центр масскластера, к которому принадлежит элементxi. Лучшая кластеризация характеризуется максимальным значением (CHM+1-CHM) - (CHM-CHM-1). Индекс не может быть применен в работе, так как подходит только для алгоритмов кластеризации, где количество кластеров является входным параметром;

Сю-индекс (Xu-index) [19]:



Где D-размерность пространства, N - количество элементов выборки, M-количество кластеров в выборке, СКВ

- центр масс кластера, к которому принадлежит элементxi.Чем меньше значение Xu, тем лучше результаты кластеризации;

Индекс Кржановски-Лай (Krzanowski-Laiindex, KL) [19]:

где M - количество кластеров в выборке, D - размерность пространства, СКВ

- центр масс кластера, к которому принадлежит элемент xi.Чем меньше значение KL, тем лучше результаты кластеризации;

Индекс Хартигана (Hartigan index, H) [19]:

где M - количество кластеров в выборке, СКВ

- центр масс кластера, к которому принадлежит элементxi, сумма квадратов между кластерами (СКМ, sum-of-squaresbetween (SSB) clusters)

ni-количество элементов i-ом кластере, - центр масс кластераi-го кластера, - среднее значение элементов выборки. Лучшая кластеризация характеризуется минимальным значением (HM+1-HM) - (HM-HM-1). Индекс не может быть применен в работе, так как подходит только для алгоритмов кластеризации, где количество кластеров является входным параметром;

Индекс силуэта(Silhouette index, S) [25]:



где -«силуэт» элемента xj кластера cp, apj-среднее расстояние от xjдо элементов кластера cp, - степень отличия элемента от элементов ближайшего кластера, dqj- расстояние от xj до элементов другого кластера. Чем больше значение SI, тем лучше результаты кластеризации;

WB-индекс [26]:

где M - количество кластеров в выборке, СКВ

- центр масс кластера, к которому принадлежит элемент xi, СКМ

ni-количество элементов i-ом кластере, - центр масс кластераi-го кластера, - среднее значение элементов выборки. Чем меньше значение WB, тем лучше результаты кластеризации;

I индекс [27]:



где K - количество кластеров,, n - количество элементов выборки, zk - центр k-го кластера. Чем больше значение I, тем лучше результаты кластеризации;

CS мера [28]:

Где d - функция вычисления расстояния, c - число кластеров, Ai-элементы i-го кластера, vi-центр i-го кластера, xi-элемент i-го кластера. Чем меньше значение CS, тем лучше результаты кластеризации;

PS мера [29]:

где с - число кластеров, ni-i-ый элемент выборки, dmin-минимальное Евклидово расстояние между центрами кластеров, vi-центр i-го кластера, xj-i-ый элемент выборки, , -Евклидово расстояние между xj и центром кластера c, расстояние симметрии



Чем меньше значение PS, тем лучше результаты кластеризации;

Score Function [30]:

где расстояние между кластерами

расстояние внутри кластера

k- количество кластеров, zi-центр i-го кластера, ztot-центр всех кластеров, ni-размер i-го кластера, n-количество элементов выборки, x - элементы выборки. Чем больше значение SF, тем лучше результаты кластеризации;

Индекс CDbw [31]:



гдеSC = Sep(C) * Compactness(C)-разделение по компактности, связность кластера -

компактность кластера -

относительная плотность внутри кластера -

мощность точки -

изменение плотности кластера -

С - кластер,- изменяющийся фактор сжатия (авторы рекомендуют диапазон [0.1, 0.8] с шагом 0.1),r-количество точек-представителей кластера (авторы рекомендуют r? 10), c-количество кластеров, vij-центргипер-сферы,

d - функция расстояния между кластерами, stdev-стандартное отклонение рассматриваемых кластеров, отделимость кластеров

межкластерная плотность -

множество ближайших представителей для расчета плотности и отделимости кластеров -



обозначает, что представитель vik является ближайшим представителем кластера ciк vjl. Чем больше значение СВbw, тем лучше результаты кластеризации;

Дисперсия ближайшего соседа (Variance of the Nearest Neighbor Distance, VNND) [32], в которой измеряется лишь компактность кластера, что не позволяет в полной мере оценить качество результатов кластеризации;

C индекс [33]:

где Smin - сумма Nw наименьших расстояний между всеми парами элементов выборки, Smax - сумма Nw наибольших расстояний между всеми парами элементов выборки, общее количеcтво пар наблюдений, принадлежащих одному кластеру -

q - количество кластеров, nk-количество элементов кластера Ck. Чем меньше значение С, тем лучше результаты кластеризации;

Индекс Ратковски-Ланса (Ratkowsky-Lance index, RL) [33]:



где q - количество кластеров,

сумма квадратов между кластерами -

метрика кластеризация метод тестирование

nk-количество элементов кластера Ck, ck-центр масс кластера Ck, -центр матрицы n * p, n-количество элементов выборки, p- количество измерений выборки, общая сумма квадратов -

xi - p-мерный вектор наблюдений i-го объекта в кластере Ck. Чем больше значение RL, тем лучше результаты кластеризации;

Индекс Рэй-Тури (Ray-Turiindex, RT) [34]:



где N - количество элементов выборки, K-количество кластеров, x-элемент кластера Ci, zi-центр кластера Ci. Чем меньше значение RT, тем лучше результаты кластеризации;

Индекс TraceW (TrW) [33]:

где матрица дисперсии внутри группы для данных, сгруппированных в q кластеров -

xi - p-мерный вектор наблюдений i-го объекта в кластере Ck, ck-центр кластера Ck. Лучшая кластеризация характеризуется максимальным значением (TrWq+1-TrWq) - (TrWq-TrWq-1). Индекс не может быть применен в работе, так какподходит только для алгоритмов кластеризации, где количество кластеров является входным параметром;

Индекс Веммерта-Гансарски (Wemmert-Ganзarskiindex, WG) [35]:

где N- количество элементов выборки, K-количество кластеров, nk - количество элементов кластера Ck, Ik-множество индексов наблюдений, принадлежащих кластеру Ck,



M - элемент кластера Ck, G-центр масс кластера Ck. Чем больше значение WG, тем лучше результаты кластеризации.

Индекс Марриот (Marriot index, M) [33]:

где q - количество кластеров, матрица дисперсии внутри группы для данных, сгруппированных в q кластеров -

xi - p-мерный вектор наблюдений i-го объекта в кластере Ck, ck-центр кластера Ck. Лучшая кластеризация характеризуется максимальным значением (Mq+1-Mq) - (Mq-Mq-1). Индекс не может быть применен в работе, так как подходит только для алгоритмов кластеризации, где количество кластеров является входным параметром;

Индекс Trace CovW (TrCW) [33]:

где матрица дисперсии внутри группы для данных, сгруппированных в q кластеров -



xi - p-мерный вектор наблюдений i-го объекта в кластере Ck, ck-центр кластера Ck. Лучшая кластеризация характеризуется минимальным значением (TrCWq+1-TrCWq) - (TrCWq-TrCWq-1). Индекс не может быть применен в работе, так как подходит только для алгоритмов кластеризации, где количество кластеров является входным параметром;

Индекс Скотта-Саймонса (Scott-Symonsindex, SS) [36]:

где n-количество элементов выборки, T - матрица рассеяния элементов выборки, W- сумма Tдля каждого кластера. Лучшая кластеризация характеризуется максимальным значением SSq-SSq-1, где q-количество кластеров. Индекс не может быть применен в работе, так как подходит только для алгоритмов кластеризации, где количество кластеров является входным параметром;

ИндексTraceW-1B (TrW-1B) [33]:

где W- сумма матриц рассеяния для каждого кластера, B - матрица рассеяния центров кластеров. Лучшая кластеризация характеризуется максимальным значением TrW-1Bq-TrW-1Bq-1, где q-количество кластеров. Индекс не может быть применен в работе, так как подходит только для алгоритмов кластеризации, где количество кластеров является входным параметром;

Индекс [36]:

Где T - матрица рассеяния элементов выборки, W- сумма T для каждого кластера. Лучшая кластеризация характеризуется минимальным значением (q+1-q) - (q-q-1), где q-количество кластеров. Индекс не может быть применен в работе, так как подходит только для алгоритмов кластеризации, где количество кластеров является входным параметром;

Индекс kCE [37]-применяется только к итерационным алгоритмам перемещения, таким как K-средних, и не может применяться для оценки качества результатов кластеризации, полученных с помощью модифицированного метода выявления связных компонент.

Индекс Се-Бени (Xie-Beniindex, XB) [38] - индекс позволяет оценить результаты нечеткой кластеризации, и поэтому не может быть применен в данной работе;

Байесовский информационный критерий (Bayesianinformation criterion, BIC) [19]:

где L -log функции правдоподобия, N-количество элементов кластера, M - количество кластеров, D-размерность данных, ni - размер i-го кластера. Также существуют модернизации метода, такие как угловой BIC (Angel-basedBIC) иDiffBIC. Чем меньше значение BIC, тем лучше результаты кластеризации.

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

По таблице видно, что лучшими метриками являются SD, WB, S, CDbw, RL, WG, CH иS_Dbw, которая признана лучшей в трех из восьми исследований. Учитывая то, что результаты исследований, где лучшими признаны метрики SD, WB иS, перекрываются другими, более масштабными (с большим количеством тестируемых метрик и/или выборок данных) исследованиям, имеются основания также вычеркнуть их из списка метрик для тестирования.

Таблица 2 - Сравнительные результаты тестирования метрик оценки качества результатов кластеризации

Источник	Типы тестируемых данных	Тестируемые алгоритмы	Тестируемые метрики	Лучшие метрики
[17]	4 синтетических (3 двумерных и 1 шестимерный)	K-средних, CURE [39]	RS, RMSSTD, DB, SD, S_Dbw	S_Dbw
[16]	4 синтетических двумерных и 1 реальный (часть сети дорог Греции)	K-средних, CURE	RS, RMSSTD, DB, SD	SD
[19]	Обладающий выраженной формой, Гауссово-распределенный и реальный (изображения)	Метод случайного обмена с повторениями [19]	BH, CH, H, KL, Xu, WB, Dunn, DB, S, XB, BIC, ABIC, DiffBIC	WB, S
Источник	Типы тестируемых данных	Тестируемые алгоритмы	Тестируемые метрики	Лучшие метрики
[20]	Хорошо отделенный, хорошо отделенный с шумом, с различной плотностью, с подкластерами, с перекошенными распределениями (все двумерные)	K-средних	RMSSTD, RS, Г, CH, I, Dunn, S, DB, SD, S_Dbw, XB	S_Dbw
[15]	Гауссово-распределенные, концентрической формы, IRIS	K-средних, DBSCAN	Dunn, DB, SD, S_Dbw, S, CS, VNND, Score, I, CDbw	СВbw
[36]	162 синтетических	k-средних и метод сложного конкурентного обучения [40]	RL, Xu, SS, CH, C, DB, TrW-1B, M, TrW, NLL, SSI, H, TrCW, , BH	RL
[41]	7 синтетических, 6 реальных	K-медиан, K-средних, K-пространственных медиан	kCE, WB, CH, DB, I, RT, WG	WG
[42]	2 десятимерных из 30000 объектов с 5 кластерами разного размера и плотности	CluStream [43] (K-средних для макро-кластеров),DenStream [44]	RMSSTD, RS, Г, CH, I, Dunn, S, DB, XB, SD, S_Dbw	CH, S_Dbw

Результатов кластеризации ЭКГ модифицированным методом выявления связных компонент. Искомая метрика должна позволять точно оценивать качество результатов кластеризации для всех описанных ранее типов выборок и иметь наименьшую вычислительную сложность.

2.2 Тестирование метрик оценки качества результатов кластеризации

Тестирование метрик оценки качества кластеризации проводилось согласно методике, описанной ниже.

На языке программирования JavaScript (JS) были реализованы метрики RL, WG, CH,S_DbwиCDbw. CDbwбыл реализован в двух вариантах, поскольку описание параметра stdev(стандартное отклонение рассматриваемых кластеров) можно интерпретировать различным образом:

значение stdev рассчитывается один раз для всех кластеров;

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

С помощью реализованных метрик были рассчитаны оценки качества результатов кластеризации ЭКГ при rmax = {0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1, 1.1, 1.2, 1.5, 2, 3} для следующих выборок ЭКГ:

по 14 пациентам:

7330- мужчина 23 лет;

7564 - курящий мужчина 57 лет;

4166 - мужчина 68 лет;

1215 -мужчина 66 лет;

7561 - женщина 58 лет;

1408 -мужчина 34 лет;

1023 -женщина 37 лет;

2395 -курящий мужчина 31 года;

6131 -женщина 25 лет;

1382 - курящий мужчина 72 лет с электрокардиостимулятором;

4199 - мужчина 44 лет;

6061 -мужчина 74 летс сахарным диабетом 2-го типа;

4106 - курящиймужчина31года;

2506 - мужчина 73 лет;

для всех спортсменов, представленных в БД системы обработки и анализа ЭКГ (allathletes);

для всех пациентов, больных туберкулезом, представленных в БД системы обработки и анализа ЭКГ (tb+);

для всех пациентов, больных ИБС, представленных в БД системы обработки и анализа ЭКГ (ibs+);

для всех пациентов возрастом от 14 до 25 лет, представленных в БД системы обработки и анализа ЭКГ (all 14-25);

для всех пациентов женского пола возрастом от 50 до 65 лет, представленных в БД системы обработки и анализа ЭКГ (all ж 50-65).

Значения rmax более 3 проверки не подлежали, поскольку было заранее известно, что при таких значениях результатом кластеризации будет один значимый кластер, включающий подавляющее большинство ЭКГ, и незначительное количество кластеров с малым количеством ЭКГ в них, по отношению к общему количеству ЭКГ.

Результаты тестирования метрик представлены в табл. 3. В ней для каждой метрики приведено значение rmax, которое является лучшим по оценке используемой метрики для 3 интервалов значений rmax- [0, 3], [0, 1.2] и [0.2, 1].В табл. 3 используются следующие цветовые обозначения:

Красная ячейка - плохой результат для данного интервала значений выборки;

Желтая ячейка - результат чуть хуже лучшего для данного интервала значений выборки;

Светло-зеленая ячейка - лучший результат для данного интервала значений выборки;

Темно-зеленая ячейка - лучший результат для всех интервалов значений выборки.

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

...