K-Means Clustering for Problems with Periodic Attributes

0328432 - ÚI 2010 RIV SG eng J - Journal Article
Vejmelka, Martin - Musílek, P. - Paluš, Milan - Pelikán, Emil
K-Means Clustering for Problems with Periodic Attributes.
[Shlukovací algoritmus K-Means v problémech s periodickými atributy.]
International Journal of Pattern Recognition and Artificial Intelligence. Roč. 23, č. 4 (2009), s. 721-743. ISSN 0218-0014. E-ISSN 1793-6381
R&D Projects: GA AV ČR 1ET400300513
EU Projects: European Commission(XE) 517133 - BRACCIA
Institutional research plan: CEZ:AV0Z10300504
Keywords : clustering algorithms * similarity measures * K-means * periodic attributes
Subject RIV: BB - Applied Statistics, Operational Research
Impact factor: 0.512, year: 2009

The K-means algorithm is very popular in the machine learning community due to its inherent simplicity. However, in its basic form, it is not suitable for use in problems which contain periodic attributes, such as oscillator phase, hour of day or directional heading. A commonly used technique of trigonometrically encoding periodic input attributes to artificially generate the required topology introduces a systematic error. In this paper, a metric which induces a conceptually correct topology for periodic attributes is embedded into the K-means algorithm. This requires solving a non-convex minimization problem in the maximization step. Results of numerical experiments comparing the proposed algorithm to K-means with trigonometric encoding on synthetically generated data are reported. The advantage of using the proposed K-means algorithm is also shown on a real example using gas load data to build simple predictive models.

Algoritmus K-means je díky své jednoduchosti velmi populární v oblasti strojového učení. Ve své základní formě však není vhodný k použití v problémech s periodickými atributy, jakými jsou např. fáze oscilátoru, hodina dne, nebo azimut. Běžně používaná technika trigonometrického zakódování periodických atributů vytvářející deformovanou kruhovou topologii vnáší do řešení systematickou chybu. V této práci je do algoritmu K-means zapracována metrika, která indukuje kruhovou topologii bez deformací. Použití této metriky vyžaduje vyřešení nekonvexního minimalizačního problému v kroku maximalizace algoritmu K-means. Dále jsou shrnuty numerické experimenty porovnávající shlukování pomocí trigonometrického kódování a pomocí navrhované modifikace K-means algoritmu. V závěru je popsána úloha shlukování dat odběru plynu a vytvoření jednoduchých prediktivních modelů, kde je patrné zlepšení přesnosti v důsledku použití nové modifikace algoritmu K-means.
Permanent Link: http://hdl.handle.net/11104/0174747