Ant colony opimization algorithms for clustering problems

• Autorzy: Schiff K.

Warianty tytułu

PL

Algorytmy mrówkowe dla problemów klasteryzacji

• Języki publikacji: EN

Abstrakty

EN

The clustering problem is one of the main problems which can be encountered in a data analysis. This problem can be modelled by means of a graph; finding clusters means finding cliques in the graph. Often there is a need to find clusters (cliques) in a graph in different ways and to construct a list of clusters. This paper describes two such ways, these can be stated as the cluster minimum covering problem and the vertex cluster minimum partitioning problem. This paper describes new ant algorithms which were used in order to make a list of clusters in both presented problems, and also discusses the results of their comparison.

PL

Problem klasteryzacji jest jednym z często spotykanych problemów w analizie danych. Problem klasteryzacji może być zamodelowany przy pomocy grafów i znajdowanie klasterów sprowadza się wówczas do znajdowania klik w grafach. W tym artykule opisano dwa sposoby wyznaczania klasterów, czyli klik w grafach, takich jak: problem pokrycia klastrami (klikami) grafu oraz problem wierzchołkowego podziału grafu na klastry (kliki) oraz także przedstawiono dwa nowe algorytmy bazujące na zachowaniu mrówek służące do wyznaczania klastrów (klik) dla obu problemów, a także dokonano porównania ich ze znanymi algorytmami rozwiązującymi te problemy.

Słowa kluczowe

EN

clustering; clique covering problem; clique vertex partitioning problem; ant algorithms

PL

klasteryzacja; pokrycie klikami; wierzchołkowy podział na kliki; algorytm mrówkowy

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Automatyka
• Rocznik: 2013
• Tom: R. 110, z. 4-AC
• Strony: 77--87
• Opis fizyczny: Bibliogr. 18 poz., rys., wz., tab.

Twórcy

autor

Schiff K.

• Department of Automatic Control and Information Technology, Faculty of Electrical and Computer Engineering, Cracow University of Technology

Bibliografia

• [1] Garey M., Johnson D., Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York 1979.
• [2] Ponce J., Ponce E., Padilla F., Padilla A., Ant Colony Algorithm for Clustering through of Cliques, 2006.
• [3] Ponce J., Ponce E., Padilla F., Padilla A., Ochoa A., Algoritmo De Colonia De Hormigas Para El Problema Del Clique Máximo Con Un Optimizador Local K-Opt, Hífen, Uruguaiana, Vol. 30, No. 58, Brasil 2006.
• [4] Fenet S., Solnon C., Searching for Maximum Cliques with Ant Colony Optimization EvoWorkshops 2003, LNCS 2611, 2003, 236-245.
• [5] Xu X., Ma J., Lee J., An Improved Ant Colony Optimization for the Maximum Clique Problem, IEEE Third International Conference on Natural Computation, 2007.
• [6] Bron C., Kerbosh J., Finding all cliques of an undirected graph, Association of Computer Machine, 16, 1973, 575-577.
• [7] Wang J., Xu X., Tsng Z., Bi W., Chen X., Li Y., A New Neural Network Algorithm for Clique Vertex-Partition Problem, Yin F., Wang J., Guo C. (Ed.): ISNN 2004, LNCS 3173, Springer-Verlag, Berlin 2004, 425-29.
• [8] Kellerman E., Determination of keyword conflict, IBM Technical Disclosure Bulletin 16, 1973, 544-546.
• [9] Behrisch M., Taraz A., Efficiently covering complex networks with cliques of similar vertices, TCS: Theory of Computer Science 355, 2006, 37-47.
• [10] Cazals F., Karnade C., An algorithm for reporting maximal c-cliques, Theory of Computer Science 349, 2005, 484-490.
• [11] Gramm J., Guo J., Huffner F., Niedermeier R., Data reduction and exact algorithms for clique cover, ACM J. Exp. Algorith. 13, 2.2–2.15, 2009.
• [12] Tseng C., Siewiorek D., IEEE Trans. CAD 5, 379 (1986).
• [13] Harmanani H., A Parallel Neural Networks Algorithm for the Clique Partitioning Problem, IJCA, Vol. 9, No. 2, 2002
• [14] Little P., Rylander B., Problem Partitioning in Hybrid Genetic Algorithms, Proceedings of the 5th WSEAS Int. Conf. on circuits, systems, electronics, control and signal processing, Dallas, USA, November 1–3, 2006
• [15] Rizzo J., An Ant System Algorithm for Maximum Clique, The Pennsylvania State University, Master Thesis, 2003.
• [16] Orlin J., Contentment in graph theory: covering graphs with cliques, Mathematics 39, 1977, 406-424.
• [17] Snyers D., Clique Partitioning Problem and Genetic Algorithms in Albrecht R.F.(eds.), Artificial Neural Nets and Genetic Algorithms Springer-Verlag, 1993.
• [18] Tseng C., Sieworek D., Facet: A Procedure for the Automated Synthesis of Digital Systems, Proceeding of the 20th ACM/IEEE Design Automated Conf., 1983, 490-496.