CN107578070A

CN107578070A - 基于邻域信息和平均差异度的K‑means初始聚类中心优选方法

Info

Publication number: CN107578070A
Application number: CN201710849046.4A
Authority: CN
Inventors: 吴仲城; 吴紫恒; 李芳�; 张俊; 罗健飞
Original assignee: Anhui Kemei Network Information Technology Co Ltd
Current assignee: Anhui Kemei Network Information Technology Co Ltd
Priority date: 2017-09-19
Filing date: 2017-09-19
Publication date: 2018-01-12

Abstract

本发明公开一种基于邻域信息和平均差异度的K‑means初始聚类中心优选方法，包括S1、输入n个对象的样本集X＝{X₁，X₂，…，X_i，…，X_n}，确定聚类数K，初始化当前确定的初始聚类中心个数k＝0；S2、形成距离矩阵D；S3、确定邻域半径值δ；S4、计算每个样本点X_i的δ邻域内样本数量N_i，形成矩阵N；S5、将N中δ邻域内样本数量最大N_i对应的样本点X_i作为第1个聚类中心C₁，k＝k+1，将N中相应N_i置0；S6、寻找N中δ邻域内样本数量最大N_j对应的样本点X_j，计算其与聚类中心{C₁，C₂，…，C_k}的距离，将N中相应N_j置0；S7、若X_j与聚类中心的距离均不小于平均差异度M，则k＝k+1，C_k+1＝X_j，否则返回S6；S8、若当前聚类中心个数k等于聚类类别数K，输出K个初始聚类中心，否则返回S6；S9、运用K‑均值聚类算法对整个样本集进行聚类，输出聚类结果。

Description

基于邻域信息和平均差异度的K-means初始聚类中心优选方法

技术领域

本发明涉及数据挖掘技术领域，特别涉及一种基于邻域信息和平均差异度的K-means初始聚类中心优选方法。

背景技术

聚类算法是一种无监督的分类算法，是指按照某种相似性将一组没有类别标识的对象分为若干类别，使得类间对象距离尽可能大，而类内对象距离尽量小，是系统建模和数据挖掘的基本方法之一，已经广泛应用于各种领域，如文本分类、图像识别等领域。

而K-均值聚类算法(K-means)是一种基于划分的动态聚类算法，由于其方法简单，已经成为当前最流行的聚类方法之一。传统的K-均值聚类算法的缺陷在于：一是，算法的聚类结果易受初始聚类中心影响，当初始聚类中心选择不合理时会出现一致性聚类和无法收敛的情况。二是，不能克服离群点对聚类结果带来的不利影响，从而导致聚类结果不稳定且正确率较低。

发明内容

本发明的目的在于提供一种基于邻域信息和平均差异度的K-means初始聚类中心优选方法，以提高K-均值聚类算法的正确率。

为实现以上目的，本发明采用的技术方案为：提供一种基于邻域信息和平均差异度的K-means初始聚类中心优选方法，包括：

S1、输入n个对象的样本集X＝{X₁，X₂，…，X_i，…，X_n}，X_i为m维向量，确定聚类类数K，初始化当前确定的初始聚类中心个数k＝0；

S2、计算样本集中对象两两之间的距离，并形成距离矩阵D；

S3、计算样本集总体平均差异度M，确定邻域半径值δ，

S4、基于距离矩阵D，计算每个样本点X_i的δ邻域内样本数量N_i，形成矩阵N；

S5、将N中δ邻域内样本数量最大N_i对应的样本点X_i作为第1个聚类中心C₁，令k＝k+1，并在矩阵N中将最大N_i置0；

S6、继续查找矩阵N中δ邻域内样本数量最大N_j对应的样本点X_j，，计算其与已有聚类中心{C₁，C₂，…，C_k}的距离，并在矩阵N中将最大N_j置0；

S7、若X_j与{C₁，C₂，…，C_k}中聚类中心的距离均不小于平均差异度M，则k＝k+1，C_k+1＝X_j，否则返回步骤S6；

S8、若当前聚类中心个数k等于聚类类别数K，则输出K个初始聚类中心C＝{C₁，C₂，…，C_K}，否则返回步骤S6；

S9、运用K-均值聚类算法对整个样本集进行聚类，输出聚类结果。

其中，所述的步骤S2中，样本集中对象两两之间的距离的计算过程具体为：

假设样本集中两对象分别为X_i、X_j，其中X_i＝{X_i1，X_i2，…，X_im}，X_j＝{X_j1，X_j2，…，X_jm}，则X_i与X_j的距离d_ij为：

其中，所述的步骤S3中，计算样本集总体平均差异度M的过程具体为：

计算样本X_i的平均差异度为：

计算样本集的总体平均差异度为：

与现有技术相比，本发明存在以下技术效果：本发明全面考虑了数据集的空间分布，得到的聚类中心更加合理和符合实际情况。本发明不仅有效克服了K-均值算法初始聚类中心选取的盲目性和随机性，明显提高了聚类结果的正确率和稳定性，迭代次数少，而且在一定程度上克服了离群点敏感性问题。

附图说明

下面结合附图，对本发明的具体实施方式进行详细描述：

图1是本发明中一种基于邻域信息和平均差异度的K-means初始聚类中心优选方法的流程示意图。

具体实施方式

为了更进一步说明本发明的特征，请参阅以下有关本发明的详细说明与附图。所附图仅供参考与说明之用，并非用来对本发明的保护范围加以限制。

如图1所示，本实施例公开了一种基于邻域信息和平均差异度的K-means初始聚类中心优选方法，包括如下步骤：

S2、计算样本集中对象两两之间的距离，并形成距离矩阵D；

S3、计算样本集总体平均差异度M，确定邻域半径值δ，

S6、继续查找矩阵N中δ邻域内样本数量最大N_j对应的样本点X_j，计算其与已有聚类中心{C₁，C₂，…，C_k}的距离，并在矩阵N中将最大N_j置0；

进一步地，步骤S2中，样本集中对象两两之间的距离的计算过程具体为：

进一步地，步骤S3中，计算样本集总体平均差异度M的过程具体为：

计算样本X_i的平均差异度为：

计算样本集的总体平均差异度为：

进一步地，在步骤S4中，邻域半径值δ的计算过程为：δ＝M/4。

进一步地，在步骤S3中，邻域定义为：

设<U,Δ>为一非空度量空间，其中U为对象的非空有限集，以X∈U为中心、以δ为半径的闭球，称为X中每个样本数据的δ邻域，定义为：

n(X)＝{y∈U|Δ(X，y)≤δ}；

其中：δ≥0，Δ为距离函数，采用欧式距离。

进一步地，距离矩阵D具体为：其中d_ij为X_i与X_j的距离。

进一步地，矩阵N具体为：其中N_i为样本点X_i的δ邻域内样本数量。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims

1.一种基于邻域信息和平均差异度的K-means初始聚类中心优选方法，其特征在于，包括：

S2、计算样本集中对象两两之间的距离，并形成距离矩阵D；

S3、计算样本集总体平均差异度M，确定邻域半径值δ，

S5、将矩阵N中δ邻域内样本数量最大N_i对应的样本点X_i作为第1个聚类中心C₁，令k＝k+1，并在矩阵N中将最大N_i置0；

2.如权利要求1所述的方法，其特征在于，所述的步骤S2中，样本集中对象两两之间的距离的计算过程具体为：

3.如权利要求2所述的方法，其特征在于，所述的步骤S3中，计算样本集总体平均差异度M的过程具体为：

计算样本X_i的平均差异度为：

<mrow> <msub> <mi>d</mi> <mi>i</mi> </msub> <mo>=</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>j</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>d</mi> <mrow> <mi>i</mi> <mi>j</mi> </mrow> </msub> <mo>/</mo> <mi>n</mi> <mo>;</mo> </mrow>

计算样本集的总体平均差异度为：

<mrow> <mi>M</mi> <mo>=</mo> <munderover> <mi>&Sigma;</mi> <mrow> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mi>n</mi> </munderover> <msub> <mi>d</mi> <mi>i</mi> </msub> <mo>/</mo> <mi>n</mi> <mo>.</mo> </mrow>