K-Means聚类算法的改进和研究

王佩科，赵 驰

（1.淮海工学院计算机工程学院，连云港 222000；2.延安大学数学与计算机科学学院，延安 716000）

1 引言

在数据挖掘和处理方面，聚类分析是非常常见的一种方法。聚类算法中按照不同的标准分类众多，k-均值算法属于其中之一。其中的K-均值算法，又叫做K-Means聚类法，是聚类算法中的经典算法，是一种简单、容易实现且具有明确易于理解的几何意义。

2 基于K-means算法改进

传统的K-Means的k值是随机的，而数据集中包含有孤立点（和其他数据点相似度低且处在边缘），若选择在了这些特殊的点，算法的结果会和实际结果有着较大的出入，这样就会使得算法在计算结果上严重偏离预想，因此，剔除“孤立点”无疑是K-Means改进的有效方法。

2.1 改进算法的基本思想

首先，计算出数据集中每两个数据点之间的距离，输出结果为dist矩阵，然后对其行进行递增排列，列递减排列，在每行找到与数据点距离最近的n个距离，接着找到m个距离数据点的最邻近点。每如此处理，找到每一列的最邻近点，随后进行唯一化去重，通过向量中的元素计算出最近邻距离差并找到max减数作为密度半径。与人工给出的阈值进行比较，判别出“孤立点”并在输入集中剔除。

2.2 改进算法的描述

输入：输入集 Input_Data，定义n为邻距离的个数，定义m为与其相距最大距离的个数。

输出：检测到的孤立点Outier。

步骤：

（1）首先计算输入集Input_Data中两两数据点的距离dist，把输出结果记为Dist矩阵，定义Dist的对角线的值为∞，表示它与自己的距离。

（2）将Dist矩阵的行元素按照递增顺序排列。

（3）将矩阵的每一列按照递减顺序排列，取前n个数据元素，并存在孤立点向量Outier_ Data里。

（4）对Outier _Data 做唯一化处理，再对Outier_Data内的每个数据点对间隔矩阵Dist计较，找到最近邻距离差ΔD（i，j），并将最大的ΔD（i，j）记为maxΔD，几下此时相应的密度半径为E。

（5）计算每个数据点在Dist矩阵在E下的在矩阵Dist中的密度记为r。

（6）用r与人共设置的阈值进行比较，若大，则保留，反之视为孤立点剔除。

2.3 改进算法的效果

改进算法和k-Means的准确率对比见表1。

表1 改进算法和k-Means的准确率对比

3 结束语

本文提出了孤立点对K-Means算法的结果和精准性的干扰，并在此基础上做出优化，剔除一种通过剔除孤立点来提高算法精准度的思想。■