改进的大数据分层建树KNN聚类算法牛耕（陕西警官职业学院警察技术系，西安710043）摘要：对大数据的分层建树聚类，提高对大数据的检测和大数据应用系统的故障分析能力。传统方法中对大数据的分层聚类采用K-Means聚类算法，容易陷入局部收敛，聚类效果不好。提出一种基于核向量机的数据的分层建树聚类。采用四叉树算法对多维数据进行数据预处理，进行KNN中心区域的聚类中心扩展处理，针对大数据的类域交叉性进行了一次核向量机差分比较，得到KNN模糊划分矩阵，根据所属类别的不同对已知样本进行分层，得到一维差分分层建树模型和二维差分分层建树模型，计算数据核向量之间的相似度特征，实现矩阵的数据点数模糊集合贴近度填充，实现聚类算法改进。仿真结果表明，该算法具有优越的大数据聚类性能，收敛性好，应用到网络在线故障诊断中，实现对故障信号的和恢复跟踪，提高了故障诊断效益，展示了较好的应用价值。关键词：大数据；分层建树；聚类算法中图分类号：TP391 文献标识码：A 文章编号：1001-7119（2015）08-0129-03Improved Large Data Stratification Contribution KNN Clustering AlgorithmNiu Geng(The Police Technology Department, Shaanxi Police Academy, Xian 710043,China)Abstract:on the stratified data clustering analysis of achievements, improve the capability of fault detection for large dataand data application system. K-Means clustering algorithm and hierarchical clustering for large data by using the tradition⁃al method, is easy to fall into local convergence, clustering effect is not good. Put forward a kind of contribution of hierarchi⁃cal cluster core vector machine based data. Using four binary tree algorithm of data pretreatment on multidimensional data,the clustering center of the central region of the KNN extension processing, according to the kind of cross domain of big da⁃ta for a core vector machine differential comparison, get the KNN fuzzy partition matrix, according to the category of theknown sample of different stratification, one-dimensional difference a hierarchical contribution model and two-dimension⁃al differential layered contribution model, calculating the similarity between the characteristics of nuclear data vector, therealization of matrix data points close to the degree of filling of fuzzy set. Realization of improved clustering algorithm is ob⁃tained. Simulation results show that the algorithm has excellent performance of clustering large data, good convergence, it isapplied to the online fault diagnosis network, the realization of fault signal tracking and recovery, improve the fault diagno⁃sis efficiency. It shows a good application value.Keywords:large data;hierarchical difference;clustering algorithm0 引言对数据的挖掘和聚类处理，本质就是从海量无规则的数据中提取出有用的潜在的有规则的信息。现有的分类算法有很多种，比较常用的有KNN（K - nearestNeighbor），Native Bayes，Neural Net，SVM（Support Vec⁃tor Machine）[1]，传统方法中，对此相关文献进行了深入的研究，实现对大数据环境下的异常数据扰动自动分类，但没有实现对故障监测异常数据的自适应解卷积，挖掘效果不好，对网络的故障诊断效果不好[2]。文献[3]中，提出一种基于语义相似度的大数据的奇异特征提取方法，对满足松弛挖掘的大数据进行自适应重写挖掘，但算法采用基于统计分析的方法挖掘奇异特征，受经验约束较强，特征挖掘效果不佳，对网络数据库的故收稿日期：2014-08-20作者简介：牛耕（1982-），女，陕西西安人，硕士，讲师，研究方向：计算机应用与技术。第31卷第8期2015年8月科技通报BULLETIN OF SCIENCE AND TECHNOLOGYVol.31 No.8Aug. 2015DOI:10.13774/j.cnki.kjtb.2015.08.044科技通报第31卷障诊断效果不好，不能有效实现对大数据库的极值扰动盲分离。文献[4]提出采用粒子滤波的盲解卷积技术，从海量大数据中恢复出奇异特征信号，但算法建立的粒子滤波器采用瞬时梯度下降法控制滤波加权系数，无法彻底消除挖掘信道对奇异特征具有卷积效应，对Web 故障监测异常数据的挖掘性能不好，计算量大。对此，相关算法进行改进设计，提出了支持向量机（core vector machine, CVM）和K-Means聚类方法，大减小了算法的时间和空间复杂度，但传统方法中对大数据的分层聚类采用K-Means聚类算法，容易陷入局部收敛，聚类效果不好[5]。针对上述问题，本文提出了一种基于核向量机的数据的分层建树聚类方法，进行了聚类系统模型构建和算法改进设计，通过实验进行性能测试与描述，展示了其优越的数据聚类性能。1 KNN聚类算法总体描述与问题分析经典的KNN 法最初由Cover 和Hart 于1968 年提出，其基本思想是计算它与训练样本集中每个文本的相似度，找出K 个最相似的文本，比较类的权重，将文本分到权重最大的那个类别中，进行数据聚类分析，算法描述设计如下。对已知样本进行分层，如图1所示。图1 KNN聚类分层模型Fig.1 KNN hierarchical cluster model结合图1可见，第一层只有a 和b 两个类别，如果判断出来未知样本属于a 类，那么在第二层时只需要在a1，a2，a3类中进行比较。决定测试样本的类别时，该算法只计算“最近邻的样本”[6]，数据集合中含有n 个样本，其中样本xi ，i =1,2,…,n 的特征矢量为：xi =(xi1,xi2,…,xis)T (1)比较第二层中第一类的子类，如果D12 ≤D0 则继续进行判断，进行得到聚类任务进入队列的平均时间为：W = Kˉγ =1γΣk =1K Σn =1Nkpk,n （2）大数据包转换等待时间为：Wq =W -Xˉ=1γΣk =1K Σn =1Nkpk,n - (N -1) μ +rμr（3）比较第二层中第1类中的第k 类的子类，得到KNN聚类中心利用率可以表示为：Uutil =γXˉ （4）按照差分进化思想，结合约束条件式（3），采用La⁃grange定理，产生一个初始隶属度矩阵，选出初始最优个体和全局最优个体，求得聚类目标函数的极值为：μik =1/Σj =1c (dik djk) 2 m -1 （5）Vi =Σk =1m (μik)m xk /Σk =1n (μik)m （6）通过上述算法描述，得到基于决策树KNN大数据聚类算法总体设计。但分析上算法流程可见，传统的KNN聚类算法，明显缺陷是对初始值聚类中心敏感，对噪声数据敏感等，严重影响分类的准确性，因此需要进行算法的改进设计。2 基于分层建树的KNN聚类算法改进在上述进行传统算法分析和模型构建的基础上，进行大数据聚类算法的改进设计。对大数据的分层建树聚类，提高对大数据的检测和大数据应用系统的故障分析能力。传统方法中对大数据的分层聚类采用K-Means 聚类算法，容易陷入局部收敛，聚类效果不好。提出一种基于核向量机的数据的分层建树聚类。本文设计的分层模型的基本思想是根据所属类别的不同对已知样本进行分层，假设x 是未知样本，a，b，c，d 为已知类别，其中x 到a，b，c，d 的距离分别为Δa，Δb，Δc，Δd，得到一维差分分层建树模型和二维差分分层建树模型如图2和图3所示。图2 一维差分分层建树模型Fig.2 One-dimensional layered model of differential contributiona b图3二维差分分层建树模型Fig.3 dimensional differential layered contribution model图中， 如果Δa =max{Δa，Δb，Δc，Δd} ，Δb =max{Δb，Δc，Δd} ，由于大数据具有类域交叉性的130第8期特点，本文提出了一种基于核向量机的数据的分层建树聚类方法，本文改进后的算法采用构建树状分层结构首先对高层进行比较，具体算法步骤如下：（1）对于训练文本集，考虑一组时间有序数据向量X ={x } i:i =1,2,3,…,n ，各数据向量有p 个核向量机元素，xi = (x ) i1,xi2,xi3,…,xip ,i =1,…,n ，基本分布的变化决定了必须要定期更新训练集，通过分层建树进行输出向量分支。（2）依次计算该测试文本与第1到n 层训练集，为了提高数据聚类性能，通过分层建树，计算数据核向量之间的相似度特征，实现矩阵的数据点数模糊集合贴近度填充为：Sim1(di,d1j )= Σk =1MWik ×W1jkΣk =1MW 2ik Σk =1MW 21jk(7)式中：di 为测试文本的特征向量，d1j 为第1层第j类的核向量机中心向量。继续迭代，实现KNN聚类优化。3 仿真实验与结果分析为了测试本文算法的优越性能，进行仿真实验。通过大数据聚类分析并应用在故障诊断领域。本实验将数据分为三层，具有大数据分层建树和KNN聚类，得到数据聚类结果如图4所示。聚类中心聚类测试如图5所示。图4 大数据KNN分层建树聚类结果Fig.4 Knn large data stratified contribution of clustering results图5间隔距离Fig.5 Clustering distance从图可见，采用本文算法，能有效实现对大数据的分层聚类，聚类准确度较高，收敛性能较好。采用本文算法能有效地实现对故障监测数据的重写和恢复，能准确的实现对故障信号的和恢复跟踪，通过有效聚类算法，提高了故障诊断效益。4 结论对大数据的分层建树聚类，提高对大数据的检测和大数据应用系统的故障分析能力。传统方法中对大数据的分层聚类采用K-Means聚类算法，容易陷入局部收敛，聚类效果不好。提出一种基于核向量机的数据的分层建树聚类。采用四叉树算法对多维数据进行数据预处理，进行KNN中心区域的聚类中心扩展处理，针对大数据的类域交叉性进行了一次核向量机差分比较，得到KNN模糊划分矩阵，根据所属类别的不同对已知样本进行分层，得到一维差分分层建树模型和二维差分分层建树模型，计算数据核向量之间的相似度特征，实现矩阵的数据点数模糊集合贴近度填充。实现聚类算法改进。仿真结果表明，该算法具有优越的大数据聚类性能，收敛性好，应用到网络在线故障诊断中，实现对故障信号的和恢复跟踪，提高了故障诊断效益。参考文献：[1] Yigal Bejerano.Coverage Verification without Location In⁃formation [J].IEEE Transactions on Mobile Computing,2012,11(4):631-643[2] Schölkopf B,Platt J C,Shawe-Taylor J,et al.Estimating thesupport of a high-dimensional distribution [J]. Neural com⁃putation, 2001,13(7):1443-1471[3] Rajasegarar S,Leckie C,Bezdek J C,et al.Centered hyper⁃spherical and hyperellipsoidal one-class support vector ma⁃chines for anomaly detection in sensor networks [J].IEEETransactions on Information Forensics and Security,2010,5(3): 518-533[4] Zhang Y,Meratnia N,Havinga P J M.Ensuring high sensordata quality through use of online outlier detection tech⁃niques[J].International Journal of Sensor Networks,2010,7(3):141-151[5] Ratsch G,Mika S,Scholkopf B,et al.Constructing boosting al⁃gorithms from SVMs:an application to one-class classifica⁃tion[J].IEEE Transactions on Pattern Analysis and MachineIntelligence,2002,24(9): 1184-1199[6] Szafranski M,Grandvalet Y,Rakotomamonjy A. Compositekernel learning [J].Machine learning,2010, 79(2):73-103牛耕.改进的大数据分层建树KNN聚类算法131