Metoda ewolucji różnicowej w klasteryzacji z ograniczeniami twardymi

• Autorzy: Dziedzic M. , Łukasik S.

Warianty tytułu

EN

Differential evolution method in hard constrained clustering /

• Języki publikacji: PL

Abstrakty

PL

Gwałtowny wzrost pojemności baz danych oraz znaczne zwiększenie wymiarowości rozpatrywanych zbiorów wymusza wykorzystanie do ich analizy skutecznych metod komputerowych. Głównym celem artykułu jest zaprezentowanie możliwości zastosowania oraz skuteczności ewolucji różnicowej w zadaniu klasteryzacji z ograniczeniami, które stanowi wariant jednego z najważniejszych zagadnień eksploracji danych. W artykule przedstawiono formalnie zadanie klasteryzacji z ograniczeniami oraz metodę ewolucji różnicowej wraz z jej implementacją Zaprezentowano również wyniki badań eksperymentalnych, w tym dotyczących klasteryzacji zestawów przebiegów czasowych. Mogą być one zinterpretowane jako przykład grupowania pomiarów wartości elektrycznych.

EN

Rapid increase of database capacity and high dimensionality of considered datasets forces the usage of effective computer methods to their analysis. The main goal of this paper is a presentation of possibility of employing and efficiency of Differential Evolution in the constrained clustering, a variant of one of the most important data mining tasks. In the paper the constrained clustering task and Differential Evolution method, with it's implementation, was presented. Moreover, the results of the experimental studies were shown, including the clustering of time series set. It could be interpreted as an example of grouping of electrical variables measurement.

Słowa kluczowe

PL

eksploatacja danych; ewolucja różnicowa; klasteryzacja z ograniczeniami; metody heurystyczne

EN

constrained clustering; data mining; Differentia Evolution; heuristic methods

• Wydawca: Wydawnictwo Politechniki Krakowskiej im. Tadeusza Kościuszki
• Czasopismo: Czasopismo Techniczne. Elektrotechnika
• Rocznik: 2010
• Tom: R. 107, z. 1-E
• Strony: 3--20
• Opis fizyczny: Bibliogr. 22 poz.,Wz., tab., wykr.,

Twórcy

autor

Dziedzic M.

autor

Łukasik S.

• Katedra Automatyki i Technik Informacyjnych, Wydział Inżynierii Elektrycznej i Komputerowej, Politechnika Krakowska

Bibliografia

• [1] Basu S., Davidson I., Wagstaff K., Constrained Clustering: Advances in Algorithms, Theory and Applications, Chapman and Hall/CRC, 2009.
• [2] Bilenko M., Basu S., Mooney J., Integrating Constraints and Metric Learning in Semi-Supervised Clustering, Proceedings of the Twenty-First International Conference on Machine Learning, 2004, 11-18.
• [3] Das S., Abraham A., Konar A., Particle Swarm Optimization and Differential Evolution Algorithms: Technical Analysis, Applications and Hybridization Perspectives, [w:] Advances of Computational Intelligence in Industrial Systems, pod red. Liu Y., Sun A., Loh H.T., Lu W.F., Lim E.-P., Springer, 2008, 1-38.
• [4] Demiriz A., Bennett K.P., Embrechts M.J., Semi-Supervised Clustering Using Genetic Algorithms, Proceedings of Artificial Neural Networks in Engineering (ANNIE'99), 1999, 809-814.
• [5] Dryer M.,Frieze A.M., A Simple Heuristic for the p-Centre Problem, Operations Research Letter 3(6), 1985, 285-288.
• [6] Ferligoj A., Batagelj V., Clustering with Relational Constraint, Psychometrica 47(4), 1982, 413-426.
• [7] Frank A., Asuncion A., UCI Machine Learning Repository, [online] 2010-11-30, (dostępny w Internecie: http://archive.ics.uci.edu/ml/).
• [8] Kaelo P., Ali M.M., A numerical study of some modified differential evolution algorithms, European Journal of Operational Research, 169(3), 2006, 1176-1184.
• [9] Keogh E.J., Pazzani M.J., Derivative Dynamie Time Warping, Proceedings of First SIAM International Conference on Data Mining, 2001, 187-194.
• [10] MacQueen J.B., Some methods for classification and analysis of multivariate observations, Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967, 281-297.
• [11] Michalewicz Z., Fogel D.B., How to Solve it: Modern Heuristics, Springer, 2000.
• [12] Paterlini S., Krink T., Differential evolution and particle swarm optimization in partitional clustering, Computational Statistics & Data Analysis 50(5), 2006, 1120-1247.
• [13] Pedersen M.E.H., Tuning & SimplifyingHeuristical Optimization, praca doktorska, University of Southampton, 2010.
• [14] Price K., Storn R.M., Lampinen J.A., Differential Evolution: A Practical Approach to Global Optimization, Springer, 2005.
• [15] Pyle D., Data Preparation for Data Mining, Morgan Kauffman, 1999.
• [16] R and W.M., Objective Criteria for the Evaluation of Clustering Methods, Journal of the American Statistical Association, 66(336), 1971, 846-850.
• [17] Storn R., Price K., Differential Evolution - A simple and efficient adaptive scheme for global optimisation over continuous spaces, raport instytutowy TR-95-012, ICSI, 1995.
• [18] Storn R., On the Usage of Differential Evolution for Function Optimization, NAFIPS'96, 1996, 519-523.
• [19] Storn R., Price K., Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization 11, 1997, 341-359.
• [20] Storn R., Differential Evolution Homepage, [online] 2010-11-30, (dostępny w Internecie: http://www.icsi.berkeley.edu/~storn/code.html).
• [21] Wagstaff K., Cardie C., Clustering with Instance-level Constraints, Proceedings of the 17th International Conference on Machine Learning, 2000, 1103-1110.
• [22] Wagstaff K., Cardie C., Rogers S., Schroedl S., Constrained k-means Clustering with Background Knowledge, Proceedings of the 18th International Conference on Machine Learning, 2001, 577-584.