聚类分析及算法研究 王国祝 （河北省张家口市桥西区人防信息保障中心，河北张家口０７５０００） 摘要：聚类分析已经成为数据挖掘中的一项重要技术，是分析数据并从中发现有用信息的一种有效手段。 伴随着计算机存储技术和计算能力的提升，仿生学、人工智能技术的进步，为聚类分析的发展创造了良好的条件， 各种聚类分析算法层出不穷。因此基本的聚类的类型特征基础上，对基于这些类型且应用较为广泛的算法思想 归纳总结，比较算法的优劣，指出存在的问题和不足，寄希望于从中得到一些启发，使聚类分析的方法有新的发展 和发现。 关键词：数据挖掘；聚类分析；聚类方法 中图分类号：Ｆ２３ 文献标识码：Ａ １ 引言 随着数据收集和数据存储技术的快速进步使得各 组织机构可以积累海量数据，如何从大规模的数据存 储中自动地发现有用信息，从而诞生了数据挖掘技术。 数据挖掘技术不但发现未知数据库的应用模式，而且， 通过数据挖掘还可以预测未来结果。聚类分析作为统 计学的一个基本方法，已不断的发展为数据挖掘中的 一项重要技术，成为从数据库中发现有用信息的一种 有效手段。应用于生物学、社会学、医学、环境科学、信 息检索、商业策划、图像处理等诸多领域。例如，生物 学家从早期创建所有生物体的系统分类学，到如今使 用聚类分析大量的遗传信息，发现具有类似功能的基 因组；通过搜索引擎可以从数以亿计的Ｗｅｂ页面中搜 索到数百上千个具有共同性质或特征的网页；分析客 户的购买数据或销售数据预测客户未来的需求，为商 业策划提供决策依据。 聚类分析是从海量的数据中发现有用信息的过 程，其本质是把不同类别或不同属性的数据区别开来， 其核心的依据数据样本的特征不同，采用不同的方法 即算法实现聚类，随着数字化的迅速发展，数据不论是 数量还是类型都在不断的扩展，各种聚类分析算法也 层出不穷，针对各种算法存在的缺陷和不足，新的改进 算法和探索途径在不断产生。针对不同的数据对象， 依据什么选择算法以及选择哪种算法，给应用者带来 困惑。本文在阐述基本的聚类分析的类型特征的基础 上，对基于这些类型且应用较为广泛的算法思想归纳 总结，比较算法的优劣，指出存在的问题和不足，寄希 望于从中得到一些启发，使聚类分析的方法有新的发 展和发现。 ２聚类的基本类型 人类早先基于“物以类聚”的朴素思想，运用统计 学的方法对事物进行分类，这就是最原始的聚类，比如 物种的分类，就是从数据中发现所描述的对象及其关 系的信息。聚类分析与分类不同，信息时代，聚类的含 义已发生了深刻的变化，它是从海量数据库或数据对 象中，去发现数据对象的相似或相异（不相似），究竟有 无相异的对象子集？这样的子集又有多少？这些事先 都是未知的。也就是说，聚类分析所要发现的类及其 类的数量都是未知的。 聚类分析发现知识和信息的过程分以下四个步 骤： （１）数据预处理，从数据库中选择与目标任务相关 的数据集，或者具有某种特征的数据集，转换或规范成 适合分析的数据。 （２）分析数据特征，判断聚类的类型，选择合适的 聚类算法对数据集进行聚类，发现相似的或共同性质 的类。 （３）验证和评价聚类结果，以确定对数据集的划分 和评判所得结果是否是有效的、正确的。 （４）对结果进行解释，即分析和理解聚类结果，从 中得到有用的信息。 数据集经过聚类分析划分成若干个子集，即分成 不同的类或组，每个子集在聚类分析中通常称为一个 簇。所有簇的集合称为聚类。依据簇的不同形态，存 在不同类型特征的聚类。 ２．１基于原型的聚类——划分聚类 仅当数据包含在相互远离的自然簇时，簇中每个 对象到同簇中的其他对象的距离比到不同簇中任意对 象的距离都近（或更加相似）。这种聚类称为基于原型 的。其聚类的特征是簇相互之间是明显分离的，如图１ （ａ）所示。通过划分可将数据集分割成三个相互 的子集。 划分聚类也叫分割聚类。通过分割将数据划分为 Ｋ组。典型算法有Ｋ～均值算法，Ｃｌａｒａ算法和Ｃｌａｒａｎｓ 算法。 （ａ】基 白聚类（ｂ】基予翻 图１不同族类型 ２．２层次聚类 如果聚类是嵌套的，如图ｌ（ｂ），并且允许簇具有子 商舅 业一｝＿ｚｐ１７￣第２２期 ｌ １０５ 簇，则聚类组成一棵树，树中每一个节点（簇）都是其子 女（子簇）的并，而树根就是包含所有对象的簇，这种聚 类称为层次聚类。 如图２（ａ）所示，数据集为｛ａ，ｂ，Ｃ，ｄ，ｅ，ｆ，ｇ，ｈ，ｋ），如 果按自上而下进行分解，称为式层次聚类，第１步 将数据集分解为｛ａ，ｂ，ｃ，ｇ，ｈ，ｋ）和｛ｄ，ｅ，ｆ｝；第２步将 ｛ａ，ｂ，Ｃ，ｇ，ｈ，ｋ）分解为｛ａ）和｛ｂ，Ｃ，ｇ，ｈ，ｋ｝；第３步将 ｛ｂ，ｅ，ｇ，ｈ，ｋ｝分解为｛ｂ，Ｃ｝和｛ｇ，ｈ，ｋ｝；第４步将｛ｄ，ｅ， ｆ｝分解为｛ｄ）和｛ｅ，ｆ｝；第５、６、７步分别将｛ｅ，ｆ）、｛ｂ，ｃ）、 ｛ｇ，ｈ，ｋ）分解为只有一个元素的叶子节点，算法结束。 其结果如图２（ｂ）所示，簇的形成自左到右的过程。反 到簇不发生变化，即等价于质心不发生变化或变化到 达给定条件的阈值，终止算法。 ３．１＿２ ＣＬＡＲＡ聚类算法 算法的基本思想是：首先，从数据集随机选取一定 数量的样本（一般设为４Ｏ＋２＊ｋ），ｋ为预设的聚类数 目，从样本中选ｋ个元素作为中心点，用ＰＡＭ算法，在 整个数据集中找到更具有代表性的元素替换现有中心 点位置，得到目前为止具有代表性的中心点。再次随 机选取样本，重复ＰＡＭ算法过程。选择ｑ次样本，进 行ｑ次迭代，ＣＬＡＲＡ算法最终从ｑ个样本中得到最佳 的聚类结果。 之，如果自下而上由单个元素逐步聚合成大类的过程， 称为凝聚式层次聚类。如图２（ｂ）中自右至左的聚类过 程。代表的算法是ＢＩＲＣＨ算法，ＣＵＲＥ算法等。 凝墨司睽 （ｂ】甚 过爱示蛐 图２层次聚类 ２．３基于密度聚类 簇是对象的稠密区域，或者，簇的分布是不规则或 是重叠的，如图１（ｂ）所示。这种情况下难以分割或分 层，根据数据分布密度的不同，把相同或相近密度的数 据分到一个簇中，从中可以发现数据的分布模式，或者 不同密度之间的关联关系，从而发现有用信息。其特 点是适合于发现不同形状的簇。代表算法有ＤＢＳＣＡＮ 算法ＤＥＮＣＬＵＥ算法。 ３聚类分析算法 数据对象所拥有的簇不同，采取的聚类方法也不 同。随着聚类分析技术的不断发展，各种聚类方法或 算法改进应运而生。本文介绍划分聚类、层次聚类、基 于密度的聚类的常用算法。 ３．１划分聚类 ３．１．１ Ｋ均值聚类算法 Ｋ均值聚类算法是由Ｊ．Ｂ．Ｍａｃ Ｑｕｅｅｎ于１９６７ 年提出来的一种基于划分的经典聚类算法。它是基于 原型的聚类技术创建数据对象的单层划分。 算法的基本思想是：首先，选取Ｋ个初始质心（质 心点到簇中其他数据之间欧式距离的平均值或是簇的 中心点），初始质心是随机选择的某个数据元素，其中 Ｋ是用户指定的参数，即指定需要划分的簇的个数Ｋ 值，对欧式空间中的点使用欧几里得距离度量数据对 象的相似性，通过计算各个数据对象到Ｋ个初始质心 的距离，按照最近邻原则将数据对象指派到距离它最 近的质心所在的簇中，形成初次划分。然后，根据初始 产生的簇更新每个簇的质心，重复指派和更新步骤，直 《１０６§现代商贸工业ｌ ２０１７年第２２期 比较（１）和（２），两者的共同点是Ｋ值都需要经验 给出。两者的不同之处是，Ｋ均值算法适用于呈球形 状的数据聚类，初始质心的随机选取影响聚类的结果， 对离群点和噪声都敏感。ｃＩＡＲＡ算法是在随机选取 样本的基础上聚类，所以适用于大数据量的聚类，通过 样本不断更新中心对象，与初始质点没有关系，同时， 也避免了噪声或离群点的干扰。 ３．２分层聚类 ３．２．１ ＢＩＲＣＨ算法 算法的基本思想是：ＢＩＲＣＨ算法是把层次聚类过 程看作是一棵树的分解或凝聚。第１步遍历整个数据 集，按照事先确定的初始阈值，建立初始聚类特征树 簇；第２步增加阈值，把满足条件的特征簇加入合并构 成一颗新树即为凝聚，并用新的阈值所有结点是否满 足阈值，大于阈值的结点进行删减即为，的结 点合并到最邻近的特征树中。重复第２步，随着阈值 的增大最终凝聚成一颗完整的树，得到层次聚类的 结果。 ３．２．２ ＣＵＲＥ算法 算法的基本思想是：ＣＵＲＥ算法是介于均值聚类 选取质心和ＣＬＡＲＡ聚类选择中心对象之间的策略。 数据集的每个点看成是一个类，给定常数Ｃ，第１步将Ｃ 个较为分散的点“收缩”成一个类，收缩因子为小于１ 的数，根据目标任务设置。第２步改变收缩因子，将最 相似或相近的两个类再“收缩”；重复第２步，直到收缩 因子为１时，所有对象都收缩成一点，完成分层聚类。 ＣＵＲＥ算法是一种界于基于层次和基于划分的方法。 ＣＵＲＥ算法有效的解决了非球状类或相似性大小不均 匀的类。 比较（１）和（２）都是通过逐步凝聚的过程聚类，适 用于呈球形或相似度（或距离）变化较大的类；采用凝 聚或收缩的方式，不容易受到噪声或离群点的影响。 （１）通过遍历建立特征树，需要增加内存开销，对于大 数据量的聚类，可通过选取样本的方式进行。（２）能够 较好的解决呈非球类的聚类，过滤噪声或离群点。 ３．３基于密度的聚类 ３．３．１ Ｄ］３ＳＣＡＮ算法 ＤＢＳＣＡＮ算法是由Ｅｓｔｅｒ等人１９９６年在第二届 关于知识发现和数据挖掘的国际会议的会议上提出 的，关于大型空间数据库中发现集群的一种基于密度 的算法。 当代大学生旅游消费情况调查分析 以南京市为例 姚程柏 萍 罗万琪 汪春萍 陈建宇 （三江学院商学院，江苏南京２１００００） 摘要：近年来，伴随着社会经济的快速发展和人们生活质量的显著提高，消费者旅游上的投资也在同样的 增加。而大学生这庞大的人群在旅游市场群体所占比例不容或缺，研究并开发大学生旅游市场成为促进经济持 续增长和社会可持续发展不可缺少的内容。因此，以南京市大学生为研究对象，分析了南京市大学生旅游消费行 为及其影响因素，期望对旅游机构在大学生旅行服务方面的发展有一定促进作用。 关键词：大学生旅游；消费行为；分析 中图分类号：Ｆ２３ 文献标识码：Ａ ｄｏｉ：１０．１９３１１／ｊ．ｃｎｋｉ．１６７２—３１９８．２０１７．２２．０５２ １前言 随着大学生生活水平的不断提高以及当下消费观 ２．１旅游消费行为理论 旅游消费行为研究成果对于旅游目的地制定合理的 念的转变，大学生逐渐成为一个不可忽视的消费群体， 市场拓展及开发策略意义重大。随着人们生活水平的提 人们对生活的追求也越来越高，旅游成为人们的新宠， 其消费行为也越来越受到旅游经营者和相关研究者的 高，旅游业显著的经 关注。社会经济的快速发展，带动了旅游经济的提升， 旅游业正逐渐成为国民经济的支柱产业， 旅游业经济也逐渐成为国民经济的支柱产业，旅游业 济地位与解决就业的作用受到各国的重视。显著的经济地位与解决就业的作用已为各国所重 ２．２旅游消费的时代背景 瑞士学者汉沃克尔和克拉普夫１９４２年对旅游进 视。大学生生活水平的不断提高以及消费观念的转 变，使得大学生成为旅游消费市场一个不可忽视的消 行了定义，认为旅游是非定居者的旅行和暂时居留而 费群体，其消费行为也受到旅游经营者和相关研究者 引起的一种社会现象及社会关系的总和，这些人不会 因而永久居留，并且主要不从事赚钱的活动。此定义 越来越多的关注。 于２Ｏ世纪７０年代被旅游科学专家国际联合会所采 ２ 大学生旅游消费概况 算法的基本思想是：第１步根据目标距离设邻域为ｒ的 参数，邻域内的点标记为核心点，落在多个邻域的点标 记为边界点，不属于任何邻域的点为噪声点。以此法 将数据集表示的点都做标记；第２步删除噪声点；第３ 步将最相似（或最近）的核心点聚合成一个簇，与簇相 关的边界点聚合到簇中；重复第３步直到得到聚类结 ４结论 聚类分析技术是一项正在蓬勃发展的新型技术， 基本理论还处在不断发展和完善过程中。为了适应不 同数据类型的分析研究，经典算法也在不断得到改进 以适应实际问题的需要。文章分析了划分聚类、层次 聚类、基于密度的聚类的基本特征，并概括总结了这几 果。 种聚类分析算法的基本思想，比较了它们的优劣。聚 ３．３．２ ＤＥＮＣＬＵＥ算法 类分析值得研究和解决的问题还很多，有待于进一步 ＤＥＮＣＬＵＥ算法是由Ｈｉｎｎｅｂｕｒｇ等人１９９８年在 丰富聚类分析的理论方法和针对性的技术研究。 知识发现和数据挖掘的第四届ＡＣＭ ＳＩＧＫＤＤ会议上 参考文献 提出的，解决多媒体数据库与噪声聚在一起的有效算 法。 ［１］周世兵．聚类分析中的最佳聚类数确定方法研究及应用［Ｄ］．无 锡：江南大学，２０１１． 算法的基本思想是：构造一个影响函数，将数据集 ［２３朱峰．蚁群算法在聚类分析中的应用研究［Ｄ］．西安：西北大学， 所表示的数据空间的整体密度模型化为所有数据点的 ２００９． 影响函数的总和，将局部最大的密度点聚集在一起，最 Ｅ３３陈志强，刘钊，张建辉．聚类分析中ＰＡＭ算法的分析与实现［Ｊ］． 终得到聚类的结果。 比较（１）和（２），两者对对噪声点不敏感。（１）只需 计算机与现代化，２００３，（９）：１－３，６． ［４］仝磊光，谢景新，高明亮．ＣＩ，ＡＲＡ算法聚类蛋白质序列的实现 要确定１个参数，相对容易；不适合处理高维数据和密 Ｅ５３蒋盛益，李霞．一种改进的ＢＩＲＣＨ聚类算法［Ｊ］．计算机应用， 度变化较大的数据；（２）中需要确定２个参数来构造影 ２００９，（１）：２９３—２９６． 响函数，且参数选择比较困难，但（２）的方法适合高维 ［６］王鸿遥，孙璐，游克思．基于ＤＥＮＣＬＵＥ聚类算法的交通事故多 发点鉴别方法［Ｊ］。交通运输工程与信息学报，２０１３，（２）：５－１０． 数据的聚类和不同密度的数据。 ＥＪ３．微计算机信息，２０１０，（１３）：２３１—２３３． 基金项目：江苏省大学生创新项目：当代大学生旅游消费情况调查分析——以南京市为例（项目号：Ｄ１６０３）。 作者简介：姚程、柏萍、罗万琪、汪春萍、陈建宇均为三江学院商学院市场营销专业的学生。 现代商贸工业ｉ ２ｏ１７￣２２期 ｌ １０７
