Improvement and Research of K-means Clustering Algorithm

Digital Communication World - - Contents -

Wang Peike1, Zhao Chi2

(1. Huaihai Institute of Technology, Computer Engineering, Lianyungang, 222000; 2.Yan'an University Computer Science and Technology, Yan'an, 716000)

Abstract: In the traditional K-means clustering algorithm, reasonable selection of K and K initial clustering point values will have a greater influence on the clustering results. The idea of improving the K-means algorithm and its follow-up research route was put forward, and the accuracy of the clustering algorithm was improved.

Keywords: Isolated point exclusion

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算法的结果和精准性的干扰,并在此基础上做出优化,剔除一种通过剔除孤立点来提高算法精准度的思想。■

参考文献[1]刘钢,李宗辰.基于统计距离和极大极小值的改进K-means算法研究[j].电

脑知识与技术,2017,13(12):215-217+219.

Newspapers in Chinese (Simplified)

Newspapers from China

© PressReader. All rights reserved.