Innovative Biosystems and Bioengineering (Jun 2018)
Оценка эффективности алгоритмов в задаче кластеризации биологических объектов
Abstract
Проблематика. Задача определения функциональной связи между биофизическими параметрами является составной частью актуальной проблемы поиска оптимального воздействия на биологический объект и в настоящее время не является полностью решенной. Одной из важных задач в этой области является разбиение исходного пространства признаков на такие области (кластеры), которые относятся к различным функциональным соотношениям, связывающим биофизические параметры, и имеют, в общем случае, произвольную форму. Такие кластеры в дальнейшем логично называть функциональными. Для получения и анализа функциональных кластеров существует ряд алгоритмов, каждый из которых обладает своими преимуществами и недостатками. В то же время решение определенной практической задачи требует оценки эффективности алгоритмов с точки зрения адекватности выделения кластеров. Цель. В статье для достаточно общего примера задачи кластеризации биологических объектов (ирисы Фишера) оценивается эффективность ряда типичных инструментов кластеризации. Рассмотрено применение алгоритма k-средних, алгоритма Варда, а также разработанной в данной работе нечеткой версии кластеризации для алгоритма k-средних с ограниченной массой рабочей области формирования кластеров. Методика реализации. В алгоритм включена процедура априорной оценки количества кластеров. Оценка проводится по гистограмме частот, для определения оптимального количества столбцов гистограммы обосновывается применение формулы Скотта. Алгоритм позволяет формировать кластеры произвольной конфигурации с получением значения меры принадлежности объекта каждому из кластеров. На наборе данных "Ирисы Фишера" проведено сравнительное тестирование указанных алгоритмов. Результаты. Наилучшее значение F1-score получено для алгоритма, предложенного в работе – F1 = 0,92, F1 = 0,90 для метода Варда и F1 = 0,88 для классического алгоритма k-средних. Выводы. Полученные результаты тестирования свидетельствуют о том, что в задачах анализа кластеров произвольной формы целесообразно отдать предпочтение разработанной в данной работе версии нечетких k-средних с ограниченной массой рабочей области формирования кластеров. Расчет значения меры принадлежности в алгоритме позволяет получить дополнительную информацию о структуре кластерных образований, а также осуществить поправки результата кластеризации k-средних с ограниченной массой, что особенно важно при формировании кластеров за один проход. Сравнение требуемых для расчета вычислительных ресурсов для алгоритмов с относительно близкими результатами теста также свидетельствует о преимуществе предложенного в работе алгоритма. По сравнению с алгоритмом Варда ему требуется меньше вычислительных ресурсов, так как не нужна дополнительная память для хранения матрицы расстояний и нет затрат времени на ее перерасчет.
Keywords
