k-means类型变量加权聚类算法的研究与实现.pdf

Classified Index:
:




Dissertation for the Master Degree of Engineering
RESEARCH AND IMPLEMENTATION
ON VARIABLE WEIGHTING IN
K-MEANS TYPE CLUSTERING



Candidate: Li Xiao Ming
Supervisor: Prof. Xu Xiao Fei
Associate Supervisor: Associate Prof. Ye Yun Ming
Academic Degree Applied for: Master of Engineering
Specialty: Computer Science and Technology
Affiliation: Shenzhen Graduate School
Date of Defence: June, 2006
Degree-Conferring-Institution: Harbin Institute of Technology
哈尔滨工业大学工学硕士学位论文
摘要

迄今为止,人们已经提出了许多聚类算法。由于 k-means 类型算法在对
大规模数据进行聚类时效率较高而且具有处理数值属性和分类属性的能力,
从而被广泛应用在市场研究和数据挖掘领域中。
然而,在数据挖掘过程中,应用 k-means 类型算法的一个主要问题就是
变量选择问题。k-means 类型算法在聚类过程中对每一个变量都同等看待,
不具备自动选择变量的能力。实际上,一个用户感兴趣的聚类结构通常只限
定在变量集合的一个子集上,而并非整个变量集合,由于包含了某些噪音变
量可能会掩盖了聚类结构的发现。在现实世界的数据库中,例如大银行中的
客户数据库, 通常包含大量的属性(变量),而每个变量对聚类结果的贡献
都不相同。因此,怎样从大量的变量当中选择合适的变量进行聚类是一个非
常困难并且非常重要的问题。
本文实现了一个基于k-means的变量自动加权聚类算法W-k-means,并通
过在模拟数据上与不带权重的k-means类型算法和具有固定权重的k-means
类型算法进行了实验分析,证明了W-k-means算法在识别噪音变量和发现聚
类能力上的优越性。其次,本文基于W-k-means 算法并结合K-mode和
K-prototypes算法,分别提出了处理分类属性的变量加权聚类算法W-k-mode
和处理数值和分类混合属性的变量加权算法W-k-prototypes,并通过实验证
明其发现聚类能力的优越性。最后,基于W-k-prototypes算法实现了一个符
合业界标准CRISP(Cross Industry Standard Process for Data Mining)模型的
聚类分析系统。

关键词数据挖掘;聚类分析;变量加权;







- I -
哈尔滨工业大学工学硕士学位论文
Abstract

So far, many clustering algorithms have been proposed, but the k-means
type clustering algorithms are widely used in real world applications such as
marketing research and data mining to cluster very large data sets due to their
efficiency and ability to handle numeric and categorical variables that are
ubiquitous in real databases.
However, a major problem of using the k-means type algorithms in data
mining is selection of variables. The k-means type algorithms can’t select
variables automatically because they treat all variables equally in the clusting
process. In pratice, an interesting c