Попередня класифікація даних за допомогою багаторівневої сегментації гістограм для кластеризації гіперкубів
DOI:
https://doi.org/10.15587/2706-5448.2020.220428Ключові слова:
кумулятивна гістограма, багаторівнева сегментація, кусково-лінійна апроксимація, ієрархічна кластеризація, розклад простору даних.Анотація
Об'єктом дослідження є алгоритм класифікації даних великих розмірів, що базується на алгоритмі ієрархічної кластеризації. Нелінійна складність алгоритму кластеризації не дозволяє їх використання для вибірок даних розмірами 5–10 тисяч і вище. Для класифікації даних необхідне їх попереднє групування. Тому предметом дослідження виступає алгоритм сегментування даних на основі кусково-лінійної апроксимації.
У процесі дослідження використовувалися алгоритми ієрархічної кластеризації, метод кусково-лінійної апроксимації кумулятивної гістограми, обчисленої за спеціальною процедурою, та процедури пошуку порогів сегментування.
Обчислювальна складність класичного ієрархічного алгоритму досягає значення O(N3), а певні кроки з обмеження пошуку можуть досягати значення O(N2), що було підтверджено експериментами з вивчення залежності ієрархічного дерева від вихідної вибірки. Реалізовано наближений підхід до кластеризації ключів з розбивкою набору базових ключів. Щоб ще більше знизити складність алгоритму ієрархічної кластеризації, запропоновано підхід декомпозиції, заснований на поділі вихідної вибірки великих даних на кілька підмножин. У даній роботі для використання алгоритму ієрархічної кластеризації для класифікації великих даних запропоновано метод попередньої декомпозиції. Цей метод засновано на багаторівневій сегментації кумулятивних або звичайних гістограм, отриманих для кожної координати ознаки, що характеризує об'єкт даних. Кусково-лінійною апроксимацією гістограмних функцій отримані пороги багаторівневої сегментації. Побудовані гіперкуби даних приймаються як об'єкти для трьохетапного алгоритму кластеризації.
Отримано потужний інструмент класифікації даних, використання якого дозволяє проводити багато експериментів з даними різних типів для виявлення закономірностей серед ознак даних. Його застосування призначено для опрацювання даних хворих, молекулярних структур, економічних задач для прийняття оптимальних рішень лікування, діагностики та моделювання. Завдяки цьому підходу класифікацію даних можна здійснювати в онлайн режимі для отримання результатів безпосереднього аналізу при надходженні даних, наприклад, з космічних апаратів.
Посилання
- Yip, A. M., Ding, C., Chan, T. F. (2006). Dynamic cluster formation using level set methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28 (6), 877–889. doi: http://doi.org/10.1109/tpami.2006.117
- Viattchenin, D. (2009). Developments in fuzzy clustering. The collection of papers. Minsk: Vever, 216.
- Sandeep, V. (2010). Effective level sets and shape detection: an application to natural images. Gulbarga: Electronics and Communications Engineering, 132.
- Grady, L., Schwartz, E. L. (2006). Isoperimetric graph partitioning for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28 (3), 469–475. doi: http://doi.org/10.1109/tpami.2006.57
- Pavan, M., Pelillo, M. (2007). Dominant Sets and Pairwise Clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29 (1), 167–172. doi: http://doi.org/10.1109/tpami.2007.250608
- Foggia, P., Percannella, G., Vento, M. (2014). Graph matching and learning in pattern recognition in the last 10 years. International Journal of Pattern Recognition and Artificial Intelligence, 28 (1), 1450001. doi: http://doi.org/10.1142/s0218001414500013
- Dong, X., Shen, J., Shao, L., Van Gool, L. (2016). Sub-Markov Random Walk for Image Segmentation. IEEE Transactions on Image Processing, 25 (2), 516–527. doi: http://doi.org/10.1109/tip.2015.2505184
- Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C. (2016). Recent Advances in Graph Partitioning. Lecture Notes in Computer Science, 117–158. doi: http://doi.org/10.1007/978-3-319-49487-6_4
- Wang, N., Gao, X., Tao, D., Yang, H., Li, X. (2018). Facial feature point detection: A comprehensive survey. Neurocomputing, 275 (31), 50–65. doi: http://doi.org/10.1016/j.neucom.2017.05.013
- Ding, C., He, X. (2005). Cluster aggregate inequality and multilevel hierarchical clustering. Proc. 9th European Conf. Principles of Data Mining and Knowledge Discovery, 71–83. doi: http://doi.org/10.1007/11564126_12
- Melnyk, R., Tushnytskyy, R. (2009). Algorithm accuracy and complexity optimization by inequality merging for data clustering. Proc. of the 10-th Intern. Conf. The Experience of Designing and Application of CAD Systems in Microelectronics (CADSM), 453–455.
- Melnyk, R., Aleekseev, O. (2006). Clustering of pattern keys base on decomposition of their set. Editing and processing of information, 24 (100), 110−114.
- Melnyk, R., Tushnytskyy, R. (2008). Pattern keys clustering using large-scale dataset cascading decomposition. Computer Science and Information Technology, 604, 249−254.
- Shenkoya, T., Kim, E. (2019). A case study of the daedeok innopolis innovation cluster and its implications for Nigeria. World Technopolis Review, 8 (2), 104−119. doi: http://dx.doi.org/10.7165/wtr19a1218.21
- Ramer, U. (1972). An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing, 1 (3), 244–256. doi: http://doi.org/10.1016/s0146-664x(72)80017-0
- Douglas, D., Peucker, T. (1973). Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 10 (2), 112–122.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Roman Melnyk, Ruslan Tushnytskyy, Roman Kvit, Tetyana Salo
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
