Exploring the impact of clustering algorithms on hierarchical divisive clustering for multiclass classification

Yıl 2024, , 363 - 373, 30.06.2024

Celal Alagoz

https://doi.org/10.24012/dumf.1430306

Öz

Transforming a multi-class classification problem into a hierarchical form to achieve performance improvement is a topic of research. An essential aspect in automating such transformation is the process of hierarchy building. This research examines how standard clustering algorithms, including K-Medoids, K-Means, and Gaussian Mixture Models, contribute as partitioning functions within the Hierarchical Divisive Clustering method, a technique for building hierarchies, and their effects on the classification performance of multi-class datasets. Analyses conducted using two different performance metrics, namely F1 score and accuracy score, indicate that K-Means and GMM are generally more effective compared to K-Medoids. However, performance improvement and learning efficiency vary depending on the number of classes and the characteristics of the dataset. It is found that hierarchical transformation significantly influences classification performance, and different datasets exhibit different responses. The study also discusses its limitations and future research directions. This study contributes to understanding the role of clustering algorithms in Hierarchical Divisive Clustering and potential avenues for future research.

Anahtar Kelimeler

Multiclass Classification, Hierarchical Classification, Automated Hierarchy Generation, Clustering Algorithms, Hierarchical Divisive Clustering

Kümeleme algoritmalarının hiyerarşik bölücü kümeleme yönteminde çok sınıflı sınıflandırma performansına etkisi: bir analiz

Öz

Çok sınıflı sınıflandırma problemini hiyerarşik biçime dönüştürerek performans gelişimi elde etmek araştırılan bir konudur. Böylesi bir dönüşümü otomatik olarak gerçekleştirmede kritik bir bileşen, hiyerarşi oluşturma sürecidir. Bu çalışma, standard kümeleme algoritmaları olan K-Medoids, K-Means ve Gaussian Karışım Modelleri’in bir hiyerarşi inşa etme tekniği olan Hiyerarşik Bölücü Kümeleme yönteminde bölücü işlevinde kullanılmasıyla otomatik olarak elde edilen hiyerarşilerin çok sınıflı veri setlerinin sınıflandırma performansına etkisini incelemektedir. İki farklı performans metriği olan F1 skoru ve doğruluk skoru kullanılarak yapılan analizler, K-Means ve GMM'nin K-Med'e göre genellikle daha etkili olduğunu göstermektedir. Ancak, performans iyileştirmesi ve öğrenme verimi, sınıf sayısına ve veri setinin özelliklerine bağlı olarak değişmektedir. Hiyerarşik biçime dönüştürmenin sınıflandırma performansına önemli ölçüde etkisi olduğu ve farklı veri setlerinin farklı tepkiler verdiği bulunmuştur. Çalışmanın kısıtları ve gelecek araştırma yönleri de tartışılmıştır. Bu çalışma, kümeleme algoritmalarının hiyerarşik bölücü kümeleme yöntemindeki rolünü ve gelecekteki araştırmalara potansiyel yönleri anlamak için önemli bir katkı sağlamaktadır.

Anahtar Kelimeler

Çok Sınıflı Sınıflandırma, Hiyerarşik Sınıflandırma, Otomatik Hiyerarşi Üretme, Kümeleme Algoritmaları, Hiyerarşik Bölücü Kümeleme

Kaynakça

• [1] C. N. Silla, and A. A. Freitas, “A survey of hierarchical classification across different application domains,” Data mining and knowledge discovery, vol. 22, pp. 31-72, Jan. 2011, doi: https://doi.org/10.1007/s10618-010-0175-9
• [2] E. Frank and S. Kramer, “Ensembles of Nested Dichotomies for Multi-Class Problems,” in Proc. 21st Int'l Conf. Machine Learning (ICML '04), Banff, Alberta, Canada, p. 39, 2004, doi: https://doi.org/10.1145/1015330.1015363
• [3] F. Sebastiani, “Machine learning in automated text categorization,” in ACM computing surveys (CSUR), vol. 34, no. 1, pp. 1-47, Mar. 2002, doi: https://doi.org/10.1145/505282.505283
• [4] A. Sun, E. P. Lim, and W. K. Ng, “Hierarchical text classification methods and their specification,” in Cooperative internet computing, The Springer International Series in Engineering and Computer Science, vol 729. Springer, Boston, MA, USA: 2003, ch. 14, pp. 236-256, doi: https://doi.org/10.1007/978-1-4615-0435-1_14
• [5] S. Dumais and C. Hao, “Hierarchical classification of web content,” in Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, Athens, Greece. 2000, pp. 256-263, doi: https://doi.org/10.1145/345508.345593
• [6] I. Dimitrovski, D. Kocev, S. Loskovska, and S. Džeroski, “Hierarchical annotation of medical images,” Pattern Recognition, vol. 44, no. 10-11, pp. 2436-2449, Oct. 2011, doi: https://doi.org/10.1016/j.patcog.2011.03.026
• [7] L. Li, S. Jiang and Q. Huang, “Learning Hierarchical Semantic Description Via Mixed-Norm Regularization for Image Understanding,” IEEE Transactions on Multimedia, vol. 14, no. 5, pp. 1401-1413, Oct. 2012, doi: https://doi.org/10.1109/TMM.2012.2194993
• [8] J. Spehr, D. Rosebrock, D. Mossau, R. Auer, S. Brosig and F. M. Wahl, “Hierarchical scene understanding for intelligent vehicles,” in 2011 IEEE Intelligent Vehicles Symposium (IV), Baden-Baden, Germany, 2011, pp. 1142-1147, doi: https://doi.org/10.1109/IVS.2011.5940566
• [9] P. Arbeláez, M. Maire, C. Fowlkes and J. Malik, "Contour Detection and Hierarchical Image Segmentation," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 33, no. 5, pp. 898-916, May 2011, doi: https://doi.org/10.1109/TPAMI.2010.161
• [10] H. Blockeel, L. Schietgat, J. Struyf, S. Dzeroski and A. Clare, “Decision trees for hierarchical multilabel classification: A case study in functional genomics”, in Proc. 10th Eur. Conf. Principle Pract. Knowl. Discovery Databases: Lecture Notes in Computer Science(), vol 4213. Springer, Berlin, Heidelberg, doi: https://doi.org/10.1007/11871637_7
• [11] A. Breschi, M. Muñoz-Aguirre, V. Wucher, C. A. Davis, D. Garrido-Martín, S. Djebali, J. Gillis et al., “A limited set of transcriptional programs define major cell types," Genome research, vol. 30, no. 7, pp. 1047-1059, Jul. 2020, doi: https://doi.org/10.1101/gr.263186.120
• [12] K. Punera, S. Rajan and J Ghosh, “Automatically learning document taxonomies for hierarchical classification,” Special interest tracks and posters of the 14th international conference on World Wide Web, pp. 1010-1011, 2005, doi: https://doi.org/10.1145/1062745.1062843
• [13] M. Sun, W. Huang and S. Savarese, “Find the Best Path: An Efficient and Accurate Classifier for Image Hierarchies,” 2013 IEEE International Conference on Computer Vision, Sydney, NSW, Australia, 2013, pp. 265-272, doi: https://doi.org/10.1109/ICCV.2013.40
• [14] H. Lei, K. Mei, N. Zheng, P. Dong, N. Zhou, and J. Fan, “Learning group-based dictionaries for discriminative image representation,” Pattern Recognition, vol. 47, no. 2, pp. 899-913, Feb. 2014, doi: https://doi.org/10.1016/j.patcog.2013.07.016
• [15] V. Melnikov and E. Hüllermeier, "On the effectiveness of heuristics for learning nested dichotomies: An empirical analysis", Mach. Learn., vol. 107, no. 8, pp. 1537-1560, Sep. 2018, doi: https://doi.org/10.1007/s10994-018-5733-1
• [16] P. del Moral, S. Nowaczyk, A. Sant’Anna, S. Pashami, “Pitfalls of assessing extracted hierarchies for multi-class classification,” Pattern Recognition, vol. 136, pp.109-225, Apr. 2023, doi: https://doi.org/10.1016/j.patcog.2022.109225
• [17] K. Punera, S. Rajan and J. Ghosh, "Automatic Construction of N-ary Tree Based Taxonomies," Sixth IEEE International Conference on Data Mining - Workshops (ICDMW'06), Hong Kong, China, 2006, pp. 75-79, doi: https://doi.org/10.1109/ICDMW.2006.35
• [18] B. Larsen, C. Aone,”Fast and effective text mining using linear-time document clustering,” in Proc.5th ACM SIGKDD (KDD’99), San Diego, CA, USA, 1999, pp. 16–22, doi: https://doi.org/10.1145/312129.312186
• [19] T. Li, S. Zhu and M. Ogihara,”Hierarchical document classification using automatically generated hierarchy,” J. Intell. Inf. Syst., vol. 29, no. 2, pp. 211-230, Oct. 2007, doi: https://doi.org/10.1007/s10844-006-0019-7
• [20] C. Alagoz,”Performance Improvement in Multi-class Classification via Automated Hierarchy Generation and Exploitation through Extended LCPN Schemes,” arXiv preprint arXiv:2310.20641, Oct. 2023, doi: https://doi.org/10.48550/arXiv.2310.20641
• [21] R.A. Fisher, "The Use of Multiple Measures in Taxonomic Problems", Ann. Eugenics, vol. 7, pp. 179-188, Sep. 1936, doi: https://doi.org/10.1111/j.1469-1809.1936.tb02137.x
• [22] L. Kaufman and P. J. Rousseeuw,”Finding Groups in Data: An Introduction to Cluster Analysis,” New York, NY, USA:Wiley, 1990, doi: https://doi.org/10.1002/9780470316801
• [23] J. H. Friedman, "Greedy function approximation: A gradient boosting machine", Ann. Statist., pp. 1189-1232, Oct. 2001.
• [24] J. Vanschoren, J. N. van Rijn, B. Bischl and L. Torgo, “OpenML: Networked science in machine learning”, ACM SIGKDD Explor. Newslett., vol. 15, no. 2, pp. 49-60, Jun. 2014, doi: https://doi.org/10.1145/2641190.2641198
• [25] M. Feurer et al., “OpenML-Python: An extensible Python API for OpenML,” J. Mach. Learn. Res., vol. 22, no. 100, pp. 1-5, 2021.
• [26] F. Wilcoxon, “Individual Comparisons by Ranking Methods,” in: Kotz, S., Johnson, N.L. (eds) Breakthroughs in Statistics. Springer Series in Statistics. Springer, New York, NY, 1992, doi: https://doi.org/10.1007/978-1-4612-4380-9_16
• [27] S. Godbole, “Exploiting confusion matrices for automatic generation of topic hierarchies and scaling up multi-way classifiers,” Technical report, IIT Bombay, 2002.
• [28] S. Bengio, J. Weston and D. Grangier, “Label embedding trees for large multi-class tasks,” Proc. Neural Inform. Process. Syst., pp. 163-171, 2010.
• [29] D. Silva-Palacios, C. Ferri and M. J. Ramírez-Quintana, "Probabilistic class hierarchies for multiclass classification", J. Comput. Sci., vol. 26, pp. 254-263, May 2018, doi: https://doi.org/10.1016/j.jocs.2018.01.006