Kernel matrix trimming for improved Kernel K-means clustering

Nikolaos Tsapanos; Anastasios Tefas; Nikolaos Nikolaidis; Ioannis Pitas

doi:10.1109/ICIP.2015.7351209

Kernel matrix trimming for improved Kernel K-means clustering

Nikolaos Tsapanos, Anastasios Tefas, Nikolaos Nikolaidis, Ioannis Pitas

Department of Electrical & Electronic Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

273 Downloads (Pure)

Abstract

The Kernel k-Means algorithm for clustering extends the classic k-Means clustering algorithm. It uses the kernel trick to implicitly calculate distances on a higher dimensional space, thus overcoming the classic algorithm's inability to handle data that are not linearly separable. Given a set of n elements to cluster, the n × n kernel matrix is calculated, which contains the dot products in the higher dimensional space of every possible combination of two elements. This matrix is then referenced to calculate the distance between an element and a cluster center, as per classic k-Means. In this paper, we propose a novel algorithm for zeroing elements of the kernel matrix, thus trimming the matrix, which results in reduced memory complexity and improved clustering performance.

Original language	English
Title of host publication	2015 IEEE International Conference on Image Processing (ICIP 2015)
Subtitle of host publication	Proceedings of a meeting held 27-30 September 2015, Quebec City, Quebec, Canada
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	2285-2289
Number of pages	5
ISBN (Electronic)	9781479983391
ISBN (Print)	9781479983407
DOIs	https://doi.org/10.1109/ICIP.2015.7351209
Publication status	Published - Jan 2016
Event	2015 IEEE International Conference on Image Processing (ICIP) - Quebec City, ON, Canada Duration: 27 Sep 2015 → 30 Sep 2015

Conference

Conference	2015 IEEE International Conference on Image Processing (ICIP)
Country/Territory	Canada
City	Quebec City, ON
Period	27/09/15 → 30/09/15

Access to Document

10.1109/ICIP.2015.7351209

Full-text PDF (accepted author manuscript)Accepted author manuscript, 235 KB

Cite this

Tsapanos, N., Tefas, A., Nikolaidis, N., & Pitas, I. (2016). Kernel matrix trimming for improved Kernel K-means clustering. In 2015 IEEE International Conference on Image Processing (ICIP 2015): Proceedings of a meeting held 27-30 September 2015, Quebec City, Quebec, Canada (pp. 2285-2289). Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/ICIP.2015.7351209

Tsapanos, Nikolaos ; Tefas, Anastasios ; Nikolaidis, Nikolaos ; Pitas, Ioannis. / Kernel matrix trimming for improved Kernel K-means clustering. 2015 IEEE International Conference on Image Processing (ICIP 2015): Proceedings of a meeting held 27-30 September 2015, Quebec City, Quebec, Canada. Institute of Electrical and Electronics Engineers (IEEE), 2016. pp. 2285-2289

@inproceedings{9db4c6a1acc749d4842e88f8c9b841d3,

title = "Kernel matrix trimming for improved Kernel K-means clustering",

abstract = "The Kernel k-Means algorithm for clustering extends the classic k-Means clustering algorithm. It uses the kernel trick to implicitly calculate distances on a higher dimensional space, thus overcoming the classic algorithm's inability to handle data that are not linearly separable. Given a set of n elements to cluster, the n × n kernel matrix is calculated, which contains the dot products in the higher dimensional space of every possible combination of two elements. This matrix is then referenced to calculate the distance between an element and a cluster center, as per classic k-Means. In this paper, we propose a novel algorithm for zeroing elements of the kernel matrix, thus trimming the matrix, which results in reduced memory complexity and improved clustering performance.",

author = "Nikolaos Tsapanos and Anastasios Tefas and Nikolaos Nikolaidis and Ioannis Pitas",

year = "2016",

month = jan,

doi = "10.1109/ICIP.2015.7351209",

language = "English",

isbn = "9781479983407",

pages = "2285--2289",

booktitle = "2015 IEEE International Conference on Image Processing (ICIP 2015)",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "2015 IEEE International Conference on Image Processing (ICIP) ; Conference date: 27-09-2015 Through 30-09-2015",

}

Tsapanos, N, Tefas, A, Nikolaidis, N & Pitas, I 2016, Kernel matrix trimming for improved Kernel K-means clustering. in 2015 IEEE International Conference on Image Processing (ICIP 2015): Proceedings of a meeting held 27-30 September 2015, Quebec City, Quebec, Canada. Institute of Electrical and Electronics Engineers (IEEE), pp. 2285-2289, 2015 IEEE International Conference on Image Processing (ICIP), Quebec City, ON, Canada, 27/09/15. https://doi.org/10.1109/ICIP.2015.7351209

Kernel matrix trimming for improved Kernel K-means clustering. / Tsapanos, Nikolaos; Tefas, Anastasios; Nikolaidis, Nikolaos; Pitas, Ioannis.

2015 IEEE International Conference on Image Processing (ICIP 2015): Proceedings of a meeting held 27-30 September 2015, Quebec City, Quebec, Canada. Institute of Electrical and Electronics Engineers (IEEE), 2016. p. 2285-2289.

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Kernel matrix trimming for improved Kernel K-means clustering

AU - Tsapanos, Nikolaos

AU - Tefas, Anastasios

AU - Nikolaidis, Nikolaos

AU - Pitas, Ioannis

PY - 2016/1

Y1 - 2016/1

N2 - The Kernel k-Means algorithm for clustering extends the classic k-Means clustering algorithm. It uses the kernel trick to implicitly calculate distances on a higher dimensional space, thus overcoming the classic algorithm's inability to handle data that are not linearly separable. Given a set of n elements to cluster, the n × n kernel matrix is calculated, which contains the dot products in the higher dimensional space of every possible combination of two elements. This matrix is then referenced to calculate the distance between an element and a cluster center, as per classic k-Means. In this paper, we propose a novel algorithm for zeroing elements of the kernel matrix, thus trimming the matrix, which results in reduced memory complexity and improved clustering performance.

AB - The Kernel k-Means algorithm for clustering extends the classic k-Means clustering algorithm. It uses the kernel trick to implicitly calculate distances on a higher dimensional space, thus overcoming the classic algorithm's inability to handle data that are not linearly separable. Given a set of n elements to cluster, the n × n kernel matrix is calculated, which contains the dot products in the higher dimensional space of every possible combination of two elements. This matrix is then referenced to calculate the distance between an element and a cluster center, as per classic k-Means. In this paper, we propose a novel algorithm for zeroing elements of the kernel matrix, thus trimming the matrix, which results in reduced memory complexity and improved clustering performance.

U2 - 10.1109/ICIP.2015.7351209

DO - 10.1109/ICIP.2015.7351209

M3 - Conference Contribution (Conference Proceeding)

SN - 9781479983407

SP - 2285

EP - 2289

BT - 2015 IEEE International Conference on Image Processing (ICIP 2015)

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - 2015 IEEE International Conference on Image Processing (ICIP)

Y2 - 27 September 2015 through 30 September 2015

ER -

Tsapanos N, Tefas A, Nikolaidis N, Pitas I. Kernel matrix trimming for improved Kernel K-means clustering. In 2015 IEEE International Conference on Image Processing (ICIP 2015): Proceedings of a meeting held 27-30 September 2015, Quebec City, Quebec, Canada. Institute of Electrical and Electronics Engineers (IEEE). 2016. p. 2285-2289 https://doi.org/10.1109/ICIP.2015.7351209

Kernel matrix trimming for improved Kernel K-means clustering

Abstract

Conference

Access to Document

Fingerprint

Cite this