K-means优化（精选7篇）
K-means优化 篇1
0引言
K-means算法是一种使用广泛的分割聚类算法,它取类中所有样本点的平均值作为类的中心,因此k-means聚类算法易受孤立点数据的影响,导致算法可能收敛于局部最优值。为避免此问题的出现,该文介绍一种优化初始聚类中心的改进k-means算法,它基本消除了孤立点对聚类结果的影响,使聚类准确率获得明显提高。
1基于初始中心优化的k-means算法
传统K-means算法对初始聚类中心具有较强的依赖性,不同的初始中心导致每次的聚类结果有所不同。通常,我们选择相互距离最远的k个数据对象作为中心点,但是如果仅基于距离,容易取到噪声数据,因此在选择初始聚类中心时,我们可以将密度和距离因素都考虑在内。为此,该文提出了基于密度和距离的优化初始中心的k-means算法,优化算法的主要思想是取相距最远的处于高密度区域的k个样本点作为初始聚类中心。下面定义样本点α 所处区域的密度:
其中D为样本点集,r为球体半径, Dis (α,d)为距离测量。样本点 α 所处区域的密度是以 α为中心,r为半径的球体所包含的样本点数。半径r的确定方法如下:
<1> 求解每两个数据对象的距离,然后求出所有距离的均值 λ
<2> 用户根据经验给出一个常数β,半径r = λ * β
求出每个样本点所处区域的密度, 然后将高密度区域中的所有点组成集合ZA,在集合中取Density值最大的样本点作为第一个初始中心c1,然后取离c1最远的高密度样本点作为第二个初始中心c2,然后取满足max(min(d(αi, c1),d(αi,c2))) i=1,2,…,n的样本点αi作为第三个初始中心c3,依次类推,取满足max(min(d(αi,c1),d(αi,c2),… d(αi,cq-1))) i=1,2,…,n的样本点 αi作为cq,最后确定了聚类的k个初始中心。
综上所述,改进算法取距离最远的k个高密度样本点作为聚类的初始中心, 这些中心点基本上是稳定的,进而消除了初始中心选择的随机性,提高了聚类结果的精确度。
2实验
为证明优化算法的高效性,本文采用两种数据集对算法进行测试,分别从初始中心,循环次数,准确度三个方面对传统K-means(KMS) 算法,优化的K-means(PKMA) 算法的实验结果进行比较。其中Iris数据集为160,每个数据有5个属性属性,正确聚类个数为4, glass数据集为220, 每个数据有10个属性,正确聚类个数为5。
由表1可以看出,传统k-means算法平均收敛速度较慢,并且聚类结果的平均正确率较低。相反,改进算法不仅结果平均正确率高于传统k-means算法, 而且收敛速度获得明显提高。从实验结果中还可得出,传统k-means算法的收敛速度有时优于PKMA,但结果正确率低于60%。这表明传统k-means算法的初始聚类中心易受孤立点和噪声数据的影响而使聚类结果收敛于局部最优值, 降低了聚类质量;而PKMA算法的优化初始中心基本符合数据的实际分布,使算法尽快收敛于全局最优值,从而提高了聚类正确率。
3结论
本文介绍了一种优化初始聚类中心的方法,实验证明,该方法可降低孤立点数据对聚类结果的影响,进而提高了聚类正确率。
K-means优化 篇2
K-Means算法是聚类分析中使用最为广泛的算法之一, 该算法简单、计算速度快、资源耗费少, 尤其对大型数据集的处理效率较高, 在网络信息处理领域有着广泛的应用[1]。
K-Means算法是以随机选取的初始聚类中心为前提, 从而该算法有个明显的缺陷[2]:不同的初始聚类中心会导致聚类的结果差别很大, 导致算法容易陷入局部最优解而找不到全局最优解, 这在很大程度上影响其聚类效果。
针对算法K-Means算法随机选取的初始聚类中心的缺陷, 进行改进的方法有很多。文献[3]通过k-dist的差值 (DK) 图分析, 选择主要密度水平曲线上k-dist值最小的点作为初始聚类中心。文献[4]提出基于数据样本分布选取初始聚类中心的改进k-means算法。王丽娟等人[5]提出了基于随机取样的选择性K-means聚类融合算法 (RS-KMCE) , 避免了算法陷入局部最优解。王永贵等人[6]提出结合双粒子群和K-means的混合文本聚类算法, 发挥了两者优势, 提高了算法鲁棒性和准确性, 产生了较好的聚类效果。
在研究K-Means算法及其一些改进算法的基础上, 本文提出采用基于最远距离的方法选取初始聚类中心。
1 改进 K-Means 聚类算法
为了避免最终仅得到局部最优结果, 选取最具有代表性的相互距离最远的K个点作为初始聚类中心。
数据对象之间的相似度采用欧氏距离来进行度量, 公式为:
目标函数采用误差平方和准则函数, 公式为:
优化初始聚类中心的K-Means算法描述如下:
输入包含n个数据对象的数据集
输出聚类结果
(1) 在数据集里随机取一数据点xa, 计算距离xa最远的数据点xb, 然后计算距离数据点xb最远的数据点xc, 若Dab>=Dbc, 则xa、xb为距离最远的两个数据点;若Dab
(2) 将距离最远的两个数据点作为最初的两个初始聚类中心;
(3) 在数据集中寻找下一个聚类中心xk, 其必须满足
(4) 将n-k个数据对象按照最近距离划分到k个聚类中心, 计算目标函数值E, 若Ek>=Ek+1, 则输出k个聚类结果;若Ek
2 实验分析
2.1 实验一
为验证上述算法, 选用UCI数据库上的Iris数据作为测试数据。UCI数据库是加州大学欧文分校提出的用于测试机器学习、数据挖掘算法的数据库, 库中的数据都有确定的分类, 因此可以用准确率直观地表示聚类的质量。
传统K-Means算法进行5次运算和本文改进K-Means算法最终运算结果如表1所示, 通过表1说明了改进K-Means算法的准确率优于传统K-Means算法。
2.2 实验二
实验选择数据集KDD cup 1999作为测试数据, 该数据集是网络入侵检测的标准, 这些数据全部采用tcpdump格式, 每条记录包涵34个数字型字段和7个非数值型字段, 并带有Normal, Probe, Do S, R2L, U2L五种标签。Normal, Probe, Do S, R2L, U2L五种标签。
为了更好的说明算法的改进效果, 实验过程中对数据进行了筛选, 只从数据集中选择出10000条数据记录, 其中Norma记录9500条, Do S记录300条, Probe记录100条, R2L记录50条, U2L记录50条。除此之外, 对数据记录中对实验结果影响不大的属性除去, 只取其中12种关键属性, 包括3个离散型属性和9个连续型属性。
对选择好的数据集同时运用传统K-Means算法和改进K-Means算法进行聚类, 得到的初始聚类中心类型以及聚类结果如表2和表3所示。
从表2和表3中可以看出, 按数据所占比例来看, 传统K-Means算法得到的5个聚类结果中Normal数据占有较高的比例, 因此5个聚类都为Normal聚类。虽然对数据进行了一定的划分且有较高的准确率, 但该聚类结果未能有效标记出异常的攻击数据。而改进K-Means算法除了聚类1、聚类3和聚类5为Normal数据聚类外, 还得到了两个异常聚类:聚类2和聚类4。在聚类2中Do S中类型的数据占记录总数的绝大多数, 因此可以记为Do S聚类;而在聚类4中Probe类型的数据占记录总数的绝大多数, 因此可以记为Probe聚类。与传统K-Means算法相比, 改进K-Means算法对数据进行了有效划分, 且提高了算法的准确率。
3 结束语
针对K-Means算法由于随机选取初始聚类中心和而造成聚类精度及效率降低等问题, 提出了一种改进的K-Means算法。实验验证, 相对于传统K-Means算法, 改进K-Means算法能够获得更好的聚类效果。在实际应用中, 将改进的K-Means算法运用到僵尸网络检测系统, 对于提高僵尸网络的检测率将发挥更好的作用。
摘要：针对K-Means算法所存在的问题, 提出了一种改进的K-Means算法, 该方法通过选取相互距离最远的数据点作为初始聚类中心, 能够很好地排除随机选取初始聚类中心点的影响。通过实验验证, 相对于传统K-Means算法, 改进K-Means算法能够获得更好的聚类效果。
关键词：K-Means算法,距离最远,初始聚类中心
参考文献
[1]杜强, 孙敏.基于改进聚类分析算法的入侵检测系统研究[J].计算机工程与应用, 2011, 47 (11) :106-108, 181.
[2]孙吉贵, 刘杰, 赵连宇.聚类算法研究[J].软件学报, 2008, 19 (1) :48-61.
[3]郑丹, 王潜平.K-Means初始聚类中心的选择算法[J].计算机应用, 2012, 32 (8) :2186-2188, 2192.
[4]仝雪娇, 孟凡荣, 王志晓.对k-means初始聚类中心的优化[J].计算机工程与设计, 2011, 32 (8) :2721-2723, 2788.
[5]王丽娟, 郝志峰, 蔡瑞初等.基于随机取样的选择性K-means聚类融合算法, 计算机应用, 2013, 33 (7) :1969-1972.
K-means优化 篇3
聚类分析是多元统计分析中的一种, 也是非监督模式识别的一个重要分支[1]。它把一个没有类别标记的样本集按某种准则划分成若干个子集 (类) , 使相似的样本尽可能归为一类, 而不相似的样本尽量划分到不同的类中。聚类通过比较数据的相似性和差异性, 能发现数据的内在特征及分布规律, 从而获得对数据更深刻的理解与认识。聚类分析也是知识发现的重要工具, 其中的文本聚类是模式识别、机器学习、统计学和信息检索技术相互结合发展的结果。文本聚类在信息检索, 邮件过滤和网页分类等领域有广泛的应用。
1 问题的提出
聚类算法多种多样, 大致可以将它们分为基于划分、基于层次以及基于网格的方法。其它的聚类算法还有Methods Based on Co-Occurrance of Categorical Data、Constraint-Based Clustering、Clustering Algorithms Used in Machine Learning、Scalable Clustering Algorithms和Algorithms For High Dimensional Data等方法。其中基于层次的方法可以分为凝聚算法 (Agglomerative Algorithms) 和分裂 (Divisive Algorithms) 算法两种。按照度量两簇临近度的不同方式, 基于层次的凝聚聚类算法分为单链接、全链接和平均链接三种[2]。
基于划分的聚类主要是K-平均及其变种。它们聚类速度快、易于实现, 而且还适合于文本、图像特征等多种数据的聚类分析。然而, K-平均算法目的是通过在完备数据空间的不完全搜索, 使得目标函数取得最大值。由于局部极值点的存在以及启发算法的贪心性, 传统的K-平均算法对初始聚类中心敏感, 从不同的初始聚类中心出发, 得到的聚类结果也不一样, 并且一般不会得到全局最优解。在实际应用中, 由于初始输入不同而造成结果的波动是不能接受的。因此, 怎样找到一组较优的初始中心点, 从而获得一个较好的聚类效果并消除聚类结果的波动性对K-平均算法具有重要意义。本文以该问题为出发点, 先采用文献[3]中提出的一种改进的遗传算法来获取近似最优聚簇数K, 然后采用一种数学模型来获得一组优化初始聚点。
2 优化初始点的K-平均
如上所述, K-平均算法聚类结果有波动性, 造成这一结果的原因是由于局部极值点的存在以及启发算法的贪心性, 使得K-平均算法对初始聚类中心敏感[4,5]。因此, 从不同的初始聚类中心出发, 会得到不一样的聚类结果。为此提出了一种对初始聚类中心点优化的思路:先用一种改进的遗传算法获得文档集合的近似最优聚簇数K, 然后采用网络中心与重心数学模型来获得优化的初始聚类中心点。
2.1 改进GA (Genetic Algorithm) 获得聚簇数K及文档集合的密集区域
本文的思路之一是先采用遗传算法来获得聚类的簇数该遗传算法使用Calinski and Harabasz Stopping Rule中的VRC (Variance Ratio Criterion) 作为适应度函数[6,7]。
(1) The Calinski and Harabasz Stopping Rule
①假设有N个文档, 每个用V维向量表示, 在V维欧几里德空间这N个文档表示成为N个点。
②计算文档间的距离矩阵Dn*n。根据距离矩阵得到最小生成树 (Minimum Spanning Tree) 。
③若要将N个文档划分为K个簇, 则要删除最小生成树上的K-1条边。为了得到最优K值。该方法从K=2开始, 对每种可能的划分计算VRC (Variance Ratio Criterion) 值:
undefined
其中, WGSS为簇内各点到簇中心的距离平方和, BGSS为各簇间的距离平方总和, N为文档数。该方法采用VRC作为判断K是否为最优的一项非正式指标。从K=2, 3, ……选择VRC绝对值最大时对应的K为聚簇数。改进的遗传算法使用VRC作为适应性函数。
(2) 改进的遗传算法 (Genetic Algorithm)
遗传算法是根据自然界“物竞天择, 适者生存”现象提出的一种随机搜索算法。遗传算法起源于对生物系统所进行的计算机模拟研究。早在本世纪40年代, 就有学者开始研究如何利用计算机进行生物模拟的技术, 他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。60年代后, 美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发, 创造出了一种基于生物遗传和进化机制的适合子复杂系统优化计算的自适应概率优化技术——遗传算法[8]。
本文采用的遗传算法基于Calinski and Harabasz Stopping Rule。使用一个n-1维向量来存储两个信息, 该向量的n-1个元素代表MST (最小生成树) 的n-1条边, 元素值为“0”表示该元素代表的最小生成树的边被保留, 元素值为“1”表示该元素代表的最小生成树的边被淘汰;向量中值为“1”的元素个数为k-1, 其中k为簇数。例如:含有5个文档的集合, 它的最小生成树含有5个节点、4条边, 代表它的一个染色体向量是 (0, 1, 1, 0) , 这个向量表示该最小生成树保留第1, 第4条边, 删除第2, 第3条边, 此时k=3。
改进遗传算法:
①选择双亲, 根据自然遗传规律具有最好适应性的染色体产生子代的概率最大。从表示文档集合最小生成树的向量 (染色体或个体) 中选择具有最大VRC值的个体来遗传生成子代。
②交叉, 一旦双亲产生了两个子代, 两个子代都将遗传到双亲的基因 (信息) , 在此采用随机选择染色体交叉点。例如:
双亲染色体:pa=0110 pb=1001
如果随机选择交叉点为C=2, 则产生的子代为:oa=0101 ob=1010
在遗传算法中随机选择交叉点, 使得各个点的机会均等。
③变异, 在进化遗传过程中, 会出现一种基因突变现象。为了保证所有的染色体都被探测到, 本文使用了一个较低的变异概率0.008%。
④停止标准, 为了使遗传算法收敛于一个最优解, 使用了两个重要的常用停止标准。第一个是当适应性最好 (VRC值最大) 的染色体个体不在发生变化时停止迭代。第二个是当达到最大遗传迭代数时停止, 取最大迭代数为文档个数n。
算法结束后, 从所有染色体向量中选择VRC值最大的向量, 因为VRC值越大, 得到的K值就越好。通过该向量代表的信息, 也可以得到文档集合的一个初始划分, 遗传算法使得相似高的文档的文档尽可能处于一个划分中。
2.2 优化初始中心的K-平均
遗传算法结束后, 得到文档集合的初始划分, 对这些划分本文采用网络中心与重心数学模型来获得优化的中心点。网络中心的概念可定义为:设D= (dij) n×n为一网络N中各点间的最短距离矩阵, 令undefined, 如果undefined, 则称点νk为该网络的中心。通过最短距离矩阵找到的中心点充分考虑了各个节点间的最短路径, 因此该中心点能很好地代表该簇。本文将每个簇看成是一个网络来计算它的优化中心点。步骤如下:
(1) 写出各文档节点间的距离矩阵W。文档节点间的距离用相似度的倒数1/sim (dl, dm) 来度量, 相似度为simundefined, 因为两个文档的相似度越大, 其距离越近。在距离矩阵中节点νi到νi的距离记为0, 相似度小于给定阈值的文档节点间的距离为无穷大, 但为了方便计算将其设为一个足够大的实数, 这并不影响计算的结果。
(2) 根据距离矩阵求出各点间的最短路径, 即最短距离矩阵。记矩阵Dk=a (dundefined) n×n, 当k=1时, 令D1= (dundefined) n×n≜ (wij) n×n=W。定义DK=Dk-1*Dk-1, k=1, 2, …, p, DK中元素值的求法是, 矩阵DK-1中对应的行列元素相加后取各个分量中最小值, 即:undefined。若在计算过程中出现Dk=Dk-1, 则停止计算, 且Dk就是各点间的最短距离矩阵。
(3) 对最短距离矩阵进行分析, 根据网络中心的定义, 依次从各行中找出各个节点到各个节点最短路中最大值, 然后取最大值中那个最小值对应的节点作为中心节点。该中心节点到其余各节点路径最短, 即为求得的优化中心点。
(4) 采用优化的中心点进行K-平均聚类并与传统的K-平均聚类进行比较。
3 实验及算法评估
在实验过程中, 将传统的K-平均算法与优化初始中心点后的K-平均算法对时间效率和聚类效果等方面进行了比较。
3.1 测试数据集
本文采用的sogou文本分类语料库来源于Sohu新闻网站保存的大量经过编辑手工整理与分类的新闻语料与对应的分类信息。涉及十几个分类节点, 网页规模为十万篇文档。本文从中构造一个测试数据集合进行评测, 如表1所示。
3.2 实验步骤及结果
(1) 对文档集合进行预处理, 用向量模型表示各个文档。
(2) 计算各文档间的相似度, 构造连通图, 图的节点表示各个文档, 边用两文档间相似度的倒数表示 (相似度越大边的长度越短) 。
(3) 依据连通图构造最小生成树。
(4) 通过改进的遗传算法取得文档集合的密集区域划分如下:
①选择最优个体进行遗传迭代。取k=2…n (n为文档个数) , 用n-1维向量表示最小生成树。该向量的n-1个元素代表MST (最小生成树) 的n-1条边, 元素值为“0”表示该元素代表的最小生成树的边被保留, 元素值为“1”表示该元素代表的最小生成树的边被淘汰。在所有的向量表示中有k-1个元素值为“1”, 从所有n-1维向量中选择VRC值最大做为最优个体。
②通过上文改进的遗传算法得到密集区域的划分。
(5) 对密集区域采用网络中心数学模型计算得到优化的初始聚类中心点。实验结果如表2所示。
4 结束语
通过实验发现, 在小规模的数据集上, 经过优化初始中心点K-平均聚类算法的准确率有明显提高, 消除了算法对初始聚类中心的敏感性。但通过实验发现, 该初始中心优化的聚类算法计算量较大, 且优化过程占整个聚类过程的时间较多, 在以后的工作中, 将改进优化算法, 提高该算法的效率, 并在大的数据集上进行测试验证。
摘要：从传统K-means算法对初始中心的敏感性分析出发, 提出了一种优化初始聚类中心的算法。该算法结合一种改进的遗传算法和网络中心数学模型对初始中心进行优化, 有效地解决了算法对初始聚类中心的敏感性问题, 取得了较好的实验结果。
关键词：K-平均算法,聚类中心,遗传算法,网络中心
参考文献
[1]HANJW, KAMBER M.Data Mining Concep ts and Techniques[M].BeiJ ing:ChinaMachine Press.2001:223-259.
[2]熊云波.文本信息处理的若干关键技术研究[D].复旦大学博士论文, 2006:9-30.
[3]Casillas A, GonzálezdeLena MT, Martínez R.Document clusteringinto an unknown number of clusters using a Genetic Algorithm[C].Interna-tional Conference on Text Speech and Dialogue TSD, 2003.
[4]Willett P.Recent trends in hierarchic document clustering:a critical re-view[J]//Information Processing and Management, 1988, 24 (5) :577-597.
[5]KANUNGOT, MOUNTDM, NETANYAHUNS, et al.An Efficient K-Means Clustering Algorithm:Analysis and Implementation[J].Pattern Analysis andMachine Intelligence, 2002, 24 (7) :881-892.
[6]Goldberg D E.Genetic Algorithms in Search, Optimization, and Machine Learning[C].Addison Wesley Longman, Inc, 2002.
[7]Estivill-Castro V, Murray AT.Spatial Clusteringfor Data Mining with Genetic Algorithms[C].Proceedings of the International ICSC Sympo-siumon Engineering of Intelligent Systems, EIS-98, 1998.
K-means优化 篇4
聚类分析是统计分析、机器学习领域的重要研究方向。聚类分析中使用最为广泛的传统k-means算法对初始聚类中心敏感, 通常受到初始聚类条件的影响, 不同的初始中心往往对应着不同的聚类结果。因此对初始聚类中心优化以便取得更好的聚类效果成为目前聚类算法研究的热点。
聚类分析是通过数据建模简化数据的一种方法, 目的是将物理或抽象对象的数据集合分组成为由类似的对象组成的多个类。为了提高聚类分析器的准确率, 通常是对数据进行预处理, 为衡量数据点间的相似度定义一个距离函数, 用以获取一个偏差小的正确性高的数据集。但是这样也使统计分析出现了种种问题。第一, 聚类所要求划分的类是未知的, 预处理后的数据集可能对聚类结果的正确性有所降低。第二, 由于特征类型和特征标度的多样性, 距离度量经常依赖于应用, 由于相似度的定义差异可能对聚类的结果产生不同的差异。第三, 将数据对象划分到不同的类中, 由于划分的聚类分析算法不同, 结果也不同。这样, 准确有效的选择一个划分聚类的算法, 不仅有助于提高聚类分析的效率, 还能有效提高聚类分析结果的准确率。因此, 近些年来很多机器学习方面的学者对聚类分析算法感兴趣, 也使得聚类分析成为机器学习领域的一个重要研究方向[1]。
k-means聚类算法, 首先创建k个划分, k为要创建的划分个数;然后利用循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。但是在实际应用中, 通常遇到的困难是: (1) 对初始聚类中心敏感, 不同的初始聚类中心将产生不同的聚类结果; (2) 评价函数的选取也比较复杂, 求解最优聚类结果不是很理想。
针对以上问题, 通过对初始聚类中心点的优化可以使得到的聚类分析结果尽可能符合实际需求, 而不仅仅是将传统的聚类分析算法优化到最优。初始聚类中心点优化的k-means算法在现实中将更加符合用户的应用需求。
1 聚类分析中k-means算法介绍
k-means算法接受输入量k;然后将n个数据对象划分为k个聚类以便使所获得的聚类满足:同一聚类中的对象相似度较高, 而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象” (引力中心) 来进行计算的。首先从n个数据对象任意选择k个对象作为初始聚类中心;而对于所剩下其它对象, 则根据它们与这些聚类中心的相似度 (距离) , 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类;然后再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) ;不断重复这一过程直到标准测度函数开始收敛为止。[2]一般都采用均方差作为标准测度函数。k个聚类具有以下特点:各聚类本身尽可能紧凑, 而各聚类之间尽可能分开。
设需要聚类分析的数据集为:
k个聚类中心分别为Z1, Z2, ……ZK, 用Wj (j=1, 2, ……k) 表示聚类分析的k个类别。再有如下的定义:
定义1:两个对象之间的欧式距离为
定义2:隶属于同一类别的数据对象的算术平均为
定义3:目标函数
传统的k-means算法具体描述如下:
输入:聚类个数k以及包含n个数据对象的数据集
输出:满足目标函数值最小的k个聚类中心
(1) 从n个数据对象中由用户选择k个对象作为初始聚类中心;
(2) 循环下述流程 (3) 到 (4) , 直到目标函数J取值不再变化;
(3) 根据每个聚类对象的均值 (中心对象) , 计算每个对象与这些中心对象的距离, 并且根据最小距离重新对相应对象进行划分;
(4) 重新计算每个聚类的均值 (中心对象) 。
聚类分析中的划分方法k-means算法是一种基于划分的聚类算法, 目的是通过在完备数据空间的不完全搜索, 使得目标函数取得最大值。由于局部极值点的存在以及启发算法的贪心性, 传统的kmeans算法对初始聚类中心敏感, [3]从不同的初始聚类中心出发, 得到的聚类结果也不一样, 并且一般不会得到全局最优解。本文的主要目的就是研究和分析了目前对传统k-means算法进行初始聚类中心点优化的方法, 并在此基础上提出了一种改进算法。
2 改进的基于密度分析初始中心点优化的k-means算法
在一般的基于贪心算法的初始中心点聚类分析过程中, 由于是基于距离因素来进行判断, 所以往往找到许多孤立的点作为中心点。实际上, 对于初始中心点, 不但希望分布得尽量散开之外, 还希望这些选取的中心点具有一定的代表性, 即具有较高的密度特征。所以有了上述基于密度分析对初始聚类中心点优化的k-means算法。但是基于密度分析的算法是基于输入的数据服从高斯混合分布的假设提出的, 即认为输入数据集的密集区域中包含的是自然聚类划分, 从而通过划分高密度点中的各个点的距离得到聚类的初始中心。该算法的局限性在于它仅在凸形结构的数据集上有较好的聚类效果, 却不适合具有任意复杂形状的聚类实际问题。针对高斯函数的局限性, 我们可以提出另外一种基于密度区域逐个提取的初始中心点选择算法[4]。采用密度敏感的相似性度量函数来满足聚类的全局特征分布结构, 逐个从数据集中选取密度高的点, 直至取完k个为止。其中第一个初始点是选择密度最大的点, 其余的点则根据一个启发式的规则依次从剩余的点中选取。
先对算法进行一些定义, 为了计算数据对象Xi所处区域的密度, 可以定义一个密度参数:以Xi为中心, 包含常数个R (可以自己定义个数) 数据对象的半径称之为对象Xi的密度参数, 用ε表示。ε所取的值越大, 说明数据对象所处区域的数据密度越低。反之, ε的取值越小, 说明数据对象所处区域的数据密度越高。通过计算每个数据对象的密度参数, 就可以发现许多处于高密度区域的点, 从而得到一个高密度点集合。
算法的基本思想是首先在数据集当中选择密度最大的一个点作为第一个初始中心点, 然后在数据集中删去该点及其邻域 (即R个数据对象) 内的所有数据对象, 再按同样的方法确定第二个初始中心点, 以此类推, 循环执行直到初始中心点集中有k个点为止。改进的基于密度分析对初始聚类中心点优化的k-means算法描述如下:
输入:包含x个数据对象的数据集
输出:满足目标函数值最小的k个聚类中心
(1) 计算数据集当中任意两个对象间的距离d (Xi, Xj) ;
(2) 计算每个数据对象的密度参数, 得到所有数据对象的密度集合M;
(3) 选择密度最大的数据对象作为第1个初始中心Z1, 然后在数据集中删去Z2及其邻域 (即R个数据对象) 内的所有数据对象;
(4) 对于第2个初始中心点, 则可以根据同样的方法确定, 即是在现在的数据集的所有点当中计算并选择密度最大的数据对象作为第2个初始中心Z2, 然后在数据集中删去Z2及其邻域 (即R个数据对象) 内的所有数据对象。后面新的初始中心也可以此类推得到。
(5) 从这k个聚类中心出发, 使用k-means聚类算法, 得到聚类结果。
(6) 输出得到的k个聚类中心结果。
对于聚类分析算法而言, 主要的困难在于算法要适应实际应用中的各种情况, 聚类应用都是根据经验和实验来确定参数的取值。对于改进的基于密度分析对初始聚类中心点优化的k-means算法而言, 由于密度参数和邻域所包含的数据个数是未知的, 所以它们的取值因实验数据的不同而不同, 并且会影响到初始中心点的选择和最终生成的聚类结果, 所以密度参数和邻域所包含的数据个数都可以根据实际应用由经验判断给出。邻域所包含的数据个数要尽可能的反应出数据集的特征结构分布, 过大或者过小均不能有效的达到最优聚类效果。相对现有的初始化聚类中心方法而言, 改进后的算法优点如下: (1) 与未作改进的基于密度分析对初始聚类中心点优化k-means算法相比, 改进后设计的密度可在距离测度上直接计算数据特征的相似度。这样既可以满足数据在同一分布上的数据点具有较高的相似性, 还可以克服未作改进的基于密度分析的算法对于尺度敏感的缺陷; (2) 在实际的应用中, 对于不同的数据集, 可以根据经验判断选择合适的密度参数和邻域所包含的数据个数。
3 结束语
在本文的基础之上, 还有一些问题是值得进一步的探讨:
(1) 对于在实际应用中适合不同情况下使用的kmeans算法的选择问题。在传统的k-means算法聚类分析效率不高的情况下, 面对众多对初始聚类中心点优化的k-means算法, 在实际应中选择哪一种算法才能最符合实际情况, 使得得出的聚类中心结果最大程度上反应出数据集的特征结构分布, 达到我们想要的最优分类效果。如何选择和使用也是研究k-means算法优化的关键部分。
(2) k的取值优化以及聚类效果评价标准的问题。聚类划分个数k要求用户事先给定k值, 实际操作过程中, 由于缺乏经验, k值一般是难以确定的。在实际使用k-means聚类算法过程中, 我们最关心的就是到底要分多少类, 因为没有一个已存在的划分类别给与学习经验。具体体现在两个问题上, 一个是最优的聚类结果个数到底如何才能确定, 另一个则是聚类分析之后的结果到底在实际应用当中能不能有效的正确体现出数据的分布特征和内在结构。
参考文献
[1]李双虎, 王铁洪.K-Means聚类分析算法中一个新的确定聚类个数有效性的指标[J].河北省科学院学报, 2003 (4) .
[2]Wang Shou-Qiang, Zhu Da-Ming.Research On SelectingInitial Points For K-Meansclustering[C].Proceedings Of The Seventh International Conference On Machine Learn-ing And Cybernetics, Kunming, 2008
[3]袁方, 周志勇, 宋鑫.初始聚类中心优化的k-Means算法[J].计算机工程, 2007, 33 (3) .
K-means优化 篇5
聚类的基本任务是为对象集合中所有存在特征相似或接近的对象个体进行类别标记。目前,比较流行的聚类方法有划分法、层次法、密度法、网格法等。在众多的聚类方法中,K-means聚类算法是一种应用广泛的无监督聚类划分方法。K-means聚类算法具有算法简单、时间复杂度低等优点,在数据呈球状分布的领域有着较好的聚类效果。但是,由于K-means聚类算法通过随机的方式来确定初始聚类中心,所以其聚类结果呈现出一定的不稳定性,并容易陷入局部最优解。为了提高K-means聚类稳定性,人们对初始聚类中心进行了各种优化。汪中等[1]提出了通过采用密度敏感的相似性度量来计算对象的密度,以此来启发式地生成样本初始中心的方法。赖玉霞等[2]提出了采取聚类对象分布密度方法来确定初始聚类中心,然后选择相互距离最远的k个处于高密度区域的点作为初始聚类中心的方法。张斌等[3]提出了基于距离估计优化初始聚类中心的K-Means算法。上述三种算法分别从密度分布和距离角度来选择聚类初始中心点,但没有考虑类蔟的规模对聚类结果的影响。曹付元等[4]提出了利用邻域模型中对象邻域耦合度和分离度实现初始聚类中心选择的K-Means算法。Fouad Khan[5]提出了在具有最大对象间隔的特征基础上生成初始聚类中心的K-means算法。上述两种算法直接在对象几何参数上进行选择初始聚类中心,当干扰较大时其聚类效果受影响的概率较大。Juanying Xie等[6]提出了通过全局搜索稳定的对象位置来生成初始聚类中心的K-means算法。该算法在对象规模较大时时间复杂度也较大。Yan Zhu等[7]提出了通过AP算法来生成初始聚类中心的CAK-means算法,该算法在AP生成的所有聚类中心基础上进行K-means聚类,并通过比较最终的聚类效果以选出最佳的初始聚类中心,其聚类效果较好但时间复杂度较高。本文提出了通过近邻传播聚类算法生成若干个初始聚类,然后通过考察初始聚类的规模来确定K-means的初始聚类中心的K-means算法(APK-means)。该算法充分发挥了近邻传播聚类(AP)算法能够快速进行大规模数据聚类的优点,同时规避了其无法确定聚类数量的缺陷,有效提高了聚类的稳定性和有效性。本文第1节分别简述了K-means算法和AP算法,第2节详细介绍了APK-means算法,第3节通过实验验证了APK-means算法的有效性和稳定性。
1 K-means聚类算法和AP算法
1.1 K-means聚类算法
设某对象集对象之间的距离为该对象集的k个类别,k个类别的聚类中心
K-means聚类算法通过迭代计算距离逐渐把对象划分成k个类蔟,使得目标函数最小化。
K-means算法描述如下:
输入:聚类的数目k和包含n个对象的数据集。
输出:满足目标函数值最小的k个类蔟。
step 1:从n个数据对象中任意选择k个对象作为初始聚类中心;
step 2:循环step 3和step 4,直到目标函数E的值在某范围内不再发生变化为止或者迭代次数超过上限;
step 3:计算每个对象与聚类中心的距离,并且根据最小距离重新划分对象到相应的类蔟中;
step 4:重新计算每个类蔟的聚类中心。
1.2 AP算法
AP算法定义了以下几个概念:
(1)相似度
对象间的相似度s(i,j)反映了对象xi,xj之间的相似程度,其定义为1式和2式:
(2)吸引度和吸引度矩阵
对象间的吸引度r(i,j)反映了对象xi以对象xj为聚类中心的可能性,其定义为3式:
吸引度矩阵
(3)归属度和归属度矩阵
对象间的归属度a(i,j)反映了以对象xj为聚类中心的类蔟包含对象xi的可能性,其定义为4式和5式:
吸引度矩阵
AP算法描述如下:
输入:n个对象的数据集。
输出:若干个类蔟。
step 1:计算数据集的相似度矩阵;
step 2:计算吸引度矩阵和归属度矩阵,其中a(i,j)=0;
step 3:循环step 4,直到类蔟不再发生变化或者迭代次数超过上限;
step 4:根据式6、7更新吸引度矩阵和归属度矩阵:
step 5:由式8得到以对象xj为聚类中心的类蔟包含对象xi的聚类结果。
2 APK-means聚类算法
若K-means聚类算法所选择的初始聚类中心远离实际的聚类中心,或者是偏远的噪声干扰点等,则聚类的结果会呈现出不确定的现象,从而不能保证较高质量的聚类效果。因此,通过提高初始聚类中心的选取质量来优化K-means算法的聚类效果是可行的方法之一。
2.1 APK-means聚类思想
AP算法在对象间相似度的基础上定义了吸引度和归属度概念,通过迭代不断更新吸引度和归属度矩阵,逐渐将对象集中相似的对象划分到相同的类蔟中,以最终形成若干个类蔟并获得每个类蔟的聚类中心。本文提出在AP算法聚类结果基础上进行K-means聚类的思想。该思想以AP算法聚类生成的类蔟中心为K-means算法的初始聚类中心,充分利用AP算法快速、稳定的聚类效果,有效提高了K-means算法的初始聚类中心的质量。但是,AP算法的聚类数目受每个对象自身成为聚类中心可能性大小(该值称为偏置参数p,一般采用3式估计其值)的影响,且两者之间的映射关系是不明确的。因此AP算法在进行聚类前无法获知最终的聚类数目。而K-means聚类算法是在已知聚类数目的前提下进行聚类。当AP算法聚类生成的类蔟数目等于K-means算法要求的聚类数目时,直接以AP算法聚类结果为当前聚类结果。当AP算法聚类生成的类蔟数目小于K-means算法要求的聚类数目时,通过调整偏置参数p来增加类蔟数目,使其大于K-means算法要求的聚类数目。
当AP算法聚类生成的类蔟数目大于K-means算法要求的聚类数目时,本文提出选择类蔟中规模较大的类蔟的聚类中心作为K-means算法的初始聚类中心。K-means算法在聚类过程中,规模大的类蔟会不断和规模小的类蔟进行合并,直到完成指定的k个聚类。APK-means聚类从以下两个方面优化了K-means聚类效果:
(1)规模较大的类蔟聚类分布对对象集总体聚类分布的影响意义比规模较小的类蔟相对大些,所以规模较大的类蔟的聚类中心在距离上比随机选择的聚类中心更加接近全局最优类蔟分布的聚类中心,使得APK-means算法的聚类效果会比普通K-means算法好。
(2)由于对象间的相似度在AP算法聚类时是不会变动的,所以AP算法聚类生成的类蔟聚类分布是固定的,使得K-means算法最终的聚类结果会保持稳定。
APK-means算法建立对象相似度、吸引度和归属度共三个规模为N*N的矩阵,其时间复杂度为O(AP)+O(K-means),其空间和时间代价大于一次K-means算法的代价。但是APK-means算法只需运行一次即可获得较好的聚类效果。而K-means算法往往需要运行多次才能获取较好的聚类效果。
2.2 APK-means聚类算法
APK-means算法描述如下:
输入:聚类的数目k和包含n个对象的数据集。
输出:满足目标函数值最小的k个类蔟。
step1:运行AP算法
step2:如果AP算法生成的类蔟数等于k,返回;
step3:如果AP算法生成的类蔟数小于k,偏置参数p增加0.01p,跳转至step 2;
step4:计算所有AP算法生成的聚类类蔟的规模(既类蔟中所包含的对象数量);
step5:选取前k个规模最大类蔟的中心为初始聚类中心;
step6:运行K-means聚类算法;
3 实验结果
3.1 聚类效果指标
本文采用聚类密集性指标对K-means算法和APK-means算法的聚类效果进行评估。聚类密集性指标通过测量聚类内的方差来反映聚类数据同一性的程度,其值越小表明同一性越高,即聚类密集性效果越好。聚类密集性指标定义如下:
设对象集其方差其中为对象之间的距离,为对象集X的均值。设对象集X的k个聚类类蔟为则X的密集性指标为
3.2 仿真数据实验
仿真数据实验采用随机生成的100个分为3类的数据对象集合,分别采用K-means算法和APK-means算法进行聚类。表1所示的是运行5次K-means算法和5次APK-means算法的的聚类密集性指标值。
表2所示的是上述5次K-means算法和5次APK-means算法聚类类蔟的聚类中心坐标。
图(1)和图(2)分别是运行5次K-means算法和1次APK-means算法的聚类效果图,图中使用符号“*”、“+”和“^”分别对三个类蔟中的对象进行标记。
图2(a)中三个红色“+”大符号标记了APK-means生成的三个聚类中心。
该仿真实验结果显示K-means算法聚类结果受到了随机选取的聚类中心的影响,而APK-means算法的5次聚类结果都相同,这表明APK-means算法具有更好的聚类稳定性。K-means算法5次聚类结果的密集性指标普遍低于APK-means算法,表明APK-means算法具有更有更好的聚类有效性。
3.3 UCI数据实验
本文采用UCI数据库中的Iris数据集。该数据集包含150个具有4个属性值的对象,共分为3类。由于该数据集已经提供了分类标签,且按照同分类同组的方式顺序编排,所以聚类效果可以通过计算对象正确分类的正确率进行评估。其实验算法描述如下:
step 1:使用聚类算法进行聚类;
step 2:根据数据集的分类标签统计聚类结果中每个对象所属分类一致的数量;
step 3:将分类一致的对象总数除以数据集中对象的总数,得到聚类正确率。
表3所示的是运行5次K-means算法和5次APK-means算法的的聚类密集性指标值。
该实验结果同样表明APK-means算法比K-means算法具有更好的聚类有效性和稳定性。
4 结束语
本文基于K-means聚类算法和AP算法提出了一种APK-means聚类算法。该算法首先由AP算法生成若干类蔟,当类蔟数量小于聚类数k时,通过调整偏置参数p来提高聚类数k;当类蔟数量大于聚类数k时,以此按类蔟规模大小降序选择其对应的聚类中心为K-means聚类算法的初始聚类中心点,接着进行K-means聚类。APK-means聚类算法充分利用了AP算法能够快速稳定生成类蔟的优点,同时也避免了对所有类蔟聚类中心进行全局搜索,优化了K-means聚类算法的聚类稳定性和有效性,获得了较好的聚类效果。但是APK-means算法的空间复杂度和时间复杂度比K-means聚类算法有了一定的上升,在对象集规模较大时其计算代价较大。
摘要：K-means聚类算法在随机选择的初始聚类中心的基础上进行聚类,其聚类效果会因为初始聚类中心的不确定性而不稳定。为了优化其聚类效果,提出了基于近邻传播算法(AP算法)的K-means聚类优化算法(APK-means)。该算法首先通过近邻传播算法生成若干个初始聚类,然后依序选择k个聚类规模最大的聚类中心作为K-means聚类算法的初始聚类中心,接着运行K-means聚类。算法有效性分析和实验结果验证了该算法有效优化了K-mean算法的聚类稳定性和有效性。
K-means优化 篇6
关键词：入侵检测,K-means算法,问题与改进
0概述
入侵检测系统主要是通过对网络中的数据包或主机的日志等信息进行提取、分析, 发现入侵和攻击行为, 并对入侵或攻击做出响应。入侵检测系统的核心在于分析数据中是否有违反安全策略事件发生, 而建立一个识别入侵的标准就显得格外重要。数据挖掘可通过大量数据中挖掘出入侵的关联性特征, 建立精确的行为标准。因此数据挖掘在入侵检测上的应用有其巨大的研究价值。而入侵检测系统的数据挖掘过程如图1所示:
1 K-means聚类分析算法概述
1.1 聚类分析概述
聚类分析是指将数据对象的集合根据一定的规则分组成为多个有意义的由类似对象组成的子集的描述性任务。聚类分析可将无标识数据对象自动划分为不同的类, 并且不受人先验知识的约束和干扰, 从而获取属于数据集合中原本存在的信息。聚类分析是一种无监督的学习方法, 不依赖事先确定的数据类别和标有数据类别的学习训练样本集合, 而入侵行为无明显事先规定的行为模式, 且先验知识必须及时更新或较少, 因此聚类分析特别适合用于入侵检测技术。
1.2 K-means算法概述
K-means算法与其它聚类算法相比, 其速度快, 对大型数据处理能力强, 因此用在入侵检测技术中很有优势。其算法基本思想是:确定聚类数K, 把数据集的前K项初始化聚类中心;然后其余数据项与各聚类算法相比较, 聚集到距离最小的那个聚类中心中;接着求出新的聚类中心, 重复运算, 直到计算误差函数没有明显改变或聚类成员不再变化为止。
2 K-means算法存在的问题
2.1 K-means算法的效率严重依赖于初始K值的选定
在入侵检测中K值 (正常或异常行为的模式种类) 不是事先知道的, 甚至是不确定的, 而无论K值选得过大过小都容易陷入局部最优的陷阱, 而不是整体最优, 故算法中簇的数量选取以及如何划分是个非常大的问题, 这直接影响了入侵系统检测的效率。
2.2 K-means算法对于噪声和孤立点非常敏感
所谓孤立点, 即远离其他数据且与数据高密集区的距离较远的那个数据点。而噪声指在一个数据空间中, 高密度的数据对象区域被低密度的对象区域所分割, 处于低密度区域的点。这两类点都会使对聚类平均值大幅偏离, 从而影响聚类效果。
2.3 K-means算法还受最初聚类中心的选择的影响
数据输入顺序不同会产生不同的最初聚类中心, 随机选取的最初聚类中心无法保证聚类中心的选取是整体最优, 故K-means算法的效率取决于最初聚类中心的选择。如何确定最初的聚类中心也是关键。
3 K-means算法的改进方向
3.1 改进K值依赖
K值选取采用大多数学者的经验算法:用一些估计合理的聚类数值, 通过比对合理聚类值和现有聚类值, 用空间距离判断聚类数是否该合并, 从而判断出最后的K值。
在求类的平均距离时未排除样本空间中的孤立点和噪声点, 因此最终求出的K值可能不够精确, 应先去除孤立点和噪声点, 可通过观察, 将孤立点和噪声点分为M个类, 在对剩余样本集采用以上的算法, 得到K个聚类, 从而确定最佳聚类个数为M+K。
3.2 判断孤立点
判断孤立点的基本思想:找到点与点之间合适的距离之和, 如果有点的距离和超过正常的距离之和, 则可判断此点为孤立点。具体为:找出每个点与其他点的距离和, 并计算出距离均和, 若距离和大于均和, 则认为该点为孤立点。
3.3 初始聚类中心的选择
选择聚类中心的基本思想:初始聚类中心要求自身周围数据点的密度较大, 并且两两初始聚类中心的距离也应该尽量大, 所以可以找出两两距离最近的点分别形成集合, 每个集合再找出其他集合中与其最近的点, 兼并成新的集合, 旧有集合失去该点, 重复其过程, 直至形成K个集合, 即成为初始的聚类中心。
4 K-means算法在入侵检测上的应用
4.1改进K-means算法运用在入侵检测的过程
改进后的入侵检测过程可描述为:首先搜集来自网络上的数据包, 利用抓包工具将来自网络上的数据包中的数据记录到文件中, 同时将原始网络数据包恢复成TCP/IP层的连接记录, 再将连接记录进行数据标准化、聚类分析等处理, 最后来检测入侵情况。对数据进行标准化处理。
4.2 改进后的入侵检测模型
入侵检测系统主要是查看网络日志文件中的数据, 首先要将其标准化, 即利用每条记录的绝对值偏差为基准来交换, 再对处理过后的数据进行K-means聚类分析, 通过删除孤立点、选取K值和选定初始聚类中心等方法优化, 最终得到较为准确的聚类结果。然后进入决策报警系统, 根据聚类分析的结果判断筛选出那些具有攻击性的行为, 并启动自动报警系统, 阻止其行为的所有操作, 并将其报告给系统网络管理员。同时, 系统将自动记录入侵行为的特征, 将其保存, 再用K-means聚类挖掘其特征, 形成特定规则和知识, 成为以后辨识攻击行为的先验经验, 用于入侵检测中的误用检测。
5 总结
K-means聚类分析算法能够很好地用于入侵检测系统中。通过分析网络数据记录, 因正常行为相比入侵行为频繁, 可通过查找异常点和孤立点来找到入侵行为, 用于异常检测;而将找到的入侵行为记录保存, 再次用算法分析, 就能为入侵行为的特征分类, 总结出规律, 便于其特征编码, 用于误用检测。另外, 用改进后的算法, 结合其他数据挖掘算法 (如神经网络、模拟退火等) , 再辅助专家系统、概率状态分析等手段, 配合自动决策报警系统, 就可形成一个较为完善而高效的入侵检测系统。
参考文献
[1]尹珧人:改进的K-means算法在入侵检测系统中的应用研究.大连交通大学, 2008
[2]尹珧人等:一种改进的k-mean聚类算法在入侵检测中的应用.科学技术与工程, 2008, 第8卷16期
[3]袁方等:对k-means聚类算法的改进.计算机工程与应用, 2004, 36期
[4]杨锋:基于数据挖掘的入侵检测技术研究.哈尔滨工程大学, 2006
K-means优化 篇7
监控设备的普遍性带来了视频信息的爆发式增长, 将这些海量信息分门别类、做上标记, 然后将其选择性的储存, 这一需求随之变得越来越迫切, 因为这样不但能够帮助用户有效的检索相关信息和迅速的获取感兴趣的视频信息, 而且能够节省大量的内存, 但是这项工作需要一个能够对这些海量视频进行自动分析和处理的智能监控系统来完成。
通过智能监控系统可以将视频流分为三类选择性的存储:
(1) 有运动目标的视频序列, 可以用来实现人群密度估计、运动目标检测等。
(2) 放弃纯背景的视频序列, 节省内存。
(3) 恶意遮挡摄像头、扭动摄像头的视频序列, 方便对异常事件的定性并报警。
视频智能存储算法一般是在摄像头异常检测算法的基础上完成的, 摄像头异常检测的基础主要是背景建模或特征提取。背景建模主要有单高斯模型、码本模型、混合高斯模型等, 上述算法缺乏实时性, 因此不适合应用到视频智能存储算法上去。文献[3]中首次将轮廓波应用到摄像头干扰异常检测中, 通过比较背景图像与视频图像的特征函数做出判断, 虽然该算法缺少自适应性, 但可以借鉴特征提取的方法。
2 视频序列分割原理及特征提取
为提取视频流的特征, 借鉴文献[4]中的方法, 将摄像头拍摄到的视频流截成两段, 分别存储到两个不同长度的缓存区中去, 即长缓存区和短缓存区。帧图像顺序被存放在短缓存区中, 若短缓存区中已满, 则将短缓存区中最先进来的那一帧视频图像存放到长缓存区中去, 若长缓存区中也已满, 则将长缓存区中最先进来的那一帧视频图像丢弃。其存储流程如图1所示。
每一次抽样检测时, 长短缓存区都会被比较然后判断异常是否发生。短缓存区中的每一帧都要和长缓存区中的每一帧进行比较, 取其比较结果的中值, 记为Dbetween。将长缓存区中的任意两帧视频图像进行比较, 取其比较结果的中值, 记为Dlong。令:
当长缓存区中是正常场景, 短缓存区中是异常场景时, Dbetween表示的是类间差, Dlong表示的是类内差, 类间间距越大, 类内间距越小, Dnorm所得到的值就越大, 长短缓存区中的视频序列分别属于不同类别的可能性就会越大。
在上述方法中, 每一次抽样检测时, 都会比较长短缓存区中视频序列的差异性:归一化的RGB直方图、L1R直方图和梯度方向直方图。
2.1 归一化的RGB直方图
归一化的RGB颜色空间是一个二维的数组, 按照R, G, B三个分量所占的百分比来表示像素值, 设像素i的三个分量为Ri, Gi, Bi, 像素i的分bin其表达式如下:
归一化的RGB颜色空间对光照缓慢变化不敏感, 而只对图像的内容的变化敏感。
2.2 L1R直方图
L1R直方图也是一个二维的数组, 其分量定义如下:
对于像素i的三个分量为Ri, Gi, Bi, 像素i的分bin其表达式如下:
Ii和Si分别表示像素i的亮度值和饱和度值。而亮度和饱和度信息与光照有关, 故可用这个模型检测光照的突然改变。
2.3 梯度方向直方图
边缘检测在智能识别中比较重要。I表示当前帧图像, Gx和Gy分别表示卷积后横向及纵向边缘检测出来的图像, 其卷积表达式如下:
图像的梯度方向对缓慢的光照改变和摄像头的轻微振动或者移动不是很敏感。
2.4 直方图的绝对差
直方图的绝对差是帧图像差异的最直观的表现形式。设帧图像I1和I2的直方图分别为H1和H2, 其中直方图的bin为n, 则帧图像的直方图的绝对差的计算表达式如下:
现记FRGB表示两帧图像的归一化的RGB直方图的绝对差, FL1R表示两帧图像的L1R直方图的绝对差, FGrad表示两帧图像的边缘梯度直方图的绝对差。
故,
将上述直方图的绝对差组合成动态多特征组合, 形式为:
图2是在拍摄的几段视频中, 随机抽取的一段视频, 其中含有的事件个数为8个, 分别是:有运动目标的3个 (比较高的3个红线) 、被扭动的2个 (比较低的2个红线) 、被遮挡的3个 (蓝绿混合的3个突出的线) 。数据没有做对数变换。
从图2可以看出直方图的绝对差能够准确的反映出来帧图像序列的变化, 当视频画面出现明显的变化时, 相应的数值分量会达到不同的峰值, 然后可以借助于聚类技术将相同范围内的数据峰值聚类到一起 (尤其是K-means聚类算法具有很好的实时性, 其复杂度为O (n) , n为对象个数) 以这些峰值点为依据, 将缓存区中前后连续的帧图像序列存储到事先准备好的标签下面, 完成视频的智能存储。
3 以信息增益比率的加权距离计算方法为基础的K-means聚类算法
K-means聚类算法是把n个数据对象划分为k个类别, 使每个类别中的数据点到该类的聚类中心的距离的平方和最小, 算法具体流程如图3所示。
全部对象每被分配完一次就会被重新计算聚类中心, 不断重复, 直到标准测度函数收敛为止, 一般采用均方差作为标准测度函数:
E为数据集合中所有对象的均方差之和, P为任一对象数据点, mi为类别Ci的均值。
在计算对象到各个聚类中心的距离计算中, 欧氏距离是常用的计算方法, 而权值信息能够完全的反映各个特征分量在聚类或者分类过程中对未知类别的倾向程度。所以准确的权值为提高聚类质量提供了一个可能, 若每一变量均可被赋予一个权值, 以表示其所代表属性的重要性。那么带权值的欧氏距离计算公式为:
在统计属性中, 信息增益是衡量属性价值的一个好的定量标准。因此属性的信息增益值决定了属性在分类过程中的贡献大小, 而在聚类算法中, 相似度的度量使用的是距离的计算方法, 特征属性作为距离计算中的一个子量, 所以它的信息增益值可以作为权值表示该属性在距离计算过程中的贡献大小。
(1) 若属性是连续的则将其进行离散化处理, 否则省略此步骤;
(2) 含有未知属性值的训练样本进行相应的处理;
(3) 计算样本分类的信息熵, 表达式如下:
其中p (|Ci|) =|Ci|/N, |Ci|为类别Ci中样本的数量, ||表示统计集合中元素个数运算。
(4) 计算特征属性Ai的信息增益, 表达式如下:
(5) E (Ai) 为特征属性Ai划分成子集的熵, 其表达式如下:
(6) I (X1j, X2j, …, Xmj) 为子集Xj的熵, 其表达式如下:
其中pij为Xj中属于类Ci的概率, 其表达式为pij=|Xij|/|Xj|。
(7) 计算特征属性Ai的信息增益比率, 其表达式如下:
(8) 特征属性Ai的分类贡献率为:
γi表示该属性在聚类或分类过程中所起的贡献的大小, 也就是在计算实体之间距离的属性权值。获得特征属性的权值, 那么数据对象j和数据对象k之间距离的平方和为:
4 基于K-means视频智能存储算法步骤及仿真实验
4.1 基于K-means视频智能存储算法法流程及步骤 (如图4)
算法步骤:
步骤1动态特征提取;
步骤2 K-means聚类;
将上一步所得到的动态多特征组合数据集合使用K-means聚类算法将其聚类, 其中相似度的度量使用信息增益比率的加权距离计算方法来计算:
步骤3根据聚类结果, 借助于长短缓存区将其补全以视频流的形式存储到相应的标签下面, 完成对视频的动态智能存储。
4.2 仿真实验
测试视频采用分辨率为320*240的视频序列, 选取了50个事件, 依照采样规则, 从中抽取出来1675个数据, 然后将其分为两部分, 其中训练样本数据集的个数为400个, 包括纯背景事件中的96个数据对象、出现运动目标事件中的103个数据对象、摄像头被扭动事件中的103个数据对象以及摄像头被遮挡事件中的100个数据对象;剩下的1275个数据对象为测试数据集, 其中包括在纯背景事件中的378个数据对象、出现运动目标事件中的294个数据对象、摄像头被扭动事件中的306个数据对象以及摄像头被遮挡事件中的297个数据对象。
(1) 计算权值。将上述400个测试样本记为S, 分布如表1所示。
则信息增益为:
(2) 计算属性FRGB的信息增益比率, 现将其对应的数据离散化, 分成四个区间, 如表2所示。
则该属性的信息增益为:
则该属性的信息增益比率为:
其中分裂信息Split Information (S, FRGB) 为2.2495, 所以该属性的信息增益比率为:
将剩余的两个属性离散化处理, 区间均是选取的3个, 按照上述计算步骤得
到另外两个属性的信息增益比率分别为:
然后将其归一化, 则得到相应的权值。
(3) 将上述权值带入距离的计算公式, 实验结果如表3所示。
在展示实验结果之前先引入两个概念, 即检测率ρr和误报率ρe, 测试数据集T={T1, T2, T3, T4}, Ti为各个事件相对应的数据总数, i=1, 2, 3, 4, 经过聚类后所得到的数据集记为T_k={T_k1, T_k2, T_k3, T_k4}, 其中T_ki为各个事件相对应的数据总数, 且T_ki=ri+ei, i=1, 2, 3, 4, ri表示被正确聚类的个数, ei表示被错误聚类的个数。则
能够得出上述实验结果中较高的准确率, 与视频序列的特征提取方法准确、及时分不开;而且在K-means聚类过程中, 使用了信息增益比率的加权距离计算方法来度量样本数据点和当前聚类中心点的相似度, 依靠权值各个特征分量能够在聚类算法中的优势发挥出来。
5 结论
基于K-means的视频智能存储算法取得了较好应用成果, 在动态多特征组合的基础上利用聚类算法将视频序列分门别类, 达到智能存储的目的。如何简单快捷选择聚类中心和减少对于运动目标的重复存储, 是接下来研究的重点。
参考文献
[1]谭铁牛.智能视频监控技术概述[C].北京:第一届全国智能视觉监控学术会议, 2002.
[2]C R Wren, A Azarhayejani.Pfinder:Real-Time Tracking of The Human[J].IEEE Transaction on Pattern Analysis and Machine Intelligence, vol.19, no.7, pp.781-785, 1997.
[3]梁爽.基于轮廓波的摄像头干扰检测[D].河北师范大学, 2012.
[4]徐红丽.智能视频监控中的摄像头异常检测[D].河北工业大学, 2012.
[5]杨圣云, 袁德辉, 赖国明.一种新的聚类初始化方法[J].计算机应用与软件, 2007, 8 (24) :51-52.