Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20] [ 21] [ 22] [ 23] [ 24]

@

Journal of Information Science and Engineering, Vol. 26 No. 2, pp. 649-658 (March 2010)

A Novel Spectral Clustering Method Based on Pairwise Distance Matrix

CHI-FANG CHIN1, ARTHUR CHUN-CHIEH SHIH2 AND KUO-CHIN FAN1,3
1Institute of Computer Science and Information Engineering
National Central University
Chungli, 320 Taiwan
E-mail: annking@iis.sinica.edu.tw
2Institute of Information Science
Academia Sinica
Taipei, 115 Taiwan
E-mail: arthur@iis.sinica.edu.tw
3Department of Informatics
Fo Guang University
Ilan, 262 Taiwan
E-mail: kcfan@csie.ncu.edu.tw

In general, the similarity measure is indispensable for most traditional spectral clustering algorithms since these algorithms typically begin with the pairwise similarity matrix of a given dataset. However, a general type of input for most clustering applications is the pairwise distance matrix. In this paper, we propose a distance-based spectral clustering method which makes no assumption on regarding both the suitable similarity measure and the prior-knowledge of cluster number. The kernel of distance-based spectral clustering is that the symmetric LoG weighted matrix constructed by applying the Laplace operator to the pairwise distance matrix. The main difference from the traditional spectral clustering is that the pairwise distance matrix can be directly employed without transformation as a similarity pairwise matrix in advance. Moreover, the inter-cluster structure is embedded and the intra-cluster pairwise relationships are maximized in the proposed method to increase the discrimination capability on extracting clusters. Experiments were conducted on different types of test datasets and the results demonstrate the correctness of the extracted clusters. Furthermore, the proposed method is also verified to be robust to noisy datasets.

Keywords: spectral clustering, laplace operator, LoG weighted matrix, pairwise distance matrix, PoD histogram

Full Text () Retrieve PDF document (201003_19.pdf)

Received March 14, 2008; revised May 23, 2008; accepted June 5, 2008.
Communicated by H. Y. Mark Liao.