孤立点

一种改进的K-means聚类算法与孤立点检测研究

摘要:传统的K-means算法对于孤立点数据是非常敏感

的,少量的该类数据就能对聚类结果产生很大影响。该文提

出了一种改进的K-means算法来消弱这种敏感性。算法基于孤立

点检测LOF算法中计算K距离的思想,将大于K距离的数据点

作为伪聚类中心参与聚类划分,通过对聚类结果的评价来判断该

数据点是否为孤立点。若为孤立点则去掉该点,进而来提高聚类

质量。

关键词:K-means;K距离;孤立点;伪聚类中心中图分类

号:TP311文献标识码:A文章编号:1009-3044(2010)21-6085-02

AModifiedK-meansClusteringAlgorithmandRearchon

OutlierDetection

YINGMin-jie,DONGChun-zhao

(SouthwestJiaotongUniversity,Chengdu610031,China)

Abstract:lassicalK-meansalgorithmisverynsitiveto

outlierdata,smallamountsofsuchdatacanhaveagreatimpact

paper,amodifiedK-means

algorithmbasontheideaofLOFoutlierdetectionalgorithm,

whichregardsthedatathataregreaterthanK-distanceasa

htheevaluationofclusteringresultsto

,the

outlierdatapointisremovedinordertoimprovethequalityof

clustering.

Keywords:k-means;k-distance;outlierdatapoint;pudo-

center

聚类是把一组个体按照相似性归成若干类别,使得属于

同一类别个体之间的距离尽可能小,而不同类别个体间的距

离尽可能的大。聚类作为数据挖掘中的一种重要技术,在模式

识别、数据分析以及市场研究等很多领域都发挥着重要作用。目

前主要的聚类算法[1-2]有基于划分方法的K-means算法和K-中

心算法，基于密度的DBSCAN和OPTICS方法基于网格的CLIQUE和

STING方法等。本文重点研究了K-means算法,并针对该算法的孤

立点敏感性提出了一种改进算法。改

进后的K-means算法能很好的削弱孤立点的影响,大大提高

了聚类质量。

1K-means算法研究

1.1K-means算法[1,6]

K-means是基于划分方法的一种核心算法,划分的思路是以k

为参数,把n个对象分为k个簇,并使簇内具有较高的相似度,簇间

具有较低相似度,相似度根据一个簇中对象的平均值来计算。

K-means算法的处理流程如下:

(1)随机选择k个对象，每个对象都代表一个初始簇中心;

(2)对剩余的对象,计算其与各个簇中心的距离,并将它赋

给距离最近的簇;

(3)重新计算每个簇的平均值,并将该平均值作为新的簇

中心;

(4)不断重复第(2)、(3)步,直到准则函数收敛或聚类中心

不再发生变化,准则函数通常采用平方误差准则。

1.2K-means算法的优缺点

当结果簇是密集的,而且簇之间的区分明显时,它的效果较

好。对于大数据集处理,效率较高。但K-means算法不适合发现

非凸面形状的簇,并且它对孤立点数据敏感,少量的孤立点数据

对聚类效果产生很大影响。

2LOF局部孤立因子算法[3]之K距离[4]

本论文中，为区分K-means的初始簇中心个数k,将LOF算法

的K距离称为K'距离。

K'距离，又称局部最大距离，定义为：当对象p至少有k'个

邻居时,对象p与这k'个邻居的最大距离。任何与对象p的距离大

于p的k'距离的对象不是p的邻居。即若对象o为p的邻居,则

满足以下条件[5]：

1)至少存在k'个对象o',使d(p,o')

2)至多存在k'-1个对象o',使d(p,o')