On the Existence of Kernel Function for Kernel-Trick of k-Means in the Light of Gower Theorem

• Autorzy: Kłopotek Mieczysław A.

Identyfikatory

DOI

10.3233/FI-2019-1822

• Języki publikacji: EN

Abstrakty

EN

This paper, constituting an extension to the conference paper [1], corrects the proof of the Theorem 2 from the Gower’s paper [2, page 5]. The correction is needed in order to establish the existence of the kernel function used commonly in the kernel trick e.g. for k-means clustering algorithm, on the grounds of distance matrix. The correction encompasses the missing if-part proof and dropping unnecessary conditions.

Słowa kluczowe

EN

kernel trick; k-means; Gower Theorem; Euclidean embedding; kernel function

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 168, nr 1
• Strony: 25--43
• Opis fizyczny: Bibliogr. 22 poz.

Twórcy

autor

Kłopotek Mieczysław A.

• Institute of Computer Science of the Polish Academy of Sciences, ul. Jana Kazimierza 5, 01-248 Warsaw, Poland

Bibliografia

• [1] Klopotek MA. On the Existence of Kernel Function for Kernel-Trick of k-Means. In: Foundations of Intelligent Systems-23rd International Symposium, ISMIS 2017, Warsaw, Poland, June 26-29, 2017, Proceedings. 2017 pp. 97-104. doi:10.1007/978-3-319-60438-1_10.
• [2] Gower J. Euclidean Distance Geometry. Math. Scientist, 1982. 7:1-14.
• [3] Dhillon I, Guan Y, Kulis B. Kernel K-means: Spectral Clustering and Normalized Cuts. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’04. ACM, New York, NY, USA. ISBN 1-58113-888-1, 2004 pp. 551-556. doi:10.1145/1014052.1014118.
• [4] Schölkopf B. The Kernel Trick for Distances. In: Advances in Neural Information Processing Systems 13. Max-Planck-Gesellschaft, MIT Press, Cambridge, MA, USA, 2001 pp. 301-307. URL http://papers.nips.cc/paper/1862-the-kernel-trick-for-distances.pdf.
• [5] Balaji R, Bapat R. On Euclidean distance matrices. Linear Algebra and its Applications, 2007. 424(1):108-117. doi:10.1016/j.laa.2006.05.013.
• [6] Cox TF, Cox MAA. Multidimensional Scaling. Chapman & Hall, London, 2nd edition, 2000. ISBN-10:1584880945, 13:978-1584880943.
• [7] Schoenberg IJ. Metric spaces and positive definite functions. Trans. Amer. Math. Soc., 1938. 44:522-536. URL https://doi.org/10.1090/S0002-9947-1938-1501980-0.
• [8] Schoenberg I. Remarks to Maurice Frchets article Sur la dfinition axiomatique dune classe despace distancis vectoriellement applicable sur lespace de Hilbert. Annals of Mathematics, 1935. 36(3):724-732. doi:10.2307/1968654.
• [9] Li C, Georgiopoulos M, Anagnostopoulos GC. Kernel-based Distance Metric Learning in the Output Space. In: International Joint Conference on Neural Networks (IJCNN). Dallas, TX, August 04-09, 2013 pp. 1-8. doi:10.1109/IJCNN.2013.6706862.
• [10] Pekalska E, Paclik P, Duin RPW. A Generalized Kernel Approach to Dissimilarity-based Classification. J. Mach. Learn. Res., 2002. 2:175-211. doi:10.1162/15324430260185592.
• [11] Nikolentzos G, Meladianos P, Vazirgiannis M. Matching Node Embeddings for Graph Similarity. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA. 2017 pp. 2429-2435.
• [12] Pavoine S, Dufour AB, Chessel D. From dissimilarities among species to dissimilarities among communities: a double principal coordinate analysis. Journal of Theoretical Biology, 2004. 228(4):523-537. doi:10.1016/j.jtbi.2004.02.014.
• [13] Handhayania T, Hiryantob L. Intelligent Kernel K-Means for Clustering Gene Expression. In: International Conference on Computer Science and Computational Intelligence (ICCSCI 2015) Procedia Computer Science, 2015. 59:171-177. URL https://doi.org/10.1016/j.procs.2015.07.544.
• [14] Sarma T, Vishwanath P, Reddy B. Single pass kernel k -means clustering method. Sadhan, 2013. 38, Part 3:407-419.
• [15] Tzortzis G, A L. The global kernel k-means algorithm for clustering in feature space. IEEE Trans Neural Netw., 2009. 7(20):1181-94. doi:10.1109/TNN.2009.2019722.
• [16] Chitta R, Jin R, Havens TC, Jain AK. Approximate Kernel K-means: Solution to Large Scale Kernel Clustering. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’11. ACM, New York, NY, USA. ISBN 978-1-4503-0813-7, 2011 pp. 895-903.
• [17] Yao Y, Chen H. Multiple Kernel k-Means Clustering by Selecting Representative Kernels, 2018. arXiv: 1811.00264.
• [18] Dokmanic I, Parhizkar R, Ranieri J, Vetterli M. Euclidean Distance Matrices: Essential Theory, Algorithms and Applications. 2015. doi:10.1109/MSP.2015.2398954. arXiv:1502.07541.
• [19] Wierzchoń S, Kłopotek M. Modern Clustering Algorithms, volume 34 of Studies in Big Data. Springer Verlag, 2018. ISBN 978-3-319-69307-1.
• [20] Wierzchoń S, Kłopotek M. Algorithms of Cluster Analysis, volume 3 of Monograph Series. Institute of Computer Science of Polish Academy of Sciences Publishing House, 2015. ISBN 978-83-63159-10-8.
• [21] Gower J, Legendre P. Metric and Euclidean properties of dissimilarity coefficients. Journal of classification, 1986. 3(1):5-48. Here Gower: 1982 is cited in theorem 4, but with a different form of conditions for D and s. doi:10.1007/BF01896809.
• [22] Gower J. Properties of Euclidean and non-Euclidean distance matrices. Linear Algebra and its Applications, 1985. 67:81-97. URL https://doi.org/10.1016/0024-3795(85)90187-9.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).