Information-Theoretic Distance Measures for Clustering Validation: Generalization and Normalization

doi:10.1109/TKDE.2008.200

	Information-Theoretic Distance Measures for Clustering Validation: Generalization and Normalization
	Luo, Ping 1,2; Xiong, Hui 3; Zhan, Guoxing 4; Wu, Junjie 5; Shi, Zhongzhi 6
	2009-09-01
发表期刊	IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
ISSN	1041-4347
卷号	21 期号:9 页码:1249-1262
摘要	This paper studies the generalization and normalization issues of information-theoretic distance measures for clustering validation. Along this line, we first introduce a uniform representation of distance measures, defined as quasi-distance, which is induced based on a general form of conditional entropy. The quasi-distance possesses three properties: symmetry, the triangle law, and the minimum reachable. These properties ensure that the quasi-distance naturally lends itself as the external measure for clustering validation. In addition, we observe that the ranges of the distance measures are different when they apply for clustering validation on different data sets. Therefore, when comparing the performances of clustering algorithms on different data sets, distance normalization is required to equalize ranges of the distance measures. A critical challenge for distance normalization is to obtain the ranges of a distance measure when a data set is provided. To that end, we theoretically analyze the computation of the maximum value of a distance measure for a data set. Finally, we compare the performances of the partition clustering algorithm K-means on various real-world data sets. The experiments show that the normalized distance measures have better performance than the original distance measures when comparing clusterings of different data sets. Also, the normalized Shannon distance has the best performance among four distance measures under study.
关键词	Clustering validation entropy information-theoretic distance measures K-means clustering
DOI	10.1109/TKDE.2008.200
收录类别	SCI
语种	英语
资助项目	National Basic Research Priorities Program[2007CB311004] ; National Basic Research Priorities Program[2003CB317004] ; National Science Foundation of China[60435010] ; National Science Foundation of China[90604017] ; National Science Foundation of China[60675010] ; National Science Foundation of China[60775035] ; 863 Project[2006AA01Z128] ; 863 Project[2007AA01Z132] ; Rutgers Business School-Newark ; New Brunswick
WOS研究方向	Computer Science ; Engineering
WOS类目	Computer Science, Artificial Intelligence ; Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS记录号	WOS:000268062400002
出版者	IEEE COMPUTER SOC
引用统计	被引频次：13[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/11493
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Luo, Ping
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100084, Peoples R China 2.Hewlett Packard Labs, Beijing 100084, Peoples R China 3.Rutgers State Univ, Dept Management Sci & Informat Syst, Rutgers Business Sch, Newark, NJ 07102 USA 4.Wayne State Univ, Dept Comp Sci, Detroit, MI 48202 USA 5.Beihang Univ, Dept Informat Syst, Sch Econ & Management, Beijing 100191, Peoples R China 6.Chinese Acad Sci, Inst Comp Technol, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Luo, Ping,Xiong, Hui,Zhan, Guoxing,et al. Information-Theoretic Distance Measures for Clustering Validation: Generalization and Normalization[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2009,21(9):1249-1262.
APA	Luo, Ping,Xiong, Hui,Zhan, Guoxing,Wu, Junjie,&Shi, Zhongzhi.(2009).Information-Theoretic Distance Measures for Clustering Validation: Generalization and Normalization.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,21(9),1249-1262.
MLA	Luo, Ping,et al."Information-Theoretic Distance Measures for Clustering Validation: Generalization and Normalization".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 21.9(2009):1249-1262.