K+均值

K+均值（通用7篇）

K+均值 篇1

link

appraisement

industry

point

实行学分制使得因材施教成为可能, 为学生的个性化发展提供了基础, 同时, 也给学校的学生日常管理工作带来了巨大的挑战。为了更好地管理学生, 文中使用K均值对学生进行聚类, 给出了具体的聚类方法和实行过程, 在实验中采用三种不同的距离计算方法对学生进行聚类, 表明了该方法是有效的。

随着高等教育教学改革的不断深化, 各地高校为适应高等教育大众化、阶段多样化的要求, 都积极探索并实施学分制的管理模式。实行学分制给学生的个性培养和教学的因材施教提供了良好的发展空间, 但从学校方面来说, 学分制下的学生管理突破了原有的学生管理体制, 对学生管理提出了严峻的考验。

在学分制下, 虽然每一个学生的自由度加大, 但是整个学校里所有的学生在长期会有一些相同或相似的情况, 即所谓的“物以类聚, 人以群分”, 如果能根据长期以来的学生的表现对学生进行聚类, 使得同一类的学生有更多的共同点, 不同类的学生有较大的不同, 然后可以针对不同类型的学生采用不同的方法进行管理, 不仅可以提高管理的针对性, 而且可以更好的研究不同类型的学生的具体情况, 为以后的学生选课、就业等方面提供一些有益的建议。

聚类是将数据分类到不同的类或者簇这样的一个过程, 所以同一个簇中的对象有很大的相似性, 而不同簇间的对象有很大的相异性。K均值聚类算法是一种有效的聚类技术, 具有对大型数据集进行高效分类的特点, 因此, 本文采用该方法对学生进行聚类。

K均值聚类

k均值聚类是最著名的划分聚类算法, 由于简洁和高效使得其成为所有聚类算法中最广泛使用的。具体的计算过程如图1所示。

基于K均值的学生聚类

聚类不仅可以降低学生管理的难度, 而且使得学生管理具有针对性和高效性的优点;K均值是一种有效的聚类算法, 因此本文其应用于学生管理。由于学生的身高、性别、年龄等这些因素对于学生管理的意义不大, 而性格虽然重要, 但是数据很难收集, 而学生在学校的首要根本任务是学习, 而且学完课程都会有一个考试来检验学习的效果, 因此, 成绩数据不仅数据量大, 而且可以指导学生此后的选课及教学计划的制定, 因此, 文中使用学习成绩对学生进行聚类。具体的流程如图2所示。

(1) 数据预处理

由于描述成绩的数据可能是数值或者是等级这样的模糊值, 为了计算的方便, 需要对模糊数据进行数值化, 在本文中, 根据图3的对应关系进行数值化。

(2) 缺失值的处理

由于在收集数据的过程中各种因素导致的数据缺失是不可避免的, 因此, 需要对项目中存在的缺失值进行处理。常用的缺失值处理方法有删除存在缺失值的个案和缺失值插补。删除法是对缺失值进行处理的最原始方法, 它将存在缺失值的个案删除。由于成绩数据缺失的情况现有发生, 因此, 本文使用该方法对缺失值进行处理。

(3) K均值聚类

对成绩进行处理以后就可以聚类了, 首先确定将成绩聚为几类, 并确定相应的聚类中心;然后分别使用欧氏距离、余弦距离和相关度三种方法计算每一个同学的成绩与各个聚类中心的距离进行聚类;最后, 根据聚类结果重新计算聚类中心, 重复该过程直到收敛。

实验

本文以某校计算机专业的一个班一年的成绩为例进行实验, 使用前文的模糊数值和缺失值的处理方法进行数据预处理, 然后使用matlab对其进行聚类, 三种距离计算方法的聚类结果如图4, 5, 6所示。

结束语

本文探讨了在学分制下的学生管理工作, 并采用K均值方法对学生进行聚类, 并给出将K均值聚类算法应用于学生聚类的步骤和具体实施过程, 表明了该方法的有效性。

基于最近邻思想的K-均值算法 篇2

数据聚类是数据挖掘的一个非常活跃的研究方向。聚类在文献[1]中定义为:将数据对象进行分组, 成为多个类或簇。在聚类过程中无须用户提供先验的分类知识, 而是根据数据实际的分布情况得到自然的聚集结果。当前主要的聚类算法可以划分为如下几类:

1) 基于划分的方法, 如k-means (K-均值) 文献[2], k-medoids (K-中心点) 文献[3];

2) 基于层次的方法, 如BIRCH文献[4], C U R E文献[5], R O C K文献[6], Chameleon文献[7];

3) 基于密度的方法, 如D B S C A N文献[8];

4) 基于网格的方法, 如S T I N G;

5) 基于模型的方法。

全文内容安排如下:第二节介绍传统K-均值算法的基本思想, 并进行特性分析;第三节介绍改进的K-均值算法;第四节实验;第五节结束语。

2 传统的K-均值算法

2.1 基本思想

K-均值算法是一种重要的聚类算法, 它是目前应用最广的基于划分的聚类算法, K-均值算法以K为参数, 把N个对象分为K个簇, 使簇内具有较高的相似度, 而簇间的相似度较低。相似度的计算根据一个簇中的对象的平均值来进行。

K-均值算法的处理流程如下:首先从N个数据对象任意选择K个对象作为初始聚类中心, 而对于所剩下的其他对象则根据它们与这些聚类中心的相似度量 (距离) 分别将它们分配给与其最相似的 (聚类中心所代表的) 聚类。然后再计算每个所获新聚类的聚类中心 (该聚类中所有对象的均值) 。不断重复这一过程直到标准函数开始收敛为止。

2.2 K-均值算法的基本过程

输入:聚类个数K, 以及包含N个数据对象的数据库。

输出:K个簇。

处理流程:

(1) 从N个数据对象任意选择K个对象作为初始聚类中心。

(2) 循环下述流程 (3) 到 (4) 直到每聚类不再发生变化。

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

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

2.3 K-均值算法的优缺点

优点:K-均值算法实现起来比较简单其计算复杂度为 (nkt) , 其中, n为对象个数, k为聚类个数, t为循环次数, 它具有可扩展性。

缺点:K-均值算法有以下四个缺点:

(1) K-均值算法只适用于聚类均值有意义的情况。

(2) 用户必须事先指定聚类个数K。

(3) K-均值算法还不适合发现非凸状的聚类。

(4) K-均值算法对噪声和异常数据非常敏感。因为这类数据可能会影响到各聚类的均值。

要想使一种聚类算法能克服以上所有缺点几乎不可能。针对K-均值算法对异常点和噪声敏感的这一缺点, Kaufman和Rousseeuw在文献中提出了一种K-中心点算法, K-中心点算法不采用簇中对象的平均值作为参照点, 而是选用簇中位置最中心的点 (中心点) 作为聚类的中心点。剩余的对象根据其与代表点的距离分配给最近的一个簇。然后反复地用非代表对象代替代表对象, 以改进聚类的质量。

K-中心点聚类算法虽然比K-均值算法更健壮, 但K-中心点聚类算法的执行代价要比K-均值算法要高得多。

3 基于最近邻思想的K-均值算法

3.1 基本思想

在传统K-均值算法中存在的一个主要缺点是对噪声和异常点敏感, 其原因是在K-均值算法的每一次迭代中, 簇中的所有对象都参与计算平均值, 再将新的平均值作为新的聚类中心进行计算, 这样噪声和异常点都会参与平均值的计算。因而对平均值 (聚类中心) 有较大的影响。为了避免该情况发生, 我们可以选择参与平均值 (聚类中心) 计算的对象, 不是全部的对象都参与计算平均值, 而是选择与上次聚类中心最近邻的i (i<n/k) 个数据对象参与计算平均值。如果某个簇中对象个数不足i个则可以将其删除。该簇中的对象在进行下一次迭代时被分配到别的簇。这样就可以有效地去除噪声和异常点对平均值的影响。从而使聚类结果更加合理。

下面分析聚类初始点对该算法的影响。如果所选初始点为正常对象 (不是异常) 点, 则其近邻数一般都会大于i这种情况该中心点形成的簇不会被删除。如果某一初始点选中了异常点, 由于异常点与正常对象之间的距离较远, 则其近邻对象一般都会小于i, 这样就可以将该中心点所形成的簇删除, 从而使聚类结果更加合理。不会受到异常点的影响。

在聚类过程中, 如果某一聚类中心所形成的簇中包含有异常点, 如果该簇中包含的对象个数小于i个, 则该簇被删除;如果该簇中对象的个数大于i个则在计算新的聚类中心时, 异常点必定不会参与计算;如果该簇中对象的个数刚好是i个, 则异常点参与计算。但经过数次迭代之后, 该情况出现的概率很小。

综上所述, 该算法可以有效地去除噪声 (异常点) 对传统K-均值算法中平均值 (聚类中心点) 的影响, 从而使聚类结果更加合理。

3.2 基本过程

输入:簇的数K, 包含n个对象的数据库, i簇中参与计算平均值的对象数目。

输出:K个或小于K个簇。

处理流程:

(1) 任意选择K个对象作为初始的簇中心。

(2) 循环下述流程 (3) (4) 直到每个聚类不再发生变化。

(3) 根据簇中前i个对象的平均值, 将每个对象重新赋给最类似的簇。

(4) 更新簇中聚类中心的值。 (计算每个簇中与前一次聚类中心最邻近的前i个对象平均值。)

3.3 时间复杂度分析

改进后的K-均值算法与传统K-均值算法的最大区别就是取每个簇中与聚类中心最邻近的i个对象作为计算平均值 (下一次聚类中心) 的对象。而不是计算簇中所有对象的平均值作为下一次聚类的中心。这样就需要在计算平均值之前进行一次排序。排序的时间复杂度为k m 2 (其中k为簇的个数, m为最大簇中对象的个数) 。因此改进后的K均值算法的时间复杂度为k (m 2+n) t (其中k为簇的数目, m为最大簇中对象的个数, n为全体数对象个数, t为迭代次数。影响m值的因素很多, 如果则改进后的K均值算法与传统的K_均值算法时间复杂性相同, 但通常m 2>n所以改进后的K平均算法要比传统的K_均值算法时间复杂度要高。

4 实验

我们将本算法应用到学生成绩信息分析中, 学生成绩信息分析的目的是研究学生成绩的分布情况, 找出异常信息, 为教务部门进行教学督查提供决策信息。

1) 实验环境

计算机配置:C P U A t h l o n 6 43 0 0 0+, 1 G H z内存, 1 6 0 G B硬盘

操作系统:Microsoft Windows XP

开发平台:Microsoft Visual Studio2005

开发语言:C#

数据库:Microsoft SQL Server 2005

2) 数据集

近两年来收集的学生公修课学生成绩信息, 数据中含学生学号、姓名、高等数学成绩、大学英语成绩。

实验比较了改进后的K-均值算法与传统K-均值算法。实验前首先将指定数据全部读入内存, 并完成相应的预处理工作。

3) 实验结果分析

通过实验表明改进后的K-均值算法和传统的K-均值算法用时基本相当, 并没有显著增加用时, 但聚类效果却明显改善。

5 结束语

在本文中, 我们提出了一种基于最近邻思想的K-均值算法, 该算法在计算聚类中心点时, 采用了一种最近邻思想有效克服了‘噪声’对平均值的影响, 从而使聚类结果更加合理, 并通过实际数据的实验验证明这种算法是有效的。如何将该算法应用到更多的实际数据的聚类是下一步的研究。

摘要：K-均值聚类算法是一种基于划分方法的聚类算法, 本文通过对传统的K-均值聚类算法的分析, 提出了一种改进的K-均值算法, 并对该算法的时间复杂度和空间复杂度进行了分析。该算法在计算聚类中心点时采用了一种最近邻的思想, 可以有效地去除“噪声”和“孤立点”对簇中平均值 (聚类中心) 的影响, 从而使聚类结果更加合理。最后通过实验表明该算法的有效性和正确性。

关键词：数据挖掘,聚类,K-均值

参考文献

[1]Jiawei Han, Micheline Kamber著;范明, 孟小峰, 等译.数据挖掘概念与技术.机械工业出版社

[2]J.MacQueen.Some methods for classificationand analysis of multivariate observations.Journal of the American Statistical Association, 83:715----728, 1967

[3]L.Kaufman and P.J.Rousseeuw.FindingGroups in Data:An Introduction to ClusterAnalysis.New York:John Wiley&Sons, 1990

[4]T.Zhang, R.Ramakrishnan, and M.Livny.BIRCH:An efficient data clustering method forvery large databases.In Proc.1996 ACM-SIGMOD Int.Conf.Management of data (SIGMOD’96) , oages 103----114, Mibtreak, Cabada, June 1996

[5]S.Guha, R.Rastogi, and K.Shim.Cure:Anefficient clustering algorithm for largedatabases.In Proc.1998 ACM-SIGMOD Int.Conf.Management of Data (SIGMOD’98) , pages73—84, seattle, WA, June 1998

[6]S.Guha, R.Rastogi, and K.Shim.Rock:AnRobust clustering algorithm for categoricalattributes.In Proc.1999 Int.Conf.DataEngineering (ICDE’99) , page512—521, Stdebet, Australia, Mar.1999

[7]G..Karypis, E.-H.Han, and V.Ku-mar.CHANELEON:A hierarchical clustering algorithmusing dynamic modeling.COMPUTER, 32:68—75, 1999

K+均值 篇3

雷达信号分选的研究起于20世纪70年代,当时雷达体制较为简单,分选难度不大。随着新体制雷达的大量出现并列入装备使用,现有的电磁环境越来越复杂,使得传统基于直方图的分选算法越来越难以适应分选的要求。近年来一些聚类算法被尝试到信号的分选领域中来,比如空间距离聚类、K-均值聚类、模糊聚类、BFSN聚类等,在这些聚类中K-均值聚类因算法思想简单,易于实现并且收敛速度快等优点,受到科研人员的青睐。但K-均值算法最大的局限性在于聚类的数目需要事先确定,这一要求在实际电子对抗侦察中几乎是不能满足的,这也大大限制了K-均值算法在未知信号分选中的应用。

从目前文献来看,大多数应用K-均值算法的论文中聚类数都是人为设定的。也有少量文献将该算法与其他算法进行结合,使得自动确定聚类数和聚类中心,如将蚁群算法与K-均值算法结合[1],遗传算法与K-均值算法结合[2],以此来确定K-均值聚类的聚类数目,但这些方法存在计算繁琐,运算量较大,难以工程化实现等缺点。因而,如何对K-均值进行相应的改进,使得改进算法在保留算法编程思想简单,易工程化实现等优点的基础上,能够自动确定聚类的数目和聚类中心,便显得意义重大。

本文针对这一问题展开研究,借助文献[3]中的思想对K-均值算法进行改进处理。改进算法自动确定聚类中心和聚类数目,使得算法适应未知信号分选的能力增强。仿真实验验证了其有效性。

1 K-均值算法原理

K-均值算法使用的聚类准则函数是误差平方和准则。该算法的思想是将N个对象进行K个类的划分(K≤N)。其算法步骤如下:

(1) 任选K个初始聚类中心Z${}_2^{(1)}$,Z${}_3^{(1)}$,…Z${}_{{\rm K}}^{(1)}$,其中,上角标表示聚类过程中的迭代运算次数。

(2) 假设已进行到第r次迭代,若对某一样本x有:

$d(x,z{}_j^{(r)})=\min \{d(x,z{}_i^{(r)}),i=1,2,\cdots ‚{\rm K}\}(1)$

则x∈S${}_j^{(r)}$。式中d(x,z${}_j^{(r)}$)为样本x～z${}_j^{(r)}$间的距离,S${}_j^{(r)}$是以z${}_j^{(r)}$为聚类中心的样子子集。以此种方法,即最小距离原则,将全部样本分配到K个聚类中。

(3) 计算重新分类后的各聚类中心

$z{}_j^{(r+1)}=\frac{1}{n{}_j^{(r)}}{\displaystyle \sum _{x\in S{}_j^{(r)}}X},j=1,2,\cdots ,{\rm K}(2)$

式中:n${}_j^{(r)}$为S${}_j^{(r)}$中所包含的样本数。

(4) 若z${}_j^{(r+1)}$=z${}_j^{(r)}$,j=1,2,…,K,则结束;否则转步骤(2)。

2 改进的K-均值算法

改进K-均值算法思想是通过设定距离阈值TMS2812,将脉冲间的欧几里德距离与距离阈值TMS2812进行比较,按照一定准则,完成聚类中心和聚类数目的动态确定。在进行分选前,需完成脉冲的数值处理、特征参量选择以及阈值TMS2812设定等工作。

2.1 数值处理

改进的K-均值算法采用加权欧几里德距离表征脉冲信号参数之间的距离[3]。

$r=[(x-u){}^{\text{Τ}}\mathit{W}(x-u)]{}^{1/2}(3)$

式中:x表示脉冲参数的测量值;u表示脉冲聚类中心的参数值;它随聚类运算的进行完成更新;W表示加权矩阵。

设Δ=x-u,当用多脉冲参数进行表征时:

$\Delta =\left[\begin{array}{l}\Delta {}_1\\ \Delta {}_2\\ ⋮\\ \Delta {}_n\end{array}\right](4)$

脉冲参数加权矩阵为:

$\mathit{W}=\left[\begin{array}{cccc}W{}_1& 0& \cdots & 0\\ 0& W{}_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & W{}_n\end{array}\right](5)$

则脉冲参数之间的几何距离为:

$r=\left[[\Delta {}_1\Delta {}_2\cdots \Delta {}_n]\times \left[\begin{array}{cccc}W{}_1& 0& \cdots & 0\\ 0& W{}_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & W{}_n\end{array}\right]\times \left[\begin{array}{c}\Delta {}_1\\ \Delta {}_2\\ ⋮\\ \Delta {}_n\end{array}\right]\right]{}^{1/2}(6)$

为便于计算,在参数进行运算之前,先进行归一化处理。归一化的方法可根据实际情况进行设置。此处采用下列归一化公式:

$\tilde{x}=\frac{x-x{}_{\min }}{x{}_{\max }-x{}_{\min }}(7)$

式中:xmin表示该参数集合中的最小值;xmax表示该参数集合中的最大值。如果特征参量选择为DOA,RF和PW时,则xmin,xmax表示DOA,RF和PW的最小值和最大值。

2.2 特征参量选择与阈值TMS2812设定

雷达的脉冲描述字PDW包括RF,DOA,PW,PA,在不考虑脉内信息的情况下,此处选择DOA,RF和PW作为特征参量。

上面提到脉冲信号之间的相似度用欧几里德距离表征,距离越小,相似度越大。此处设定一个参数Sd,作为该欧几里德距离的门限。

2.3 改进K-均值算法步骤

改进K-均值聚类算法的步骤如下:

(1) 在进行聚类之前,设定好距离门限Sd、最大迭代次数iteNum,将迭代次数计数器counter至于0,标志位变量change置于1(用以表征是否完成类的更新),并选取第一个点作为聚类中心。

(2) 读取新的脉冲参数,将其与已有的聚类中心点计算加权距离,得到最小的距离Distance_min,再将Distance_min与Sd进行比较,如果Distance_min<Sd,则将该脉冲参数归为该类,如果Distance_min>Sd,则将该脉冲参数作为新的聚类中心。

(3) 更新各聚类中心特征值。

(4) 判断counter<iterNum,change==1是否同时成立,若同时成立,则进行下一步。若有一项不成立,程序结束。

(5) 将change赋值为0;counter加1。

(6) 重新读取脉冲参数,计算该对象到自身类中心的距离和到其他类中心的距离。如果它到其他类中心的距离更小,则将其归为离它距离小的类,并更新change=1,跳到步骤(3)。否则重复该步,直到所有脉冲都计算一遍或满足类更新条件为止。

2.4 改进算法流程图

改进的K-均值算法流程图如图1所示。

3 仿真实验

为验证改进算法的有效性,此处借助Matlab进行仿真测试。本次的仿真中通过DOA,RF,PW参数完成测试。

(1) 仿真1:常规雷达分选测试

选用3部常规体制雷达。3部雷达类型和参数见表1。

经过程序验证,很容易将上述脉冲分为3类,与真实情况相符,成功率达到100%。

(2) 仿真2:复杂体制雷达分选测试

在实际情况下,雷达体制复杂,脉冲流不仅表现在时间轴上的交错,在其他脉冲参数上也表现为出现部分混叠的情况。典型的例子是两部频率捷变雷达在频域上的数值混叠。仿真2在考虑实际情况下对算法进行仿真分析,表2为雷达类型和参数表。

经过仿真,聚类前到达角-载频分布图如图2所示。

经过聚类以后的结果二维显示和三维显示分布图见图3、图4(图中用点表示雷达1,用圈表示雷达2,用下三角表示雷达3)。

从仿真图上可以看出,改进算法能够自动将这些对象聚类成3类,与实际情况相符。从图4中可以看到,在聚类的过程中,除有一个属于雷达1的对象被聚类到雷达3中外,其余聚类结果都是正确的,改进后的算法具有较高的准确性。

4 结 语

对近年来引入到信号分选领域中的K-均值算法展开研究,主要针对传统K-均值算法需要先验知识,无法有效应用于未知雷达信号的分选的问题。经过对仿真结果分析,结论如下:

(1) 改进后的算法只需设定初始距离阈值TMS2812,就能够自动确定聚类数目和聚类中心,并完成相应的聚类,有效地适用于未知信号的分选。

(2) 仿真实验表明,改进算法能够准确完成常规体制雷达的分选,同时对于重频抖动、重频滑变、频率跳变和频率捷变等复杂体制雷达也有很好的分选效果。

(3) 本文给出改进算法流程图,易于工程化实现。

虽然文中提到的改进算法能够自动地完成聚类数目和聚类中心的确定,但仍然需要借助于距离阈值TMS2812的人为设定,现阶段距离阈值TMS2812主要是通过经验和实验得到。关于距离阈值TMS2812的优化或动态设定还需要进一步深入研究。

参考文献

[1]孙秀娟.基于遗传算法的K-means聚类算法分析研究[D].济南:山东师范大学,2009.

[2]赵贵喜,骆鲁秦,陈彬.基于改进的蚁群聚类雷达信号分选算法研究[J].电子信息对抗技术,2009(3):27-29.

[3]祝正威.雷达信号的聚类分选方法[J].电子对抗,2005(6):6-10.

[4]韩俊,何明浩,朱元清.基于多参数的雷达辐射源分选新方法[J].数据采集与处理,2009(1):91-94.

[5]李峰.复杂环境下雷达辐射源信号分选算法研究[D].西安:西安电子科技大学,2009.

[6]曹俊纺,陈建军,孟晓琳.雷达信号分选技术研究[J].雷达与对抗,2009(1):20-22.

[7]张红昌,阮怀林,龚亮亮,等.一种新的未知雷达辐射源聚类分选方法[J].计算机工程与应用,2008,44(27):200-201.

[8]陈惠民,盛骥松.一种新的雷达信号分选方法[J].现代电子技术,2009,32(1):20-22.

[9]何明浩,朱元清,冒燕,等.一种雷达辐射源信号分选新方法[J].武汉理工大学学报:交通科学与工程版,2007(3):430-433.

一种并行的加速k-均值聚类方法 篇4

聚类作为一种典型的数据挖掘方法,目前已在图像识别、股票分析等领域得到成功应用[3,4]。其任务是从大规模数据集中发现相似的类别,将样本划分为多个不重合的子集。在聚类结果中,相同类内样本应具有较大相似性,不同类间样本具有较大相异性。目前,常见的聚类模型包括:划分聚类[5]、层次聚类[6]、密度聚类[7]、网格聚类[8]、概率聚类[9]和谱聚类[10]等。

在这些聚类方法中,k-均值聚类是一种最为经典使用最为广泛的划分聚类方法[11,12]。k-均值聚类方法以各类样本的质量中心代表该类进行迭代,从而通过不断地动态调整各类中心进行聚类。但是,k-均值聚类算法复杂度高,对大规模数据无法进行有效聚类。因此,如何采用k-均值聚类方法解决大规模数据的聚类问题一直是聚类分析领域的一个研究热点。

随着数据挖掘领域处理样本规模的日趋增大,要求研究人员能够提出高效的挖掘算法来处理海量数据问题。并行计算作为一种定量、精细、高效的方法在海量数据挖掘中得到了成功的应用[13]。狭义上的并行计算是指在并行/分布式计算机上所做的计算,从广义上讲,将多个问题同时求解的过程都可以看做是并行计算的过程。尽管目前已经有学者提出了一些基于并行计算的聚类技术以改进传统的聚类方法[14,15],但是,这些技术效率还不足够高,对于大规模数据的聚类问题的处理能力依然有限。因此,如何结合并行计算技术进一步提高k-均值聚类方法处理海量数据的能力依然是一个值得探讨的问题。

针对传统k-均值聚类方法不能有效处理海量数据聚类的问题,该文提出一种基于并行计算的加速k-均值聚类方法。该方法首先将聚类样本随机划分为多个独立同分布的聚类工作集,并在每个工作集上并行进行传统k-均值聚类,对聚类后的每个类计算其中心和半径,通过衡量不同工作集聚成的子类的中心和半径,对不同工作集的子类进行快速合并,并对子类中的少数特殊数据进行二次归并以校正聚类结果,从而有效处理海量数据的聚类问题。

1 基于并行计算的加速k-均值聚类算法

1.1 k-均值聚类方法

设数据集X={x1,∙∙∙,xi,∙∙∙xn}且xi∈Rd,其中n为样本个数,d为样本维度,k为聚类之前指定的聚类个数。传统k-均值聚类算法首先随机选择k个样本作为初始聚类中心C={c1,∙∙∙,cj,∙∙∙,ck},然后计算每个样本xi∈X到聚类中心cj∈C的距离d(xi,cj),根据每个样本到聚类中心的距离将样本划分到与之最近类中,并计算更新后每个类的中心C,如此循环迭代直到更新后的类中心与更新前一致时停止。

由于传统k-均值聚类方法由于在每次迭代聚类时都需要衡量所有样本到每个类中心的距离,因此算法复杂度为O(nkq),其中,q为聚类迭代次数。当数据规模较大时,算法往往需要很多次迭代才能结束,运行效率较低,不能够有效处理海量数据的聚类。

1.2 并行的加速k-均值聚类方法

针对传统k-均值聚类方法不能有效处理大规模数据聚类的问题,该文结合并行计算思想,提出一种基于并行计算的加速k-均值聚类方法(Pk-means)。该方法首先将聚类样本集X随机划分为多个独立同分布的聚类工作集,即X→{X1,∙∙∙,Xj,∙∙∙,Xm},并在每个工作集Xj上并行进行传统k-均值聚类,得到聚类结果Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。然后,对于每个聚类后得到的类Xjp(共mk个),求解其类中心cjp和类半径rjp,然后通过衡量不同工作集中类中心之间的相似度,将相似度最高的合并为一个类,类中心(两个不同样本)相似度的求法如下:

与第i个工作集中第p个类合并的第j个工作集中类别确定方法为:

将每个工作集的聚类结果均按照上述规则进行合并,最后得到一个划分,即X→{X1,∙∙∙,Xt,∙∙∙,Xk},并计算其新的中心C={c1,∙∙∙,ct,∙∙∙,ck}及半径R={r1,∙∙∙,rt,∙∙∙,rk}。然后判断聚类结果是否需要更新,若rt<=range,则不更新,否则对子集Xt中符合条件(3)的样本按照式(4)进行更新。

基于并行计算思想的k-均值方法由于将样本划分为n k的大小,且并行执行传统k-均值聚类方法,所以初始复杂度为O(nq'),其中q'为每个工作集进行传统k-均值聚类的最大迭代次数,且易得到q'<

基于并行计算的k-均值方法具体如下:

初始化:设数据集为X={x1,∙∙∙,xi,∙∙∙xn}(其中xi∈Rd),随机划分工作子集参数为m,工作子集聚类参数为k,聚类结果更新参数为range。

Step1:将样本集X随机划分为m个工作子集,即得到划分模式X→{X1,∙∙∙,Xj,∙∙∙,Xm}。

Step2:对每个工作子集Xj进行k-均值聚类,得到每个工作子集的聚类模式Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。具体方法如下:

Step2.1:在每个工作子集Xj随机选择k个样本作为初始聚类中心;

Step1.2:根据式(5)计算每个样本xjq与所有不同类Classjp之间的相似度,并将xjq归为与其最相似的类中心所属的类;

Step1.3:根据式(6)计算样本重新分配后的第每个类的中心Cj={cjp}kp=1

Step1.4:若类中心有更新,则返回Step1.2继续聚类,直到类中心不发生更新时迭代停止,得到每个工作子集Xj的聚类结果Xj→{Xj1,∙∙∙,Xjp,∙∙∙,Xjk}。

Step3:根据式(1)计算不同工作子集中的类之间的相似度,并根据式(2)合并工作子集的聚类结果,从而生成对整个数据集X实现k类的划分,即X→{X1,∙∙∙,Xi,∙∙∙,Xk}。

Step4:根据式(3)和式(4)对聚类结果进行更新调整,从而得到更为优秀的聚类结果X→{X1opt,∙∙∙,Xiopt,∙∙∙,Xkopt}。

算法结束。

2 实验结果及分析

为验证基于并行计算的k-均值方法聚类方法处理大规模数据聚类的有效性,该文在一个人工构造的模拟的社会网络社团结构数据集上进行了实验,并将聚类结果与经典k-均值聚类方法所得到的结果进行了比较。实验在1台PC机(2.66Ghz CPU,1G内存)上进行,实验平台是Matlab2008。

为充分反应本文提出的并行加速k-均值聚类方法的有效性,实验构造了两组数据集。第一组数据集中,人工模拟的网络社团机构数据集包含100个顶点,它们被划分成相同大小的4个社团结构,每个社团结构包含25个顶点,且所有顶点的度均符合如下条件:

其中zin为每个顶点随机指向落在相同社团中顶点的有向边数目,zout为每个顶点随机指向落在不同社团中顶点的有向边数目。网络中100个顶点在zin=12,zout=3时被划分成4个社团结构时的示意图如图1所示,第二组实验数据与第一组构造方法一致,但数据规模扩大了20倍。

本文从两个方面衡量了算法的性能,即聚类结果的抱团性和聚类时间。。聚类抱团性的定义如下:

为充分反应本文提出的基于并行计算的加速k-均值聚类方法的性能,实验中与传统k-均值聚类方法进行了对比。两组实验中子集划分参数m分别取5和10,聚类个数参数均为4,聚类结果更新参数为range取当前类的1.2倍数值,所得实验结果见表1。

从以上实验结果可以看出,在构造的网络社团结构数据集上,当样本规模为100时,该文提出的基于并行计算的k-均值聚类方法的J值较高,样本的抱团性较差,聚类时间与传统k-均值聚类方法有一些提高;但是,当样本规模增加到2000时,该文提出的基于并行计算的k-均值聚类方法的J值接近于传统k-均值聚类方法的J值,而聚类的时间则只有传统k-均值聚类方法的25%左右。

综上可看出,由于本文提出的Pk_means聚类方法采用了并行计算的模式,并且采用了独立同分布的样本初始工作集划分方法,因此能够以较高的训练效率处理大规模数据的聚类问题,同时保证了聚类结果的抱团性能。

3 结论

K+均值 篇5

关键词：车牌识别,车牌定位,K-均值,聚类,字符识别

机动车号牌识别系统主要功能是通过图像采集和图像识别的手段识别机动车的身份。对车牌识别领域的研究最初起源于二十世纪九十年代的发达国家, 而国内的研究起源于二十世纪末。号牌识别的最主要的步骤是:车牌定位、字符分割和字符识别。而后两者现在基本已经达成共识, 字符分割采用对二值化图片进行垂直投影和水平投影, 字符识别使用模板匹配方法或者SVM方式。最重要而且方案最多样化的步骤还是在车牌定位上。

车牌定位基本可以分为三种大的研究方向:对灰度图像进行边缘检测、对灰度图像进行角点检测和对彩色图像进行颜色模型处理。边缘特征是人类视觉感知的重要来源, 文献将边缘检测理论、形态学填充、腐蚀开运算后得到车牌待选区域, 最后分析获取车牌位置, 边缘检测作为研究范围最广和目前大多数产品使用的技术, 的确具有速度快、准确率较高的特点, 尽管现有的边缘检测算子十分成熟, 但是没有一种适应于任何图像质量、任何图形环境的边缘提取方法, 而且为了得到高识别率, 对于每幅图像要选用合适的边缘检测算子。文献将彩色图像转换到HSV颜色空间中对色彩进行分层处理是车牌定位彩色图像处理方向较新颖的方法, 但是这类方法的缺点也是很明显的, 当车身颜色与牌照颜色相近时, 辨识就变的几乎不可能了。文献提出了角点检测法, 因为角点代表的特征像素点占图像像素总数的百分之一, 却构成物体大部分的外形要素, 由于牌照的字符部分角点数较多, 所以作者使用Harris算法获取整幅图像的所有角点, 然后使用一个固定大小的滑窗去遍历图中的角点以得到牌照待选区域。通过角点获取牌照区域受干扰小, 识别的效率也比较高, 是应该深入研究的方向。

1 车牌标准分析

现行的《中华人民共和国公共安全行业标准——中华人民共和国机动车号牌》 (GA36-2007) , 于2007年9月28日发布, 同年11月1日实施, 用来代替原来的国标GA36-1992。按照GA36-2007的标准, 为了我们计算机识别的方便, 我重新整理从号牌行数和号牌特征着手归纳, 见表1。

经过归类并简化后, 很大程度上避免了排列方式对识别算法的干扰, 在字符分割阶段对车牌进行横向投影分析号牌分类是单行牌照还是双行牌照, 并根据上表优化算法, 可以达到快速准确的目的, 见图1。

下面从典型的单行牌照, 分析其字符规律。牌照中的字符分为三段:第一个字符是省、自治区或者直辖市的简称, 确定为汉字字符;第二个字符是发牌机关代号, 是大写的英文字母;第三至第七个字符为序号, 通常为大写英文字符和阿拉伯数字字符的排列, 对于特别号段的车辆会在末位字符出现“警”“领”“学”“临”“试”“港”“澳”等汉字字符。

典型的双行牌照, 见图2。双行牌照第一行就是单行牌照分割点前的两个字符, 第二行是单行牌照的第三位到第七位。双行牌照和单行牌照相比, 长宽比更小。

从颜色方面看, 无论是单行的牌照还是双行的牌照, 都有多种颜色的排列组合。但是归纳来说, 牌照背景颜色和牌照字体颜色的组合一共是四种, 分别是:黄底黑字、蓝底白字、黑底白字、白底黑字。特殊分类的字符颜色为红色, 而且特殊字符不会出现在蓝底背景的牌照上面。

2 原始K-均值算法

用Harris角点检测算法运算后的图像, 通过观察可以发现“牌照区域肯定是角点聚集的区域, 但是角点聚集的区域不一定是牌照所在区域”, 需要使用一个聚类分析方法来找到若干个角点聚集区域, 然后通过对区域特征的筛选, 最终决定牌照位置。K-均值算法是一种得到了广泛使用的基于划分的聚类算法, 算法把n个数据点按照目标函数分为k个簇, 以使簇内数据点具有较高的相似度, 而这个目标函数可以是欧氏距离。K-均值算法满足了希望把n个角点以欧氏距离分为k个号牌待选区域的思想, 而且它的时间复杂度是O (tkn) , t是迭代次数, 所以对图3 (a) 上由Harris算法得到的角点执行K-均值算法, 经t次迭代得到k个簇, 见图3。

3 改进K-均值算法

使用原始K-均值算法并不能在每次收敛后都得到牌照正确的区域 (见图4) , 因为其算法本身是用于数据挖掘的, 算法中初始点是随机决定的, 目标函数使用的是欧氏距离, 为适应号牌识别的效率和识别率双重的要求, 需要对其修改。在这个过程中, 参考了文献, 但是考虑到文中AP算法的时间复杂度高, 所以还是用K-均值算法。

首先从算法的随机取初始点着手, 通过实验发现初始随机点选择的结果不同, 收敛后的簇是可能不一致的, 所以尽量要选择一种既能接近最终收敛簇的形心, 又能是一种快速稳定的初始点提取算法。研究后决定用分冶思想把图像分成若干个矩形区域, 算法1的步骤如下:

步骤2, 遍历Ci, 2这张存放了角点的二维表, , 1/ij=C×M W, k Ci, 2N/H=×, Aj, kAj, k1=+。

步骤3, 设值max, 遍历Aj, k, 当Aj-1, k, Aj+1, k, Aj, k-1, Aj, k+1均未被访问过时, max=Aj, k, 并标记Aj, k为已访问过。

步骤4, 循环到步骤3, 所有的初始点都选出为止。

第二点的改进是传统的K-均值聚类时使用的欧氏距离, 而牌照的规格不是圆, 需要使用标准化的欧氏距离公式。两个n维向量a (x11, x12, ..., x1n) 与

b (x21, x22, ..., x2n) 间的标准化欧氏距离公式为:

其中ks是分量的标准差, 对于最常见的440mm×140mm的机动车牌照上二维的角点数据, 公式可以推导为

于是整个号牌定位的算法可以这样描述:

步骤1, 使用FAST角点算法获取图中角点。

步骤2, 使用算法1提取K-均值的初始点。

步骤3, 以计算出的中心点执行K-均值算法。

步骤4, 修改K-均值算法使用公式1。

步骤5, 在聚类后获取的簇所组成的矩形中, 根据车牌标准, 删除以下情况:高要比宽大;宽大于高的3.5倍;宽小于高的2倍;号牌颜色面积小于总面积50%。

执行上述算法后得到图5, 其中左边一张是通过上述算法得到的初始点, 右图是通过初始点再调用K-均值算法得到最终的角点分类后各个区域的中心, 从中可以发现初始点已经很接近最终的收敛结果, 所以这种算法可以大大的加快K-均值算法迭代的速度, 而且使得K-均值算法的执行速度是快速的, 结果是稳定的。

4 算法效率实验

测试数据集的描述:本文采用从网上随机选取的二十七张车辆正面图片作为样本来验证改进后的算法的效率。通过FAST角点检测, 其中每张图产生一千个以下的角点。

算法对比:分别用传统K-均值算法、滑窗定位法和改进过的K-均值算法分别对样本图片的角点进行聚类, 分别从平均识别速度和平均识别率两个方面进行对比, 见表2。

表2是对三种不同聚类算法的实验结果的汇总, 给出了具体量化的数据, 通过表2可看出传统K-均值算法由于迭代次数多而收敛速度慢, 并且识别率低。而改进后的K-均值算法虽然算法复杂但是由于迭代过程的改进使得识别速度和平均识别率都得到了很好的平衡。

5 车牌字符分割算法研究

本章节将讨论车牌字符分割问题。车牌字符的分割是车辆号牌识别流程中承上启下的环节, 主要是继续前章车牌定位的工作结果, 主要任务是从一张车牌图像中准确可靠的分割得到各个字符并完成归一化的工作, 提供给下面字符识别环节来进行分析。

由于机动车牌照存在单行车牌和双行车牌, 所以进行列分割之前要首先进行判断。通过分析车牌区域的水平投影图的形态就可以知道, 见图7。

因为车牌尺寸不同, 必须对它进行归一操作:将牌照灰度图缩放到100×50像素, 计算各行中段约25%~75%的区域, 在这个区域中搜索灰度值最小点, 若该点在接近1/3处, 该号牌就是双行车牌, 否则是单行车牌。下面介绍用列分割方法把单行车牌进行字符分割。首先对车牌定位后的图像进行二值化操作 (临界灰度值是160) , 这样得到的二值化图像减少了光照不均的影响。然后对单行车牌区域的二值化图像做垂直投影, 见图8。

然后通过下列的步骤实现字符分割, 其中投影图为P。

步骤1:令max P=MAX (P) , 得到投影图中的最值。

步骤2:寻找N中的0值点, 以0值点将N分为若干块:recti, i=1, 2, 3, ...。

步骤4:各块宽度为width=imax (recti) -min (recti) 。宽度中值为media Width。将widthi<media Width×1.2的块就近合并。

步骤5:若recti的宽度大于两倍中值宽度, 按中点将其分拆成两块。

步骤6:重复步骤4和5, 直到无合并或拆分操作为止。

步骤7:如果块宽度小于各块平均宽度, 以该块中心左右往外media Width2作为分割点;否则以该块左右边界为分割点。

步骤8:按照分割点分割图像, 按照各分割块的左右次序对其编号。

步骤9:分析各块底色 (二值化图像为0的点) 的平均色度值, 将其和车牌区域底色比较, 删除误差超过50%的块。

这样就把字符从定位好的牌照图像中分离出来了, 见图9。

6 车牌字符分割识别研究

支持向量机来识别号牌字符, 利用其良好的分类能力, 可以用来对字符进行分类, 有很高的字符识别率。

1992年开始在统计学习理论领域发展了一种称为支持向量机 (Support Vector Machine, SVM) 的新的模式识别方法, 在解决小样本、非线性及高维模式识别的问题中表现出很好的性能。由于同时神经网络遇到了网络结构固定、过学习和欠学习问题, 所以支持向量机方法成了机器学习领域内新的热点。

SVM方法从线性可分的最优分类面 (Optimal Hyper-plane) 提出了二类分类技术。它通过构造最优超平面使得不同样本类的距离最大化。

yi[ (wixi) +b]-1≥0, i=1, 2, ..., n就得到了最优的分类面。表述成约束优化问题就是在 (l) d的条件下, 求方程

对w和b偏微分并使之等于0, 得到对偶问题

在线性不可分情况下, 增加了松弛项ξi≥0, 分类条件方程变成:

所谓SVM的训练, 就是通过已有的样本, 求得支撑最优分类面的样本向量。由于SVM自身的特点, 相对于识别的样本, 只需要少量样本进行训练。这一点就满足车牌字符识别系统的要求。同时, 如果把整个字符作为输入数据, 输入样本就具有高维度的特征, 这要求分类器能够进行高效的高维度数据分类能力, 这也是SVM的优势所在。鉴于以上这些原因, 构造了用于车牌字符识别的支持向量机, 并使用大量实际数据效验所设计方法的有效性。训练中从100多张尺寸为800×600的各类机动车照片中分割出700多张字符照片, 其中某种字符的照片数是大于1的, 按照字符分类, 每种字符抽取一张, 一共71张字符照片, 手动选定字符系统自动对其进行缩放操作, 统一成32×16像素的图片, 然后再进行灰度化操作和二值化操作 (通过实验二值化的阀值定为灰度值160) , 这样每个字符照片所包含的信息量是相同的。实验中使用的支持向量机是由台湾林智仁教授开发的libsvm, 由于Objective-C是向下支持C语言的, 所以libsvm (C语言版) 是可以直接用于Objective-C开发的, 见图10。使用svm_train来进行训练。

识别的步骤和训练的步骤是相似的。对于从字符分割后的字母/数字图片, 首先进行灰度化和二值化处理 (二值化的阀值定为灰度值160) , 这样把产生的二进制数值作为一个svm节点, 加载SVM自识别系统在磁盘上的识别模型, 返回识别的结果。

7 号牌识别应用

最后在一台联想Think Pad T430上, 安装了Mac OS Mountain Lion (10.8.5) X64位操作系统和Xcode编程开发软件, 并把APP运行在一台i Phone 4 (操作系统IOS7.1.2) 上实现了号牌识别的全部功能, 见图11。

经过号牌定位、字符分割和字符识别三大步骤后, 实验在真机上的运行效果如图10所示。

8 结语

针对车牌定位这个难点问题, 本文将K-均值算法用于号牌识别的算法并进行了优化, 首先提出用分冶思想用于K-均值算法的初始点选取;然后对K-均值算法得到的结果, 也就是号牌候选区域进行筛选, 结合形状和颜色等因素来最后精确定位车牌, 这样既提高了算法的收敛速度, 又增加了算法的准确性。经IOS平台上实现的整个号牌识别程序实验结果, 证明改进后的号牌定位算法提高了识别率, 成效显著。

参考文献

[1]王晓雪, 苏杏丽.数字图像处理在车牌识别中的应用[J].自动化仪表, 2010, 31 (7) :22.

[2]迟晓君.一种基于支持向量机的车牌字符识别方法[J].信息技术与信息化, 2007, (6) :

K+均值 篇6

在电力系统负荷中,感应电动机是其中重要的、也是最主要的组成部分。感应电动机的运行情况在很大程度上影响着系统的运行与控制[1,2]。感应电动机数量庞大,对系统进行分析计算时,采用详细的动态模型对其进行刻画往往是不现实的,因此,在负荷建模工作中,为了降低负荷模型的阶数,通常采用统计综合法。

对统计综合法而言,合理地聚合感应电动机群是其核心工作,在该领域已有一定的研究基础[3,4,5,6,7,8,9]。基于容量加权法,文献[3]以近似特征值对感应电动机进行分群。考虑电动机稳态时的等效电路,文献[4]将得到感应电动机的3阻抗并联模型,进一步并联相同母线下所有电动机的阻抗,依次作为该母线下等值电动机的参数。文献[5,6]分别考虑空载、堵转这2种电动机的极端情况,并采用这2种情况下的近似等效电路对等值电动机的参数进行计算。文献[7]考虑了电动机负载率和临界滑差对容量加权法的影响。文献[8,9]对电动机分群时采用了基于统计思想的聚类算法。在电力系统遭受的干扰很大或很小时(也即系统处于稳定状态或失稳时),以上方法聚合得到的等值模型都可以较为准确地描述电动机群负荷的动态特性。然而,当系统在临界情况下这些方法得到的结果均存在保守或冒进的问题。

本文首先研究了感应电动机各参数的轨迹灵敏度,并以此作为聚类算法的特征权值对电动机进行分群,然后与基于空转-堵转的等值电动机参数计算方法相结合进行感应电动机群聚合计算。最后利用数值仿真,分析比较了本文方法与传统方法得到的聚合电动机在不同故障切除时间下的系统稳定性,结果表明了本文所提电动机聚合方法的正确性和有效性。

1 利用特征权值的聚类算法进行电动机分群

目前,在负荷建模的研究工作中广泛采用的即为本文中提到的考虑机电暂态的三阶动态模型来描述感应电动机的动态特性,图1为其等值电路。该模型可以准确地描述感应电动机负荷在不同程度扰动下的动态行为。本文以该模型为基础,研究了感应电动机群动态模型的聚合降阶。

感应电动机数学模型为:

其中,X=X2+Xm;X'=X1+X2//Xm;T'=(X2+Xm)/R2。

机械转矩Tm和电磁转矩Te分别为

式中:R1为定子电阻;X1为定子电抗;Xm为励磁电抗;R2为转子电阻;X2为转子电抗;T1为惯性时间常数;A,C为机械转矩系数;Re为取实算子;s为电动机转差;E'为暂态电势;s0为初始转差:T'为暂态时间常数;p为微分算子。

当多台感应电动机接入同一母线上时,可以通过聚合算法将其等值为1台电动机。然而,当这些电动机参数或运行特性差异较大时,仅用1台等值电动机很难正确反映多台感应电动机的总体特性。因此,合理地对多台电动机进行分群,并将每个群用1台电动机等值,可以提高电动机聚合的精度。

1.1 考虑特征权值的K-均值聚类算法

聚类分析是基于基础数据源,并将其按照相似性划分为不同的若干个类别的算法。划分后的类别具有以下性质:1)相同类别中元素之间的相似性尽可能大;2)不同类别中元素之间的相似性尽可能小K-均值算法是一种经典聚类算法,它用欧几里德距离的倒数度量相似度。

K-均值算法将n个向量xj(j=1,…,n)分成c个类Gi(i=1,…,c),以均值的思想求取各类别的聚类中心,使得与非相似性指标相关所构建的目标函数最小。当选择欧几里德距离作为度量向量xk与某类别中心的距离,此时目标函数见式(3)。

式(3)通过欧几里德距离进行度量,目标函数中包含了向量xk的所有维度分量(xk的所有属性),且认为xk的每一维度分量在计算距离时具有相同的权重

然而,在实际问题中,xk的不同属性往往对类别划分具有不同的相关性程度。在聚类时如果不加区分地平等对待每一个属性,那么相关性低的属性则会引起“维数陷阱”[10,11,12]误导,影响聚类的结果。因此,在聚类时应对xk的每一个维度分量赋予与之相对应的特征权系数,用以区分不同属性的重要程度。从欧几里德空间上讲,较小的权系数代表了相关度低的分量所对应的轴被缩短,较大的权系数说明相关度高的分量所对应的轴被拉长。那么将式(3)改写为:

式中:wl为特征权值;m为特征数;xkl和和Gil分別为考虑特征权值后的向量和聚类中心。

1.2 基于轨迹灵敏度求取特征权值

基于轨迹灵敏度的概念,通过计算各参数的轨迹灵敏度来确定聚类算法中的特征权值。

轨迹灵敏度反映系统中某一参数、结构发生变化时系统动态轨迹的变化程度,可反映系统轨迹与参数、结构的相互关系[13]。通过计算感应电动机模型中各个参数的灵敏度,可以量化各个参数对系统轨迹的影响,并以此来确定特征权值。

目前,计算轨迹灵敏度的方法主要有解析法、数值差分法(摄动法)、伴随方程法及卷积法等。这些方法各有优缺点,其应用范围也各不相同。本文采用参数摄动法来求解各参数的轨迹灵敏度。

某个参数的轨迹灵敏度定义如下:

式中:yi为系统中第i个变量的轨迹,θj(j=1,…,m)为系统的参数;tk(k=1,…,N)代表第k个时刻。

考虑到参数正负2个方向变化对灵敏度的影响,可以利用中值法来计算导数,即分别用参数正向变化和负向变化来计算第k个时刻的轨迹

并据此计算第k个时刻的轨迹灵敏度

这样,就得到了1条反映参数θj对输出变量yi影响程度的曲线,可以通过式(7)的方式比较各参数的灵敏度:对求取的每个时刻的轨迹灵敏度取绝对值并求和,就可得到参数θj对系统响应yi的影响:

应用上述方法对参数不同的感应电动机数学模型分别进行轨迹灵敏度分析。表1给出了3台典型电动机的参数,其中L为电动机负载率。

本文采用电力系统典型故障(电压小干扰带阻尼震荡以及经历故障切除的暂态电压曲线)下感应电动机的等值阻抗轨迹作为式(7)中的yi来计算各参数的灵敏度均值。结果如表2所示

由表2可以看出,R1,X1,X2,R2和L的灵敏度均值一般较大,这表明其对模型的响应影响较大,而其余的参数Xm,A,C和T1的灵敏度均值都很小,表明其对于模型的响应影响较小。且当电动机参数变化时,各参数的灵敏度均值变化相对较小。因此可将表2中不同电动机各参数灵敏度均值的算术平均值作为各参数的特征权值。结果如表3所示。

在得到各电动机参数的特征权值后,可利用1.1节中考虑特征权值的K-均值聚类算法进行电动机分群计算。

2 基于空转-堵转的等值电动机参数计算

2.1 等值电动机电气参数

在完成多台电动机的分群后,将每个群内的电动机聚合为1台等值电动机(等值机)。在文献[5,6]的基础上,本文提出了一种基于空转一堵转的等值电动机参数计算方法。

在感应电动机空转时,可以认为转差s=0,而当感应电动机堵转时,可认为s=1。这样,就可根据这2种特殊状态来计算等值电动机的参数。

下面以2台电动机为例,说明等值电动机参数的计算方法。2台电动机的等值电路如图2所示,其参数已经归算至同一基准之下。

当电动机堵转时,即s=1,由于Xm远大于X2与R2,可近似认为励磁回路开路。所以2台电动机的等值阻抗可以简化为:

当电动机空转时,即s=0,可近似认为转子回路开路。所以2台电动机的等值阻抗可以简化为:

由式(8)、式(9)可以求出等值机的和,对于等值机定子和转子电抗以及励磁电抗,还需要1个方程。

可近似认为等值机的励磁电抗等于参与聚合的n台机的励磁电抗并联而成。即

由式(8)～式(10)联立即可求得等值机的电气参数。

2.2 等值电动机初始运行滑差

对于等值机的初始运行转差,可由参与聚合的n台电动机的总功率PΣ、负荷节点初始电压V以及前文中计算得到的等值机参数来进行计算。令等值机的功率等于参加聚合的n台电动机功率之和P∑,即可求得等值机的初始运行转差。

其中,

2.3 等值电动机惯性时间常数及机械转矩系数

对于等值机的惯性时间常数及机械转矩系数,可采用式(13)进行计算(以惯性时间常数TJ为例)。

式中:Si为第i台电动机的容量。

其中,

3 算例分析

本文采用Anderson 3机9节点系统对本文提出的方法进行仿真,该系统见图3。对于母线5上的负荷,算例采用恒阻抗负荷与动态负荷相结合的模型。对于母线6和8,其负荷采用恒阻抗模型。

假设母线5上的动态负荷包括了6台感应电动机。其中,居民负荷占42%;工业负荷占58%。各电动机参数如表4所示。

昏先应用基于近似特征值的电动机分群方法对6台电动机进行聚合计算。

各电动机的近似特征值可通过计算-1/(R2TJ)得到[3],结果分别为-33.69,-1 6.23,-3.03,-2.96,-39.68,-37.04。通过分析,可以将它们分为2群,电动机1,5和6分为一个群;2,3和4分为一个群。各群的等值电动机参数如表5所示。

下面用本文提出的方法对6台电动机进行分群,并求取等值电动机参数。

为了便于比较,将6台电动机分为2类(c=2),利用考虑特征权值的K-均值聚类算法对电动机群进行分群计算。得到的各电动机隶属度和各群的聚类中心Ci如表6和表7所示。

由表6可以看出,电动机1,2,3和4属于第一类,电动机5,6属于第二类。这样可以把前4台电动机聚合为1台等值机,后2台电动机聚合为1台等值机。

然后利用第2节中等值机参数计算方法得到各等值机参数如表8所示。

下面分别将传统方法与本文方法得到的等值电动机参数代入系统中进行暂态仿真,并与实际系统的暂态仿真结果进行比较,以此检验聚合方法的正确性与精度。

假设故障是仿真时间为1s发生在线路5-7靠近母线7处,故障类型为三相接地短路。故障清除方式为断开线路5-7。

假设在仿真时间为110 ms时对故障进行清除,发电机1号～3号之间的功角摇摆曲线和母线3的电压曲线见图4、图5。

从图4和图5可以看出,与原6机系统相比,以本文提出的方法对电动机群进行分群和等值后进行仿真,系统的发电机功角与电压的差别较小,相对于根据近似特征值进行分群和综合的计算结果有着明显的改善。

将故障清除时间延长至113 ms后进行仿真,发电机1号～3号之间的功角摇摆曲线和母线3的电压曲线见图6、图7。

将故障清除时间延长为118 ms,发电机1号～3号之间的功角摇摆曲线和母线3的电压曲线见图8、图9。

通过算例可以看出,根据近似特征值进行感应电动机分群的方法在某些情况下并不能区分特性相差较大的电动机,会对电动机聚合效果产生不利影响,尤其是当系统运行在临界情况下时,该方法的误差非常大。从图6可以看出,该方法在113 ms清除故障情况下其仿真结果仍是稳定的,而该情况下精确模型的仿真结果已经出现失稳的情况。当故障清除时间为118 ms时,该方法得到的仿真结果才会出现失稳的情况。

通过考虑特征权值的聚类分析来进行电动机分群,可以有效地消除某些相差较大但又对系统动态响应影响较小的参数对分群效果产生的负面影响,提高了感应电动机群的聚合精度。从仿真结果可以看出,在不同的故障清除时间下,本文方法的仿真结果都有着较好的精度。另外,表9还给出了2种聚合方法与精确模型下的极限切除时间,由表9可以看出本文提出的方法,即在故障下保持系统稳定运行的最大切除时间与精确模型下一致,而传统方法的极限切除时间发生了偏差。因此,本文提出的方法在反映系统临界状态时的动态行为是准确的。

4 结语

本文提出了一种新的电动机聚合方法,通过对电动机动态模型进行轨迹灵敏度分析并求其均值来得到各参数的特征权值,再利用考虑特征权值的K-均值聚类算法来优化电动机分群,并结合基于空转-堵转的等值电动机参数计算方法得到等值电动机的电气和机械参数。

K+均值 篇7

随着互联网技术的快速发展,多媒体图像、Web文档、影像视频等海量数据大量涌现,在丰富人们生活的同时,也给检索带来了巨大的工作量。采用自动化、智能化、模式化的聚类分析方法,已经成为海量数据应用研究的热点。K均值作为一种聚类算法,其思想和应用执行过程较为方便,一直以来受到互联网企业青睐,在入侵检测、图像处理、视频聚类、文本数据挖掘、电子商务推荐、遥感信息识别、软件聚类等领域得到了广泛应用,取得了较好的效果[1,2,3]。随着对K均值算法研究的深入,算法得到了极大的改进。

王敞等[4]分析了K均值聚类算法存在中心设置容易陷入局部最优化等问题,提出了一种基于遗传算法的K均值聚类算法,能够有效结合遗传算法寻找全局最优。在自适应交叉和变异操作中引入K均值操作,克服了传统K均值算法的局部性和敏感性,能够实现较好的聚类效果。陈宗海等[5]分析了聚类算法强化学习过程中,连续状态空间对自适应划分方法存在的缺点,提出了一种基于节点生长的K均值聚类算法,分别给出了离散动作和连续动作下强化学习方法的执行步骤,实验结果显示,该方法可以自动调整划分的精确度、优化学习最佳策略。高滢等[6]提出了一种半监督K均值多关系数据聚类算法,该算法在K均值算法的基础上,改进了类簇的选择方法和数据对象之间的相似性度量方法,将其应用于多关系的半监督学习过程中,充分利用标记数据、对象属性,提高了K均值算法的准确度。陶新民等[7]详细地分析了K均值算法存在的缺点,提出了一种改进的粒子群优化的K均值混合聚类算法。该算法引入小概率随机变异操作,以便能够增强种群的多样性,提高混合聚类算法的全局搜索能力;根据群体适应度方差确定K均值算法操作的时机,增强局部精确搜索能力,缩短算法的收敛时间。王莉等[8]分析了粗k均值聚类算法易受随机初始聚类中心和离群点的影响,导致出现一致性和无法收敛的问题,提出了一种改进的粗K均值聚类算法。该算法能够选择潜能最大的K个对象作为聚类中心,基于其它数据对象和中心之间的距离判定数据归属类簇,提高了算法准确度,克服了离群点的不利影响。胡伟等[9]分析了K均值算法随机指定不同的聚类个数而导致聚类错误率较高的问题,集合层次划分算法,提出了一种改进的层次K均值聚类算法,能够自底向上聚类分析,形成一棵树型结构,并且在树形结构上自动选择聚类。实验结果表明,该聚类提高了数据分析的准确度。赵冬玲等[10]整合网格聚类和K均值聚类算法优势,提出一种基于网格的K均值聚类算法,改进了算法中计算密度阈值的函数,可以有效降低算法的低凝聚度,提高数据聚类分析效率。

传统聚类算法对初始化的聚类中心比较敏感,并且随着初始化聚类中心的不同,具有不同的聚类结果,因此需要根据经验设置聚类中心,很容易陷入局部最优化。另外,传统的K均值算法属于硬划分,每个对象都归属于一个具体的类簇,降低了算法的准确度。为了解决上述问题,本文引入模糊聚类思想,提出一种模糊K均值聚类算法。实验结果表明,该算法能够有效提高聚类的准确度。

1 背景理论

假设数据集包含n个样本,用X={x1,x2,L,xn}表示,每一个样本都可以使用m个特征刻画,则第j个样本的特征向量xj={x1j,x2j,L,xmj}T,数据集可使用矩阵进行描述,如公式(1)所示:

其中,xij表示样本j的特征i,j=1,2,…n,i=1,2,…m。

在模糊聚类处理过程中,为了消除数据集m个特征值之间的量纲差别,需要对其进行归一化处理,具体处理过程如公式(2)所示:

其中,ximax表示第i个指标特征的最大取值;ximin表示第i个指标特征的最小取值;rij表示归一化后xij的取值。

归一化之后,数据集的描述矩阵X可以使用矩阵R表示,如公式(3)所示:

假设数据集X拥有C个类别,则数据集X的模糊识别矩阵如公式(4)所示:

其中,uhj表示数据集中的样本j归属于h类的隶属度,h=1,2,…,C,并且满足以下约束条件:0≤uhj≤1,

假设类别h的m个特征值称为类的聚类中心,则c个类别的特征值可以使用模糊聚类中心矩阵,如公式(5)所示:

其中,sih表示类别h指标i的归一化特征值,0≤sih≤1。

在模糊聚类执行过程中,可以设置不同的特征权重,一般能够优化突出较为重要的特征贡献,特征权重向量如公式(6)所示:

通过分析,模糊聚类目标函数如公式(7)所示:

实际应用中,具体算法可以采用迭代执行过程求取目标函数的最优解。

2 模糊K均值算法分析与设计

为了更好地实现模糊聚类,本文针对模糊K均值算法进行了分析和设计。模糊K均值描述如下:

假设数据集集合为X={x1,x2,L,xn},数据集的簇数目为K个,mi表示第i个簇的中心,i=1,2,…k。uj(xi)表示K均值聚类过程中第xi个样本对第j类的隶属度,模糊K均值的目标函数可以使用公式(8)描述:

其中,b是一个可以控制模糊聚类结果的模糊度常数,通过对模糊K均值隶属度函数求导数,即可得到K均值算法的最优解,如公式(9)和公式(10)所示:

在聚类算法执行过程中,可以对公式(9)和公式(10)进行迭代执行,得到一个具体的模糊K均值聚类算法,在实际的数据集划分过程中使用。

本文基于模糊思想的K均值聚类算法描述如下:

算法输入:簇数目K,参数b,包含N个数据对象的数据集。

算法输出:K个簇。

算法步骤:(1)采用随机初始法为数据集设定K个簇,并指定每个簇的中心为mi;(2)计算数据集中每个数据对象的隶属函数,计算方法为公式(10);(3)基于步骤(2)的隶属度函数,计算各个簇的中心值mi,计算簇中心采用公式(9);(4)遍历数据集中每个数据对象,当隶属度不再发生变化时,算法终止;否则返回步骤(2)。

3 实验与结果分析

3.1 实验数据与环境

系统实验工具为Matlab2012程序处理平台,实验环境采用的服务器为一台酷睿双核PC,CPU型号为i3-2310M,其主频为2.10GHz,内存为4G,操作系统为Win7。

算法实验数据采用Lang收集的20-NG数据集,使用BoW工具对数据集进行预处理,从中选择4 500篇文档,将这些文档分成9个子数据集,每个数据集包含的文章数量为500篇,具体如下:数据集Binary_1、Binary_2、Binary_3分别包含2个档类别,分别是talk.politics.mideast和talk.politics.misc,每个类别包含250篇文档;数据集Multi5_1、Multi5_2、Multi5_3分别包含5个文档类别,分别是comp.graphics、rec.motorcycle、rec.sport.baseball、sci.space和talk.politics.mideast,每个类别包含100篇文档;数据集Multi10_1、Multi10_2、Multi10_3分别包含10个文档类别,分别是sci.electronics、comp.sys.mac.hardware、rec.sport.hockey、misc.forsale、alt.atheism、talk.politics.guns、rec.autos、sci.crypt、sci.med和sci.space,每个类别包含50篇文档。

为了评估模糊K均值聚类算法,使用召回率评估算法聚类的精确度,算法召回率定义如公式(11)所示:

其中,T表示聚类算法执行结果的簇标号,C表示数据集拥有的真实类别,A1(c,T)表示文档c分到其归属类别T中的文档数目;A2(c,T)表示文档c被错误划分到非归属类别T中的数量。

3.2 实验结果分析

为了比较本文算法的有效性和准确性,对模糊K均值算法与经典K均值算法、基于粒子群的K均值算法进行比较分析。

所有数据集上,本文提出的模糊K均值算法的召回率较高,尤其是在数据集Multi10_1、Multi10_2、Multi10_3,较K均值算法召回率提高54.4%,较粒子群的K均值算法提高23.9%,有效实现了文本数据的准确分类。另外,本文算法具有较好的鲁棒性,无论是在2个簇、还是在5个簇或10个簇的数据集上,准确度均较高,没有出现显著的召回率差异,波动幅度很小,表明本文算法适应各类数据集的划分。3个算法的实验结果如表1所示。

4 结语

传统K均值算法属于硬划分,并且算法的初始中心节点需要人为指定,容易降低算法的执行效率及准确度。本文基于模糊聚类思想提出了一种新的K均值聚类算法,将每个数据对象按照隶属度划分到真实的类别中,提升了算法的准确度。未来工作的方向主要是:(1)改进模糊聚类隶属度函数,以便能更有效地提高算法准确度;(2)基于遗传算法、粒子群算法、模拟退火算法等,改进K均值初始中心的设置,提高初始设置的准确度,进一步改进算法划分效果。

摘要：随着云计算、移动计算等互联网技术的快速发展,海量数据分析已成为企业战略决策、营销推广的基础,海量数据挖掘愈显重要。传统的K均值算法作为一种硬聚类算法存在诸多问题,例如数据划分武断、准确率较低等。引入模糊数学思想,提出了一种模糊K均值算法,基于隶属度关系对数据进行了有效的聚类分析,以提高数据挖掘的准确度。

关键词：模糊数学,K均值,硬聚类,隶属度

参考文献

[1]胡艳维,秦拯,张忠志.基于模拟退火与K均值聚类的入侵检测算法[J].计算机科学,2010,37(6):122-124.

[2]吴永芳,杨鑫,徐敏,等.基于K均值聚类的医学图像分割算法[J].计算机工程,2011,37(5):232-234.

[3]杨宏宇,常媛.基于K均值多重主成分分析的App-DDoS检测方法[J].通信学报,2014,35(5):16-23.

[4]王敞,陈增强,袁著祉.基于遗传算法的K均值聚类分析[J].计算机科学,2003,30(2):163-164.

[5]陈宗海,文锋,聂建斌,等.基于节点生长k-均值聚类算法的强化学习方法[J].计算机研究与发展,2006(4):661-666.

[6]高滢,刘大有,齐红,等.一种半监督K均值多关系数据聚类算法[J].软件学报,2008,19(11):2814-2819.

[7]陶新民,徐晶,杨立标,等.一种改进的粒子群和K均值混合聚类算法[J].电子与信息学报,2010,32(1):92-97.

[8]王莉,周献中,沈捷.一种改进的粗K均值聚类算法[J].控制与决策,2012,27(11):1711-1714.

[9]胡伟.改进的层次K均值聚类算法[J].计算机工程与应用,2013,49(2):157-159.