Оценка эффективности алгоритмов в задаче кластеризации биологических объектов
Проблематика. Задача определения функциональной связи между биофизическими параметрами является составной частью актуальной проблемы поиска оптимального воздействия на биологический объект и в настоящее время не является полностью решенной. Одной из важных задач в этой области является разбиение исх...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Igor Sikorsky Kyiv Polytechnic Institute
2018-06-01
|
| Series: | Innovative Biosystems and Bioengineering |
| Subjects: | |
| Online Access: | http://ibb.kpi.ua/article/view/133466 |
| _version_ | 1797997547221942272 |
|---|---|
| author | Vitalii Umanets Bogdan Voinyk Volodymyr Pavlov Ievgen Nastenko |
| author_facet | Vitalii Umanets Bogdan Voinyk Volodymyr Pavlov Ievgen Nastenko |
| author_sort | Vitalii Umanets |
| collection | DOAJ |
| description | Проблематика. Задача определения функциональной связи между биофизическими параметрами является составной частью актуальной проблемы поиска оптимального воздействия на биологический объект и в настоящее время не является полностью решенной. Одной из важных задач в этой области является разбиение исходного пространства признаков на такие области (кластеры), которые относятся к различным функциональным соотношениям, связывающим биофизические параметры, и имеют, в общем случае, произвольную форму. Такие кластеры в дальнейшем логично называть функциональными. Для получения и анализа функциональных кластеров существует ряд алгоритмов, каждый из которых обладает своими преимуществами и недостатками. В то же время решение определенной практической задачи требует оценки эффективности алгоритмов с точки зрения адекватности выделения кластеров.
Цель. В статье для достаточно общего примера задачи кластеризации биологических объектов (ирисы Фишера) оценивается эффективность ряда типичных инструментов кластеризации. Рассмотрено применение алгоритма k-средних, алгоритма Варда, а также разработанной в данной работе нечеткой версии кластеризации для алгоритма k-средних с ограниченной массой рабочей области формирования кластеров.
Методика реализации. В алгоритм включена процедура априорной оценки количества кластеров. Оценка проводится по гистограмме частот, для определения оптимального количества столбцов гистограммы обосновывается применение формулы Скотта. Алгоритм позволяет формировать кластеры произвольной конфигурации с получением значения меры принадлежности объекта каждому из кластеров. На наборе данных "Ирисы Фишера" проведено сравнительное тестирование указанных алгоритмов.
Результаты. Наилучшее значение F1-score получено для алгоритма, предложенного в работе – F1 = 0,92, F1 = 0,90 для метода Варда и F1 = 0,88 для классического алгоритма k-средних.
Выводы. Полученные результаты тестирования свидетельствуют о том, что в задачах анализа кластеров произвольной формы целесообразно отдать предпочтение разработанной в данной работе версии нечетких k-средних с ограниченной массой рабочей области формирования кластеров. Расчет значения меры принадлежности в алгоритме позволяет получить дополнительную информацию о структуре кластерных образований, а также осуществить поправки результата кластеризации k-средних с ограниченной массой, что особенно важно при формировании кластеров за один проход. Сравнение требуемых для расчета вычислительных ресурсов для алгоритмов с относительно близкими результатами теста также свидетельствует о преимуществе предложенного в работе алгоритма. По сравнению с алгоритмом Варда ему требуется меньше вычислительных ресурсов, так как не нужна дополнительная память для хранения матрицы расстояний и нет затрат времени на ее перерасчет. |
| first_indexed | 2024-04-11T10:33:28Z |
| format | Article |
| id | doaj.art-358cc3f99dcb49b0b2acd811a9533b5b |
| institution | Directory Open Access Journal |
| issn | 2616-177X |
| language | English |
| last_indexed | 2024-04-11T10:33:28Z |
| publishDate | 2018-06-01 |
| publisher | Igor Sikorsky Kyiv Polytechnic Institute |
| record_format | Article |
| series | Innovative Biosystems and Bioengineering |
| spelling | doaj.art-358cc3f99dcb49b0b2acd811a9533b5b2022-12-22T04:29:21ZengIgor Sikorsky Kyiv Polytechnic InstituteInnovative Biosystems and Bioengineering2616-177X2018-06-0122848910.20535/ibb.2018.2.2.133466133466Оценка эффективности алгоритмов в задаче кластеризации биологических объектовVitalii Umanets0Bogdan Voinyk1Volodymyr Pavlov2Ievgen Nastenko3Igor Sikorsky Kyiv Polytechnic InstituteIgor Sikorsky Kyiv Polytechnic InstituteIgor Sikorsky Kyiv Polytechnic InstituteIgor Sikorsky Kyiv Polytechnic InstituteПроблематика. Задача определения функциональной связи между биофизическими параметрами является составной частью актуальной проблемы поиска оптимального воздействия на биологический объект и в настоящее время не является полностью решенной. Одной из важных задач в этой области является разбиение исходного пространства признаков на такие области (кластеры), которые относятся к различным функциональным соотношениям, связывающим биофизические параметры, и имеют, в общем случае, произвольную форму. Такие кластеры в дальнейшем логично называть функциональными. Для получения и анализа функциональных кластеров существует ряд алгоритмов, каждый из которых обладает своими преимуществами и недостатками. В то же время решение определенной практической задачи требует оценки эффективности алгоритмов с точки зрения адекватности выделения кластеров. Цель. В статье для достаточно общего примера задачи кластеризации биологических объектов (ирисы Фишера) оценивается эффективность ряда типичных инструментов кластеризации. Рассмотрено применение алгоритма k-средних, алгоритма Варда, а также разработанной в данной работе нечеткой версии кластеризации для алгоритма k-средних с ограниченной массой рабочей области формирования кластеров. Методика реализации. В алгоритм включена процедура априорной оценки количества кластеров. Оценка проводится по гистограмме частот, для определения оптимального количества столбцов гистограммы обосновывается применение формулы Скотта. Алгоритм позволяет формировать кластеры произвольной конфигурации с получением значения меры принадлежности объекта каждому из кластеров. На наборе данных "Ирисы Фишера" проведено сравнительное тестирование указанных алгоритмов. Результаты. Наилучшее значение F1-score получено для алгоритма, предложенного в работе – F1 = 0,92, F1 = 0,90 для метода Варда и F1 = 0,88 для классического алгоритма k-средних. Выводы. Полученные результаты тестирования свидетельствуют о том, что в задачах анализа кластеров произвольной формы целесообразно отдать предпочтение разработанной в данной работе версии нечетких k-средних с ограниченной массой рабочей области формирования кластеров. Расчет значения меры принадлежности в алгоритме позволяет получить дополнительную информацию о структуре кластерных образований, а также осуществить поправки результата кластеризации k-средних с ограниченной массой, что особенно важно при формировании кластеров за один проход. Сравнение требуемых для расчета вычислительных ресурсов для алгоритмов с относительно близкими результатами теста также свидетельствует о преимуществе предложенного в работе алгоритма. По сравнению с алгоритмом Варда ему требуется меньше вычислительных ресурсов, так как не нужна дополнительная память для хранения матрицы расстояний и нет затрат времени на ее перерасчет.http://ibb.kpi.ua/article/view/133466Clusteringk-meansBiological objectMembership functionEstimation of a number of clustersFuzzy clustering |
| spellingShingle | Vitalii Umanets Bogdan Voinyk Volodymyr Pavlov Ievgen Nastenko Оценка эффективности алгоритмов в задаче кластеризации биологических объектов Innovative Biosystems and Bioengineering Clustering k-means Biological object Membership function Estimation of a number of clusters Fuzzy clustering |
| title | Оценка эффективности алгоритмов в задаче кластеризации биологических объектов |
| title_full | Оценка эффективности алгоритмов в задаче кластеризации биологических объектов |
| title_fullStr | Оценка эффективности алгоритмов в задаче кластеризации биологических объектов |
| title_full_unstemmed | Оценка эффективности алгоритмов в задаче кластеризации биологических объектов |
| title_short | Оценка эффективности алгоритмов в задаче кластеризации биологических объектов |
| title_sort | оценка эффективности алгоритмов в задаче кластеризации биологических объектов |
| topic | Clustering k-means Biological object Membership function Estimation of a number of clusters Fuzzy clustering |
| url | http://ibb.kpi.ua/article/view/133466 |
| work_keys_str_mv | AT vitaliiumanets ocenkaéffektivnostialgoritmovvzadačeklasterizaciibiologičeskihobʺektov AT bogdanvoinyk ocenkaéffektivnostialgoritmovvzadačeklasterizaciibiologičeskihobʺektov AT volodymyrpavlov ocenkaéffektivnostialgoritmovvzadačeklasterizaciibiologičeskihobʺektov AT ievgennastenko ocenkaéffektivnostialgoritmovvzadačeklasterizaciibiologičeskihobʺektov |