实习生的监控算法: 利用机器学习方法进行曲线分类

导语

各位老司机晚上好啊，上篇文章主要采用了Frechet Distance进行曲线分类，这篇文章主要采用机器学习的方法来实现曲线分类，基本思路是对训练集先用聚类方法(如Kmeans和Birch等进行聚类，对数据打上标签)，然后在对测试集采用分类方法(决策树，KNN等)进行分类，决定测试集中曲线的类别，实现曲线较为准确的分类。主要内容包括数据处理，聚类分类算法讨论和结果分析。

一. 数据处理

首先是数据采集，数据采集这一部分我在之前的文章”实习生的程序优化:从90min到90s”已经详细描述了数据采集的全过程，这里主要关注的是数据特征的提取和数据的标准化方法。

1.1 数据特征提取

数据特征的提取，可以把把数据特征分成三个部分:统计特征，时域特征，频域特征。当然还有很多中分法，比如在我的下一篇文章，时序特征分析的，可以将数据分为四个部分:趋势特征，周期特征，季节特征和随机特征。

先来说说数据的统计特征，统计特征主要集中在数据的中心趋势和离中趋势，中心趋势例如均值(mean)，中位数(median)，众数(mode)，中列数(midrange)等，离中趋势例如方差(variance)，极差(range)，四分位数(quartiles),四分位数极差(interquartiles range)，变异系数(coefficient of variation, CV)等

在统计特征方面，主要选择了均值，中位数，方差，变异系数。下面来解释下为啥选择这四个数值作为统计特征。

均值(mean): 这里没有直接使用均值的定义，因为均值极易受到极端值的影响。这里使用了截断均值(trimmed mean)，就是去掉极端值后剩余的数据做一个平均，在计算均值前，去掉了极端值正负1%的数据。这样就可以较为客观的反映出数据的中心趋势。

中位数(median): 其实本来想用众数的，不过数据归一化后，众数就不太好找了，也可以用中位数来表达数据的集中趋势，反映出数据的分布情况。

方差(variance): 经常被用来描述数据的离散情况，就是离中趋势和分散度。这里也是用来描述数据的离散程度

变异系数(coefficient of variation, CV): 变异系数定义为标准差与均值的比值，是数据离散程度归一化的一种描述。主要用于均值大于0的情况，优点是不需要参照数据的平均值。这个是为了消除测量尺度差距导致的误差，因为采样曲线有在好几万的数量级，也有在个位数的数量级。当然在使用变异系数时，最好将均值和标准差列出，变异系数的大小，同时受平均数和标准差两个统计量的影响。

其次是数据时域方面的特征。时域方面选择了自相关系数和信息熵作为参考。

自相关系数(auto-correlation): 也称为序列相关，直观的理解，这个系数是反映的是同一事件在两个不同时期的相关程度，就是度量自己过去的行为对现在的影响。这个系数主要在具有周期性的数据分析比较有用，可以有效的区分出具有周期的曲线数据。

信息熵(information-entropy): 这个特征表示曲线的不确定性，换句话说，如果曲线呈现不规则或者随机的变化，则信息熵越大，反之，呈现周期性或者规律性变化，则信息熵越小。这个特征可以有效分辨出不规则的毛刺数据。

最后是频域特征，频域特征我处理的比较粗糙，就是将曲线进行小波变换得到一系列小波系数(低频系数， 高频系数)。

小波变换的实质是：原信号与小波基函数的相似性。小波系数就是小波基函数与原信号相似的系数。（英文文献中是这样解释：The definition of wavelet transform shows that the wavelet analysis is a measure of similarity the basis functions(wavelets)and the original function .The coefficients caculated indicate how close the function is to the danghter wavelet at that particular scale )。

所以，处理的时候我就是简单的将小波系数去平均值，来描述曲线和基函数的相似度，区分不同特征的曲线。这一点确实有问题，关键是我对小波理论没有理解。哪位老司机带带我，怎样更好的使用小波变换描述信号的频域特征?

当然除了这些特征，我还加入了一些自己造出来的特征，例如，为了识别下面的定时任务，我加入了一个”连续为0时间长度”这样一个特征，用来专门区分定时任务。

图1 定时任务数据类型

1.2 数据标准化方法

还有其他的方法，比如用反函数(正弦，余弦，正切等)将数据映射到[-1,1]区间上，也可以实现规范化，效果也不错。

二．聚类算法实现过程

数据特征提取完之后，把数据集分为训练集和测试集，先用测试集做聚类(无监督学习)打标签，并观察输出聚类结果，调整参数直到聚类结果达到较好的效果。

聚类算法首先选用的是KMeans，这是一种选定初始质心，不断更新质心的值直到聚类结果不在发生变化的算法，Kmeans的基本步骤如下:

1. 从D中随机取k个元素，作为k个簇的各自的质心。
2. 分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。
3. 根据聚类结果，重新计算k个簇各自的中心，计算方法是取簇中所有元素各自维度的算术平均数。
4. 将D中全部元素按照新的中心重新聚类。
5. 重复第4步，直到聚类结果不再变化。
6. 将结果输出。

在实际应用时采用scikit-learn中的Kmeans函数，可以指定簇的个数(num_clusters), 选定质心的方式(init是随机还是k-means++, 官网上的例子一般是选的k-means++, 给出的解释是可以提高算法效率),还有质心误差控制tol，就是说在迭代过程中，如果质心的变化小于tol, 则算法结束。

主要调整的参数就是这三个，算法结束后会返回计算出的标签值(lables_)，kmeans聚类结果如下图所示，共3000条数据(分钟粒度)作为训练集(主要展示毛刺，定时任务和周期性变化的数据)。

图2 周期性数据(7天数据，一天不明显)

图3 毛刺(1天数据)

图4 定时任务(1天数据)

关于聚类算法的总结，昨天看到了一篇老司机的总结，写的太好了，这里就不一一总结了(文末有链接，已收藏)。我来说说我用过的方法和一些聚类算法的思考。

Birch聚类算法: Birch算法是一种层次聚类算法(hierarchical cluster)，适用场景主要是大规模数据和较多的簇，基本原理是构建一颗CF树(特征树)，通过将节点不断的加入到CF树中，调整CF树的结构，最后完成聚类。Birch算法是一种增量的俄聚类算法，如果簇不是球形的，Birch不能很好的工作，因为Birch方法用了半径的概念控制聚类的边界。

簇半径表示簇中所有点到簇质心的平均距离。CF中存储的是簇中所有数据点的特性的统计和，所以当我们把一个数据点加入某个簇的时候，那么这个数据点的详细特征，例如属性值，就丢失了，由于这个特征，BIRCH聚类可以在很大程度上对数据集进行压缩。所以，半径和质心的选择会影响CF树的规模。

Scikit-learn中Birch算法主要调整两个参数，一个是n_cluster(簇的个数)，另一个是compute_lables(计算标签)。还有一个branching_factor主要用于调整CF树的规模，这个我不太会调，因为我不太清楚这个参数和样本规模之间的准确关系，所以我是使用的默认值。如果有老司机知道的话，快带我上车。

Mean-Shift聚类算法: 基于质心的一种算法。这个算法不用指定簇的个数，而是给出一个estimate_bandwith这个值，由这个值来决定簇的个数。基本思路是通过一个不断移动的高维圆，规定一个Mean-shift向量，向概率密度高的地方不断移动，将概率密度高(相似的)的数据归为一类。

这个算法结果也不错，在使用过程中estimate_bandwith这个值对最后结果产生主要影响。scikit-learn中estimate_bandwith有两个参数quantile(我理解的是计算mean-shift向量所需要的样本百分比), n_samples每次计算所需要的样本数。对于采集到的样本，quantile=0.2，n_samples=250聚类结果较为合理，将数据集聚类为6种，定时任务和毛刺数据可以区分。

这里就介绍了运行结果比较好的算法，关于其他的聚类算法。老司机们可以参考scikit-learn官网(文末有链接)。

三．分类算法实现过程

训练集聚类完成打上标签过后，就可以对测试集进行分类了。分类算法我主要尝试了两种，决策树和KNN。

先来看下决策树，scikit-learn中DecisionTreeClassifier提供了很多参数，详细的解释如下图所示，实际应用的时候我只调整了一个参数criterion就是选择采用信息熵还是基尼系数构建决策树。

决策树明显的优点就是结果易于解释，整个过程也比较好理解。看了一些论文和博客，感觉决策树算法很像人类做决策的过程。计算复杂度还好，泛化能力高，预测出来的结果较为准确。只需要少量的数据就可以做出较为精确的预测。

决策树的缺点就是容易过拟合，设置叶节点所需的最小样本数(min_samples_split)可以避免这个问题。还有就是通过剪枝也可以避免过拟合的问题，关于如何剪枝我没有进行深入的研究，哪位老司机懂得话，萌新求上车，带带我啊。还有就是决策树生成的时候一般采用的是贪心算法，可能会陷入局部最优解，达不到全局最优。

采用决策树方法分类的结果如下图所示:

图5 毛刺数据(1天数据)

图6 定时任务(1天数据)

图7 周期性规律数据(7天数据)

可以看出，决策树分类算法比较有效，可以将毛刺数据和定时任务和周期性任务加以区分。

但是决策树生成的规则有点复杂，我用一天的数据进行训练，决策树一共生成了近2000条分类规则。这些过于复杂的分类规则会不会影响测试集的分类结果呢，这个有待进一步深究，就分类效果看来，复杂的规则没有对分类结果产生重大的影响。

再来看下KNN(K近邻)算法，这种被称作懒惰学习(lazy-learning)的方法。KNN是基于距离的一种分类方法，基本思路是如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。

KNN的优点就是简单，不需要估计参数和训练，适合对多分类问题进行分类。

KNN的缺点是计算量大，因为对于每一个待分类的数据都要计算距离，开销大。而且当出现样本倾斜时，可能会使分类效果变差。

KNN算法现在出现了一些变种算法，采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN (weighted adjusted k nearest neighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。

其他的一些分类算法比如说SVM(这个比较适合二分类)，随机森林(RandomForest,这个我也尝试了下，直白点就是多个决策树做决策，效果不错)。还有一些基于贝叶斯的分类方法，比如scikit-learn中的GaussaianNB(这个我没有尝试，因为没有完全理解算法原理，回学校会关注下贝叶斯分类器的原理)。

四．结尾

这篇文章的思路和做法和之前在KM上的文章很类似，这里只是详细的描述曲线分类过程中自己遇到的问题和解决方法。但是还是有一些缺陷的，比如对于定时任务的分类:

可以看出，定时任务数据中混入了一些其他的数据，仔细观察了下属于毛刺数据。一开始怀疑是聚类或者分类算法没有选好，但是在分析试验多个算法过后，范县结果并没有明显的改善。仔细分析过后，觉得是数据特征提取的问题，之前虽然加入了一个”连续为0的时间长度”这样一个特征，然而还是没有区分出来。或许可以考虑小波变换，从频域的角度考虑下这个问题，因为看起来毛刺数据和定时任务应该在频率上有明显的分别，这个我回去好好学一下小波变换相关的知识。

下一篇文章萌新想从时间序列挖掘方面对监控平台的曲线预测做的工作做一个介绍，时间序列模型我觉得还是挺有意思的。

图8 定时任务混入了一些毛刺数据

参考文献:

1.scikit-learn官方网站: http://scikit-learn.org (搜索框输入clustering可以看到所有聚类算法的说明和对比)

2.数据挖掘:概念与技术 第二版(数据特征提取和处理方面的参考书)

3.维基百科关于数据频域时域特征的解释(小波变换，自相关，信息熵等)

4.麦子学院的机器学习课程，关于机器学习的方法我就是看这个课程入门的

5.聚类方法的总结：机器学习：基于层次的聚类算法