四种聚类方法之比较

四种聚类方法之比较

介绍了较为常见的k-means、层次聚类、SOM、FCM等四种聚类算法，阐述了各自的原理和使用步骤，利用国际通用测试数据集IRIS对这些算法进行了验证和比较。结果显示对该测试类型数据，FCM和k-means都具有较高的准确度，层次聚类准确度最差，而SOM则耗时最长。

关键词:聚类算法；k-means；层次聚类；SOM；FCM

聚类分析是一种重要的人类行为，早在孩提时代，一个人就通过不断改进下意识中的聚类模式来学会如何区分猫狗、动物植物。目前在许多领域都得到了广泛的研究和成功的应用，如用于模式识别、数据分析、图像处理、市场研究、客户分割、Web文档分类等[1]。

　聚类就是按照某个特定标准(如距离准则)把一个数据集分割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同数据尽量分离。

　聚类技术[2]正在蓬勃发展，对此有贡献的研究领域包括数据挖掘、统计学、机器学习、空间数据库技术、生物学以及市场营销等。各种聚类方法也被不断提出和改进，而不同的方法适合于不同类型的数据，因此对各种聚类方法、聚类效果的比较成为值得研究的课题。

1 聚类算法的分类

　目前，有大量的聚类算法[3]。而对于具体应用，聚类算法的选择取决于数据的类型、聚类的目的。如果聚类分析被用作描述或探查的工具，可以对同样的数据尝试多种算法，以发现数据可能揭示的结果。

　主要的聚类算法可以划分为如下几类：划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法[4-6]。

　每一类中都存在着得到广泛应用的算法，例如：划分方法中的k-means[7]聚类算法、层次方法中的凝聚型层次聚类算法[8]、基于模型方法中的神经网络[9]聚类算法等。

　目前,聚类问题的研究不仅仅局限于上述的硬聚类，即每一个数据只能被归为一类，模糊聚类[10]也是聚类分析中研究较为广泛的一个分支。模糊聚类通过隶属函数来确定每个数据隶属于各个簇的程度，而不是将一个数据对象硬性地归类到某一簇中。目前已有很多关于模糊聚类的算法被提出，如著名的FCM算法等。

　本文主要对k-means聚类算法、凝聚型层次聚类算法、神经网络聚类算法之SOM,以及模糊聚类的FCM算法通过通用测试数据集进行聚类效果的比较和分析。

2 四种常用聚类算法研究

21 k-means聚类算法

　k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。

　k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。k-means算法的处理过程如下：首先，随机地选择k个对象，每个对象初始地代表了一个簇的平均值或中心;对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下：

　这里E是数据库中所有对象的平方误差的总和，p是空间中的点，mi是簇Ci的平均值[9]。该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧几里得距离,当然也可以用其他距离度量。k-means聚类算法的算法流程如下：

输入：包含n个对象的数据库和簇的数目k；

输出：k个簇，使平方误差准则最小。

步骤：

(1) 任意选择k个对象作为初始的簇中心；

(2) repeat；

(3) 根据簇中对象的平均值，将每个对象(重新)赋予最类似的簇；

(4) 更新簇的平均值，即计算每个簇中对象的平均值；

(5) until不再发生变化。

22 层次聚类算法

根据层次分解的顺序是自底向上的还是自上向下的，层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。

　凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。四种广泛采用的簇间距离度量方法如下：

这里给出采用最小距离的凝聚层次聚类算法流程：

　(1) 将每个对象看作一类，计算两两之间的最小距离；

　(2) 将距离最小的两个类合并成一个新类；

　(3) 重新计算新类与所有类之间的距离；

　(4) 重复(2)、(3)，直到所有类最后合并成一类。

23 SOM聚类算法

　SOM神经网络[11]是由芬兰神经网络专家Kohonen教授提出的，该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。

　SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。

　算法流程：

　(1) 网络初始化，对输出层每个节点权重赋初值；

　(2) 将输入样本中随机选取输入向量，找到与输入向量距离最小的权重向量；

　(3) 定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢；

　(4) 提供新样本、进行训练；

　(5) 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类结果。

24 FCM聚类算法

　1965年美国加州大学柏克莱分校的扎德教授第一次提出了‘集合’的概念。经过十多年的发展，模糊集合理论渐渐被应用到各个实际应用方面。为克服非此即彼的分类缺点，出现了以模糊集合论为数学基础的聚类分析。用模糊数学的方法进行聚类分析，就是模糊聚类分析[12]。

FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法。该聚类算法是传统硬聚类算法的一种改进。

算法流程：

　(1) 标准化数据矩阵；

　(2) 建立模糊相似矩阵，初始化隶属矩阵；

　(3) 算法开始迭代，直到目标函数收敛到极小值；

　(4) 根据迭代结果，由最后的隶属矩阵确定数据所属的类，显示最后的聚类结果。

3 四种聚类算法试验

31 试验数据

　实验中，选取专门用于测试分类、聚类算法的国际通用的UCI数据库中的IRIS[13]数据集，IRIS数据集包含150个样本数据，分别取自三种不同的莺尾属植物setosa、versicolor和virginica的花朵样本,每个数据含有4个属性，即萼片长度、萼片宽度、花瓣长度，单位为cm。在数据集上执行不同的聚类算法，可以得到不同精度的聚类结果。

32 试验结果说明

　文中基于前面所述各算法原理及算法流程，用matlab进行编程运算，得到表1所示聚类结果。

　如表1所示，对于四种聚类算法，按三方面进行比较：(1)聚错样本数：总的聚错的样本数，即各类中聚错的样本数的和；(2)运行时间：即聚类整个过程所耗费的时间，单位为s；(3)平均准确度：设原数据集有k个类,用ci表示第i类，ni为ci中样本的个数，mi为聚类正确的个数,则mi/ni为第i类中的精度，则平均精度为：

33 试验结果分析

四种聚类算法中，在运行时间及准确度方面综合考虑，k-means和FCM相对优于其他。但是，各个算法还是存在固定缺点：k-means聚类算法的初始点选择不稳定，是随机选取的，这就引起聚类结果的不稳定，本实验中虽是经过多次实验取的平均值，但是具体初始点的选择方法还需进一步研究；层次聚类虽然不需要确定分类数，但是一旦一个分裂或者合并被执行，就不能修正，聚类质量受限制；FCM对初始聚类中心敏感，需要人为确定聚类数，容易陷入局部最优解；SOM与实际大脑处理有很强的理论联系。但是处理时间较长，需要进一步研究使其适应大型数据库。

聚类分析因其在许多领域的成功应用而展现出诱人的应用前景，除经典聚类算法外，各种新的聚类方法正被不断被提出。

一、公开数据库

常用数据公开网站：

UCI：经典的机器学习、数据挖掘数据集，包含分类、聚类、回归等问题下的多个数据集。很经典也比较古老，但依然活跃在科研学者的视线中。

国家数据：数据来源中华人民共和国国家统计局，包含了我国经济民生等多个方面的数据，并且在月度、季度、年度都有覆盖，全面又权威。

亚马逊：来自亚马逊的跨科学云数据平台，包含化学、生物、经济等多个领域的数据集。

figshare：研究成果共享平台，在这里可以找到来自世界的大牛们的研究成果分享，获取其中的研究数据。

github：一个非常全面的数据获取渠道，包含各个细分领域的数据库资源，自然科学和社会科学的覆盖都很全面，适合做研究和数据分析的人员。

二、利用爬虫可以获得有价值数据

这里给出了一些网站平台，我们可以使用爬虫爬取网站上的数据，某些网站上也给出获取数据的API接口，但需要付费。

1财经数据，2网贷数据；3公司年报；4创投数据；5社交平台；6就业招聘；7餐饮食品；8交通旅游；9电商平台；10影音数据；11房屋信息；12购车租车；13新媒体数据；14分类信息。

三、数据交易平台

由于现在数据的需求很大，也催生了很多做数据交易的平台，当然，出去付费购买的数据，在这些平台，也有很多免费的数据可以获取。

优易数据：由国家信息中心发起，拥有国家级信息资源的数据平台，国内领先的数据交易平台。平台有B2B、B2C两种交易模式，包含政务、社会、社交、教育、消费、交通、能源、金融、健康等多个领域的数据资源。

数据堂：专注于互联网综合数据交易，提供数据交易、处理和数据API服务，包含语音识别、医疗健康、交通地理、电子商务、社交网络、图像识别等方面的数据。



四、网络指数

百度指数：指数查询平台，可以根据指数的变化查看某个主题在各个时间段受关注的情况，进行趋势分析、舆情预测有很好的指导作用。除了关注趋势之外，还有需求分析、人群画像等精准分析的工具，对于市场调研来说具有很好的参考意义。同样的另外两个搜索引擎搜狗、360也有类似的产品，都可以作为参考。

阿里指数：国内权威的商品交易分析工具，可以按地域、按行业查看商品搜索和交易数据，基于淘宝、天猫和1688平台的交易数据基本能够看出国内商品交易的概况，对于趋势分析、行业观察意义不小。

友盟指数：友盟在移动互联网应用数据统计和分析具有较为全面的统计和分析，对于研究移动端产品、做市场调研、用户行为分析很有帮助。除了友盟指数，友盟的互联网报告同样是了解互联网趋势的优秀读物。

五、网络采集器

网络采集器是通过软件的形式实现简单快捷地采集网络上分散的内容，具有很好的内容收集作用，而且不需要技术成本，被很多用户作为初级的采集工具。

造数：新一代智能云爬虫。爬虫工具中最快的，比其他同类产品快9倍。拥有千万IP，可以轻松发起无数请求，数据保存在云端，安全方便、简单快捷。

火车采集器：一款专业的互联网数据抓取、处理、分析，挖掘软件，可以灵活迅速地抓取网页上散乱分布的数据信息。

八爪鱼：简单实用的采集器，功能齐全， *** 作简单，不用写规则。特有的云采集，关机也可以在云服务器上运行采集任务。

以上就是关于四种聚类方法之比较全部的内容，包括:四种聚类方法之比较、如何获取大数据信息、等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！