聚类算法几个特征

❶ 聚类算法（上）06

这篇文章的整体排版主要是根据个人的博客来哒，如果感兴趣的话可以去我的自己搭建的个人博客看这篇 文章 。

聚类算法很多，所以和讲回归算法一样，分成了上下，上中主要讲了传统的K-Means算法以及其相应的优化算法入K-Means++，K-Means||和Canopy等。下中主要讲了另外两种的思路的聚类算法，即层次聚类和密度聚类。

聚类算就是怼大量未知标注的数据集，按照数据 内部存在的数据特征 将数据集 划分为多个不同的类别 ，使类别内的数据比较相似，类别之间的数据相似度比较小，属于 无监督学习 。

从定义就可以看出，聚类算法的关键在于计算样本之间的 相似度 ，也称为 样本间的距离 。

说到聚类算法，那肯定核心就是计算距离的公式了，目前常用的有以下几种。
闵可夫斯基距离（Minkowski） ：公式2.1

KL距离（相对熵） ：
思考下条件熵的定义，简单的来说就是在放生一件事情的时候，发生另一件事的概率。公式如下公式2.7.
注：这里书的概率不是实指概率，而是熵表达的含义。这个公式其实就是条件熵的公式。

杰卡德相似系数(Jaccard) ：
这个很好理解，它的核心就是使用两个集合的交集和并集的比率来代表两者的相似度，也就是说重合的越多越相似。公式如下，公式2.8.

Pearson相关系数 ：
这个就是考研数学中的相关系数，表达就是两者之间的想关系，所以直接拿来用就好了，公式如下公式2.9。

给定一个有M个对象的数据集，构建一个具有k个簇的模型，其中k<=M。满足 以下条件:

基本思想:
对于给定的类别数目k，首先给定初始划分，通过迭代改变样本和簇的隶属关系，使的每次处理后得到的划分方式比上一次的好，即 总的数据集之间的距离和变小了

K-means的核心算法如下：

再循环中的第二步，我们移动了中心点的位置，把中心点移到了隶属于该中心点类别的所有样本的中间，并使用样本的均值作为位置。这样子看似是拍脑袋想的移动策略，其实是可以推导出来的。正如聚类算法思想所指出的，我们要让所有的点到自己的分类的中心点的欧几里得距离最小，所以我们设置目标放称为公式4.1，公式中的1/2是为了之后求导运算方便。我们为了让目标函数尽可能的小，所以使用了之前一直在使用的思考方式，对其使用梯度下降算法，求导后得到公式4.2，之后令其等于0，就得到了公式4.3。

最后这个看似不错的算法，其实有着不小的缺点，那就是 初值敏感 。我们来仔细想一想，如果两个不小心随机生成的初值落到了一个类别中，两者的距离还特别近，这中情况下就很难正确分类了。除此之外，由于移动策略中使用的是均值，也就是说如果集合中含有非常大的误差点的话，这样子会是中心点的设置偏离正确点很远，所以很多时候我们改用 中值来更新中心点 ，这就是我们说的K-Mediods聚类，即K中值聚类。

总结下K-means算法
优点：

由于K-Means对初始中心点非常敏感，我们这里就尝试着通过二分法弱化初始中心点。这种算法的具体步骤如下：

我们在这个算法中提到了SSE，这个可以是簇内所有样本点，到其中心点的距离的总和，代表着簇内的点是不是高度相关。计算公式如下公式4.4。

可以看出在这种算法下，很好的避开了，两个中心点都在一起的情况。

K-Means++做的改善，是直接对初始点的生成位置的选择进行优化的，他的初始点生成策略如下：

Canopy属于一种“粗略地”聚类算法，简单的来说就是，不那么追求自动获得最优解，而是引入了一种人为规定的先验值进行聚类，具体步骤如下：

注：Canopy算法得到的最终结果的值，聚簇之间是可能存在重叠的，但是不会存在 某个对象不属于任何聚簇的情况
显然，这种算法虽然快，但是很难生成满足我们应用的模型，所以通常我们将它作为解决K-Means初值敏感的方案，他们合在一起就是Canopy+K-Means算法。
顺序就是先使用Canopy算法获得K个聚类中心，然后用这K个聚类中心作为K-Means算法。这样子就很好的解决了K-Means初值敏感的问题。

Mini Batch K-Means算法是K-Means算法的一种优化变种，采用小规模的数据子集，来减少计算时间。其中采用小规模的数据子集指的是每次训练使用的数据集是在训练算法的时候随机抽取的数据子集。Mini Batch K-Means算法可以减少K-Means算法的收敛时间，而且产生的结果效果只是略差于标准K-Means算法。
它的算法步骤如下：

聚类算法的衡量标准有很多，包括均一性、完整性、V-measure、调整兰德系数（ARI ，Adjusted Rnd Index）、调整互信息(AMI，Adjusted Mutual Information)以及轮廓系数等等。

均一性：一个簇中只包含一个类别的样本，则满足均一性。其实也可以认为就是正确率，即每个聚簇中正确分类的样本数占该聚簇总样本数的比例和。其公式如下公式5.1。

完整性：同类别样本被归类到相同簇中，则满足完整性。每个聚簇中正确分类的样本数占该类型的总样本数比例的和，通俗的来说就是，我们已分类类别中，分类正确的个数。
其公式如下，公式5.2：

在实际的情况中，均一性和完整性是往往不能兼得的，就好像抓特务时的矛盾一样，到底是保证每个抓的人都是特务，还是宁可错抓也不放过一个特务，之间的取舍很难把握。所以再一次贯彻，鱼和熊掌不可兼得，我们就加权，于是得到的就是V-measure，其公式如下公式5.3：

兰德系数（RI，Rand index） ，我用中文看了不少讲兰德系数的博客，其中的文字说明几乎都是相同的，对个人的理解帮助不是特别大，于是用英文查的。最终理解了这个系数的参数的意思，想看英文说明的，个人觉得还挺好懂的参考 这里 。以下是我个人的讲解。

首先，将原数据集中的元素进行两两配对形成一个新的数据集，我们称之为S数据集。这时候，我们将原数据集，根据两种不同的策略分别划分成r份和s份，并对这两个数据集命名为X和Y。在这里我们可以看出，X和Y的元素是相同的，只是他们的划分方式不同。
接下来我们来思考，S数据集中，每个元素中的两个样本，在X和Y中只有两种可能，就是两个样本都在一个子集中，或者不在一个子集中，那么对于S中的一个元素，只有四种可能性。

接下来引入， 调整兰德系数(ARI，Adjusted Rnd Index) ，ARI取值范围 ，值越大，表示聚类结果和真实情况越吻合。从广义的角度来将，ARI是衡量两个数据分布的吻合程度的，公式5.5如下：

调整互信息，整体的流程很像ARI，AMI则是对MI进行调整。而MI是使用信息熵来描述的。那么互信息表示了什么呢，首先先看下 维基网络的定义 ：

之前我们说到的衡量指标都是有标签的，这里的轮廓系数则是不包含标签的评价指标。

❷ 四种聚类方法之比较

四种聚类方法之比较
介绍了较为常见的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 四种常用聚类算法研究
2.1 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不再发生变化。
2.2 层次聚类算法
根据层次分解的顺序是自底向上的还是自上向下的，层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。
凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。四种广泛采用的簇间距离度量方法如下：

这里给出采用最小距离的凝聚层次聚类算法流程：
(1) 将每个对象看作一类，计算两两之间的最小距离；
(2) 将距离最小的两个类合并成一个新类；
(3) 重新计算新类与所有类之间的距离；
(4) 重复(2)、(3)，直到所有类最后合并成一类。
2.3 SOM聚类算法
SOM神经网络[11]是由芬兰神经网络专家Kohonen教授提出的，该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。
SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。
算法流程：
(1) 网络初始化，对输出层每个节点权重赋初值；
(2) 将输入样本中随机选取输入向量，找到与输入向量距离最小的权重向量；
(3) 定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢；
(4) 提供新样本、进行训练；
(5) 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类结果。
2.4 FCM聚类算法
1965年美国加州大学柏克莱分校的扎德教授第一次提出了‘集合’的概念。经过十多年的发展，模糊集合理论渐渐被应用到各个实际应用方面。为克服非此即彼的分类缺点，出现了以模糊集合论为数学基础的聚类分析。用模糊数学的方法进行聚类分析，就是模糊聚类分析[12]。
FCM算法是一种以隶属度来确定每个数据点属于某个聚类程度的算法。该聚类算法是传统硬聚类算法的一种改进。

算法流程：
(1) 标准化数据矩阵；
(2) 建立模糊相似矩阵，初始化隶属矩阵；
(3) 算法开始迭代，直到目标函数收敛到极小值；
(4) 根据迭代结果，由最后的隶属矩阵确定数据所属的类，显示最后的聚类结果。
3 四种聚类算法试验
3.1 试验数据
实验中，选取专门用于测试分类、聚类算法的国际通用的UCI数据库中的IRIS[13]数据集，IRIS数据集包含150个样本数据，分别取自三种不同的莺尾属植物setosa、versicolor和virginica的花朵样本,每个数据含有4个属性，即萼片长度、萼片宽度、花瓣长度，单位为cm。在数据集上执行不同的聚类算法，可以得到不同精度的聚类结果。
3.2 试验结果说明
文中基于前面所述各算法原理及算法流程，用matlab进行编程运算，得到表1所示聚类结果。

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

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

❸ 机器学习算法中的SVM和聚类算法

相信大家都知道，机器学习中有很多的算法，我们在进行机器学习知识学习的时候一定会遇到过很多的算法，而机器学习中的SVM算法和聚类算法都是比较重要的，我们在这篇文章中就重点给大家介绍一下这两种算法，希望这篇文章能够帮助大家理解这两种算法。

机器学习算法——SVM

提道机器学习算法就不得不说一说SVM，这种算法就是支持向量机，而支持向量机算法是诞生于统计学习界，这也是机器学习中的经典算法，而支持向量机算法从某种意义上来说是逻辑回归算法的强化，这就是通过给予逻辑回归算法更严格的优化条件，支持向量机算法可以获得比逻辑回归更好的分类界线。不过如果通过跟高斯核的结合，支持向量机可以表达出非常复杂的分类界线，从而达成很好的的分类效果。核事实上就是一种特殊的函数，最典型的特征就是可以将低维的空间映射到高维的空间。

于是问题来了，如何在二维平面划分出一个圆形的分类界线？其实我们在二维平面可能会很困难，但是通过核可以将二维空间映射到三维空间，然后使用一个线性平面就可以达成类似效果。也就是说，二维平面划分出的非线性分类界线可以等价于三维平面的线性分类界线。接着，我们可以通过在三维空间中进行简单的线性划分就可以达到在二维平面中的非线性划分效果。而支持向量机是一种数学成分很浓的机器学习算法。在算法的核心步骤中，有一步证明，即将数据从低维映射到高维不会带来最后计算复杂性的提升。于是，通过支持向量机算法，既可以维持计算效率，又可以获得非常好的分类效果。因此支持向量机在90年代后期一直占据着机器学习中最核心的地位，基本取代了神经网络算法。

机器学习算法——聚类算法

说完了SVM，下面我们给大家介绍一下聚类算法，前面的算法中的一个显着特征就是我的训练数据中包含了标签，训练出的模型可以对其他未知数据预测标签。在下面的算法中，训练数据都是不含标签的，而算法的目的则是通过训练，推测出这些数据的标签。这类算法有一个统称，即无监督算法。无监督算法中最典型的代表就是聚类算法。而聚类算法中最典型的代表就是K-Means算法。这一算法被广大朋友所应用。

现在，我们可以清楚认识到机器学习是一个综合性很强的学科。在这篇文章中我们给大家介绍了很多关于机器学习中的支持向量机和聚类算法的相关知识，通过这些知识我们不难发现机器学习中有很多有用的算法，熟练掌握这些算法是我们真正学会机器学习的必经之路。

❹ 常用的聚类方法有哪几种

聚类分析的算法可以分为划分法、层次法、基于密度的方法、基于网格的方法、基于模型的方法。

1、划分法，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。

2、层次法，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。

3、基于密度的方法，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。

4、图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。

5、基于网格的方法，这种方法首先将数据空间划分成为有限个单元的网格结构,所有的处理都是以单个的单元为对象的。

6、基于模型的方法，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。

(4)聚类算法几个特征扩展阅读：

在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。

它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。

许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导致有偏的结果。

许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。

❺ 聚类算法有哪几种

聚类分析计算方法主要有： 层次的方法(hierarchical method)、划分方法(partitioning method)、基于密度的方法(density-based method)、基于网格的方法(grid-based method)、基于模型的方法(model-based method)等。其中，前两种算法是利用统计学定义的距离进行度量。

k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象，则根据它们与这些聚类中心的相似度(距离)，分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然 后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。

其流程如下：

(1)从 n个数据对象任意选择 k 个对象作为初始聚类中心;

(2)根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离;并根据最小距离重新对相应对象进行划分;

(3)重新计算每个(有变化)聚类的均值(中心对象);

(4)循环(2)、(3)直到每个聚类不再发生变化为止(标准测量函数收敛)。

优点： 本算法确定的K个划分到达平方误差最小。当聚类是密集的，且类与类之间区别明显时，效果较好。对于处理大数据集，这个算法是相对可伸缩和高效的，计算的复杂度为 O(NKt)，其中N是数据对象的数目，t是迭代的次数。

缺点：

1. K 是事先给定的，但非常难以选定;

2. 初始聚类中心的选择对聚类结果有较大的影响。

❻ 聚类算法有哪些分类

聚类算法的分类有：

1、划分法

划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K小于N。而且这K个分组满足下列条件：

（1） 每一个分组至少包含一个数据纪录；

（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；

2、层次法

层次法(hierarchical methods)，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。

例如，在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。

3、密度算法

基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。

4、图论聚类法

图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。因此，每一个最小处理单元数据之间都会有一个度量表达，这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源，因而其主要优点是易于处理局部数据的特性。

5、网格算法

基于网格的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。

代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

6、模型算法

基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。

通常有两种尝试方向：统计的方案和神经网络的方案。

(6)聚类算法几个特征扩展阅读：

聚类算法的要求：

1、可伸缩性

许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导致有偏的结果。

我们需要具有高度可伸缩性的聚类算法。

2、不同属性

许多算法被设计用来聚类数值类型的数据。但是，应用可能要求聚类其他类型的数据，如二元类型(binary)，分类/标称类型（categorical/nominal），序数型（ordinal）数据，或者这些数据类型的混合。

3、任意形状

许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。

4、领域最小化

许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。

5、处理“噪声”

绝大多数现实中的数据库都包含了孤立点，缺失，或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。

6、记录顺序

一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以不同的顺序交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。

❼ 用于数据挖掘的聚类算法有哪些，各有何优势

聚类方法的分类，主要分为层次化聚类算法，划分式聚类算法，基于密度的聚类算法，基于网格的聚类算法，基于模型的聚类算法等。

而衡量聚类算法优劣的标准主要是这几个方面：处理大的数据集的能力；处理任意形状，包括有间隙的嵌套的数据的能力；算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于数据输入顺序；处理数据噪声的能力；是否需要预先知道聚类个数，是否需要用户给出领域知识；算法处理有很多属性数据的能力，也就是对数据维数是否敏感。

.聚类算法主要有两种算法，一种是自下而上法（bottom-up），一种是自上而下法（top-down）。这两种路径本质上各有优势，主要看实际应用的时候要根据数据适用于哪一种，Hierarchical methods中比较新的算法有BIRCH主要是在数据体量很大的时候使用；ROCK优势在于异常数据抗干扰性强……

关于数据挖掘的相关学习，推荐CDA数据师的相关课程，课程以项目调动学员数据挖掘实用能力的场景式教学为主，在讲师设计的业务场景下由讲师不断提出业务问题，再由学员循序渐进思考并操作解决问题的过程中，帮助学员掌握真正过硬的解决业务问题的数据挖掘能力。这种教学方式能够引发学员的独立思考及主观能动性，学员掌握的技能知识可以快速转化为自身能够灵活应用的技能，在面对不同场景时能够自由发挥。点击预约免费试听课。

❽ 数据挖掘干货总结（四）--聚类算法

本文共计2680字，预计阅读时长七分钟

聚类算法

一 、 本质

将数据划分到不同的类里，使相似的数据在同一类里，不相似的数据在不同类里

二 、 分类算法用来解决什么问题

文本聚类、图像聚类和商品聚类，便于发现规律，以解决数据稀疏问题

三 、 聚类算法基础知识

1. 层次聚类 vs 非层次聚类

– 不同类之间有无包含关系

2. 硬聚类 vs 软聚类

– 硬聚类：每个对象只属于一个类

– 软聚类：每个对象以某个概率属于每个类

3. 用向量表示对象

– 每个对象用一个向量表示，可以视为高维空间的一个点

– 所有对象形成数据空间（矩阵）

– 相似度计算：Cosine、点积、质心距离

4. 用矩阵列出对象之间的距离、相似度

5. 用字典保存上述矩阵（节省空间）

    D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}

6. 评价方法

– 内部评价法（Internal Evalution）：

• 没有外部标准，非监督式

• 同类是否相似，跨类是否相异

DB值越小聚类效果越好，反之，越不好

– 外部评价法（External Evalution）：

• 准确度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)

• 精度（Precision）: C11 / (C11 + C21 )

• 召回（Recall）: C11 / (C11 + C12 )

• F值（F-measure）：

β表示对精度P的重视程度，越大越重视，默认设置为1，即变成了F值，F较高时则能说明聚类效果较好。

四 、 有哪些聚类算法

主要分为 层次化聚类算法 ， 划分式聚类算法 ， 基于密度的聚类算法 ， 基于网格的聚类算法 ， 基于模型的聚类算法等 。

4.1 层次化聚类算法

又称树聚类算法，透过一种层次架构方式，反复将数据进行分裂或聚合。典型的有BIRCH算法，CURE算法，CHAMELEON算法，Sequence data rough clustering算法,Between groups average算法,Furthest neighbor算法,Neares neighbor算法等。

凝聚型层次聚类 ：

先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。

算法流程：

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

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

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

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

特点：

1. 算法简单

2. 层次用于概念聚类（生成概念、文档层次树）

3. 聚类对象的两种表示法都适用

4. 处理大小不同的簇

5. 簇选取步骤在树状图生成之后

4.2 划分式聚类算法

预先指定聚类数目或聚类中心，反复迭代逐步降低目标函数误差值直至收敛，得到最终结果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等

经典K-means：

算法流程：

1. 随机地选择k个对象，每个对象初始地代表了一个簇的中心；

2. 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；

3. 重新计算每个簇的平均值，更新为新的簇中心；

4. 不断重复2、3，直到准则函数收敛。

特点：

1.K的选择

2.中心点的选择

– 随机

– 多轮随机：选择最小的WCSS

3.优点

– 算法简单、有效

– 时间复杂度：O(nkt)

4.缺点

– 不适于处理球面数据

– 密度、大小不同的聚类，受K的限制，难于发现自然的聚类

4.3 基于模型的聚类算法

为每簇假定了一个模型，寻找数据对给定模型的最佳拟合，同一”类“的数据属于同一种概率分布，即假设数据是根据潜在的概率分布生成的。主要有基于统计学模型的方法和基于神经网络模型的方法，尤其以基于概率模型的方法居多。一个基于模型的算法可能通过构建反应数据点空间分布的密度函数来定位聚类。基于模型的聚类试图优化给定的数据和某些数据模型之间的适应性。

SOM 神经网络算法 ：

该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。

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

算法流程：

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

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

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

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

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

4.4 基于密度聚类算法

只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类，擅于解决不规则形状的聚类问题，广泛应用于空间信息处理,SGC,GCHL，DBSCAN算法、OPTICS算法、DENCLUE算法。

DBSCAN：

对于集中区域效果较好，为了发现任意形状的簇，这类方法将簇看做是数据空间中被低密度区域分割开的稠密对象区域；一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据中发现任意形状的簇。

4.5 基于网格的聚类算法

    基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构（即量化空间）上进行。这种方法的主要优点是它的处理 速度很快，其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但这种算法效率的提高是以聚类结果的精确性为代价的。经常与基于密度的算法结合使用。代表算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。 

❾ 聚类算法的算法分类

很难对聚类方法提出一个简洁的分类，因为这些类别可能重叠，从而使得一种方法具有几类的特征，尽管如此，对于各种不同的聚类方法提供一个相对有组织的描述依然是有用的，为聚类分析计算方法主要有如下几种： 划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。而且这K个分组满足下列条件：
（1） 每一个分组至少包含一个数据纪录；
（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；
对于给定的K，算法首先给出一个初始的分组方法，以后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案都较前一次好，而所谓好的标准就是：同一分组中的记录越近越好，而不同分组中的纪录越远越好。
大部分划分方法是基于距离的。给定要构建的分区数k，划分方法首先创建一个初始化划分。然后，它采用一种迭代的重定位技术，通过把对象从一个组移动到另一个组来进行划分。一个好的划分的一般准备是：同一个簇中的对象尽可能相互接近或相关，而不同的簇中的对象尽可能远离或不同。还有许多评判划分质量的其他准则。传统的划分方法可以扩展到子空间聚类，而不是搜索整个数据空间。当存在很多属性并且数据稀疏时，这是有用的。为了达到全局最优，基于划分的聚类可能需要穷举所有可能的划分，计算量极大。实际上，大多数应用都采用了流行的启发式方法，如k-均值和k-中心算法，渐近的提高聚类质量，逼近局部最优解。这些启发式聚类方法很适合发现中小规模的数据库中小规模的数据库中的球状簇。为了发现具有复杂形状的簇和对超大型数据集进行聚类，需要进一步扩展基于划分的方法。
使用这个基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法； 层次法(hierarchical methods)，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。
例如，在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。
层次聚类方法可以是基于距离的或基于密度或连通性的。层次聚类方法的一些扩展也考虑了子空间聚类。层次方法的缺陷在于，一旦一个步骤（合并或分裂）完成，它就不能被撤销。这个严格规定是有用的，因为不用担心不同选择的组合数目，它将产生较小的计算开销。然而这种技术不能更正错误的决定。已经提出了一些提高层次聚类质量的方法。
代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等； 基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。
这个方法的指导思想就是，只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。
代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等； 基于网格的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。
代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法； 基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。
通常有两种尝试方向：统计的方案和神经网络的方案。

❿ K-Means 聚类算法

问题导入

    假如有这样一种情况，在一天你想去某个城市旅游，这个城市里你想去的有70个地方，现在你只有每一个地方的地址，这个地址列表很长，有70个位置。事先肯定要做好攻略，你要把一些比较接近的地方放在一起组成一组，这样就可以安排交通工具抵达这些组的“某个地址”，然后步行到每个组内的地址。那么，如何确定这些组，如何确定这些组的“某个地址”？答案就是聚类。而本文所提供的k-means聚类分析方法就可以用于解决这类问题。

一，聚类思想

        所谓聚类算法是指将一堆没有标签的数据自动划分成几类的方法，属于无监督学习方法，这个方法要保证同一类的数据有相似的特征，如下图：

        根据样本之间的距离或者说相似性，把越相似，差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。

二，K-Means聚类分析算法

        K-Means是一种基于自下而上的聚类分析方法，基本概念就是空间中有N个点，初始选择K个点作为中心聚类点，将N个点分别与K个点计算距离，选择自己最近的点作为自己的中心点，不断地更新中心聚集点。

相关概念：

        K值：要得到的簇的个数

        质心：每个簇的均值向量，即向量各维取品军即可

        距离度量：常用欧几里得距离和余弦相似度(先标准化)

        两点之间的距离：

算法流程：

        1    首先确定一个K值，即我们希望将数据集经过聚类得到 K个集合；

        2    从数据集中随机选择K个数据点作为质心；

        3    对数据集中每一个点，计算其与每个质心的距离(如欧式距离)，离哪个质心近，就划分到哪个质心所属的集合

        4    把所有数据归好集合，一共有K个集合，然后重新计算每个集合的质心；

        5    如果新计算出来的质心和原来的质心之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大，趋于稳定，或者说收敛)，我们可以认为聚类已经达到期望的结果，算法终止。

        6    如果新质心和原质心距离变化大，需要迭代3-5步骤

K-means实现过程

K-means 聚类算法是一种非监督学习算法，被用于非标签数据（data without defined categories or groups）。该算法使用迭代细化来产生最终结果。算法输入的是集群的数量 K 和数据集。数据集是每个数据点的一组功能。

算法从 Κ 质心的初始估计开始，其可以随机生成或从数据集中随机选择 。然后算法在下面两个步骤之间迭代：

1.数据分配：

每个质心定义一个集群。在此步骤中，基于平方欧氏距离将每个数据点分配到其最近的质心。更正式一点， ci 属于质心集合 C ，然后每个数据点 x 基于下面的公式被分配到一个集群中。

其中 dist（·）是标准（L2）欧氏距离。让指向第 i 个集群质心的数据点集合定为 Si 。

2. 质心更新：

在此步骤中，重新计算质心。这是通过获取分配给该质心集群的所有数据点的平均值来完成的。公式如下：

K-means 算法在步骤 1 和步骤 2 之间迭代，直到满足停止条件（即，没有数据点改变集群，距离的总和最小化，或者达到一些最大迭代次数）。

K 值的选择

上述算法找到特定预选 K 值和数据集标签。为了找到数据中的集群数，用户需要针对一系列 K 值运行 K-means 聚类算法并比较结果。通常，没有用于确定 K 的精确值的方法，但是可以使用以下技术获得准确的估计。

Elbow point 拐点方法

通常用于比较不同 K 值的结果的度量之一是数据点与其聚类质心之间的平均距离。由于增加集群的数量将总是减少到数据点的距离，因此当 K 与数据点的数量相同时，增加 K 将总是减小该度量，达到零的极值。因此，该指标不能用作唯一目标。相反，绘制了作为 K 到质心的平均距离的函数，并且可以使用减小率急剧变化的“拐点”来粗略地确定 K 。

DBI（Davies-Bouldin Index）

DBI 是一种评估度量的聚类算法的指标，通常用于评估 K-means 算法中 k 的取值。简单的理解就是：DBI 是聚类内的距离与聚类外的距离的比值。所以，DBI 的数值越小，表示分散程度越低，聚类效果越好。

还存在许多用于验证 K 的其他技术，包括交叉验证，信息标准，信息理论跳跃方法，轮廓方法和 G 均值算法等等。

三，数学原理

K-Means采用的启发式很简单，可以用下面一组图来形象的描述：

上述a表达了初始的数据集，假设 k=2 。在图b中，我们随机选择了两个 k 类所对应的类别质点，即图中的红色质点和蓝色质点，然后分别求样本中所有点到这两个质心的距离，并标记每个样本类别为和该样本距离最小的质心的类别，如图c所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图d所示，新的红色质心和蓝色质心大热位置已经发生了变化。图e和图f重复了我们在图c和图d的过程，即将所有点的类别标记为距离最近的质心的类别并求出新的质心。最终我们得到的两个类别如图f.

四，实例

坐标系中有六个点：

1、我们分两组，令K等于2，我们随机选择两个点：P1和P2

2、通过勾股定理计算剩余点分别到这两个点的距离：

3、第一次分组后结果：

        组A：P1

        组B：P2、P3、P4、P5、P6

4、分别计算A组和B组的质心：

        A组质心还是P1=（0，0）

        B组新的质心坐标为：P哥=（（1+3+8+9+10）/5，（2+1+8+10+7）/5）=（6.2，5.6）

5、再次计算每个点到质心的距离：

6、第二次分组结果：

        组A：P1、P2、P3

        组B：P4、P5、P6

7、再次计算质心：

        P哥1=（1.33，1） 

        P哥2=（9，8.33）

8、再次计算每个点到质心的距离：

9、第三次分组结果：

        组A：P1、P2、P3

        组B：P4、P5、P6

可以发现，第三次分组结果和第二次分组结果一致，说明已经收敛，聚类结束。

五、K-Means的优缺点

优点：

1、原理比较简单，实现也是很容易，收敛速度快。

2、当结果簇是密集的，而簇与簇之间区别明显时, 它的效果较好。

3、主要需要调参的参数仅仅是簇数k。

缺点：

1、K值需要预先给定，很多情况下K值的估计是非常困难的。

2、K-Means算法对初始选取的质心点是敏感的，不同的随机种子点得到的聚类结果完全不同 ，对结果影响很大。

3、对噪音和异常点比较的敏感。用来检测异常值。

4、采用迭代方法， 可能只能得到局部的最优解，而无法得到全局的最优解 。

六、细节问题

1、K值怎么定？

答：分几类主要取决于个人的经验与感觉，通常的做法是多尝试几个K值，看分成几类的结果更好解释，更符合分析目的等。或者可以把各种K值算出的 E 做比较，取最小的 E 的K值。

2、初始的K个质心怎么选？

        答：最常用的方法是随机选，初始质心的选取对最终聚类结果有影响，因此算法一定要多执行几次，哪个结果更reasonable，就用哪个结果。      当然也有一些优化的方法，第一种是选择彼此距离最远的点，具体来说就是先选第一个点，然后选离第一个点最远的当第二个点，然后选第三个点，第三个点到第一、第二两点的距离之和最小，以此类推。第二种是先根据其他聚类算法（如层次聚类）得到聚类结果，从结果中每个分类选一个点。

3、关于离群值？

        答：离群值就是远离整体的，非常异常、非常特殊的数据点，在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉，否则会对于聚类的结果有影响。但是，离群值往往自身就很有分析的价值，可以把离群值单独作为一类来分析。

4、单位要一致！

        答：比如X的单位是米，Y也是米，那么距离算出来的单位还是米，是有意义的。但是如果X是米，Y是吨，用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方，最后算出的东西没有数学意义，这就有问题了。

5、标准化

        答：如果数据中X整体都比较小，比如都是1到10之间的数，Y很大，比如都是1000以上的数，那么，在计算距离的时候Y起到的作用就比X大很多，X对于距离的影响几乎可以忽略，这也有问题。因此，如果K-Means聚类中选择欧几里德距离计算距离，数据集又出现了上面所述的情况，就一定要进行数据的标准化（normalization），即将数据按比例缩放，使之落入一个小的特定区间。