资源描述：
《考虑数据分布的K-均值聚类研究.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、附件2论文中英文摘要作者姓名：吴俊杰论文题目：考虑数据分布的K・均值聚类研究作者简介：吴俊杰，男，1979年7月出生，2002年9月师从于清华大学陈剑教授，于2008年1月获博士学位。中文摘要1…商务智能通常被理解为将企业中现有的数据转化为知识，帮助企业做岀明智的业务经营I••I决策的工具。数据挖掘是商务智能的核心技术之一。实践表明，数据挖掘已经被广泛应用于II客户细分和客户行为分析、冃标市场定位、金融价格预测和风险管理、工作流管理、欺诈检Ii测等商业领域，对企业的决策支持、成本管理、组织协同等提供了极大的帮助。随着信息搜iIIi索、电子商务和Web2.0的迅猛发展，数据挖掘将
2、为信息抽取、管理与使用发挥更大的作用，I•I聚类分析是数据挖掘研究的重要子领域。聚类分析为探索未知的数据结构提供帮助，并II能成为一系列数据分析的起点。聚类分析已长时间在市场营销、生产监测、信息检索与分类I
3、等商业领域发挥重要作用。在聚类分析的众多算法中，K-均值算法因其简单、高效、鲁棒、
4、；数据适应性强等优点得到了非常广泛的应用。许多文献已经对K-均值算法的特点进行了深入:••I研究，并针对海量数据、高维数据、流式数据、噪声数据等现实问题提出了许多改进方法。II然而，无论从理论、算法还是实践层而，考虑到商务实践中大量数据的不均衡分布特征，仍Ii有很多极具挑战性的问题亟待解决：
5、iII；■是否所有适于K-均值聚类的距离函数都具有统一的泛化形式？；••
6、-是否数据的不均衡分布会对K-均值聚类带来不利影响？
7、
8、-如何在数据不均衡分布的情况下对K-均值聚类结果进行客观评价？
9、
10、-能否利用K-均值算法这样的无监督学习去提高有监督学习一一如数据分布极端不平衡
11、；的稀有类分析问题一一的绩效？：I•
12、有鉴于此，本文围绕商务智能中广泛使用的聚类分析方法一一K-均值算法，在考虑数据
13、1不均衡分布的统一框架下，做了如下工作：1••IIII一、K-均值算法距离函数的泛化理论研究；••II
14、我们对所有适于K-均值算法的距离函数进行泛化，提出一个新的概念：K-均值距离
15、■:（K
16、-meansdistance）。该距离具有统一的形式，核心要素是其中的一个凸函数；通过使用不：:;同的凸函数，可以得到一族K-均值距离。包括平方欧几里德距离、KL散度、余弦相似度等为1I•i人熟知的接近度函数，都是K-均值距离的特例。我们严格证明了，K-均值距离适用于K-均值iII
17、聚类；而在一定的假设条件下，K-均值距离也是适用于K-均值聚类的唯一距一离函数。提出这
18、
19、么一个泛化的距离函数是非常有益的，这主要体现在：1）有助于我们把握适于K-均值聚类
20、
21、的距离函数的共同特点，从而能够从本质上认识K-均值聚类的某些独特性质，如第三部分研
22、1究的“均匀效应”；2）有助于我们从一个
23、较高的层面来考察以及改进传统的K-均值算法，如iII
24、第二部分利用SBIL解决K-均值算法无法在稀疏数据上直接计算KL散度的问题。（相关研究
25、:;发表于ICDM2007ri11）ii二、SBIL算法的设计与应用研究i■I•I
26、我们基于K-均值距离对传统的K-均值目标函数进行了简化，并基于简化的目标函数设计
27、i了一个新颖的增量学习算法：SBILoSBIL仍然具有K-均值算法高效运算的特点，但无需直接
28、:计算数据与簇心的K-均值距离，这对于Info-K-means(基于KL散度的K-均值算法)是至关i
29、重要的。一直以来，由于在稀疏数据上计算KL散度会出现分母为零的情况，Info-K
30、-means］
31、被认为在文木数据上比SphericalK-means(基于余弦相似度的K-均值算法)的聚类效果差J［然而，利用SBIL只需计算各簇心的某个凸函数值这一特点，我们可以巧妙地绕开KL散度的
32、1直接计算，为Info-K-means的实践应用奠定了基础。我们在大量的高维文木数据上进行了实If1i验。实验结果表明：1)直接计算KL散度的确给Info-K-means分配数据对象带来了困难，模
33、j拟退火(annealing)和更新策略的改变没有实质性地提高Info-K-means的聚类效果；2)对］I数据的光滑处理可以部分地提高Info-K-means的聚类绩效，但由于数据的
34、稀疏性被改变，而I•I［且光滑参数的设置缺乏规律性，因此在实践中很难取得令人满意的效果；3)基于SBIL的1••
35、Info-K-means显示出了优良的聚类性能，其在大量数据集上的聚类效果不逊于甚至稍强于目
36、:前最好的高维数据聚类工具CLUTO实现的SphericalK-meanso(相关研究发表于KDD200891)i!
37、t
38、fII三、数据分布对K-均值算法的影响研究!•II•
39、我们研究了K-均值算法与数据分布的关系。我们发现，在一定条件下(如各类中心比较
40、〔接近、数据集的可聚类性不是非常
