子空间聚类算法的研究及应用

《子空间聚类算法的研究及应用》由会员分享，可在线阅读，更多相关《子空间聚类算法的研究及应用（65页珍藏版）》请在装配图网上搜索。

1、江苏大学硕士学位论文子空间聚类算法的研究及应用姓名：高亚鲁申请学位级别：硕士专业：计算机应用技术指导教师：宋余庆20090607江苏大学硕士学位论文摘要随着市场竞争的日益加剧和信息技术的飞速发展，企业的经营模式逐步由“以产品为中心转向“以客户为中心”。这就要求企业根据客户的特征对客户进行细分，进而对不同的类型的客户提供不同的产品或服务。传统的客户细分方法一般是基于经验的分类方法或基于统计的简单划分方法，这些方法不再适合当前市场。根据客户属性的高维特性，本文选择了子空间聚类技术，对算法进行改进，提出聚类算法，并用聚类算法进行客户细分，实现了科学合理的划分，为市场决策提供了可靠的依据。本文对客户细

2、分进行了研究，主要包括以下工作：第一针对算法中硬性的网络划分导致的复杂度增大，精度较低的不足，本文提出了算法，该算法对网格空间中位于簇边缘的网格单元进行细化处理，减小了网格划分对聚类精度造成的损失。不同于传统的基于网格聚类算法，算法对和稠密网格单元相邻的稀疏网格单元进行二次处理，然后重新确定网格的边界。第二算法使用网格密度阈值函数来判定网格单元的类型，实现了参数的自动化确定，解决了依赖手工确定参数密度阈值的问题。通过对事务进行压缩、减少连接次数和数据库扫描次数，来提高算法执行的效率。江苏大学硕士学位论文，：（），（），（）江苏大学硕士学位论文，：，学位论文版权使用授权书本学位论文作者完全了解学

3、校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口，在年解密后适用本授权书。本学位论文属于不保密囱。学位论文作者签名：高亚鲁指导教师签名卵）年莎月，日年扫月日娟年只，独创性申明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以

4、明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：高增俨甲年月日江苏大学硕士学位论文课题背景和意义第一章绪论随着世界经济的全球化、市场经济的国际化、信息技术的飞速发展以及管理手段的不断进步，企业与企业之间的竞争越来越激烈。由于同行业之间的产品差别越来越小，企业很难通过产品的差异或产品的价格等优势来提升自身的竞争力（。在这种情况下，企业的工作重心正逐步由“以产品为中心向“以市场为中心、“以客户为中心转变。因为客户是企业最重要的资源，所以如何有效挖掘和利用客户资源成了企业面临的难题。客户关系管（）就是在这样的背景下产生的，其核心思想是将客户作为企业最重要的资源，通过完善自身

5、服务和满足客户的需求，保证客户的终生价值。客户细分作为客户关系管理的重要组成部分，是企业在明确的战略、业务模式和特定的市场中，根据客户的属性、行为、需求、喜好以及价值等因素对客户进行分类，并提供有针对性的产品、服务和营销模式的过程。正确的客户细分能够有效的降低成本，使企业获得更大的收益。传统的客户细分方法一般是基于经验的分类方法或基于统计的简单划分方法，这些方法基本都是依靠决策者的经验来完成的，虽然这些划分对企业的客户管理起到了帮助作用，但却无法发现客户的潜在需求以及客户的忠诚度，并且无法实现客户分类等。随着客户数量的飞速增长，面对海量的客户数据，传统的划分方法显得力不从心。数据挖掘的出现，为

6、解决复杂的客户细分问题提供了有效的方法。数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、人们事先不知道的、但是潜在有用知识的过程。它是一门广义的交叉学科，涉及人工智能技术，统计技术与数据库技术等多种技术，汇集了不同领域的研究者，尤其是数据库、人工智能、数理统计等方面的学者和技术人员。数据挖掘可以从海量数据中发现有用信息并抽取出人们关心的模式，找出数据变化规律和数据之间的相互依存的关系，使人们能够从宏观高层次的角度来审视数据，充分挖江苏大学硕士学位论文掘数据的潜藏价值，指导人们的行为，为决策提供科学的强有力的支持。数据挖掘能够帮助企业确定客户的特点，从而可以为客户

7、提供有针对性的服务，在方面有着广泛的应用，例如产品或服务设计，提高客户的满意程度，建立以客户为中心的营销策略，为有不同需求的客户提供个性化的服务。聚类分析是数据挖掘的一个重要研究方向。聚类是指将物理或抽象对象集合分成相似的对象类的过程。通过聚类，人们能够识别密集的和稀疏的区域，从而发现全局的分布模式和数据属性之间有趣的关联。聚类分析已经广泛地应用于许多领域，包括模式识别、数据分析、图像处理。迄今为止，人们提出了很多聚类算法，例如划分的方法、层次的方法、基于密度的方法、基于网格的方法和基于模型的方法。不同的算法有着不同的应用环境，有的适用于大数据集，可以发现任意形状的聚类；有的算法思想简单，适用

8、于小的数据集。总的来说，算法都是试图用不同的途径对数据集进行高效的、可靠的聚类分析。鉴于聚类算法具有上述特点，商业上常常采用这种技术进行市场细分，客户细分等。在生物学中，聚类能够推导植物和动物的分类，基因分类等。企业通过聚类分析实现客户细分，得到具有不同特征的客户群，进而帮助营销人员制定不同的有针对性的策略，提高客户的价值贡献。基于聚类的客户细分是利用聚类技术发现隐藏在客户数据库中的潜在知识，将客户分成若干个具有相似特征的客户群，并对客户群进行有效地客户价值评估。基于聚类的客户细分可以有效地解决多种市场问题，实现高效的、差异化的精确营销，在银行业、电信业、证券业、制造业、零售业等领域都有广泛的

9、应用价值和商业前景。可见，基于聚类的客户细分也有很好的学术价值。国内外研究现状及存在的问题聚类分析已广泛研究了许多年，大多集中在基于距离的聚类分析。基于均值，中心点和其他一些方法的聚类分析工具已经加入到许多统计分析软件包或者系统中，例如，以及。在机器学习领域，聚类是无监督学习的一个例子，与分类不同，聚类和无监督学习不依赖预先定义的类和类标号的训练实例。由于这种原因，聚类是观察式学习，而不是示例式学习。国外对客户关系管理的研究已经提出了一些应用于客户细分聚类算法，例如模江苏大学硕士学位论文糊聚类算法应用于股票交易客户细分【】，应用模糊聚类算法对在线音乐用户进行细分，聚类算法对零售商场客户细分【】

10、等。国外有些相关产品也采用了聚类：是由加拿大大不列颠哥伦比亚省大学“智能数据库系统研究实验室”创建，由公司做进步的开发而形成的产品。是一个通用的联机分析挖掘（：）系统，用在大型关系数据库和数据仓库中交互地挖掘多层次的知识。其独特之处在于紧密集成了联机分析处理（：）和多种数据挖掘功能，包括特征化、关联、分类、预测和聚类等。产品：通过访问和数据。构造模型的过程有引导。支持数据挖掘算法：神经网络，分类和回归树，最近邻居、遗传算法、基于记忆的推理、聚集和贝叶斯算法。年月，网通北京分公司和网通国际部开始建立自己的宽带客户价值金字塔，并进行了客户细分，但除了客户价值以外，所有的细分指标都是单因素，只有客户

11、价值是综合细分。年中国联通引入客户细分理念，但直到年才真正开始客户细分。年联通少数的几个省尝试进行单因素细分，结果比较理想。中国电信从年开始就根据用户的性质、消费额度将其细分，从目前的情况来看，客户细分己经取得一定的效果。由于电信行业营运商引入了客户细分的理念，国内的开发商相应地推出了各自的客户细分产品。国内也有公司运用聚类分析方法来进行客户行为预测和客户细分。例如湖南移动采用聚类算法对客户进行细分以辅助营销决策；另外还有一些将均值聚类，系统聚类法，模糊均值聚类算法应用于银行客户细分的实验等。目前，电信行业的客户关系管理及数据挖掘技术的应用在理论界和企业界都是研究的热点。这极大地推动了数据挖掘

12、在现实中的应用，但是从现状来看，还存在一些值得改进的地方：（）从数据挖掘工具的开发上看，目前仍然以横向的、通用性的挖掘工具为主，而向行业的纵向数据挖掘土具较少。从国内情况看，尚未出现行业版的数据挖扼工具，但数据挖掘的行业应用是未来发展的一大趋势。如何将普适性的江苏大学硕士学位论文数据挖掘方法和模型应用于具体行业问题是摆在大家面前的一个重要课题。（）目前的一些研究只是从某个角度或是某个层而上对问题进行分散和孤立的研究，同时在现有的研究中，着重于算法的应用，而缺乏从企业的生产经营系统分析、数据抽取、数据预处理、模型构建与评价等一整套完整的解决方案。（）基于数据挖掘的客户分类，一般都采用经典的聚类算

13、法。虽然可靠性得到了保证，但是其效率和精度受到了影响。研究内容与主要创新点论文着重研究了数据挖掘中的聚类问题及其在客户分类中的应用，深入探讨了子空间聚类算法和客户细分模型，并针对其存在的问题进行了深入的分析，进而提出了切实可行的解决方法。论文的主要创新点包括以下几个方面：详细探讨了几类主要的聚类算法，分析了它们各自的代表算法及其优缺点，并指出了现有算法存在的问题，提出了针对客户细分的解决方法。讨论了高维数据的聚类分析，针对现有的高维子空间聚类算法效率不高，随着包含簇的子空间的最大维度的增加，时间复杂度通常呈指数级增长的问题，提出了子空间算法刈。该算法通过对网格划分进行优化，实现了密度阈值参数的

14、自动化确定，解决了依赖手工确定参数密度阈值的问题。通过对事务进行压缩、减少连接次数和数据库扫描次数，来提高算法的效率。通过实验比较算法、算法和算的性能和精度，算法无论是精度还是性能都优于另外两种算法。将算法应用到客户细分模型以及电信客户细分中。论文的结构概要本文共分为六章，具体安排如下：第一章介绍课题选题背景、研究意义，国内过研究的现状以及论文研究的主要内容和创新点，同时还介绍了本文的组织结构。第二章介绍了客户细分的产生及其概念，客户细分的原因，详细介绍了客户江苏大学硕士学位论文细分的方法，其中包括分析法、客户价值矩阵分析法、数据挖掘客户细分法。第三章详细介绍了几类主要的聚类分析方法，并分析了

15、它们各自的代表算法，主要包括基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于。网格的聚类和基于模型的聚类算法。对它们的各自代表性的算法适用范围进行了探讨。第四章讨论了高维数据集的聚类分析，针对现有的高维子空间聚类算法效率不高，随着包含簇的子空间的最大维度的增加，时间复杂度通常呈指数级增长，提出了子空间算法。该算法通过对网格划分进行优化，实现了密度阈值参数的自动化确定，解决了依赖手工确定参数密度阈值的问题。通过对事务进行压缩、减少连接次数和数据库扫描次数，来提高算法的效率。第五章将算法应用到客户细分模型中，对整个客户细分模型进行了研究，并将其应用到电信客户细分模型。第六章系统地总

16、结本文研究工作，并提出下一步需要研究的内容。江苏大学硕士学位论文第二章客户细分的概述客户细分的产生及其概念客户细分理论的产生【客户细分是现代营销理念的产物，是第二次世界大战后西方发达国家市场营销理论和战略的新发展。它主要是指企业在明确的战略、业务模式和专注市场中，根据客户的价值、需求和喜好等综合因素对客户进行分类的，为不同的客户群提供有针对性的产品、服务和营销模式。经过了若干年的发展，客户细分的理论和方法不断的完善，而被广泛的应用到营销中。客户细分理论的提出和应用是有一定客观原因的，它是商品经济发展和市场竞争日益激烈的产物。其理论依据主要有以下两个方面：（）客户需求的差异性。也就是说，不同的客

17、户需求是不一样的，任何两个客户的需求都是不同的。由于客户需求、欲望和购买力呈现多样性，所以在购买产品和使用服务上有较大的差异。客户需求的异质性是进行客户细分的内在依据。（苟企业资源的有限性。企业受到了自身实力的限制，不可能提供满足所有顾客的产品和服务。这样不同的企业瞄准了不同的客户群体，为了进行有效的竞争，企业必须进行客户细分，选择最有利可图的目标群体，集中资源，制定有效的战略计划，增强企业的竞争优势。客户细分的概述【所谓的客户细分就是企业在收集和整理客户的信息资料的基础之上，依据客户的需求特点、购买行为、消费习惯、信誉状况等方面的明显差异，把某一产品的客户整体划分为若干个客户群的分类过程。客

18、户细分让同一客户群中的客户相似性尽可能的大，不同的客户群中的客户相似性尽可能小。通过客户细分实现差异化的销售，满足不同客户的不同需求，提高客户的忠诚度。客户分类结果的正确性取决于分类指标和分类方法的选择。分类指标主要来源于企业积累的数据，这些数据包括客户的基本情况数据、客户与企业的交易数据及江苏大学硕士学位论文其它的交互数据。根据数据属性的特点，本文将其分为客户的内在属性数据和消费行为数据。内在属性数据：一般指客户的内在因素所决定的属性，比如年龄，性别，收入，婚姻状况，家庭成员数，信仰等等。消费行为数据：是指客户与企业进行交易或其它交互所积累的数据。比如客户购买频率，购买金额以及最近购买情况等

19、。这些数据按照时间积累就会成为一种时间序列数据，它反映了客户与企业之间进行交易的整个过程，反映了客户的消费行为和消费习惯等其它两种数据不能体现的特征。由此我们可以看出，客户内在属性数据基本是不会变化的，所以我们又将这两种类型的数据称为客户静态属性数据：同理，客户消费行为数据，跟时间密切相关，被称为客户动态属性数据。基于客户静态属性数据得客户分类方法是比较容易而且比较直观，因此目前很多客户分类方法都是基于客户的静态属性数据的，但是具有类似客户静态属性的客户群体也会有类似的消费行为的假设是不完全正确的，这些分类方法对于客户的动态属性数据考虑较少，不利于全面反映客户特征和提高分类的准确性。由动态属性

20、和静态属性构成的客户数据是高维数据，对客户进行分类，实际上就是对高维数据进行分类。这对研究人员提出了更高的要求。客户细分的原因随着人们物质生活水平的提高，人们对个性化的需求也越来越强烈，消费者开始追求与自己生活方式贴近的消费方式，这样的倾向日益明显。客户群体因其收入、年龄、职业等属性的不同而呈现出来的消费特性差别也比较大。此外，即使是同一客户在不同的阶段可能有着不同服务需求，客户需求的差异是客户细分的基础。企业竞争益激烈，企业的竞争由“以产品为中心”向“以客户为中心”转变。这意味着客户成为企业最重要的资源。企业为了保留原来的老客户，发展新客户，而进行客户细分，同时客户细分也是开发新产品的重要基

21、础。客户数据挖掘产生的客户细分，与传统的经验细分相比，能够考虑更多的行为属性，得到更丰富的细分可能性。每个客户群体具有更鲜明的行为特征。但是，什么样的江苏大学硕士学位论文客户细分结果才是好的昵？将客户分成多少才是比较合适的呢？群体间的人数悬殊是不是一个很差的细分结果？这些都是客户细分需要研究和解决的问题。客户细分是一种双赢的行为。既能满足客户的需求，又能给企业带来丰厚的利润。未来企业之间的竞争是市场的竞争，是客户的竞争，因此客户细分对增强企业的竞争力有非常大的意义。客户细分是客户识别与定位、客户价值预测、新产品和新市场的开发、设计最优的营销策略。客户细分方法分析法分析是广泛应用于数据库营销的一

22、种客户细分方法。（）指上次购买至今期间，该时期越短，则越大。研究发现，越大的客户越有可能与企业达成新的交易，越大，企业保存该客户的数据就越准确，因此企业有的数据会迅速失效，每隔一年大约有一半以上的数据都不准确了。（）指在某一期间购买的次数，交易次数越频繁的客户越有可能和公司形成新的交易。（）指在某一期间内购买的金额。越大越有可能和企业达成新的交易。分析的所有成份都是行为方面的，应用这些容易获得的因素，能够预测客户的购买行为。以最近的行为来预测客户的购买行为。这种方法比其它采用一个因素的方法都准确和有效。进行分析，所有的客户记录都必须包含特定的交易历史数据，并准确的标号。分析给客户的每个指标打分

23、，然后计算。在确定、的值时，不能采取主观赋值的办法，例如图，对于某位客户，他过去的个月内购买了产品，则确定该客户的，对值进行了主观的赋值会带来问题。最好通过对客户的，按照期的进行倒序排列，这样可以将客户分成若干个相同的部分，离得当前期越近，权值就越大，否则越小，这样的赋值更合理一些，同时对、也按照同样的方法进行赋值。然后计算的值，最后把计算结果从大到小排序，前面的是最好的客户，企业应该尽量保持他们，因为他们给企业带来了绝大部分的利益；后面的是企业应该避免的客户；中间的的客户是企业尽量争取的，尽量挖掘这部分客户的潜能，将他们培养成企业的忠实客户。江苏垄堂塑主兰堡垒查一。一。分析是一种有效的客户细

24、分方法，在企业开展促销活动后，重新计算每个客户的，对比促销前后的，可以清楚的看到客户受该活动的影响情况，为企业开展更有效的营销活动提供可靠的依据。其缺点是分析过程复杂，时问耗费比较大，而且客户细分得到的客户群体也比较多，难以对客户群体有较准确的理解，也就是难以对客户群制定有效的营销战略。删分析的另外一个缺点是购买次数与同期的总购买额（）这瞬个变量之间存在着多重共性。所以该方法有一定的局限性。最近，次交易时问距今时间最近一次交易时间距今时间最近一次交易时间距今时间最近一次交易时问距今时间最近一次交易时间距今时间率率率率为为为为图删实例分析图蠹为客户价值矩阵分析法为了消除购买次数与总购买额间的多重

25、共性，对传统的分析进行修正，用平均购买额代替总购买额。另外，为了解决传统的分析过程中客户划分的缺陷，该方法提出了用购买次数与平均购买额构成的价值矩阵简化细分结果（图所示）。第三个变量在客户价值矩阵中被剔除，与其他的变量（如交易类型、类的长度与客户价值矩阵）结合使用。江苏大学硕士学位论文高购买次数氐购买额度高图客户价值矩阵形成客户价值矩阵需要的信息有：客户代码、代码日期、购买额、购买次数由不同的购买日期的数目确定，购买额用来计算平均购买额。可以由最近的购买同期确定，其可以用最近的购买日期减去最早的购买同期计算得到。交易类型需要收集产品信息。地理、人口统计学、偏好等方面的信息也可以与客户价值矩阵结

26、合使用。在提出的客户价值矩阵中，确定购买次数与平均购买的基准是各自的平均值，一旦确定每一个坐标轴的平均值，就确定每个客户所在的象限。然后，分析每个象限中的客户群的关键差异。客户价值矩阵的优点是细分方法有了针对性，对每个客户群制定不同的营销战略和战术。最好的客户代表了企业的基础，保持是必要的；乐于消费型，最适合战略是增加他们的购买频率，对于频繁消费，他们通过不断的购买证明了自己的忠诚，最好的战略是通过交叉销售、向上销售增加他们的平均购买额；对不确定型的客户，最好的战略可以描述为慎重精选，把营销努力集中于不确定型的新客户和那些对某些具体的产品感兴趣的客户。结合其他的客户信息，客户价值矩阵能够制定跨

27、越客户群的营销战略战术，强化客户保持。等人提出，客户之间存在着至少五种一般类型的差别：对产品利益的偏好、客户相互作用的影响、选择障碍、讨价还价的能力、盈利能力。认为，按这种差别分类能够修正或改进现有的客户细分方法，当一个或者多个差别在客户中存在但没有被考虑时，细分是次优的。例如，当一个购买频率很高的客户被关注时，同时他的平均购买额低，即该客户属于频繁消费类型，那么这可能是选择障碍引起的，客户可能由于知识、感知、转移成本、信息处理方式的缺陷而没有做出高额的购买江苏大学硕士学位论文决策，而这种选择障碍可以由营销者产生、强化、弱化、破坏：也有可能不同类型客户为企业推荐了很多其他的客户，由于客户相互作

28、用影响而带来的口碑宣传，如果忽视了这种情况，企业会损失由该客户带来的潜在客户，分析和客户价值矩，阵都没有全面考虑用户之间的这五种差别。数据挖掘客户细分法数据挖掘是随着计算机的广泛应用和数据的大量积累而发展起来的，它同数据库知识发现和数据仓库有着密切的联系。数据挖掘是指从存放在数据库、数据仓库或其他信息库中的大量数据中自动地发现相关模式、提取有潜在价值的信息、挖掘知识的过程。从的角度，数据挖掘应用就是从大量数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和规则，并能够根据已有的信息对未来发生的行为进行结果预测，为企业经营决策、市场规划等提供依据。根据数据挖掘任务划分，包含如下几种知识发现任

29、务：分类知识发现、数据总结、数据聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常发现和趋势预测等。客户细分是企业开展客户关系管理的第一步，能够根据客户价值细分客户是客户关系管理成功实施的前提条件。客户关系管理是对企业和客户之间的交互活动进行管理的全过程，是一种旨在改善企业与客户之间关系的新型管理机制，其核心思想是将企业的客户（包括最终客户、分销商和合作伙伴）作为企业最重要的资源，通过完善的客户服务和深入的客户分析来满足客户的要求，保证客户的最终价值。在中应用的主要技术有：统计、聚类、决策树、神经网络和关联规则。对于要挖掘的数据，可以是来自传统的关系数据库，也可以建立面向主题的、采

30、用多维数据立方体组织数据的数据仓库。因此用数据仓库组织高维数据十分有效，可以经常使用联机分析处理和可视化处理进行多维分析。本章小结本章主要介绍了客户细分理论形成和产生，客户细分的概念；客户细分的原因等。详细介绍了客户细分的方法，其中包括分析法、客户价值矩阵分析法、数据挖掘客户细分法。江苏大学硕士学位论文第三章聚类分析算法弟二早聚矢万忻异友聚类的基本概念“物以类聚，人以群分”，聚类是按照事物的某种属性，将事物聚成簇的过程，聚类的目标是使得类内的对象尽可能的相似，类之间的对象尽可能的相异。与分类不同，聚类是自动探测数据集中相似群体的无监督学习过程。在聚类过程中，通常没有先验知识作为指导。聚类分析源

31、于多个研究领域，包括数据挖掘、统计学、生物学以及机器学习等。聚类分析在许多领域都得到了广泛的应用，如市场和客户细分，模式识别、生物学研究、空问数据分析、文档分类等。聚类分析可以作为一个独立的数据挖掘方法，用于了解数据的分布情况，也可以作为其它数据挖掘算法的预处理步骤。基本的数据分类有如下几种】：划分聚类算法、层次聚类算法、密度聚类算法、网格聚类算法以及模型聚类算法。本章首先介绍聚类分析的基本概念，然后介绍各聚类算法的聚类性能。聚类的定义聚类可以定义为【】：在数据空间中，数据集由许多数据点（或数据对象）组成，数据点秽，口，；的每个属性（或特征、或维度）。，既可以是数值类型，也可以是枚举类型。数据

32、集相当于一个的矩阵。假设数据集中有个对象；（，如。聚类的最终目的是把数据集划分为个类（，），也可能有些对象不属于任何一个类，这些就是噪声。所有这些分割与噪声的并集是数据集，并且这些分割之问没有交集，即：【，（）这些就是聚类。江苏大学硕士学位论文聚类有效性的评价聚类的有效性评价是对聚类效果的度量，通常需要结合具体的应用场景，但是仍然存在一些客观的评价聚类效果的标准。聚类的质量受到如下因素的影响：初始值的选择、聚类数量的选择、聚类方法的选择等【。下面是常用的三种评价标准：定义分离系数：（，）三圭窆）（）假设为所有的聚类结果，则的最优值由下式决定：警警刑）扣扩七！分离系数描述了所有输入样本相对于簇心

33、的接近程度。如果每个样本仅属于一个类，且此时较大，那么数据的不确定性较小。定义分离熵：日，七）一三童窆。）（）假设为所有的聚类结果，则的最优值由下式决定：学警日叫，）扣扩，上如果所有的接近或，则熵值较小，所给出的聚类结果就较好；反之，如果“接近，则聚类的模糊程度就高，熵就越大，聚类结果就差。定义紧致与分离效果函数：刚：萼掣假设为所有的聚类结果，则的最优值由下式决定：丫【百即）扣，扩（）江苏大学硕士学位论文（，）是输入样本与它们相应的聚类中心聚类的平均值与聚类中最小间距的比值。一个好的聚类方法是聚类中一，的间距尽可能大，而样本与聚类中一，的间距尽可能小。由于紧密性与分离函数综合考虑了紧密性与分离

34、性这两个方面，因此（，）函数的性能最好。主要的聚类方法分类在过去的十年中，提出了许多有关聚类分析的算法。聚类算法的选择取决于聚类问题中的数据类型以及实际的应用场景。以下我们主要介绍几种聚类方法以及他们各自的代表算法【。划分方法划分的聚类方法为给定的数据集合指定合理的划分，每个对象都被指定给唯一的簇。簇的个数是需要用户指定的输入参数。给定一个包含个对象的数据集和要生成的簇的数目，基于划分的聚类算法将数据对象组织为个划分（），其中每个划分构成一个簇，根据所采用的相似度函数的差异，不同的算法通常具有不同的划分标准，以便簇中对象是相似的，簇之间的对象是相异的。（）算法最著名与最常用的基于划分的聚类算法

35、是算法【及它的各种变体。算法以为参数，把个对象划分为个簇，使簇内具有较高的相似度，簇间具有较低的相似度。相似度的计算由一个簇对象的平均值来决定。算法的流程如下：首先随机选取个对象作为初始的个簇心；然后将剩余的每个对象根据其与各个簇一，的距离分配到最近的簇中；重新计算每个簇的簇心，直到准则函数收敛为止。通常采用的目标函数形式为平方误差准则函数：盹，（）其中，是数据库中所有对象的平方误差的总和，是空间中的点，表示给定数据对象，；是簇的平均值。这个准则试图使生成的簇尽可能的紧凑独立。算法中计算相异度的方法是欧几里德距离，当然也可以采用其他的距离度量方式。算法的步骤如下：江苏大学硕士学位论文算法：输入

36、：，输出：个簇）随机选择个对象作为初始簇的中心；）根据簇中对象的平均值，将每个对象赋值给最近似的簇；）更新簇的平均值，即簇心；）簇心不再发生变化，则返回划分结果，否则转）；算法试图找出使平方误差函数值最小的个划分，当结果簇是密集的，并且簇与簇之间有明显的界限时，算法效果较好。算法的时间复杂度为（），其中为数据集中对象的数目，为目标簇的个数，为迭代的次数。因此算法对于大规模数据集来说具有较高的可扩展性。一般情况下，算法能够收敛于局部最优解。然而，算法只有簇的平均值被定义才可以使用。这可能不适应于某种应用，例如涉及用于分类属性的数据。同时，算法要求给出（要生成簇的数目），这要求用户具有较多的背景知

37、识。此外，算法不适合发现非凸面形状的簇，或者大小差别比较大的簇，而且对于孤立点数据和输入对象的顺序都比较敏感。（）算法算法和算法过程类似，他们的区别在于：算法用簇中最靠近中心的对象来代表簇，而算法用质心来代表簇。由于极大的值能够对质心的计算产生很大的影响，算法对孤立点数据异常敏感。而算法通过用中心来代替质心，可以有效地消除这种影响。聚类算法的基本策略是首先，随机选择个对象作为初始的个簇代表点来代替代表点，检查聚类的质量是否有所提高。若是，则保留该替换，否则放弃该替换，重复上述过程，直到不再发生变化为止。聚类结果的质量用一个代价函数来估算。各种不同的算法中，较为常见的有算法【、算法、算法等。算法

38、是最早的算法之一。该算法是经过多次迭代进行的算法，如果数据集的大小和簇的数目较大，该算法的性能可能会比较差。江苏大学硕士学位论文算法采用抽样来处理大型数据集。该算法首先对整个数据库进行抽样，用抽样得到的代表集代替原数据集合，然后使用算法从中选择簇的中心点。如果抽样是按照随机的方式进行的，那么在抽样数据集中得到的中心点就会与整个原数据集中得到的中心点非常近似。算法对原数据集进行多次抽样，并对每一个抽样都应用算法。然后，从中选择最优的作为最后的输出。该算法的性能和聚类结果都与抽样的大小紧密相关。如果抽样有偏差，就不会得到好的聚类结果。算法是在算法和算法的基础上发展而来的。它通过对图的随机搜索来发现

39、代表簇的中心点。该算法需要两个输入参数：每个节点要检查的最大邻居数目和需要搜索的局部极小点的数目。首先选择一个节点，然后检查该节点的邻居，并且重复上述过程，直到检查该节点的一个邻居为止。如果代价变小，则移动该邻居，并重复上述过程，直到检查了最大邻居数个邻居。否则，就称当前节点为局部极小点。该算法主要缺点是效率低，除此之外，因为搜索和修改抽样方法的影响，所以，可能会找不到真正的局部最小点。该算法还要求所有包含在聚类中的对象都必须装入内存，这就限制了可以检查的数据的大小，尽管该算法的聚类结果与数据的输入顺序无关，但是它只能识别简单的聚类形状，而不能识别其他复杂的聚类形状。此外，也没有处理高维数据的

40、能力。由于采用了随机抽样方法，所以当噪声比较多的时候，它可能找到的是噪声的局部极小点而不是聚类的局部极小点，从而产生错误的聚类结果。虽然算法不需要事先知道聚类的簇的数目，但是它需要输入两个参数：最大邻居数和局部极小点的数目。此外聚类效果和抽样效果相关。层次方法层次聚类方法将数据对象形成一棵以簇为节点的树。根据层次分解是自底向上还是自顶向下形成，层次的聚类方法可以分为凝聚的和分裂的层次聚类【。凝聚类的层次聚类方法首先将每个对象作为一个簇，然后合并这些原子簇，直到所有的对象都在一个簇中，或者满足某个终止条件。而分裂的层次聚类则首先将所有对象置于同一个簇中，然后逐渐细分越来越小的簇，直到每个对象自成

41、一个簇，或者到达终止条件。例如到达了某个希望的终止数目，或者最近两个簇的聚类超过江苏大学硕士学位论文了某个阈值。层次聚类方法可以在不同粒度的水平上对数据进行探测，而且容易实现相似度量或者距离的度量。但是单纯的层次聚类算法的终止条件含糊，而且执行合并或分裂簇的操作不可修正，这很可能导致聚类结果质量很低。另外，由于需要检查和估算大量的对象或簇才能决定簇的合并或分裂，所以这种方法的可扩展性较差。因此，通过在解决实际聚类问题时要把层次方法和其他的方法结合起来。多种聚类算法的结合形成多阶段的聚类，有效改善聚类的质量。（）算法】算法通过集成层次聚类和其他聚类算法对大量数据进行聚类，其中层次聚类用于初始的微

42、聚类阶段，而后使用其他方法如迭代划分方法。它克服了凝聚聚类方法所面临的两个困难：（）可伸缩性；（）不能撤销前一步所做的工作。算法中引入了两个概念：聚类特征和聚类特征树。他们分别用于概括簇的描述，这些结构帮助聚类方法对于大型数据库中取得较好的速度和伸缩性，使得该算法对增量和动态聚类也非常有效。聚类特征（）是一个三元组，它给出了一个簇的信息汇总描述。假设某个字簇中有个维的点或对象（，则该子簇的聚类特征如下：（，）其中，为子簇中点的数胃，是个点的线性和（即：玉），是数据点的平方和（即二）。反映的是质心位置，反映簇的大小，即凝聚程度。树是一棵高度平衡树，它存储了层次聚类的特征。它包含两个参数：分支因子

43、和阈值。分支因子定义了每个非叶节点子女的最大数目，而阈值存储在树叶节点中子簇的最大直径。这两个参数影响结果树的大小。采用了一种多阶段聚类技术：数据集合的单遍扫描产生一个基本的聚类，然后再经过一遍或者多遍扫描进一步进行优化和改进聚类质量。它主要包括两个阶段：（）首先扫描数据库，建立一个初始存放在内存的树，它可以看作数据的压缩，试图保留数据内在的聚类结构。（）采用某个聚类算法对的叶节点进行聚类，把稀疏的簇看作离群点删除，而稠密的簇用于合并为更大的簇。由于受到树的每个节点的大小限制，可能导致节点并不总是对应于用户所江苏大学硕士学位论文认为的一个自然簇。而且，如果簇不是球形的，算法不能很好地工作，因为

44、它采用了直径的概念来控制聚类的边界。（）算法算法【】是一种层次聚类算法，针对具有分类属性的数据使用链接这一概念。链接定义两个点公共邻近点的个数。如果连接数越大，则它们可能属于相同的簇，由于点与点之间的关系考虑相邻的数据点，因此，比其他只关注相似度的标准聚类方法显得更加鲁棒。算法使用一个相似度阈值和共享近邻的概念从一个给定的数据相似度矩阵中首先构建一个稀疏矩阵图。然后在这个稀疏矩阵图上执行凝聚层次聚类。使用一个优度度量评价聚类。采用随机采样度量大规模数据集。算法在最坏情况下的时间复杂度为（朋以），其中和分别是最近邻数目的最大值和平均值，是对象的个数。（）算法刎算法是一种层次聚类算法，采用动态的建

45、模确定簇对之间的相似度。算法是对层次聚类算法算法和算法缺点的改进。算法忽略了关于簇的邻近度信息。算法则忽略了关于簇的互联性。在算法中，簇的相似度由簇中对象的互联度和簇的邻近度来评定。也就是说，如果两个簇的互联性都很高并且它们又靠得很近就将它们合并。这样，就不用依赖于静态的，用户指定的模型，能够自适应的合并簇的内部特征。这一合并过程有利于发现自然的和同构的簇，只要定义了相似度函数就可以应用于所有类型的数据。算法通常采用最近邻居图的方法来描述对象，通过两个簇的相对互联性砌和相对邻近度来决定它们之间的相似度。两个簇和之的相对互连性（，），定义为和之间的绝对互连性，关于两个簇的内部互连性的规范化，即：

46、彤心，）面而丽（，）（）其中（，）是把和组成的簇分裂为和的边割集，（）是将江苏大学硕士学位论文对应的子图划分为大致相等的两部分需截断的边割集。两个簇和之间的相对近似性把（，）定义为和之间的绝对接近度关于两个簇内部接近性的规范化，即：删。孺乔，），卜，卜川（）其中船俺岛）是连接和！顶点的边平均权重，腑（，是】在（中边的平均权重，表示在中数据点的个数。算法首先利用图划分算法将数据对象聚类划分为若干个相对较小的子簇，然后采用凝聚的层次聚类算法合并子簇，从而发现真正的结果簇。算法选择砒和都高的簇进行合并，实质上就是合并既有良好的互连性又相互接近的两个簇。与等算法相比，算法在发现高质量的任意形状的簇方面

47、有更强的能力。不过，在处理个对象的高维数据时，算法的最坏复杂度达到）。基于密度的方法传统的聚类算法使用距离来描述数据之间的相似性，然而，对于非球状数据集来说，只用距离来描述是不够的。此类问题需要用密度来代替相似性的度量，因此产生了基于密度的聚类算法这一分支。基于密度的算法从数据的分布密度出发，把密度足够大的区域连接起来，从而可以发现任意形状的簇。此外，该类算法还能够去除噪声点的影响。常见的基于密度的聚类算法有、和等。（）算法算法将具有足够高密度的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的簇，它定义簇为密度相连的点的最大对象集，这涉及到如下一系列的定义：邻域：给定对象半径内的

48、区域称为该对象的邻域。核心对象：如果一个对象的邻域至少包含最小数目个对象，则称该对象为核心对象。江苏大学硕士学位论文直接密度可达：给定一个对象集合，如果是在的一邻域内，而是一个核心对象，我们说对象从对象出发是直接密度可达的。密度可达：如果存在一个对象链，。，而对（），是从关于和密度可达的，则对象是从对象关于和密度可达的。密度相连：如果对象集合中存在一个对象，使得对象和是从关于和密度可达的，那么对象和是关于和密度相连的。密度可达是直接密度可达的传递闭包，满足传递性，但不满足对称性，只有核心对象之间的密度可达关系满足对称性。一个基于密度的簇是基于密度可达性的大的密度相连对象的集合，不包含在任何簇中

49、的对象被认为是噪声点。算法通过检查数据库中每个点的一邻域来搜索聚类。如果点的一邻域包含的点多于个，则创建一个以为核心对象的新簇。然后，迭代地聚集从这些核心对象直接可达的对象，这个过程可能涉及一些密度可达聚类的合并。当没有新的点可以添加到任何簇时，该过程结束。算法能够识别各种复杂形状的聚类，并能有效排除噪声的干扰，并且聚类结果不受输入顺序的影响。但由于该算法需要用户确定输入参数，而现实的高维数据集中，往往很难准确地确定聚类参数，因此它不适用于高维数据集。此外它对参数非常敏感，参数值的微小变化往往会导致差异很大的聚类结果。（）算法算法计算一种聚类顺序，用于自动循环分析，是对算法的扩展。算法引入了两个概念：核心距离和可达距离。一个对象的核心距离是指使成为核心对象最小；一个对象关于另一个对象的可达距离是指的核心距离和与的欧几罩德距离之间的较大值。核心距离和可达距离都是针对核心对象来定义的。算法没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个簇次序。这个次序代表了数据的基于密度的聚类结构。它包含的信息，等同于从一个宽广的参数设置范围所获得的基于密度的聚类。