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

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

Результат анализа табл. 3 показывает, что лучшей из четырех метрик является CH, а наибольшее количество оптимальных значений получено при rmax = [0.2,1] - 72%.Но после просмотра реального набора кластеров был сделан вывод, что полученные оптимальные значения rmax не соответствую действительности. Поэтому было решено дополнительно протестировать метрику CH только для кластеров, где количество ЭКГ превышает одну (Calinski-Harabasz with outsingle clusters, CHWOS), поскольку такие кластеры, предположительно, значительно влияют на результат оценки, но незначительно влияют на результат кластеризации ввиду того, что для дальнейшей обработки результатов кластеризации важны только значимые по количеству ЭКГ относительно общего количества ЭКГ кластеры. Также автором была разработана собственная метрика оценки качества результатов кластеризации ЭКГ (NF), который вычисляется следующим образом:

где с - количество кластеров выборки, ni-количество элементов в i-ом кластере, N - количество элементов выборки, d-расстояние между верхней и нижней огибающей формы кластера.

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

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

Количество ЭКГ в выборке, шт.	Идентификатор выборки	Метрика оценки качества результатов кластеризации
		CH	RL	WG	CDbw	CDbw (stdev для всехкластеров)
		Интервалы оценки rmax, б/р
		0 - 3	0 - 1.2	0.2 - 1	0 - 3	0 - 1.2	0.2 - 1	0 - 3	0 - 1.2	0.2 - 1	0 - 3	0 - 1.2	0.2 - 1	0 - 3	0 - 1.2	0.2 - 1
		Лучшие значения rmax, б/р
23	7330	0.1	0.1	0.7	1.5	1	1	0	0	0.2	1.5, 2	1.2	0.9	2	1.2	0.8
173	4166	1.1	1.1	1	3	1.2	1	0	0	0.9, 1	0.9 - 3	0.9 - 1.2	0.9, 1	0.9 - 3	0.9 - 1.2	0.9, 1
176	1215	0.1	0.1	0.2	1.5	1.2	1	0	0	0.2	1.5	0.8, 0.9	0.8, 0.9	1	1	1
216	7561	0.5	0.5	0.5	3	1.2	0.8	0	0	0.8	2	1.2	0.9	2, 3	1.2	0.9
280	1408	2	1.2	1	2, 3	1.2	1	0	0	0.2	1.2	1.2	0.7	1.5, 2, 3	0.8, 09	0.8, 0.9
407	1023	3	1.2	0.9	3	1.2	1	0	0	0.8	0.9 - 1.1	0.9 - 1.1	0.9, 1	3	1.2	0.9, 1
420	2395	0.1	0.1	0.2	3	1.2	1	0	0	1	3	1.2	1	3	1.2	1
452	6131	0.9	0.9	0.9	3	1.2	0.9	0	0	0.2	3	1.1, 1.2	1	3	1.1, 1.2	1
519	1382	0.1	0.1	0.2	1.5	1.2	0.9	0	0	0.2	3	1.1	1	3	1.2	1
869	allathletes	0.1	0.1	0.2	3	1.2	1	0	0	0.2	3	1.2	0.9	3	1.2	1
838	4199	3	1.2	0.2	3	1.2	0.9	0	0	0.9	1.5	1.2	0.8	3	1.2	0.8
1086	6061	1.2	1.2	0.8	3	1.2	0.9	0	0	0.2	2	1.2	1	3	1	1
1257	tb+	0.1	0.1	0.8	3	1.1	1	0	0	0.2	3	1.2	1	3	1.1	1
1338	ibs+	0.1	0.1	0.2	3	1.2	1	0	0	0.2	3	1.2	1	3	1.2	1
1780	4106	1.1	1.1	0.8	3	1.2	1	0	0	1	3	1.2	1	3	0.9	0.9
2998	2506	2	1.2	0.9	3	1.2	1	0	0	0.2	3	1.2	1	3	1.1	1
3256	all 14-25	0.1	0.1	0.2	3	1.1	1	0.1	0.1	0.2	3	1.1	1	3	1.2	1
6100	all ж 50-65	0.1	0.1	0.2	3	1.2	1	0.1	0.1	0.2	3	1.2	1	3	1.2	1
Лучшие по категориям, б/р	3	4	13	2	5	6	0	0	7	3	3	5	2	3	5
Лучшие для метода, б/р	13	6	7	5	5
Правильные определенныедля лучших для метода, %	0,722222222	0,333333333	0,388888889	0,277777778

Таблица 4 - Результаты тестирования метрик CHWOS и NF, и их сравнение с CH

Количество ЭКГ в выборке, шт.	Идентификатор выборки	Метрика оценки качества результатов кластеризации
		CH	CH WOS	NF
		Интервалы оценки rmax, б/р
		0 - 3	0 - 1.2	0.2 - 1	0 - 3	0 - 1.2	0.2 - 1	0 - 3	0 - 1.2	0.2 - 1
		Лучшие значения rmax, б/р
23	7330	0.1	0.1	0.7	0.4	0.4	0.4	1.5, 2	1.1, 1.2	0.9
173	4166	1.1	1.1	1	0.4	0.4	0.4	0.9 - 3	0.9 - 1.2	0.9, 1
176	1215	0.1	0.1	0.2	0.1	0.1	0.2	1.5	1, 1.1	1
216	7561	0.5	0.5	0.5	0.6	0.6	0.6	2, 3	1.2	0.9
280	1408	2	1.2	1	1.1	1.1	1	1.5, 2, 3	1.1	0.6
407	1023	3	1.2	0.9	0.2	0.2	0.2	3	1.2	1
420	2395	0.1	0.1	0.2	0.1	0.1	0.2	3	1.2	1
452	6131	0.9	0.9	0.9	0.3	0.3	0.3	3	1.1, 1.2	1
519	1382	0.1	0.1	0.2	0.1	0.1	0.8	3	1.1	1
869	allathletes	0.1	0.1	0.2	1.5	0.1	0.7	3	1	1
838	4199	3	1.2	0.2	0.3	0.3	0.3	3	1.2	1
1086	6061	1.2	1.2	0.8	1.2	1.2	0.8	3	1	1
1257	tb+	0.1	0.1	0.8	0.1	0.1	0.8	3	1.2	0.9
1338	ibs+	0.1	0.1	0.2	0.1	0.1	0.2	3	1.2	0.9
1780	4106	1.1	1.1	0.8	1.1	1.1	0.8	3	1.2	1
2998	2506	2	1.2	0.9	2	0.9	0.9	3	1.2	1
3256	all 14-25	0.1	0.1	0.2	0.1	0.1	1	3	1.2	1
6100	all ж 50-65	0.1	0.1	0.2	0.1	0.1	0.5	3	1.1	1
Лучшие по категориям, б/р	1	2	10	6.5	7,5	13,5	0	1	0
Лучшие для метода, б/р	10	13,5	1
Правильные определенные для лучших для метода, %	0,555555556	0,75	0,055555556



Оказалась столь же малоэффективна, как RL, WGи CDbw. Все результаты были проверены и подтверждены экспертом.

В связи с этим метрика CHWOS будет использоваться в качестве основы для «Системы для оценки качества кластеризации электрокардиограмм».

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



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

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

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

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

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

в требованиях к системе указана необходимость ее исполнения на программной платформе Node.js 8 и выше. Данная платформа основана на движке V8, который интерпретирует JS;

система обработки и анализа ЭКГ и ПКИ полностью написаны на JS. Поэтому для максимальной производительности и полной совместимости с ними система оценки качества кластеризации ЭКГ также должна быть написана на JS.

В качестве среды разработки системы выбрана среда Node-RED. Этот инструмент разработки с веб-интерфейсом, основанный на концепции визуального программирования. Основными элементами Node-RED являются узлы (nodes), который объединяются в потоки (flows). Node-RED обладает набором встроенных узлов, а также библиотекой, насчитывающей более 3250 потоков и узлов, разработанных открытым сообществом разработчиков. Узлы обладают возможностью гибкой настройки и широкой функциональностью - от простейшего вывода сообщений для отладки или сохранения данных в файлы различного формата, до взаимодействия с большинством современных СУБД и полноценного исполнения программного кода на многих высокоуровневых языках программирования (например, JSилиPython).Также Node-RED имеет такие необходимые для реализации системы возможности, как:

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

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

ветвление, зацикливание и соединение потоков;

наличие системы проектов и контроля их версий.

Это позволяет с легкостью разрабатывать систему, строя схему ее функционирования прямо в ходе разработки или выстраивая схему в соответствии с заранее утвержденной структурой. Все вышеперечисленное, нативная поддержка JS, возможность работы с СУБД PostgreSQL10 и выше, а также реализация ПКИ в Node-RED, являются основанием для выбора Node-RED в качестве основного средства для разработки системы.

Для обращения к PostgreSQL используется язык программирования Structured Query Language(SQL), так как это основной единственно возможный язык для обращения к указанной СУБД.

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

Разработанная система позволяет автоматизировать процесс оценки качества результатов кластеризации ЭКГ для нахождения оптимального значения входного параметра алгоритма кластеризации ЭКГ - максимального расстояния между элементами одного кластера (rmax).Поскольку прямой перебор значений rmax малоэффективен и требует значительных временных и аппаратных ресурсов, система реализует значительно более эффективный метод золотого сечения- одномерный метод оптимизации, который позволяет осуществить поиск точки экстремума функции на заданном отрезке [45]. Так как выбранная метрика оценки качества результатов кластеризации (CHWOS) указывает на лучшую кластеризацию при своем максимальном значении, в системе реализована версия метода золотого сечения для решения задачи максимизации функции f(rmax), описанной формулой (2).

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

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

Вычисляется оценка качества результатов кластеризации (полученного набора кластеров) с помощью метрики CHWOS, обоснование использования которой приведено в п. 2.2 «Тестирование метрик оценки качества результатов кластеризации» данной работы.

Рис. 4 - Процесс оценки качества результатов кластеризации выборки ЭКГ



Указанный процесс является основой системы (вычисленная оценка передается в алгоритм золотого сечения), работа которой описана с помощью Unified Modeling Language (UML) диаграммы последовательности (рис. 5).



Рис. 5 - Диаграмма последовательности процесса работы системы

На диаграмме определены 3 объекта:

сама подсистема оценки качества кластеризации электрокардиограмм (ПОК);

ПКИ;

СУБД Postgre SQL.

А также актант - оператор, работающий с системой.

При запуске работы системы оператор указывает выборку, для которой необходимо вычислить оптимальное значение rmax, после чего фокус управления передается ПОК, в которой реализован метод золотого сечения. В ПОК задан отрезок значений rmax от a = 0 до b = 1, на котором необходимо найти максимум функции. Этот отрезок делится на три равные части точками и , где - пропорция золотого сечения. ПОК посылает запрос в ПКИ для проверки наличия результатов кластеризации рассматриваемой метрики при rmax = x1и rmax = x2(сообщение 1.1 на рис. 5, далее - 1.1). Та, в свою очередь, посылает запрос в СУБД для проверки кластеризации (1.1.1) и после получения ответа (1.1.2) в зависимости от его содержания выполняет одно из двух действий:

если отсутствуют результаты кластеризации для rmax = x1и/или rmax = x2, то ПКИ запрашивает выборку из СУБД (1.1.3, 1.1.4), проводит ее кластеризацию при rmax = x1и/или rmax = x2(1.1.5) и загружает полученные результаты (y1для rmax = x1 и y2для rmax = x2) в СУБД (1.1.6, 1.1.7). После этого ПКИ отправляет сообщение о наличии результатов кластеризации ПОК (1.2);

если результаты кластеризации для обоих значений rmax присутствуют, то ПКИ сразу отправляет сообщение о них ПОК (1.2).

После этого ПОК загружает результаты кластеризации для rmax = x1и rmax = x2 из СУБД (1.3, 1.4), проводит их оценку с помощью метрики CHWOS(1.5) и загружает результаты в СУБД (1.6).

Далеев цикле происходит сужение интервала поиска оптимального значения rmax, пока , где е = 0.1 - заданная точность:

если , то часть отрезка поиска слева от x1отбрасываетсяи происходит присваивание a = x1и (1.7). После чего происходит проверка наличия результатов кластеризации и оценка их качества аналогичная сообщениям 1.1 - 1.6 при rmax = x2(1.8 - 1.13);

если , то часть отрезка поиска справа от x2отбрасываетсяи происходит присваивание b = x2и (1.7). После чего происходит проверка наличия результатов кластеризации и оценка их качества, аналогичная сообщениям 1.1 - 1.6 при rmax = x1(1.8 - 1.13);

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

После того как выполнится условие, выполняется одно из двух присвоений-если , то a = x1, иначе b = x2, и вычисляется оптимальное значение(1.14). После чего происходит проверка наличия результатов кластеризации и оценка их качества, аналогичная сообщениям 1.8 - 1.13 при оптимальном rmax (1.15 - 1.20).

После этого система запрашивает оценки качества для rmax = a иrmax = b из СУБД (1.20, 1.21) и выбирает лучшую оценку из них и (в данном случае метод золотого сечения модернизирован для получения оптимальной оценки без дополнительных вычислений, так как при оценка может быть хуже, чем при rmax = a иrmax = b). Полученная оценка является лучшей возвращается оператору (2).

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

«Система для оценки качества результатов кластеризации электрокардиограмм» представляет из себя поток Node-RED (рис. 6), который состоит из узлов:

узел запуска системы (inject) синего цвета;

узел настроек системы (settings), где задается идентификатор выборки, заданы значения интервала поиска rmax и рассчитываются первый значения x1и x2;

узла подпотока двусторонней связи с ПКИ (clustering);

узла подпотока оценки качества результатов кластеризации ЭКГ (quality), выполняющий оценку качества кластеризации;

узла метода золотого сечения, где выполняется сравнение y1и y2, проверка значения е, вычисление новых значений x1и x2и направление работы системы (golden-section):

если , искать оптимальное значение rmax в цикле по двум предыдущим узлам;

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

узлы обратной связи серого цвета (linkinи linkout);

узла оповещения о завершении работы системы (donemsg);

узлы отладки (clumsg, qmsg, nextmsg), которые отключены во время эксплуатации системы.

Рис. 6 - Node-RED поток «Системы для оценки качества результатов кластеризации электрокардиограмм»

Подпоток оценки качества результатов кластеризации ЭКГ (quality) представлен на рис. 7. и состоит из следующих узлов:

входной узел (input);

узел настроек (settings), который обрабатывает полученные идентификатор выборки и значения rmax;

узел с текстом запроса в БД для получения кластеров, полученных в результате кластеризации(cardiograms);

узел обращения в БД голубого цвета (postgres);

узел обработки полученных кластеров с целью выявления кардиограмм, содержащихся в них, для их дальнейшего получения из БД (clusters);

узел с текстом запроса в БД для получения кардиограмм из кластеров (clusteringresults), который посылается в БД в следующем после перехода узле;

узлы перехода серого цвета (linkinи linkout);

узел соединения полученных от БД сообщений с результатами кластеризации (mergeclusters);

узел расчета оценки качества результатов кластеризации с помощью метрики CHWOS(Calinski-Harabasz);

узел компоновки результатов расчета оценки (results). В зависимости от того, промежуточное или финальное значение rmax рассчитывается, после этого узла работа осуществляется одним из двух способов:

если рассчитывается промежуточное значение, то данные отсылаются в:

узел с текстом запроса для занесения полученной оценки в БД (score), который посылается в БД в следующем узле;

выходной узел (output 1);

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

узел с текстом запроса для получения из БД оценок качества результатов кластеризации при rmax = aи rmax = b (geta&b), который посылается в БД в следующем узле;

узел производящий выбор лучшего результата кластеризации из rmax = a, rmax = bи (chose);

после чего обработка происходит в соответствии с пунктом а).

узел для отображения статуса подпотока из других узлов (status);

узел для вывода сообщений об ошибке из подпотока из других узлов (catch).



Рис. 7 - Node-RED подпоток оценки качества результатов кластеризации ЭКГ

Исходный код системы приведен в Приложении Б.

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

Разработанная система была протестирована на приведенных в п. 2.2 «Тестирование метрик оценки качества результатов кластеризации» данной работы выборках ЭКГ. Результаты, полученные с помощью системы, сравнивались с лучшими результатами, полученными в результате тестирования метрики CHWOS, и приведены в табл. 5. В табл. 5 используются следующие цветовые обозначения:

Красная ячейка - результат хуже эталона (0 баллов);

Желтая ячейка - результат незначительно хуже эталона (0.9 балла);

Зеленая ячейка - результат аналогичен или лучше эталона (1 балл);

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

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

Описание применения, руководство оператора, а также программа и методика испытаний системы приведены в Приложении В, Приложении Г и Приложении Д, соответственно.

Таблица 5 - Результаты тестирования «Системы для оценки качества кластеризации электрокардиограмм»

Количество ЭКГ в выборке, шт	Идентификатор выборки	Лучшее значение для выборки, б/р	Результаты работы системы, б/р
23	7330	0.4	0.4
173	4166	0.4	0.55
176	1215	0.2	0.6
216	7561	0.6	0.6
280	1408	1	0.85
407	1023	0.2	0.25
420	2395	0.2	0.5
452	6131	0.3	0.9
519	1382	0.8	0.75
869	allathletes	0.7	0.7
838	4199	0.3	0.3
1086	6061	0.8	0.7
1257	tb+	0.8	0.8
1338	ibs+	0.2	0.55
1780	4106	0.8	0.85
2998	2506	0.9	0.9
3256	all 14-25	1	0.75
6100	all ж 50-65	0.5	0.55



Заключение

В результате данной выпускной квалификационной работы:

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

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

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

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

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

прием данных из БД;

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

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

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

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

Все поставленные задачи выполнены полностью и в срок.



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

1. Шмид А. В., Позин Б. А., Галахов И. В., Агейкин М. А., Александров Д. О., Касимов М. Р., Клемашев Н. И., Ежов Г. А. Новые методы работы с большими данными: победные стратегии управления в бизнес-аналитике:Научно-практический сборник. Под редакцией д.т.н., проф. А. В. Шмида. - М.: ПАЛЬМИР, 2016. -528 с.: илл.

2. Машинное обучение для людей[Электронный ресурс]. URL: https://vas3k.ru/blog/machine_learning/ (дата обращения: 13.02.2019).

3. MoodyG.B. RRIntervals, HeartRate, andHRVHowto [Электронныйресурс].URL: https://www.physionet.org/tutorials/hrv/ (датаобращения: 08.01.2019).

4. Farnsworth B. Heart Rate Variability - How to Analyze ECG Data [Электронныйресурс]. URL: https://imotions.com/blog/heart-rate-variability/(дата обращения: 13.02.2019).

5. Шмид А. В., Новопашин М. А., Зимина Е. Ю. Кластеризация медицинских больших данных как инструментарий систем поддержки принятия решений в математической кардиологии с использованием облачных технологий // Системный администратор.2018.Т. 188-189,№ 07-08.С. 92-96.

6. Лагутин М. Б. Наглядная математическая статистика: учебное пособие. 2-е изд., испр. - М.: БИНОМ. Лаборатория знаний, 2009. - 472 с.: ил.

7. Часовских А. Обзор алгоритмов кластеризации данных[Электронный ресурс]. URL:https://habr.com/ru/post/101338/(дата обращения: 18.02.2019).

8. Бериков В. С., Лбов Г. С. Современные тенденции в кластерном анализе // Всероссийский конкурсный отбор обзорно-аналитических статей по приоритетному направлению «Информационно-телекоммуникационные системы». 2008. 26 с.

9. Lance G. N., Williams W. T. A general theory of classification sorting strategies. 1. Hierarchical systems // Computer J. 1967. N 9. P. 373-380.

10. Воронцов К. В. Лекции по алгоритмам кластеризации и многомерного шкалирования// МГУ. 2007. 18 с.

11. Котов А., Красильников Н. Кластеризация данных // 2006. 16 с.

12. Ester M., Kriegel H., Sander J., Xu X. A density-based algorithm for discovering clusters in large spatial databases with noise // Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) //EvangelosSimoudis, Jiawei Han, Usama M. Fayyad. AAAI Press, 1996. P. 226-231.

13. Ankerst M., BreunigM., Kriegel H., Sander J. OPTICS: Ordering Points To Identify the Clustering Structure // ACM SIGMOD international conference on Management of data. ACM Press, 1999. P. 49-60

14. Chugunov V., Zhukova L., Kovalchuk I., Kovaleva A. Mathematical Methods of Grouping Data for Making Managerial Solutions in the Tasks of Planning //Actual Problems of System and Software Engineering 2017. Proceedings of the 5th International Conference on Actual Problems of System and Software Engineering Supported by Russian Foundation for Basic Research. Project #17-07-20565 Moscow, Russia, November 14-16, 2017, 408 P. // Ed. by A. R. Cavalli, Alexander Petrenko, Boris Pozin. Vol. 1989. Aachen: CEUR Workshop Proceedings, 2017. P. 333-341.

15. Сивоголовко Е. В. Методы оценки четкой кластеризации // Компьютерные инструменты образования.2011. № 4. С. 14-21.

16. Halkidi M., Batistakis Y., Vazirgiannis M. On Clustering Validation Techniques// Journal of Intelligent Information Systems. 2001.№ 17:2/3. P. 107-145.

17. Halkidi M., Batistakis Y., Vazirgiannis M. Clustering Validity Checking Methods: Part II// ACM Sigmod Record.2002.V.31,I. 3. P. 19-27.

18. Deborah L. J., Baskaran R., Kannan A.A Survey on Internal Validity Measure for ClusterValidation // International Journal of Computer Science & Engineering Survey. 2010. V. 1,N. 2.P. 85-102.

19. ZhaoQ. Cluster Validity inClustering Methods //Publications of the University of Eastern Finland Dissertations in Forestry and Natural Sciences.2012.N. 77. P. 1-77.

20. Liu Y., Li Z., Xiong H., Gao X., Wu J. Understanding of Internal Clustering Validation Measures // IEEE International Conference on Data Mining.2010. P. 911-916.

21. Theodoridis S., Koutroumbas K.Pattern recognition. Second edition // Academic Press, San Diego, CA.2003. 689 p.

22. Halkidi M., Vazirgiannis M., Batistakis Y. Quality Scheme Assessment in the Clustering Process //ZighedD.A., KomorowskiJ., ZytkowJ. (Eds.). PKDD 2000. 2000. P. 265-276.

23. Halkidi M.,Vazirgiannis M. Clustering Validity Assessment: Finding the optimal partitioning of a data set//Proceedings 2001 IEEE International Conference on Data Mining. 2001.P.187-194.

24. Calinski T., Harabasz J. A Dendrite Method for Cluster Analysis// Communications in Statistics. 1974. V.3, I. 1.P. 1-27.c

25. Kaufman L., Rousseeuw P.J.Finding Groups in Data: An Introduction to Cluster Analysis.Hoboken: John Wiley & Sons, Inc., 2005.

26. Zhao Q., Xu M., Frдnti P. Sum-of-Square Based Cluster Validity Index andSignificance Analysis. // Int. Conf. on Adaptiveand Natural Computing Algorithms (ICANNGA'09). 2009. P. 313-322.

27. Maulik U., Bandyopadhyay S. Performance evaluation of some clustering algorithms and validity indices // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2002. V. 24, N. 12.P. 1650-1654.

28. Chou C.H., Su M. C., Lai E. A new cluster validity measure and its application to image compression // Pattern Analysis and Applications. 2004. V. 7. P. 205-220.

29. Chou C. H., Su M. C., Lai E. Symmetry as A new Measure for Cluster Validity // 2nd WSEASInternational Conference of Scientific on Computation and Soft Computing. 2002. P. 209-213.

30. Saitta S., Raphael B., Smith I. F.C.A Bounded Index for Cluster Validity // Machine Learning and Data Mining in Pattern Recognition. 2007. P. 174-187.

31. Halkidi M.,Vazirgiannis M. A Density-based Cluster Validity Approach using Multi-representatives // Pattern Recognition Letters. 2008.V. 29, I. 6. P. 773-786.

32. Kovбcs F.,Ivбncsy R.Cluster Validity Measurement for Arbitrary Shaped Clusters // Proceedings of the 5th WSEAS Int. Conf. on Artificial Intelligence, Knowledge Engineering and Data Bases. 2006.P. 372-377.

33. Charrad M., Ghazzali N., Boiteau V., Niknafs A. NbClust: An R Package for Determining the Relevant Number of Clusters in a Data Set // Journal of Statistical Software. 2014. V. 61, I.6.

34. Ray S., Turi R. H. Determination of Number of Clusters in K-Means Clustering andApplication in Colour Image Segmentation // Proceedings of the 4th International Conference on Advances in Pattern Recognitionand Digital Techniques. 1999.P. 137-143.

35. DesgraupesB. Clustering Indices // 2017. 34 p.

36. Dimitriadou E., Dolnicar S., Weingessel A.An Examination of Indexes for Determining theNumber of Clusters in Binary Data Sets // Psychometrika. 2002. V. 67, I. 1. P137-160.

37. Jauhiainen S.,Kдrkkдinen T. A Simple Cluster Validation Index withMaximal Coverage // ESANN 2017: Proceedings of the 25th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. 2017.P. 293-298.

38. Xie X. L., Beni G. A Validity Measure for Fuzzy Clustering // IEEE Transactions on Pattern Analysis & Machine Intelligence. 1991. V. 13, N. 8. P. 841-847.

39. Guha S., Rastogi R., Shim K. CURE: An Efficient Clustering Algorithm for Large Databases // Information Systems. 2001. V. 26, I. 1. P. 35-58.

40. Fritzke B. Some competitive learning methods // 1997

41. Hдmдlдinen J.,JauhiainenS., Kдrkkдinen T.Comparison of Internal Clustering Validation Indicesfor Prototype-Based Clustering // Algorithms. 2017. V. 10, I. 3. P 105-119.

42. Hassani M.,Seidl T.Using internal evaluation measures to validate the qualityof diverse stream clustering algorithms // Vietnam Journal of Computer Science. 2017. V. 4, I. 3. P. 171-183.

43. Aggarwal C. C., Han J.,Wang J., Yu P.S. A framework for clustering evolving data streams // Proceedings of the 29th international conference on Very large databases. 2003. V. 29. P. 81-92.

44. Cao F., Ester M., Qian W., Zhou A.Density-Based Clustering over an Evolving Data Stream with Noise // Proceedings of the 2006 SIAM International Conference on Data Mining. 2006. P. 328-339.

45. Kiefer J. Sequential minimax search for a maximum // Proceedings of the American Mathematical Society. 1953. V. 4, N. 3. P 502-506.



Приложение A

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

Таблица 6 - Спецификация

Наименование	Примечание
Документация
Система для оценки качества кластеризации
электрокардиограмм
Спецификация
Лист утверждения
Система для оценки качества кластеризации
электрокардиограмм
Текст программы
Система для оценки качества кластеризации
электрокардиограмм
Текст программы
Лист утверждения
Система для оценки качества кластеризации
электрокардиограмм
Описание применения
Система для оценки качества кластеризации
электрокардиограмм
Описание применения
Лист утверждения
Система для оценки качества кластеризации
электрокардиограмм
Руководство оператора
Наименование	Примечание
Система для оценки качества кластеризации
электрокардиограмм
Руководство оператора
Лист утверждения
Система для оценки качества кластеризации
электрокардиограмм
Программа и методика испытаний
Система для оценки качества кластеризации
электрокардиограмм
Программа и методика испытаний
Лист утверждения



Приложение Б

Текст программы

1 Текст системы на исходном коде

1.1 Узел настроек системы (settings)

1.2 Подпоток оценки качества результатов кластеризации ЭКГ (quality)

1.2.1 Узел настроек (settings)

1.2.2 Узел с текстом запроса в БД для получения кластеров (cardiograms)



1.2.3 Узел обработки полученных кластеров (clusters)

1.2.4 Узел с текстом запроса в БД для получения кардиограмм из кластеров (clusteringresults)

1.2.5 Узел соединения полученных от БД сообщений (mergeclusters)



1.2.6 Узел расчета оценки качества результатов кластеризации (Calinski-Harabasz)



1.2.7 Узел компоновки результатов расчета оценки (results)



1.2.8 Узел с текстом запроса для занесения полученной оценки в БД (score)

1.2.9 Узел с текстом запроса для получения из БД оценок качества результатов кластеризации (get a & b)

1.2.10 Узел, производящий выбор лучшего результата кластеризации (choose)



1.3 Узел метода золотого сечения (golden-section)



Приложение В

Описание применения

В данном программном документе приведено описание применения «Системы для оценки качества результатов кластеризации электрокардиограмм».

В разделе «Назначение системы» приведено описание назначения системы, ее возможностииосновные характеристики.

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

В разделе «Описание задачи» приведено описание решаемой с помощью системы задачи, а также методы ее решения, используемые в качестве основы системы.

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

1 Назначение системы

1.1 Назначение системы

«Система для оценки качества результатов кластеризации электрокардиограмм» работает на программной платформе Node.js8 и выше. Основной функцией системы является вычисление оценки качества результатов кластеризации ЭКГ с помощью метрики CHWOS. Выполнение работы системы начинается по команде оператора.

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

Также система реализует следующие функции:

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

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

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

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

Перечисленные функции системы позволяют оптимальным образом провести кластеризацию любой выборки ЭКГ.

1.2 Возможности системы

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

1.3 Основные характеристики системы

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

1.4 Ограничения, накладываемые на область применения системы

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

2 Условия применения

2.1 Требования к техническим (аппаратным) средствам

Минимальные требования для работы «Система для оценки качества результатов кластеризации электрокардиограмм»:

Устройство с операционной системой, позволяющей установить программную платформу Node.js 8 и систему управления базами данных PostgreSQL 10;

Дисплей с разрешением 800х600 точек;

Клавиатура и мышь.

2.2 Требования к программным средствам (другим программам)

Необходим доступ к ПКИ систем обработки и анализа ЭКГ.

Для функционирования «Системы для оценки качества результатов кластеризации электрокардиограмм» необходимо, чтобы на персональном компьютере(ПК) были установлены программная платформа Node.js 8 и выше, а также инструментальная среда Node-RED.

2.3 Общие характеристики входной информации

На вход «Системы для оценки качества результатов кластеризации электрокардиограмм» поступает идентификатор выборки ЭКГ.

2.4 Общие характеристики выходной информации

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

2.5 Требования и условия организационного характера

Для работы «Системы для оценки качества результатов кластеризации электрокардиограмм» отсутствуют условия или требования организационного характера.

2.6 Требования и условия технического характера

Для максимальной производительности«Системы для оценки качества результатов кластеризации электрокардиограмм» требуется 2 полностью свободных потока процессора ПК.

2.6 Требования и условия технологического характера

Для работы «Системы для оценки качества результатов кластеризации электрокардиограмм» отсутствуют условия или требования технологического характера.

3 Описание задачи

3.1 Определение задачи

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

3.2 Методы решения задачи

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

4 Входные и выходные данные

4.1 Сведения о входных данных

На вход «Системы для оценки качества результатов кластеризации электрокардиограмм» поступают:

данные ПКИ - сообщение о том, что необходимые выборки кластеризованны;

набор кластеров ЭКГ, каждая из которых описывается определённым пространством признаков (n(размерность пространства признаков) значений в формате числа с плавающей точкой);

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

4.2 Сведения о выходных данных

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



Приложение Г

Руководство оператора

В данном программном документе приведено руководство оператора по для «Системы для оценки качества результатов кластеризации электрокардиограмм».

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

В разделе «Условия работы системы» указаны условия, необходимые для работы с системой-минимальный состав программных, минимальный аппаратных средств и требования к оператору.

В разделе «Работа с системой» указана последовательность действий, которое необходимо выполнить оператору для запуска системы, работы с системой и завершения ее работы.

В разделе «Статусы узлов системы и сообщения оператору» приведены тексты статусов узлов системы и описание сообщений, которые система выводит оператору в процессе своей работы.

1 Назначение системы

1.1 Функциональное назначение системы

Основной функцией «Системы для оценки качества результатов кластеризации электрокардиограмм» является вычисление оценки качества результатов кластеризации ЭКГ с помощью метрики CHWOS. Выполнение работы системы начинается по команде оператора.

Также система реализует следующие функции:

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

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

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

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

1.2 Эксплуатационное назначение системы

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

1.3 Состав функций

1.3.1 Функция приема данных из БД

Для вычисления оценки качества кластеризации в п. «1.3.4 Функция вычисление оценки качества результатов кластеризации ЭКГ» «Система для оценки качества результатов кластеризации электрокардиограмм» отправляет запрос в БД, ответом на который являются результаты кластеризации для указанной в запросе выборки.

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

«Система для оценки качества результатов кластеризации электрокардиограмм» вычисляет оптимальное значение для указанной выборки путем перебора на основе метода золотого сечения различных значений rmax и расчета оценки качества кластеризации с помощью п. «1.3.4 Функция вычисление оценки качества результатов кл...