聚类算法优化本科毕业论文

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

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

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

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

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

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

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

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

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

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

K-means的核心算法如下：

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

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

总结下K-means算法 优点：

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

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

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

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)以及轮廓系数等等。

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

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

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

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

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

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

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

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

传统时间序列聚类的缺点： 1）时间序列聚类的研究一般采用等长划分，会丢失重要特征点，对聚类结果有负面影响。 2）采用时间序列测量值不能准确度量相似度。 如下埃博拉出血热、卫生部在数值上很相似，但教育部和卫生部在形状更相似。若是以形状作为度量传统的欧氏距离可能就不太合适了。 不等长时间序列滑窗STS聚类算法： 1）通过标准分数z_score预处理，消除时间序列观测值数量级差异的影响。 2）更改了相似度计算的方式，采用基于滑窗的方法计算不等长序列的距离。 3）采用类k-means的聚类算法的中心曲线计算方法。 时间序列数据因其趋势信息的直观展现形式，广泛应用于社交网络、互联网搜索和新闻媒体数据分析中。例如：Google应用搜索流感的相关信息的时间序列预测流感爆发趋势。根据某话题热度时间序列数据趋势的规律性，通过聚类区分不同类型的时间序列数据。同一类簇的Twitter话题具有相同或相似的发展趋势，进而应用于话题的发展趋势的预测。 时间序列聚类算法可以分为两类。 1）基于原始数据的时间序列聚类算法。 2）基于特征的时间序列聚类算法。 基于特征的时间序列聚类算法指根据原始数据从时间序列中提取形态特征（极值点位置、分段斜率）、结构特征（平均值、方差等统计值特征）、模型特征（模型的预测值），从而根据这些特征值进行聚类。这类方法的优点解决了不等长时间序列聚类问题，缺点是减弱了原始数据值得影响，聚类的形状趋势信息往往比较粗糙。 3. HOW 一、距离度量公式 STS距离计算的是累加时间序列间每个时间间隔斜率差的平方，公式 如上图所示，g1、g2和g2、g3的欧式距离的数值更相近。g1、g2的STS距离大于g2、g3的数值。在形状距离上，STS距离计算方式表现更好，一定程度上可以解决欧式距离度量时间序列局部特征信息确实和受观测数值数量级差异影响大的问题，但是依旧无法度量不等长时间序列的距离。 基于滑窗的STS距离公式。 如上图所示，当计算不同长度的时间序列的s和r的距离时，先不断平移时间序列s，然后找到s和r距离最近的字段，就如同上图虚线之间的位置，此时s和r距离最近，这个最近距离作为s和r之间的距离。 二、预处理过程 z-score标准分数用数据观测值和观测值平均值的距离代替原观测值。z-score处理后的数据平均值为0，标准差为1。标准差的作用是统一量纲，去除数值的数量级差异影响。 总结 本论文提出了形状距离的不等长时间序列的聚类方法。我们可以学到的有 1）z-score统一量纲，消除数值数量级差异，聚类效果更好。 2）计算x和y时间序列的STS距离，可以平移其中一个时间序列，求最小值作为STS距离值，这就消除了同一时间序列不同起始点的影响。