K近邻算法

K近邻算法（共7篇）

K近邻算法 篇1

0引言

K-最近邻(以下简称KNN)分类算法[1]是目前比较流行的一种分类方法。如今它已被广泛应用于各种人工智能领域,如模式识别、数据挖掘、后验概率估计、相似性分类、计算机视觉和生物信息学等。KNN分类算法的最大优点是其适合于属性较多或数据量很大的问题。它不需要先使用训练样本进行分类器设计,而是可以直接用训练集对数据样本进行分类,确定其类别标号。KNN分类算法思想简练,易于实现,在许多领域都有成功应用。

1K-最近邻算法简介

最近邻分类法是基于类比学习,即通过给定的检验元组与和它相似的训练元组进行比较来学习。训练元组用n个属性描述。每个元组代表n维空间的一个点,即所有训练元组都放在n维模式空间中。当给定一个未知元组时,KNN分类算法搜索该模式空间,找出最接近未知元组的k个训练元组。这k个训练元组是未知元组的k个“最近邻”。

文中的KNN分类算法是基于如下假设:1所有数据及类别都为数值类型;2度量距离越大,两个元组越相似;3每一个属性具有相等的权重;4属性值归一化;5如果元组X1和(或)X2的给定属性A的值缺失,则假定取最大可能差。

其中,“邻近性”用欧氏距离度量。两个点或元组X1= (x11,x12,...,x1n)和X2= (x21,x22,...,x2n)的欧氏距离为:

即对于每个数值属性,取元组X1和X2该属性值 的差,取差的平方并累计,并取累计距离计数的平方根。在使用式(1)之前,将每个属性的值规范化,以防止具有较大初始值域的属性(如收入)比具有较小初始值域的属性(如二元属性)的权重大,需要通过计算式(3),使用最小-最大规范化将属性A的值v变换到[0,1]区间中的v'。

其中minA和maxA分别是属 性A的最小值 和最大值[5]。

假定每个属性已经映射到[0,1]区间。如果数值属性A在元组X1和X2都缺失,则差值取1;如果只有一个值缺失,而另一个存在并且已经规范化,则取差1-v′和0-v′中的最大者。

对于近邻数k的最佳取 值,通过实验 确定。一般而言,训练元组数越多,k的值越大。随着训练元组数趋向于无穷并且k=1,误差率不会超过贝叶斯误差率的两倍(后者是理论最小误差率)。如果k也趋向于无穷,则误差率趋向于贝叶斯误差率[5]。

2实验算法流程

KNN分类算法流程如下:

Step1:准备数据,对数据进行预处理。

Step2:选用合适的数据结构存储训练数据和测试元组。

Step3:设定参数k,一般训练 元组数越 多,k的值越大,通常取奇数。

Step4:维护一个大小为k的按距离由大到小的优先级队列,用于存储最近邻训练元组。

Step5:随机从训练元组中选取k个元组作为初始最近邻元组,分别计算测试元组到这k个元组的距离,将训练元组标号和距离存入优先级队列。

Step6:遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距 离L与优先级 队列中的 最大距离Lmax进行比较。若L> =Lmax,则舍弃该元组,遍历下一个元组。若L<Lmax,删除优先级队列中最大距离的元组,将当前训练元组存入优先级队列。

Step7:遍历完毕,计算优先级队列中k个元组的多数类,并将其作为测试元组的类别。

Step8:测试元组集测试完毕后计算误差率,继续设定不同的k值重新进行训练,最后取误差率最小的k值。

3实验结果与分析

3.1实验环境和工具

实验环境:MicrosoftWindows7 + JavaDevelopKit1.7.0;服务器配置:Intel(R)Core(TM)CPU2.50GHz,4.0GB内存;实验工具:MyEclipse8.5,Matlab7.0。

3.2实验数据集

本文采用的数据集以经典乘式割草机数据集为例,一个乘式割草机的制造商希望将一个城市中的家庭分类为可能买割草机家庭及不想买割草机家庭。在该城市中,随即抽取12个拥有乘式割草机的家庭和12个没有拥有乘式割草机的家庭。

进行实验时,将实验数据分为两个部分:训练集和测试集。将75%家庭划为训练集,其它25%家庭划为测试集。当k取不同值时,利用训练集家庭对测试集家庭进行分类。乘式割草机数据集如表1所示。

将数据集分为含有18个事例的训练集和含有6个事例的测试集。测试集包含表中第6、7、12、14、19、20个事例,剩下的18个观测点构成训练集。

3.3估值标准

图1展示了在训练集和测试集中的所有事例,“*”表示测试集数据,“·”表示训练集数据。

如果选择k=1,则选择了一种对数据局部特征非常敏感的分类方式。如果选择的k值较大,则相当于取大量的数据点的平均,同时会平滑掉由于单个数据点的噪音而导致的波动性。

3.4实验结果与分析

一般而言,k值通常取奇数。从k=1开始,使用检验集估计分类器的误差率。重复该过程,每次k增值2,允许增加两个近邻。选取产生最小误差率的k值作为本次实验的最佳取值。使用Matlab7.0软件对实验结果作图,如图2所示。

对比表1中的数据分类,可知当k=13时测试集中事例全部分类正确,当k取其它值时差异较大。由图1可以得到表2所示内容。

通过实验分析可以看出,在该案例中,将选择最近邻个数k=13。该选择很好地消除了在低k值时的变动性和高k值时的过平滑现象。针对不同k值的测试可知,k值可通过有效参数的数目来推断。有效参数的数目和k值有关,约等于n/k(约为2),其中,n是该训练集中事例的数目。

4结语

由KNN算法在乘式割草机案例中的应用可知,k的取值直接影响KNN分类算法在现实应用中的数据集分类。因此,需要在已有研究的基础上融合多种技术解决k的取值问题,这也是提升KNN分类算法性能的关键。后续研究中,可采取附加权值的方法,放大邻近点对结果的影响,进一步提高KNN算法的精确度。

基于最近邻思想的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

上个世纪60年代, Mac Queen首次提出kmeans算法[1], 而后的数十年中, kmeans算法被广泛应用于各种领域, 比如马勇等人将kmeans算法应用在医疗系统中[2], 杨明峰等人将kmeans聚类算法应用于对烤烟外观的区域分类[3]。同时很多的学者投入到对kmeans算法本身特性的研究中[4,5], 目前kmeans算法已经成为机器学习, 数据挖掘等领域比较重要的方法之一。而k近邻算法是图像以及文本分类领域应用比较广泛的算法之一[6,7], 对k近邻算法而言, k值的选择以及样本间距离的度量方式都会影响到分类的精确度。但是同样有许多学者对该算法进行了一些改善, 比如孙秋月等[8]通过对度量的样本数据的每个维度赋不同权值的方式, 降低了样本数据分布不均匀导致的分类误差。严晓明等通过类别平均距离进行加权对大于某一个阈值的数据样本点进行剔除的方式来提高k近邻算法的精度[9]。k近邻算法本身是一种惰性的监督算法, 相较于其他监督算法比如支持向量机、逻辑回归、随机树等, 具有算法简单、易于理解、易于实现、无需估计参数的特性。kmeans算法由于对初始点选择较敏感, 不同的初始点将会导致不同的聚类结果。因此本文对kmeans算法进行改进, 改良的kmeans算法对二分类的结果可以接近k近邻算法的正确率, 甚至在k近邻算法选择不同的k值时, 分类效果会优于采用k近邻算法的分类结果正确率, 同时分类的结果也远高于随机指定初始点的kmeans算法。

1 传统的分类算法与改进算法

1.1 传统的kmeans算法与k近邻算法

对于传统的kmeans算法而言, 对于给定的数据集n个样本, 在不知道数据集的标记时, 通过指定该数据集中的k (k≤n) 数据样本作为初始中心, 通过如下的方式进行聚类:

(1) 对该数据集中任意一个数据样本求其到k个中心的距离, 将该数据样本归属到数据样本距离中心最短的类;

(2) 对于得到的类中的数据样本, 以求类的均值等方法更新每类中心;

(3) 重复上述过程1和2更新类中心, 如果类中心不变或者类中心变化小于某一个阈值, 则更新结束, 形成类簇, 否则继续。

但是对于传统的kmeans聚类算法而言, 由于随机指定初始点, 对kmeans算法通过迭代这样一种启发式的贪心算法而言不能形成一个全局最优解, 迭代最终收敛的结果可能都是局部最优解。这样分类的精度就会难以预料, 对最终的样本分类就难以消除随机指定初始点造成的聚类结果不一致的影响。

对于传统的k近邻算法而言, 对于给定的数据集, 有n个数据样本是已标记的, 另一部分数据样本是未标记的, 对未标记的数据样本, 通过如下的方式进行分类:

(1) 度量每个未标记数据样本与所有已标记数据样本的距离;

(2) 对所有求出的距离选择与未标记数据样本距离最近的k (k ≤n ) 个已标记数据样本;

(3) 统计这k个已标记的数据样本, 哪一类的数据样本个数最多, 则未标记的数据样本标记为该类样本K近邻算法没有一个数据样本训练的过程, 本身是一种惰性的监督算法, 该算法对k值的选择以及距离的度量方式都会影响最终的分类精度。因为该算法只是选择。

k个近邻而没有判断近邻中样本是否分布得均匀。因此, 该算法如果样本分布不均匀, 也会大大影响分类的结果。

1.2 改进的kmeans算法

由于传统kmeans算法初始点的影响较大, 因此可以做如下改进。

对于给定的数据集样本, kmeans可以通过两两比较数据集中数据样本点间的距离, 选择距离最远的两个点A, B作为初始标记。同时为了去除噪声对初始点的影响, 对于选定的初始标记点, 可以选择以初始标记点为中心, 与初始标记点距离小于阈值的若干个点的几何均值A', B' 作为最终的初始点。对于A初始标记点的若干点的选择原则是离初始标记A距离与离B距离的比值大于一定阈值的若干点, 而对于B初始标记点的若干点的选择原则是离初始标记B距离与A距离的比值大于一定阈值的若干点。选定了初始点后, 其后的步骤如下:

(1) 对该数据集中任意一个数据样本求其到A', B' 两个中心的距离, 将该数据样本归属到数据样本距离A', B' 短的类;

(2) 对于得到的类中的数据样本, 求类的均值更新两类中心;

(3) 重复上述过程1和2更新类中心, 如果类中心不变或者类中心变化小于某一个阈值, 则更新结束, 形成类簇, 否则继续。

2 实验结果与分析

采用手写数字集MNIST Handwritten Digits[10]进行实验, 该数字集库含有0-9的10类手写训练数据集和0-9的10类手写测试数据集。每个数据集样本的大小是28*28的图片, 转化成向量是1*784维大小。从手写数据集中抽取标记为1和2的两类数据集样本, 从这类数据集中随机抽取标记为1和2的数据样本各1000个, 共计2000个数据样本进行实验分析。从这2000个数据样本中随机选择1600个数据样本 (标记为1和2的两类数据各800个数据样本) 进行k近邻分析, 400个数据样本 (标记为1和2的两类数据样本各200个) 进行测试。对于改进的kmeans算法, 将小于阈值的5个点取几何均值作为最终的初始点和传统的kmeans算法采用400个数据样本进行测试。改进的kmeans算法测试的正确率为84.25%, 传统的kmeans算法初始值不确定, 可能的正确率为15.75%, 51%以及83.75%等。很明显, 改进的kmeans算法不管从精度还是稳定性方面都优于传统的kmeans算法。k近邻算法选择曼哈顿距离和欧式距离作为距离度量的方式, 同时改变k值对k近邻算法的结果进行测量, 结果如图1所示, 横轴表示k值选择的样本数, 纵轴表示对应的测试正确率。

从图1中可以看出, 随着近邻数的增多, 在一定的范围内, k近邻的精度是下降趋势。对于选择曼哈顿距离度量样本间距离的k近邻算法, 当k值大于200的时候, k近邻算法对样本的分类正确率明显低于改良的kmeans算法对样本分类的正确率。而采用欧式距离度量样本间距离的k近邻算法, 当k值大于380的时候, k近邻算法对样本的分类正确率才明显低于改良的kmeans算法对样本分类的正确率。因此对于k近邻算法而言, k近邻数目的选择以及样本间距离度量的方式对分类的结果都是至关重要的。同时从中可以发现, 在某些情况下, 无监督的学习方式可能比有监督的学习方式更有利, 也更方便。

摘要：kmeans算法作为无监督算法的一种, 对初始点的选择比较敏感;而k近邻作为一种惰性且有监督的算法, 对k值和样本间距离度量方式的选择也会影响结果。改良的kmeans算法通过遍历样本, 筛选初始点, 其准确率超过了k近邻算法, 同时稳定性也优于传统的kmeans算法。无监督算法在一些情况下优于有监督算法。

关键词：初始点,无监督,邻近点,有监督

参考文献

[1]Macqueen J.Some methods for classification and analysis of multivariate observations[C].Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, 1967:281-297

[2]马勇.一种改进的K-means聚类分析算法在医院信息系统中的应用研究[J].信息资源管理学报, 2012, (03) :93-96

[3]杨明峰, 詹良, 魏春阳, 等.基于K-means聚类分析的不同种植区烤烟外观质量区域分类[J].中国烟草科学, 2012, (02) :12-16

[4]张文明, 吴江, 袁小蛟.基于密度和最近邻的K-means文本聚类算法[J].计算机应用, 2010, (07) :1933-1935

[5]袁方, 周志勇, 宋鑫.初始聚类中心优化的k-means算法[J].计算机工程, 2007, (03) :65-66

[6]陈帅均, 蒋平, 吴钦章.改进的KNN算法在光测图像关键事件评估中的应用[J].光电工程, 2014, (08) :66-72

[7]王渊, 刘业政, 姜元春.基于粗糙KNN算法的文本分类方法[J].合肥工业大学学报 (自然科学版) , 2014, (12) :1513-1517

[8]孙秋月.基于SNN相似度的KNN分类算法研究[D].云南大学, 2008

[9]严晓明.基于类别平均距离的加权KNN分类算法[J].计算机系统应用, 2014, (02) :128-132

K近邻算法 篇4

聚类的基本任务是为对象集合中所有存在特征相似或接近的对象个体进行类别标记。目前,比较流行的聚类方法有划分法、层次法、密度法、网格法等。在众多的聚类方法中,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近邻算法 篇5

随着大数据时代的到来,多元化、复杂性数据的产生,机器学习显得尤为重要。多年来,单标签理论发展逐步成熟和广泛应用,但在现实生活中,数据样本可能拥有多个标签。比如:一则新闻可能会同时关于教育、科技、社会等多个标签。多标签学习[1]的研究主要有两大任务:多标签分类[2](Multi-label Classification,MLC)和标签排名[3](Label ranking,LR)。多标签分类是通过训练样本训练出分类器,输出未知样本对标签集中每个集合是否相关的分类结果。标签排名学习由训练集得到一个分类器,输出未知样本对标签集中每个标签相关程度的排名。在某些领域,标签分类和标签排名同等重要。例如在新闻过滤系统中[2],系统必须返回用户最感兴趣的新闻,同时将用户最感兴趣的新闻显示在最上面。理想情况下,系统可以建立一个既可以排序,又对标签进行相关判断的方法,该任务定义为多标签排序[4](Multi-label ranking,MLR)。多标签学习算法[2]主要有问题转换法(Problem Transformation)和算法改进(Algorithm Adaption)两大类。问题转换算法主要有BR(Binary Relevance)二元关系法、RPC(Ranking by Pairwise Comparison)成对比较排序法、LP(Label Powerset)标签密集法等等,而算法改进包括决策树(Decision Tree)、Boosting算法、神经网络(Neural Network)、支持向量机等等。为提高学习算法性能,在处理数据过程中往往需要对数据进行维数约简。维数约简算法包括特征选择[5]和特征提取两类,单标签领域一些算法可以直接应用于多标签学习,而一些算法经过改进后同样也可以运用于多标签学习。数据特征的选择、维数约简是决定数据挖掘方案的最重要部分,所以选择适合多标签数据集进行维数约简的算法非常重要。

1 相关工作

邻近算法(或k近邻)[1](kNN,k-Nearest Neighbor)分类算法是数据分类技术中最简单的算法。张敏灵教授和周志华教授[1]成功将kNN算法运用于多标签学习,即ML-kNN算法,成为多标签学习算法的中的经典算法。ML-kNN算法没有考虑属性特征对标签权重的影响,也未考虑标签集对属性特征的映射关系。有些属性的特征值比较小,但其影响分类的决定性比较大,如果简单采用欧式距离来计算样本的距离就很容易增大样本误分类的可能性。

根据是否利用先验知识划分,主成分分析法属于无监督降维学习方法。主成分分析法通过抽取样本的主要影响因素,简化复杂的问题。主成分分析法还被用于将高纬度数据投影到低维空间,消除数据间的冗余,提高学习算法的精度。文献[7]通过PCA对k近邻多标签学习算法的改进来实现多标签学习,提出了信息损耗率ξ和对k近邻多标签算法的改进。信息损耗率是衡量数据传输、转换过程中的完整程度,损耗率越小证明数据信息越完整。在处理数据过程中,合理控制数据的信息损耗率非常重要。

目前,多标签学习理论和应用都取得丰硕的成果。PCAIML-kNN算法就是在以往理论基础上提出的。该算法主要分两部分来改进,首先通过控制信息损耗率ξ得到样本的动态维度,进而得到特征提取后的动态样本;其次,样本距离计算加入了抽取后定义权重,多标签的评价指标优于与其它算法。该算法的主要思路是先对数据集进行维数约简,再运用改进后的ML-kNN算法对数据集进行多标签处理。

2 PCAI算法

PCAI算法基于k近邻多标签算法,并将PCA算法改进后应用于多标签学习。该改进算法的核心思想是对多标签数据集维数约简得到新数据,然后通过k近邻算法、多标签学习算法处理新数据集。与其它算法相比,该算法有效降低了多标签数据集的维数,提高了分类精度。

2.1 PCA算法

假设多标签数据集的特征向量集为X = [x1,x2,…,xn],经过PCA算法转换后的特征向量集为Y = [x1,x2,…,xn],则向量矩阵X转换成向量矩阵Y线性公式为Y= [px1,px2,…,pxn],X的协方差矩阵、Y协方差矩阵计算分别如式(1)、式(2):

比较式(1)、式(2)可知,原数据集与转换后的协方差矩阵具有相同的特征值和特征向量,样本数据在变换前后并没有改变数据的信息量。PCA改进算法具体过程改如下:

(1)向量矩阵X分解

其中,D表示协方差矩阵Σx的对角矩阵,V表示方差矩阵的对角矩阵D的特征向量。

(2)向量矩阵X奇异值

(3)信息损耗率

其中,d是向量矩阵X特征向量的个数,k是向量矩阵Y特征向量的个数,x(i)表示样本的第i个特征值,x(i)approx是向量矩阵Y的第i个特征值,‖x(i)-x(i)approx‖ 是向量矩阵X与向量矩阵Y特征值的二范数。由k个向量可以确定k个特征值

(4)向量矩阵Y

2.2 k近邻多标签学习算法改进

向量矩阵X经过PCAI算法转换成向量矩阵Y,此时转换后样本矩阵可以表示为yi= [ai1,ai2,…,aik],yj=[aj1,aj2,…,ajk]。在k近邻多标签学习算法中,在计算两个样本的距离中仅仅采用了欧式距离,欧式距离在数据样本维数比较低时比较适合,但在处理高维数据时忽略了数据样本各个特征之间的差异。在计算距离时加入了特征属性重要度,两个数据样本间的重要度可以表示为式(7),本文将特征值加入到计算特征,计算如式(8),改进后的样本间距离如式(9)。

3 实验结果与分析

本实验采用多标签精确度(Precision)、覆盖率(Coverage)、汉明损失(Hamming Loss)、One-错误率(One-Error)、标签排名(Ranking Loss)等5个评价指标。5个评价指标中精确度越大越好(用“↑”表示),其余4个评价指标越小越好(用“↓”表示)。该实验选用的算法有ML-kNN算法、PCAIML-kNN算法、FisherML-kNN算法、ReliefML-kNN算法。本实验采用Yahoo部分数据集,选取Arts、Business、Computers、Education、Entertainment 5 个数据集。5个数据集评价指标如图1~图5所示。

从图1 可以看出,与ML-kNN方法相比,PCAMLkNN算法在分类精度上提高不大,FisherML-kNN、ReliefML-kNN算法与算法PCAML-kNN相比效果显著。5个算法中,PCAIML-kNN算法在多标签数据集分类精确度上明显优于其它算法。图2~图5中,评价指标值越小其相应的评价指标性能越好。需注意的是,各个指标采用平均值和方差的形式,在上述4个评价指标中可以看出,上述方法在处理相同数据集时,方差差异不大,即比较稳定。从平均值来看,PCAIML-kNN与其它算法相比,在覆盖率、汉明损失、one-错误率、排名损失评价指标中值最低,相比而言,算法最好。

4 结语

本文利用PCA对k近邻多标签学习算法(ML-kNN)进行改进,引入信息损耗率,对k近邻多标签学习算法距离进行改进。实验结果证明,与其它多标签分类算法相比,该算法提高了多标签的评价指标性能,在数据分类、标签排序等方面比较突出。本文不足之处在于信息损耗率未能得到理论及实践证明,未能与其它无监督学习算法进行比较。后续将研究具体领域多标签学习,提高样本分类精度、降低时间与空间复杂度。

参考文献

[1]ZHANG M L,ZHOU Z H.ML-KNN:a lazy learning approach to multi-label learning[J].Pattern Recognition,2007,40(7):2038-2048.

[2]TSOUMAKAS G,KATAKIS I.Multi-label classification:an overview[J].International Journal of Data Warehousing&Mining,2007,3(3):1-13.

[3]GENG X,LUO L.Multilabel ranking with inconsistent rankers[C].Computer Vision and Pattern Recognition(CVPR),2014IEEE Conference on.IEEE,2014:3742-3747.

[4]BUCAK S S,MALLAPRAGADA P K,JIN R,et al.Efficient multilabel ranking for multi-class learning:application to object recognition[C].Computer Vision,2009IEEE 12th International Conference on.IEEE,2009:2098-2105.

[5]苏映雪.特征选择算法研究[D].长沙:国防科学技术大学,2006.

[6]FODOR I K.A survey of dimension reduction techniques[J].Perpinan,2003,volume 205:351-359(9).

K近邻算法 篇6

电力变压器作为电力系统中最为关键的设备之一,其运行可靠性直接关系到电力系统的安全,可靠、优质、经济运行。但变压器在长期运行中,故障和事故又往往是很难完全避免的。外部的破坏和影响,安装、检修中存在的问题和制作中的设备缺陷或隐患,特别是变压器长期运行后的绝缘老化、材质劣化等,都是其故障的诱因[1,2,3]。一旦变压器出现故障,往往会影响大面积供电,且修复时间比较长,所以在变压器出现故障时,及时、准确、可靠地发现变压器的故障意义重大。变压器的状态监测和故障诊断一直是国内外研究的热点,提出了多种故障诊断的方法[3,4,5],其中,根据油中溶解气体的含量进行分析(DGA:Dissolved Gas Analysis)是目前普遍受电力工业界欢迎、现场运用最多的变压器内部故障诊断思想,已列为油浸变压器32项预试项目的第1位[1,2]。

虽然传统的DGA方法存在其局限性[1,2,5];但目前我国电力工业中主要还是比较青睐传统的DGA方法,一些研究单位在长期的应用中积累了大量的宝贵数据。充分利用这些数据进行变压器故障的诊断和识别,是比较实际、可行的方法。

由于故障表象与真正的故障原因之间缺乏明确的数学关系,所以变压器故障诊断基本上是一种数据驱动的方法,需要依赖于人工经验。这里的人工经验,指的就是用来指导诊断的样本。在利用DGA思想进行诊断的众多分支中,目前应用最多也最成熟的就是基于人工智能的方法[3,4,5]。变压器故障诊断问题,又是一个典型的模式识别的问题,或者说是一个分类问题。

K-NN分类算法根据待分类样本在特征空间中K个最近邻样本中的多数样本的类别来进行分类,因此具有直观、无需先验统计知识、无师学习等特点,从而成为非参数分类的一种重要方法[6,7]。但k近邻算法中一个显然的问题是:当样本分布相对不均匀时,只按照前k个近邻样本的顺序而不考虑它们的距离差别会影响分类精度[7,8,9]。

针对这个问题,本文根据待分类样本与其各个近邻之间的距离对其进行加权,提高相似度较大的近邻的“发言权”,从而提高诊断的准确性。最后通过仿真比较经典的K-NN方法与加权的K-NN方法的性能差异。

1 诊断结构与原理

1.1 DGA概述

由于变压器的长期运行,其内部的绝缘材料,在热和电的作用下,会逐渐老化和分解,并缓慢产生少量的各种低分子烃类及一氧化碳、二氧化碳等气体。正常情况下,分解是非常缓慢的。但是,当存在潜伏性故障时,这些气体的产生速度和浓度就会增加。随着故障的进一步发展,分解出来的气体就会不断地溶解在油中。经验证明,变压器油中H2,CH4,C2H6,C2H4,C2H2,CO,CO2等特征气体的组分含量与故障的类型和严重程度有密切关系[1,2,3,5]。因此,在设备运行过程中,定期测量溶解于油中的气体组分和含量,就能尽早发现设备内部存在的潜伏性故障,并可随时掌握故障的发展情况,有助于对设备的运行情况做出诊断,制定故障的处理方案。根据这些特征气体的含量或者比值,一般可以判断出的故障类型包括:过热、放电、老化等。

1.2 K-NN算法

目前,分类算法一般分为Lazy和Eager两种类型。称之为Lazy学习算法的原因是它从局部出发,推迟对训练例子的归纳过程,直到一个新的测试例子出现[10]。K-NN就是一个典型的Lazy方法。所谓K-NN规则就是取未知样本x的k个近邻,看这k个近邻中多数属于哪一类,就把x归于哪一类。

根据1.1中的分析并结合实际工业应用的情况,本文选取6个特征量作为输入:H2,CH4,C2H6,C2H4,C2H2,C1+C2(总烃)。以上各输入均采用百分比形式。输出分为:低温过热(低于150℃)、低温过热(150-300℃)、中温过热(300-700℃)、高温过热(高于700℃)、局部放电、低能放电、低能放电兼过热、高能放电、高能放电兼过热以及正常老化等10种情况。本文构造的K-NN结构如图1所示。

2 加权K-NN算法

K-NN是一种有效的分类方法。在进行分类时,首先计算待分类对象与每个实例数据的距离,然后选择K个距离最近的实例数据,根据这些数据的类别,采用投票机制,来决定待分类对象的类别归属。

2.1 经典K-NN算法

在N个已知样本中,来自v1类的样本有N1个,来自v2类的样本有N2个,来自vc类的样本有Nc个;首先寻找待测试样本x的K个近邻,寻找近邻一般以相似性为依据,经典K-NN算法一般采用的是欧氏距离或者是余弦距离和内积,其中又以欧式距离应用最广泛。

其中,xim,xjm分别表示测试样本和训练样本的第m个特征属性。

由于距离与相似度成递减关系,所以一般又往往采用距离的倒数作为相似度:

求取相似度之后,则可以根据相似度排序得出分类样本x的近邻,若k1,k2,…kc分别是待测样本x的K个近邻中属于v1,v2,…vc类的样本个数,则定义判别函数为:

式(3)中yj为第i个分类中第j个样本与待测样本x的近邻隶属函数,其值为0或者1。yj的定义为:

分类的决策规则为:

2.2 考虑距离差别的加权K-NN算法

从2.1可见,在经典的K-NN算法中,待分类样本x的K个邻近的“发言权”是一样的,即都默认是1。但这往往与实际情况不一致。因为在实际中,我们很自然地都认为相似度最大或者说距离最小的样本,在决策中的权重应该最大,这也就是加权的K-NN的基本思想[8,10,11,12,13]。

K-NN中权重函数的选取,目前还没有比较统一的方法,但此处的权重函数比较必须是距离的函数,且是距离的减函数。

假定待分类样本x与其K个近邻x1,x2…xk的距离为d1,d2…dk,待分类样本x的第i个近邻xi对待分类样本x的决策权重为:

而改进后的K-NN算法判别函数为:

可见,经典的K-NN算法是加权K-NN方法的一种特例,即对所有权重赋值为1;而在改进的K-NN中,距离待测样本近的样本获得较高的权重,因而能更加真实地表达其相似度的差异。K取为5时,其空间示意图可参见图2。

2.3 基于改进K-NN算法的诊断流程

一个完整的K-NN诊断过程,一般包括一下几个步骤:

Step1 预处理:主要是对数据进行处理,转化为气体组分含量比值、编码或者占总含量的百分比形式;另一方面进行启动诊断的判断,即把试验结果的几项主要指标(总烃、甲烷、乙炔、氢等)与油中溶解气体含量的注意值与气速率的注意值作比较,初步判断是否可能存在故障。

Step2 寻找近邻:根据式(1)与式(2),计算待分类样本与各训练样本的距离与相似度,根据K的取值情况,寻找出待测样本x的K个近邻

Step3 计算权重:根据式(6),分别计算各个近邻的权重值

Step4 进行K-NN分类:依据式(5)和式(7),对待测数据进行分类决策,获得诊断结论并进行输出。

3 仿真

本文利用以Matlab为仿真工具,收集整理有明确诊断结论的故障数据,并结合变压器故障诊断Web Service系统[14]与浙江省电力试验研究所研发的故障诊断专家系统,共选取740组学习样本,同时选取了总共117组待诊断的样本。下文仿真中,采用经典的K-NN方法与本文改进的K-NN方法两种方法进行对比。因为K的取值对诊断有直接影响,以下在不同的K取值下进行仿真比较,限于篇幅,仅给出部分K值的统计数据。

表中F1至F10依次为:低温过热(低于150℃)、低温过热(150-300℃)、中温过热(300-700℃)、高温过热(高于700℃)、局部放电、低能放电、低能放电兼过热、高能放电、高能放电兼过热、正常老化共10种故障情况,案例数指的就是仿真中用于验证模型正确性的案例个数。表1中的“总体”指的是所有仿真案例的平均正确率,表1中的其他数值就是在K的不同取值下作出正确诊断的案例个数。

从表1、表2可知,K-NN方法与K的取值直接相关,经典的K-NN方法的K值在1或者2附近时,具有比较好的诊断准确率,当K为2时,经典的K-NN算法准确率最高;加权的K-NN方法,K值为1,2或者3时,准确率都比较高,其中K取值为2或者3时候,诊断准确性最好。综合表1和表2来看,第10种故障情况的诊断准确性都相对比较低,分析原因主要是正常老化的样本不够丰富、全面。在不同的K值下,两种方法的总体准确率如图3所示。

综合上述仿真数据易知,K值取为1时,两种方法的针对准确率一样,这与理论是相吻合的。总体而言,经典K-NN方法与加权的K-NN方法的诊断结果都受K取值的影响,在本文的测试系统中,两种方法出现最佳诊断结论时的K取值不完全一样,但最理想的诊断准确性出现在K为2附近。在能够获得较高的准确率的K取值范围内(1-4之间),加权K-NN方法的性能明显优于经典的K-NN方法,这也说明本文的改进是有效的。

4 结论

本文在将K-NN分类方法引入基于DGA方法的变压器故障诊断中,针对经典K-NN方法存在的缺陷,提出考虑加权的改进方法。根据待分类样本与近邻的距离来赋予权重,从而提高诊断的准确性。最后的仿真表明,经典的K-NN和加权的K-NN诊断方法都具有比较高的准确性;在能够获得较好的诊断准确性的K取值范围内,加权的K-NN方法比经典的K-NN体现出了更高的准确性。

摘要：该文将K近邻分类方法引入基于溶解气体法(DGA)的变压器故障诊断中。并针对经典K近邻方法(K-NN)存在的缺陷,提出根据待分类样本和近邻样本的距离来加权的改进方法。最后通过仿真验证了该方法的有效性。仿真表明,当K的取值在一定范围内时,经典的K-NN算法和加权的K-NN方法都具有比较高的准确性,且加权的K近邻方法比经典的K近邻法体现出了更好的性能。

K近邻算法 篇7

随着Internet的高速发展,网页文本信息急剧增加,如何有效地将海量的web网页信息组织分类是现代信息研究的重要领域。对于文本的自动分类,有许多优秀的算法,如朴素贝叶斯方法、支持向量机方法、K近邻方法等等。其中K近邻方法是由Cover和Hart于1968年提出的,由于K近邻方法思路简单,易于实现,且错误率低,得到了广泛的应用。在网页分类领域中,本文针对传统的K近邻算法的缺点,提出一种改进的K近邻网页分类算法。

1 网页文本分类

文本分类是一个映射的过程,它将未标明类别的文本映射到已有的类别中,文本分类的映射规则是系统根据已分类好的分类样本,总结出分类的规则,建立分类的判别公式和规则,在新文本到来时,根据总结出来的判别规则,确定文本相关的类别。网页文本分类的一般过程可以分为文本预处理、分类器的训练与分类、分类结果评价三个过程。

1.1 文本预处理

文本预处理的任务是将网页文档表示成易于计算机处理的形式,其中包括Web页面文本提取、标记剔除、分词、词频统计、特征抽取、去停用词等过程。文本表示的常用模型是向量空间模型,将文档映射为一个特征向量V(d)=(t1,w1(d);…;tn,wn(d)),其中ti(i=1,2,…,n)为互不相同的特证词,wi(d)是ti在文档d上的权值,常用的特征词权值计算方法是TF-IDF公式,TF代表一个词在一篇文章中出现的次数,次数越多,这个词就越重要。IDF代表一个词在整个库中出现的次数,次数越多,这个词就越不重要(如"是","的"等)。公式如下:

tfi是特证词ti在文档d中的出现频率,n是训练集的文档总数,dfi是训练集中含有特证词ti的文档总数。

1.2 K近邻算法介绍

K近邻方法属于懒惰学习方法,其基本思想是:给出测试文档,系统在已经分类好的训练集中查找与其最近的K个邻居,根据这些邻居的类别分布情况获得测试文档的类别。其中可以用这些邻居与测试文档的相似度进行加权,从而获得较好的分类效果。其分类过程如下:

(1)特证词选取,构建训练集中每篇文档的向量空间模型,通过上述TF-IDF方法计算特证词的权重。

(2)对于测试文档,用同样的方法构建矢量空间模型并计算特征词权重。

(3)测试文档与训练集中的每篇文档的计算相似度,常用余弦向量距离计算,公式如下:

(4)选取相似度最大的K个文本,通过这些文本的所属类别的分布情况判别测试文本的类别。

1.3 评价标准

分类效果评估指标使用常用的查准率Precision、查全率Recall以及F1测试值:

2 改进的算法

由于传统的K近邻算法是基于上述的相似度公式计算,不考虑特征词出现的位置,因此,一些特殊的噪声词会对相似度计算的结果产生很大的影响。

网民浏览网页通常采用扫描式阅读,在这种阅读方式下,导致网页文章的内容高度简洁,重要的词或句子会出现在文章的前面,特别是出现在标题中的特证词更是决定文章类别的重要因素,因此,文章中特征词的出现位置对于网页文本的分类来说,有着重要的作用。

本文提出基于向量空间模型的改进模型,将网页文本表示成多维向量模型,具体实现是,在文本分词的同时记录特证词的出现位置i,将i与所属文档总特证词的个数相除,得到相对位置比loc。文本的向量模型可以表示为V(d)=(t1,w1(d),loc1(d);…;tn,wn(d),loci(d)),注意,对于多次出现的特征值取最早出现的位置。由此,为了突出特证词出现位置对于分类的作用,对特征词权值的计算公式进行了改进:

而相似度的计算公式也进行了相应的改进:

3 实验与结果分析

本文实验所用的数据集是通过网络蜘蛛抓取新浪网上的房产、财经、科技、体育、娱乐、汽车六个栏目,共2447篇文章,分布情况如表1所列:

从每个栏目随机抽取300篇文章作为训练集,剩下的作为测试集,实现了传统的K近邻算法和改进后的算法,取K=7。对得到的结果进行统计,并计算了上述的三种评价标准,实验结果见表2所示(查准率和查全率分别用P、R代替)。

通过实验结果得知,利用特证词的出现位置对K近邻算法加以改进确实能够得到更好的分类效果,所用的测试时间相当,只是增加了网页文本预处理时间,这是由于预处理时期增加了计算特证词位置比的过程造成的。

4 结束语

本文针对传统K近邻算法对于噪声词敏感的缺点,结合网页文章构成的特殊性,对文档的特征向量表示模型进行了改进,从而也改进了K近邻算法中特证词的权值以及文档相似度的计算公式,实验结果表明改进后的K近邻算法提高了分类的精度。同时,本算法增加了网页文本的预处理时间。针对K近邻算法的懒惰性,如何能够有效地缩小算法训练和分类所用时间也是一个重要的研究方向。

摘要：K近邻(k-Nearest Neighbor)算法是进行分类时最常用的文本分类算法,基本的K近邻算法是基于余弦向量距离计算相似度,由于特证词权值的计算采用的是TF-IDF方法,使得该算法在文本分类中对于噪声特征非常敏感,本文针对这一问题,提出在网页分类的领域中,根据网页文章的特性,考虑特征词出现不同位置,改进相似度的计算公式,实验证明,提高了分类的准确性。

关键词：K近邻,网页分类,相似度

参考文献

[1]潘丽芳,杨炳儒.基于簇的K最近邻(KNN)分类算法研究[J].计算机工程与设计,2009,30(18):4260-4262.

[2]李村合,冯静.一种改进的KNN网页分类算法[J].微计算机应用,2008年,29(2):21-25.

[3]姚兴山.基于词频的中文文本分类研究[J].现代情报,2009,29(2):179-181.

[4]刘博,杨柳,袁方.改进的KNN方法及其在中文文本分类中的应用[J].西华大学学报(自然科学版),2008,27(2):33-36.

[5]张著英,黄玉龙,王翰虎.一个高效的KNN分类算法[J].计算机科学,2008,35(3):170-172.