Authors Yu. A. Kravchenko, A. N. Natskevich
Month, Year 07, 2017 @en
Index UDC 002.53:004.89
Abstract The article presents new model for solving clustering problem. Problem definition is pre-sented. Article describes some classic (k-means) and modern (kernel method, ensembles method, affinity propagation) algorithms for solving clustering problem. Overview of the research methods shows that most of them do not have a software implementation due to solving the problems of Brute-force of the sample objects. It is recommended to apply a model of the clustering system in which the objects of the training sample are completely processed only once at the step of creating initial class structure. This approach is based on the principles of evolutionary computation and allows increasing the dimension of the training sample until the required high quality of clustering is received. Moreover, the complexity of the mathematical model exponentially increases the complexity of the software implementation. Also the model complexity reduces the probability that this system will practically work. At the market can be implemented only systems, based on simple mathematical models. In this case, developer who interested in replicating his software product, creates a mathematical model, taking into account the possibilities of software implementation. The model should be as simple as possible, and implemented with lower costs and more qualitatively. The model proposed in this article is based on oriented bipartite graph and algorithms busting (for ant colony optimization algorithm and classic k-means algorithm). New approach for solving clustering problem is described. Ant colony optimization algorithm heuristic based on two techniques: common technique and iterative. Common technique is based on the single ant algorithm (for searching the graph path). Iterative technique involves the sequential construction of a solution by each individual colony agent, the subsequent evaluation of the solution and the search for the best solution is obtained. K-means algorithm realized solution search by using the averages class points (centroids). The use of boosting allows solving some problems of classical algorithms, such as the initial choice of the parameter k for the k-means algorithm and the problem of choosing the initial position of the centroids.The conducted researches showed that the solutions obtained with the use of the algorithm boosting approach allow obtaining solutions with identical or more increased quality to the solutions obtained by modern algorithms.

Download PDF

Keywords Clustering problem; evolutionary modeling; swarm algorithms; ant colony optimization; k-means.
References 1. Donkuan X. Yingjie T. A comprehensive survey of clastering algorithms, Annals of Data Sci-ence, 2015, Vol. 2, Issue 2, pp. 165-193.
2. Müller K., Mika S., Rätsch G. An introduction to kernel-based learning algorithms, IEEE Trans Neural Netw., 2001, No. 12, pp. 181-201.
3. Filippone M., Camastra F., Masulli F. A survey of kernel and spectral methods for clustering, Pattern Recognit, 2008, Vol. 41, pp. 176-190.
4. Schölkopf B., Smola A., Müller K. Nonlinear component analysis as a kernel eigenvalue problem, Neural Comput., 1998, Vol. 10, pp. 1299-1319.
5. Radha C., Rong J., Timothy C.H., Anil K.J. Scalable Kernel Clustering: Approximate Kernel k-means, Computer Vision and Pattern Recognition, 2014.
6. Yoon H., Ahn S., Lee S., Cho S., Kim J. Heterogeneous clustering ensemble method for com-bining different cluster results, In: Data mining for biomedical applications, 2006, pp. 82-92.
7. Punera K., Ghosh J. Consensus-based ensembles of soft clusterings, ApplArtifIntell, 2008, Vol. 22, pp. 780-810.
8. Busting. Primenenie v oblasti mashinnogo obucheniya [Boosting. Application in the field of machine learning]. Available at: 91%D1%83%D1%81%D1%82%D0%B8%D0%BD%D0%B3 (accessed 28 April 2017).
9. Lebedev B.K., Lebedev O.B. Modelirovanie adaptivnogo povedeniya murav'inoy kolonii pri poiske resheniy, interpretiruemykh derev'yami [Modelling of an ant colony adaptive behaviour by search of the decisions interpreted by trees], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 27-34.
10. Lebedev B.K., Natskevich A.N. Reshenie odnorodnoy raspredelitel'noy zadachi metodom modelirovaniya povedeniya murav'inoy kolonii [The solution of the homogeneous distribution of tasks by modeling the behavior of ant colonies], Informatika, vychislitel'naya tekhnika i inzhenernoe obrazovanie [Informatics, computer science and engineering education], 2015, No. 4 (24), pp. 7-15.
11. Gladkov L.A., Kravchenko Y.A., Kureichik V.V. Evolutionary Algorithm for Extremal Subsets Comprehension in Graphs, World Applied Sciences Journal, 2013, Vol. 27 (9), pp. 1212-1217.
12. Kureychik V.M., Kazharov A.A. Ispol'zovanie shablonnykh resheniy v murav'inykh algoritmakh [Template using for ant colony algorithms], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2013, No. 7 (144), pp. 11-17.
13. Kureychik V.M. Osobennosti postroeniya sistem podderzhki prinyatiya resheniy [Features of decision making support system design], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 7 (132), pp. 92-98.
14. Kureychik V.V., Rodzin S.I. O pravilakh predstavleniya resheniy v evolyutsionnykh algoritmakh [On the rules for the submission decisions in evolutionary algorithm], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7 (108),
pp. 13-21.
15. Bova V.V., Kravchenko Y.A., Kureichik V.V. Decision Support Systems for Knowledge Man-agement, Software Engineering in Intelligent Systems. Proceedings of the 4th Computer Science On-line Conference 2015 (CSOC2015). Springer International Publishing AG Switzerland, Vol. 3, pp. 123-130.
16. Gladkov L.A., Kureychik V.M., Kureychik V.V. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2006, 320 p.
17. Kureychik V.V., Bova V.V., Kureychik Vl.Vl. Kombinirovannyy poisk pri proektirovanii [Com-bined search in the design], Obrazovatel'nye resursy i tekhnologii [Educational resources and technology], 2014, No. 2 (5), pp. 90-94.
18. Kureychik V.V., Kureychik Vl.Vl. Bionicheskiy poisk pri proektirovanii i upravlenii [Search in-spired by natural systems, for the design and management], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2012, No. 11 (136), pp. 178-183.
19. Zaporozhets D.Yu., Zaruba D.V., Kureichik V.V. Hybrid bionic algorithms for solving prob-lems of parametric optimization, World Applied Sciences Journal, 2013, No. 23 (8), pp. 1032-1036.
20. Kureychik V.V., Zaporozhets D.Yu. Roevoy algoritm v zadachakh optimizatsii [Swarm algorithm in optimisation promlems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7 (108), pp. 28-32.
21. Sandro V.P., Jyrko C.M., José R.S. Weighted Partition Consensus via Kernels, Pattern Recog-nition, 2010, Vol. 43(8), pp. 2712-2724.
22. Karpov V.E. Vvedenie v rasparallelivanie algoritmov i programm [Introduction to parallel algorithms and software], Komp'yuternye issledovanie i modelirovanie [Computer research and modeling], 2010, Vol. 2, No. 3, pp. 231-272.

Comments are closed.