Estimation of Algorithms Efficiency in the Task of Biological Objects Clustering

Скорочена інформація про документ
dc.contributor.authorUmanets, Vitalii
dc.contributor.authorVoinyk, Bogdan
dc.contributor.authorPavlov, Volodymyr
dc.contributor.authorNastenko, Ievgen
dc.contributor.authorУманець, Віталій Сергійович
dc.contributor.authorВойник, Богдан Олексійович
dc.contributor.authorПавлов, Володимир Анатолійович
dc.contributor.authorНастенко, Євген Арнольдович
dc.contributor.authorУманец, Виталий Сергеевич
dc.contributor.authorВойник, Богдан Алексеевич
dc.contributor.authorПавлов, Владимир Анатольевич
dc.contributor.authorНастенко, Евгений Арнольдович
dc.date.accessioned2018-07-19T12:41:55Z
dc.date.available2018-07-19T12:41:55Z
dc.date.issued2018
dc.description.abstractenBackground. The task of determining the functional relationship between biophysical parameters is an integral part of the actual problem of finding the optimal impact on a biological object and is currently not completely resolved. One of the important tasks in this area is the partitioning of the original feature space into such areas (clusters) that relate to different functional relationships linking biophysical parameters and have, in general, an arbitrary shape. Such clusters in the future is logical to call functional. To obtain and analyze the functional clusters, there are a number of algorithms, each of which has its advantages and disadvantages. At the same time, the solution of a certain practical problem requires an evaluation of the efficiency of the algorithms in terms of the cluster separation adequacy. Objective. In this paper, for a general example of the biological objects clustering problem (Fischer’s Iris Data Set), the efficiency of a typical clustering tools series is evaluated. The application of k-means classical algorithm, the Ward algorithm and developed in this work the fuzzy version of clustering for the k-means algorithm with a limited mass of the working area for the clusters’ formation was considered. Methods. The algorithm includes a procedure for a priori estimation of the clusters quantity. The estimation is carried out according to the frequency histogram. To determine the optimal number of the histogram columns, the application of the Scott formula is justified. The algorithm allows forming clusters of arbitrary configuration with obtaining the value of the object's membership measure for each of the clusters. The comparative testing of the above algorithms was carried out on Fisher’s Iris Data Set. Results. The best value of F₁-score is obtained for the algorithm proposed in this paper: F₁ = 0.92, the value F₁ = 0.90 is obtained for the Ward method and the value F₁ = 0.88 – for the classical k-means algorithm. Conclusions. The obtained test results on the analysis problem of arbitrary-shaped clusters made it possible to give preference to the version of fuzzy k-means with a limited mass of the working area for the clusters’ formation. The calculating of the membership measure value allows us to obtain additional information on the structure of cluster formations, as well as to correct the result of clustering of k-means with a limited mass, which is especially important since the formation of clusters occurs in a single pass. Comparing the computational resources required for computing algorithms with relatively close test results also makes it possible to give preference to the developed algorithm. Compared with the Ward algorithm, it requires fewer computing resources since no additional memory is needed to store the distance matrix and no time is required to recalculate it.uk
dc.description.abstractruПроблематика. Задача определения функциональной связи между биофизическими параметрами является составной частью актуальной проблемы поиска оптимального воздействия на биологический объект и в настоящее время не является полностью решенной. Одной из важных задач в этой области является разбиение исходного пространства признаков на такие области (кластеры), которые относятся к различным функциональным соотношениям, связывающим биофизические параметры, и имеют, в общем случае, произвольную форму. Такие кластеры в дальнейшем логично называть функциональными. Для получения и анализа функциональных кластеров существует ряд алгоритмов, каждый из которых обладает своими преимуществами и недостатками. В то же время решение определенной практической задачи требует оценки эффективности алгоритмов с точки зрения адекватности выделения кластеров. Цель. В статье для достаточно общего примера задачи кластеризации биологических объектов (ирисы Фишера) оценивается эффективность ряда типичных инструментов кластеризации. Рассмотрено применение алгоритма k-средних, алгоритма Варда, а также разработанной в данной работе нечеткой версии кластеризации для алгоритма k-средних с ограниченной массой рабочей области формирования кластеров. Методика реализации. В алгоритм включена процедура априорной оценки количества кластеров. Оценка проводится по гистограмме частот, для определения оптимального количества столбцов гистограммы обосновывается применение формулы Скотта. Алгоритм позволяет формировать кластеры произвольной конфигурации с получением значения меры принадлежности объекта каждому из кластеров. На наборе данных "Ирисы Фишера" проведено сравнительное тестирование указанных алгоритмов. Результаты. Наилучшее значение F₁-score получено для алгоритма, предложенного в работе – F₁ = 0,92, F₁ = 0,90 для метода Варда и F₁ = 0,88 для классического алгоритма k-средних. Выводы. Полученные результаты тестирования свидетельствуют о том, что в задачах анализа кластеров произвольной формы целесообразно отдать предпочтение разработанной в данной работе версии нечетких k-средних с ограниченной массой рабочей области формирования кластеров. Расчет значения меры принадлежности в алгоритме позволяет получить дополнительную информацию о структуре кластерных образований, а также осуществить поправки результата кластеризации k-средних с ограниченной массой, что особенно важно при формировании кластеров за один проход. Сравнение требуемых для расчета вычислительных ресурсов для алгоритмов с относительно близкими результатами теста также свидетельствует о преимуществе предложенного в работе алгоритма. По сравнению с алгоритмом Варда ему требуется меньше вычислительных ресурсов, так как не нужна дополнительная память для хранения матрицы расстояний и нет затрат времени на ее перерасчет.uk
dc.description.abstractukПроблематика. Завдання визначення функціонального зв’язку між біофізичними параметрами є складовою частиною актуальної проблеми пошуку оптимального впливу на біологічний об’єкт і на сьогодні не є повністю вирішеним. Однією з важливих задач у цій області є розбиття початкового простору ознак на такі області (кластери), які відносяться до різних функціональних співвідношень, що зв’язують біофізичні параметри, і які мають, у загальному випадку, довільну форму. Такі кластери в подальшому логічно називати функціональними. Для отримання й аналізу функціональних кластерів існує низка алгоритмів, кожен із яких має свої переваги й недоліки. У той же час розв’язання певної практичної задачі вимагає оцінки ефективності алгоритмів з точки зору адекватності виділення кластерів. Мета. У статті для досить загального прикладу завдання кластеризації біологічних об’єктів (іриси Фішера) оцінюється ефективність низки типових інструментів кластеризації. Розглянуто застосування алгоритму k-середніх, алгоритму Варда, а також розробленої в роботі нечіткої версії кластеризації для алгоритму k-середніх з обмеженою масою робочої області формування кластерів. Методика реалізації. В алгоритм включено процедуру апріорної оцінки кількості кластерів. Оцінка проводиться по гістограмі частот, для визначення оптимальної кількості стовпців гістограми обґрунтовується застосування формули Скотта. Алгоритм дає змогу формувати кластери довільної конфігурації з отриманням значення міри приналежності об’єкта кожному з кластерів. На наборі даних "Іриси Фішера" проведено порівняльне тестування зазначених алгоритмів. Результати. Оптимальне значення F₁-score отримано для алгоритму, що запропонований у роботі – F₁ = 0,92, значення F₁ = 0,90 одержано для методу Варда і значення F₁ = 0,88 – для класичного алгоритму k-середніх. Висновки. Отримані результати тестування свідчать, що в завданнях аналізу кластерів довільної форми доцільно віддати перевагу розробленій у дійсній роботі версії нечітких k-середніх з обмеженою масою робочої області формування кластерів. Розрахунок значення міри приналежності дає можливість в алгоритмі отримати додаткову інформацію про структуру кластерних утворень, а також здійснити поправки результату кластеризації k-середніх з обмеженою масою, що особливо важливо при формуванні кластерів за один прохід. Порівняння необхідних для розрахунку обчислювальних ресурсів для алгоритмів з відносно близькими результатами тесту також свідчить про перевагу запропонованого в роботі алгоритму. Порівняно з алгоритмом Варда йому необхідно менше обчислювальних ресурсів, оскільки не потрібна додаткова пам’ять для зберігання матриці відстаней і немає витрат часу на її перерахунок.uk
dc.format.pagerangePp. 84-89uk
dc.identifier.citationEstimation of Algorithms Efficiency in the Task of Biological Objects Clustering / V. S. Umanets, B. A. Voinyk, V. A. Pavlov, Ie. A. Nastenko // Innovative Biosystems and Bioengineering : international scientific e-journal. – 2018. – Vol. 2, No. 2. – Pp. 84–89. – Bibliogr.: 9 ref.uk
dc.identifier.doihttps://doi.org/10.20535/ibb.2018.2.2.133466
dc.identifier.urihttps://ela.kpi.ua/handle/123456789/23980
dc.language.isoenuk
dc.publisherIgor Sikorsky Kyiv Polytechnic Instituteuk
dc.publisher.placeKyivuk
dc.rightsAttribution 4.0 International (CC BY 4.0)en
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/en
dc.sourceInnovative Biosystems and Bioengineering : international scientific e-journal, 2018, Vol. 2, No. 2uk
dc.subjectclusteringuk
dc.subjectk-meansuk
dc.subjectbiological objectuk
dc.subjectmembership functionuk
dc.subjectestimation of a number of clustersuk
dc.subjectfuzzy clusteringuk
dc.subjectкластеризаціяuk
dc.subjectk-середніuk
dc.subjectбіологічний об’єктuk
dc.subjectміра належностіuk
dc.subjectоцінка кількості кластерівuk
dc.subjectнечітка кластеризаціяuk
dc.subjectкластеризацияuk
dc.subjectk-средниеuk
dc.subjectбиологический объектuk
dc.subjectмера принадлежностиuk
dc.subjectоценка количества кластеровuk
dc.subjectнечеткая кластеризацияuk
dc.subject.udc004.021uk
dc.titleEstimation of Algorithms Efficiency in the Task of Biological Objects Clusteringuk
dc.title.alternativeОцінка ефективності алгоритмів у задачі кластеризації біологічних об’єктівuk
dc.title.alternativeОценка эффективности алгоритмов в задаче кластеризации биологических объектовuk
dc.typeArticleuk

Файли

Контейнер файлів
Зараз показуємо 1 - 1 з 1
Ескіз
Назва:
IBB2018.2.2_02.pdf
Розмір:
280.08 KB
Формат:
Adobe Portable Document Format
Опис:
Завантажити
Ліцензійна угода
Зараз показуємо 1 - 1 з 1
Ескіз недоступний
Назва:
license.txt
Розмір:
7.74 KB
Формат:
Item-specific license agreed upon to submission
Опис:
Завантажити

Зібрання

Innovative Biosystems and Bioengineering: international scientific e-journal, Vol. 2, No. 2