基于空间平移的K-Means初始簇心选取

K-Means Initial Cluster Center Selection Based on Spatial Translation

摘要: K-means聚类算法因其算法简单、计算效率高，在机器学习、数据挖掘等多个领域得到了广泛应用。然而，传统K-means算法在初始簇心的选取上存在随机性，这可能导致聚类结果的不稳定性。为了解决这一问题，本研究提出了一种基于空间平移的初始簇心选取算法。该算法首先将包含所有样本集的最小空间通过单位空间以一定步长遍历，在单位空间内统计样本点的密度，以此降低计算量。通过逐一选出密度最高的个点作为初始簇心，从而提高了K-means算法的聚类性能。在UCI的12种数据集上进行的实验表明，与传统的K-means、K-means++等算法相比，改进的算法在迭代次数上有所降低，聚类准确率得到了显著提高。

Abstract: K-means clustering algorithm is an important content in the field of machine learning and is widely used because of its simplicity and efficiency. In order to solve the problem that the initial cluster center selection of traditional K-means algorithm is random, an initial cluster center selection algorithm based on space segmentation is proposed. The minimum space containing all sample sets is divided to calculate the density, and the initial cluster centers with the highest density are selected one by one. The selected cluster centers are replaced by random initial cluster centers for K-means clustering. Twelve datasets were tested separately at UCI. The experimental results show that compared with traditional K-means, K-means++ and other algorithms, the improved algorithm has lower iteration times and higher clustering accuracy.

1. 引言

聚类试图将数据集的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”[1]。Han [2]等人按不同性质将聚类划分为五类：基于划分、基于分层、基于密度、基于网格以及基于模型的聚类。聚类分析作为数据挖掘和机器学习中的重要技术，广泛应用于医疗[3]、能源[4]、交通[5]、金融[6]、图像处理[7]。

K-means作为最简单高效的聚类算法之一，是学者MacQueen [8]在1967年提出的，虽然K-means聚类算法简单高效，但也存在着一些不足，如k值需要事先确定、算法对离群值较为敏感、聚类效果对初始簇心较为敏感。针对这些问题，许多学者也提出了相应的改进。

对于k值的确定，Rezaee [9]等人提出$k\in \left[2,\sqrt{n}\right]$ ，其中n为样本个数；成卫青[10]等人根据平方误差(SSE)和k值的关系提出一种自适应确定k值的算法；王建仁[11]等人针对手肘法在确定k值的过程中存在的“肘点”位置不明确问题，提出了一种改进的k值选择算法ET-SSE算法，提升了寻找k值的效率；Kristina [12]等人提出了一种新颖的无监督K均值(UK均值)聚类算法，可以自动找到最佳的聚类数量，而无须进行任何初始化和参数选择；何选森[13]等人定义了新的聚类有效性评价指标，k值就是使得此指标达到最小的整数值。

在筛除离群点方面，唐东凯[14]等人根据LOF [15] (Local Outlier Factor)算法计算每个点的可达密度来判断样本点是否为离群点；朱利[16]等人设计了一种用于连接数据点间的信息数据结构，且开发了一个新的离群因子计算公式，实现了对簇类数量的自适应评估，从而能够高效地识别出离群点。刘凤[17]等人通过局部密度筛选离群点，剔除离群点后进行聚类。

为了获得更科学的初始簇心，张玉芳[18]等人事先设定簇数$k^{\prime }>k$ ，选择合适的样本集大小，采取J次取样并进行K-means聚类，将平方误差SSE最小的聚类结果的簇心作为初始聚类簇心并聚类，再将最近的两个类合并直到簇个数为k；袁方[19]等人先设置一个类簇所含样本点个数的阈值，将位置最近的一些点归为一类直到该簇的样本点个数达到阈值，再从这些点之外的样本点重复此操作直至选出k个类，将这k个簇的质心作为初始簇心；赖玉霞[20]等人先选出密度较大的样本点，在这些点中选出相互相距最远的k个初始簇心；汪中[21]等人先计算各点密度，选出密度最大的点作为第一个初始点将其周围的点剔除，再选出剩下点中密度最大的点作为下一个初始点，直至找出k个初始点；陈光平[22]等人首先将数据集最远的两个点作为初始簇心，将其余点归为最近的簇，在簇最多的点里继续找相距最远的两个点作为新的初始簇心，直到找到k个初始簇心；谢娟英[23]等人首先定义样本点的方差，在k个不同区域选出方差最小的样本点作为初始簇心；郭永坤[24]等人给出点到簇的距离定义和类簇内样本点个数阈值$\alpha$ ，将部分样本点聚成k个簇，将每个簇的簇心作为初始簇心。

大多数选取初始簇心的文献都是基于密度来选取的，虽然这些文献对K-means初始簇心的优化有所改进，但却忽略了统计各样本点密度时的庞大计算量。针对此问题，本文提出一种划分空间的算法SK-means算法(Space-divided-based K-means)，该算法通过划分空间来降低统计样本点密度时的计算量；另一方面针对文献[25]提出的算法中密度最大样本点不止一个的问题，提出了局部平均距离，选出更为紧凑的样本点，使得聚类效果更优。实验表明，改进的算法降低了迭代次数，提高了聚类结果准确率。

2. K-Means聚类算法

K-means算法是一种基于划分的聚类算法，通过在迭代中更新簇及簇心将数据集划分到若干个不相交的簇。该算法原理为：给定类簇数k，随机选取k个样本点作为初始簇心，并将样本点划分到距离最近的簇，在一次划分完毕后更新簇心，继续重复划分和更新簇心直至簇心不再变化或达到最大迭代次数[26]。

定义1 [1]设$X=\left\{x_1,x_2,\cdots ,x_n\right\}$ 为一组维度为d的数据集、$x_i=\left(x_{i1},x_{i2},\cdots ,x_{id}\right)$ 为第i个样本、k为聚类簇数，记$C_1^t,C_2^t,\cdots ,C_k^t$ 为第t次迭代聚类结果。对任意$x_i,x_j\in X$ ，$x_i,x_j$ 间的欧氏距离为

$dist\left(x_i,x_j\right)=\sqrt{{\displaystyle \sum _{l=1}^d{\left(x_{il}-x_{jl}\right)}^2}}$ ，(1)

第t次迭代簇$C_i^t$ 的簇中心为

${\mu }_i^t=\frac{1}{\left|C_i^t\right|}{\displaystyle \sum _{x\in C_i^t}x}$ ，$i=1,2,\cdots ,k$ ，(2)

其中$\left|C_i^t\right|$ 为簇$C_i^t$ 的基数，即$C_i^t$ 中所含样本点的个数。第t次迭代聚类结果的平方误差为

$\text{SSE}={\displaystyle \sum _{i=1}^k{\displaystyle \sum _{x_j\in C_i^t}{\left(x_j-{\mu }_i\right)}^2}}$ (3)

簇心依据距离度量将一个簇内的样本点平均化，作为一个簇中心；平方误差是评价聚类好坏的最基本的指标，它直观地反映了样本点与其所属簇心之间的距离关系。传统K-means聚类算法具体步骤如下：

算法1 [27]传统K-means聚类算法

输入：数据集$X=\left\{x_1,x_2,\cdots ,x_n\right\}$ ，类簇数k。 输出：聚类的k个簇。

输入：数据集$X=\left\{x_1,x_2,\cdots ,x_n\right\}$ ，类簇数k。 输出：聚类的k个簇。

步骤1 $t=0$ ，随机选取k个样本点${\mu }_1^t,{\mu }_2^t,\cdots ,{\mu }_k^t$ 作为初始簇心，$C_i^t=\left\{{\mu }_i^t\right\}$ ，$i=1,2,\cdots ,0$ ； 步骤2 根据公式(1)计算每个点到簇心的距离，将其划分到距离最近的簇心所在的簇，即$\forall x\in X-\left\{{\mu }_1^t,{\mu }_2^t,\cdots ,{\mu }_k^t\right\}$ ，令$i=\arg \underset{1\le i\le k}{\min }dis\left(x,{\mu }_i^t\right)$ ，$C_i^t:=C_i^t\cup \left\{x\right\}$ ； 步骤3 $t:=t+1$ ，根据公式(2)更新簇心${\mu }_i^t=\frac{1}{\left|C_i^t\right|}{\displaystyle \sum _{x\in C_i^t}x}$ ，$i=1,2,\cdots ,k$ ，$C_i^t=\varnothing$ ； 步骤4根据公式(1)计算每个点到簇心的距离，将其划分到距离最近的簇心所在的簇，即$\forall x\in X$ ，令$i=\arg \underset{1\le i\le k}{\min }dis\left(x,{\mu }_i^t\right)$ ，$C_i^t:=C_i^t\cup \left\{x\right\}$ ； 步骤5 重复步骤3、步骤4直至簇心不再发生变化，即${\mu }_i^t={\mu }_i^{t-1}$ 时，停止迭代。

3. 基于空间平移的K-Means初始点选取算法

由于初始点选取的随机性，若选取到离群点作为初始簇心，则初始簇心距离最终聚类结果簇心较远，容易陷入局部最优解[28]。文献[20]指出聚类中心应位于簇内密度较高的位置，而根据文献[23] [24] [29]的理论推导和实验分析可知，聚类中心若设置在样本密度较大的区域，则能够显著提高聚类的准确性。以往基于密度选取初始点的文献在计算样本点密度时考虑了所有样本点，为了避免大量计算，快速找到密度较大的样本点，提出了SK-means初始点选取算法。

3.1. SK-Means算法思想

SK-means算法思想是：首先构造包含所有样本点的最小d维多面体，记该多面体体积为$V_S$ ，用一个体积为$V_S/k$ (k为类簇数)的d维正多面体从包含所有样本点的最小d维多面体的一角出发，以一定步长遍历上述d维多面体，在各个较小的正多面体中找出k个密度最大的初始点作为初始簇心。

3.1.1. 第一步：构造棱空间

设$X=\left\{x_1,x_2,\cdots ,x_n\right\}$ 为一组d维数据集，样本$x_i=\left(x_{i1},x_{i2},\cdots ,x_{id}\right)$ ，记${\alpha }_i=\inf \left\{x_{1i},x_{2i},\cdots ,x_{ni}\right\}$ ，${\beta }_i=\sup \left\{x_{1i},x_{2i},\cdots ,x_{ni}\right\}$ 。称包含数据集X中所有样本的最小d维多面体

$S=\left[{\alpha }_1,{\beta }_1\right]\times \left[{\alpha }_2,{\beta }_2\right]\times \cdots \times \left[{\alpha }_d,{\beta }_d\right]=\underset{i=1}{\overset{d}{\times }}\left[{\alpha }_i,{\beta }_i\right]$ (4)

为容纳空间，则容纳空间体积$V_S={\displaystyle \prod _{i=1}^d\left({\beta }_i-{\alpha }_i\right)}$ 。

定义2 设$X=\left\{x_1,x_2,\cdots ,x_n\right\}$ 为一组维度为d的数据集，数据集X的容纳空间$S=\underset{i=1}{\overset{d}{\times }}\left[{\alpha }_i,{\beta }_i\right]$ ，称$S\left(l_1,l_2,\cdots ,l_d\right)=\underset{i=1}{\overset{d}{\times }}\left[{\alpha }_i+l_{i}b,{\alpha }_i+l_{i}b+a\right)$ 是索引指标为$\left(l_1,l_2,\cdots ,l_d\right)$ 的棱空间，其中棱长$a=\sqrt[d]{V_S/k}$ ，k为类簇数，步长$b=\frac{a}{2}$ ，$l_i\in \left\{0,1,2,\cdots ,m_i\right\}$ ，$m_i=\left[\frac{{\beta }_i-{\alpha }_i}{b}\right]$ 。

例1 考虑一组2维数据集$X=\left\{x_1,x_2,\cdots ,x_{16}\right\}$ (见表1)，类簇数$k=4$ 。显然${\alpha }_1={\alpha }_2=0$ ，${\beta }_1={\beta }_2=10$ ，容纳空间$S=\left[0,10\right]\times \left[0,10\right]$ 且$V_S=100$ ，边长$a=\sqrt{V_S/k}=5$ ，步长$b=2.5$ ，所有的棱空间见表2。

Table 1. The 2-dimensional data set

表1. 2维数据集

样本点	样本点	样本点	样本点
$x_1=\left(0,1\right)$	$x_5=\left(9,7\right)$	$x_9=\left(4,9\right)$	$x_{13}=\left(5,0\right)$
$x_2=\left(0,2\right)$	$x_6=\left(8,8\right)$	$x_{10}=\left(5,9\right)$	$x_{14}=\left(6,0\right)$
$x_3=\left(1,1\right)$	$x_7=\left(10,8\right)$	$x_{11}=\left(5,10\right)$	$x_{15}=\left(5,1\right)$
$x_4=\left(1,2\right)$	$x_8=\left(9,9\right)$	$x_{12}=\left(6,10\right)$	$x_{16}=\left(6,1\right)$

Table 2. All edge space

表2. 所有棱空间

棱空间	棱空间	棱空间
$S\left(0,0\right)=\left[0,5\right)\times \left[0,5\right)$	$S\left(1,4\right)=\left[2.5,7.5\right)\times \left[10,15\right)$	$S\left(3,3\right)=\left[7.5,12.5\right)\times \left[7.5,12.5\right)$
$S\left(0,1\right)=\left[0,5\right)\times \left[2.5,7.5\right)$	$S\left(2,0\right)=\left[5,10\right)\times \left[0,5\right)$	$S\left(3,4\right)=\left[7.5,12.5\right)\times \left[10,15\right)$
$S\left(0,2\right)=\left[0,5\right)\times \left[5,10\right)$	$S\left(2,1\right)=\left[5,10\right)\times \left[2.5,7.5\right)$	$S\left(4,0\right)=\left[10,15\right)\times \left[0,5\right)$
$S\left(0,3\right)=\left[0,5\right)\times \left[7.5,12.5\right)$	$S\left(2,2\right)=\left[5,10\right)\times \left[5,10\right)$	$S\left(4,1\right)=\left[10,15\right)\times \left[2.5,7.5\right)$
$S\left(0,4\right)=\left[0,5\right)\times \left[10,15\right)$	$S\left(2,3\right)=\left[5,10\right)\times \left[7.5,12.5\right)$	$S\left(4,2\right)=\left[10,15\right)\times \left[5,10\right)$
$S\left(1,0\right)=\left[2.5,7.5\right)\times \left[0,5\right)$	$S\left(2,4\right)=\left[5,10\right)\times \left[10,15\right)$	$S\left(4,3\right)=\left[10,15\right)\times \left[7.5,12.5\right)$
$S\left(1,1\right)=\left[2.5,7.5\right)\times \left[2.5,7.5\right)$	$S\left(3,0\right)=\left[7.5,12.5\right)\times \left[0,5\right)$	$S\left(4,4\right)=\left[10,15\right)\times \left[10,15\right)$
$S\left(1,2\right)=\left[2.5,7.5\right)\times \left[5,10\right)$	$S\left(3,1\right)=\left[7.5,12.5\right)\times \left[2.5,7.5\right)$
$S\left(1,3\right)=\left[2.5,7.5\right)\times \left[7.5,12.5\right)$	$S\left(3,2\right)=\left[7.5,12.5\right)\times \left[5,10\right)$

3.1.2. 第二步：计算棱空间中样本点密度

由于各棱空间的位置明确，易得各棱空间所包含的样本点及包含的样本点数量。记$S\left(l_1,l_2,\cdots ,l_d\right)$ 包含的样本点数量为$n\left(l_1,l_2,\cdots ,l_d\right)$ ，包含样本点数量最多的棱空间的索引指标集合为$M_p=\arg \underset{\begin{array}{c}{l}_i\in \left\{0,1,2,\cdots ,m_i\right\}\\ i=1,2,\cdots ,d\end{array}}{\max }\left(n\left(l_1,l_2,\cdots ,l_d\right)\right)$ ，显然$\left|M_p\right|\ge 1$ 。只需找到索引指标在$M_p$ 的棱空间中密度最大的样本点即可，样本点密度定义为一定范围内样本点的个数与数据集大小的比值。

定义3 设$X=\left\{x_1,x_2,\cdots ,x_n\right\}$ 为一组d维的数据集，样本$x_i=\left(x_{i1},x_{i2},\cdots ,x_{id}\right)\in S\left(\gamma \right)$ ，$n\left(\gamma \right)$ 为$S\left(\gamma \right)$ 的样本数量，$M_p$ 为包含样本点数量最多的棱空间的索引指标集合，阈值半径为

$R=\frac{1}{\left|M_p\right|}{\displaystyle \sum _{\gamma \in M_p}\frac{1}{C_{n\left(\gamma \right)}^2}{\displaystyle \sum _{\begin{array}{c}{x}_i,x_j\in S\left(\gamma \right)\\ 0\le i<j\le n\left(\gamma \right)\end{array}}dist\left(x_i,x_j\right)}}$ ，(5)

样本$x_i$ 在$S\left(\gamma \right)$ 中的R邻域样本集为

$U\left(x_i,R|S\left(\gamma \right)\right)=\left\{x_j\in S\left(\gamma \right)|dist\left(x_i,x_j\right)\le R\right\}$ ，(6)

样本$x_i$ 在$S\left(\gamma \right)$ 中的密度为

$\rho \left(x_i|S\left(\gamma \right)\right)=\frac{\left|U\left(x_i,R|S\left(\gamma \right)\right)\right|}{\left|X\right|}$ 。(7)

3.1.3. 第三步：确定初始簇心

在得到包含样本点数量最多的棱空间后，需要在这些棱空间中找到密度最大的点。设$\gamma$ 为棱空间索引指标，记$S\left(\gamma \right)$ 中密度最大的样本点集合为$M_a\left(\gamma \right)=\arg \underset{x_i\in S\left(\gamma \right)}{\max }\left(\rho \left(x_i|S\left(\gamma \right)\right)\right)$ ，则$\left|M_a\left(\gamma \right)\right|\ge 1$ 。考虑到$\left|M_p\right|\ge 1$ ，$\left|M_a\left(\gamma \right)\right|\ge 1$ ，即密度最大的样本点可能不唯一。需要进一步细化算法，挑选出更为紧凑的样本点。

定义4 设$X=\left\{x_1,x_2,\cdots ,x_n\right\}$ 为一组维度为d的数据集，$M_p$ 为包含样本点数量最多的棱空间的索引指标集合，$U\left(x,R|\gamma \right)$ 为x在$S\left(\gamma \right)$ 中的R邻域样本集。$\forall \gamma \in M_p$ ，$\forall x\in S\left(\gamma \right)$ ，x在$S\left(\gamma \right)$ 中的紧凑度为

$com\left(x|\gamma \right)=\frac{{\displaystyle \sum _{x_i\in U\left(x,R|\gamma \right)\backslash \left\{x\right\}}dist\left(x_i,x\right)}}{\left|U\left(x,R|\gamma \right)\right|-1}$ (8)

紧凑度定义为样本周围的点到自身距离的平均值，紧凑度越小，反映了周围点到该点的距离越小，该点越紧凑。记${\mu }_i^0=\arg \underset{\begin{array}{c}x\in M_a\left(\gamma \right)\\ \gamma \in M_p\end{array}}{\min }com\left(x|\gamma \right)$ 为挑选出的第i个初始簇心，为了使得第$i+1$ 个初始簇心不在已经挑选出的簇心周围，需要对样本点进行剔除。在挑选出样本点后，将$U\left({\mu }_i^0,R|S\left(\gamma \right)\right)$ 从X中剔除，从$X\backslash U\left({\mu }_i^0,R|S\left(\gamma \right)\right)$ 中重复统计棱空间样本点数量、计算样本点密度、挑选初始点及剔除样本点，直至选出k个初始簇心。

3.2. 具体算法步骤

SK-means算法避开了计算所有样本点两两之间的距离，只在个别棱空间计算部分样本点的密度。在降低计算量的同时，又细化了算法，解决了密度最大的样本点同时存在只能随机挑选的问题。下面给出SK-means初始簇心选取算法的具体步骤。在已经挑选出的簇心周围，需要对样本点进行剔除。在挑选出样本点后，将$U\left({\mu }_i^0,R|S\left(\gamma \right)\right)$ 从X中剔除，从$X\backslash U\left({\mu }_i^0,R|S\left(\gamma \right)\right)$ 中重复统计棱空间样本点数量、计算样本点密度、挑选初始点及剔除样本点，直至选出k个初始簇心。

算法2 SK-means初始簇心选取算法

输入：数据集$X=\left\{x_1,x_2,\cdots ,x_n\right\}$ ，簇个数k。 输出：k个初始簇心。

步骤1 构造棱空间； 步骤2 $\forall x\in X$ ，判断x属于哪些棱空间； 步骤3 统计各空间样本点个数$n\left(l_1,l_2,\cdots ,l_d\right)$ ，$l_i\in \left\{0,1,2,\cdots ,m_i\right\}$ ，$i=1,2,\cdots ,d$ 。找到包含样本点个数最多的棱空间的索引指标集合$M_p$ ； 步骤4 $j=1$ ，$\forall \gamma \in M_p$ ，计算$S\left(\gamma \right)$ 中样本点的密度，找到$S\left(\gamma \right)$ 中密度最大的样本点$M_a\left(\gamma \right)$ ，$\forall x\in M_a\left(\gamma \right)$ ，找出使得$md\left(x|\gamma \right)$ 最小的x以及所属的棱空间的索引指标$\gamma$ ，初始簇心${\mu }_j^0=\arg \underset{\begin{array}{c}x\in M_a\left(\gamma \right)\\ \gamma \in M_p\end{array}}{\min }md\left(x|\gamma \right)$ ，$j:=j+1$ ； 步骤5 在X中剔除$U\left({\mu }_j^0,R|S\left(\gamma \right)\right)$ 中的样本点，$X:=X\backslash U\left({\mu }_j^0,R|S\left(\gamma \right)\right)$ ； 步骤6 重复步骤3-5直至选出k个初始簇心。

4. 实验结果及分析

4.1. 实验背景

实验设备的处理器是12th Gen Intel(R) Core(TM) i5-12450H 2.00 GHz，内存为16.0 GB，Microsoft Windows11的操作系统，系统类型为64位操作系统，基于x64的处理器，算法编写和编译是在Python3.12.2环境下实现的。

为了验证本文算法对降低聚类迭代次数的有效性，本文选取了UCI数据库中的Iris等十二个数据集来进行实验分析。这些数据集的维度从几维到十几维不等，数据量也比较广泛，从而反映出SK-means算法有一定的适用性。具体数据集及基本信息见表3。

Table 3. Basic data set information

表3. 数据集基本信息

数据集	数据集大小	数据维度	数据类别
Balance	625	4	3
Tae	151	5	3
Haberman	306	3	2
Iris	150	4	3
Led	500	7	10
Seeds	210	7	3
Titanic	2201	3	2
Wine	178	13	3
Heart	270	13	2
Appendicitis	106	7	2
Phoneme	5405	5	2
Hayes-Roth	160	4	3

4.2. 聚类评价指标

为了验证所提算法在聚类分析上的有效性，采用三个指标来评价算法，分别为准确率(ACC)、平方误差(SSE)、轮廓指数[30] (SI)。准确率是指预测正确的样本个数与总个数的比值，其值位于[0, 1]，值越大则表示聚类效果越接近真实聚类结果。平方误差为各点到所属簇簇心的距离平方和，值越小反映出簇越集中。若某个样本$x_i\in C_j$ ，则$x_i$ 的轮廓系数为

$S\left(x_i\right)=\frac{b\left(x_i\right)-a\left(x_i\right)}{\max \left\{a\left(x_i\right),b\left(x_i\right)\right\}}$ (9)

其中$a\left(x_i\right)=\frac{1}{\left|C_j\right|-1}{\displaystyle \sum _{x_l\in C_j,l\ne i}dist\left(x_i,x_l\right)}$ ，$b\left(x_i\right)=\underset{t\ne j}{\min }\frac{1}{\left|C_t\right|}{\displaystyle \sum _{x_l\in C_t}dist\left(x_i,x_l\right)}$ 。则整个聚类结果的轮廓指数为

$\text{SI}=\frac{1}{n}{\displaystyle \sum _{i=1}^{n}s\left(x_i\right)}$ (10)

轮廓指数的取值范围为$\left[-1,1\right]$ ，取值越大聚类结果越紧凑，聚类效果越好。

4.3. 实验结果

为了验证SK-means算法在降低迭代次数和提高聚类准确性方面是否有效，本文将SK-means算法与传统K-means、K-means++聚类算法，与文献[24]提出的算法在不同方面进行对比。由于传统的K-means和K-means++对初始簇心的选取都具有一定随机性，造成了迭代次数与准确率不稳定，于是本文对每个数据集都做了100次实验，取平均值作为传统K-means和K-means++的代表。实验结果见表3。与文献[24]对比的实验结果见于表4。考虑到表格容量，表格内数值仅保留了前几位。在各方面实数值的比较中，效果较好的算法所对应的数值已在表格内加粗。

Table 4. Results of accuracy and number of iterations of each dataset

表4. 各数据集准确率和迭代次数结果

算法	Iris			Wine			Tae
	准确率	SSE	迭代次数	准确率	SSE	迭代次数	准确率	SSE	迭代次数
K-means	0.813	89.272	7.25	0.682	2.43e+7	7.84	0.337	17,315	6.41
K-means++	0.889	78.943	6.39	0.663	2.48e+7	6.58	0.318	17,325	7.77
SK-means	0.893	78.940	5	0.702	2.37e+7	9	0.364	17,666	10
算法	Heart			Haberman			Seeds
	准确率	SSE	迭代次数	准确率	SSE	迭代次数	准确率	SSE	迭代次数
K-means	0.500	5.82e+6	8.55	0.448	31,330	8.74	0.890	588.04	8.99
K-means++	0.469	5.82e+6	8.38	0.520	31,455	7.46	0.893	587.85	6.08
SK-means	0.590	5.82e+6	6	0.520	30,533	10	0.895	587.31	5
算法	Titanic			Phoneme			Appendicitis
	准确率	SSE	迭代次数	准确率	SSE	迭代次数	准确率	SSE	迭代次数
K-means	0.709	4273.5	3.04	0.667	12,947	12.25	0.804	17.522	7.38
K-means++	0.732	4172.7	2.71	0.666	12,916	12.3	0.807	17.530	6.53
SK-means	0.776	4059.6	2	0.668	12,838	12	0.830	17.482	5
算法	Hayes-Roth			LED			New-Thyroid
	准确率	SSE	迭代次数	准确率	SSE	迭代次数	准确率	SSE	迭代次数
K-means	0.332	358.67	7.43	0.540	271.97	6.41	0.801	28,968	10.03
K-means++	0.386	356.88	7.27	0.643	240.84	4.77	0.771	28,942	9.71
SK-means	0.450	360.04	5	0.742	222.27	4	0.860	28,917	8

Table 5. Accuracy improves quantitative data

表5. 准确率提升量化数据

数据集	Iris	Wine	Tae	Heart
K-means	9.84%	2.93%	8.01%	18.00%
K-means++	0.45%	5.88%	14.47%	25.80%
数据集	Haberman	Seeds	Titanic	Phoneme
K-means	16.07%	0.56%	9.45%	0.15%
K-means++	0	0.22%	6.01%	0.30%
数据集	Appendicitis	Hayes-Roth	LED	New-Thyroid
K-means	3.23%	35.54%	37.41%	7.37%
K-means++	2.85%	16.58%	15.40%	11.54%

Table 6. Each algorithm evaluates indexes in different data clustering classes

表6. 各算法在不同数据集聚类评价指标

UCI数据集	K-means		K-means++		文献[24]		SK-means
	SI	ACC	SI	ACC	SI	ACC	SI	ACC
Iris	0.546	0.825	0.552	0.888	0.549	0.887	0.553	0.893
Wine	0.567	0.669	0.565	0.631	0.571	0.702	0.571	0.702
Hayes-Roth	0.198	0.442	0.204	0.450	0.571	0.432	0.201	0.450
Heart	0.365	0.500	0.365	0.469	0.377	0.589	0.367	0.590
Tae	0.313	0.337	0.312	0.318	0.328	0.358	0.293	0.364
Haberman	0.395	0.447	0.395	0.520	0.393	0.500	0.399	0.520

表4为SK-means算法与传统K-means、K-means++在准确率、SSE及迭代次数的比较。对比发现SK-means算法在大部分数据集有着较好的聚类结果。SK-means算法在所有数据集的准确率相较于传统K-means和K-means++均有提升、SSE和迭代次数除在极个别数据集略有增加，其余均有降低。表6为SK-means算法在6个数据集与K-means、K-means++及文献[24]的比较。对比发现SK-means的准确率在6个数据集均最优，而轮廓系数较文献[24]效果稍差。

4.4. 聚类可视化

为了更直观的展示SK-means算法的聚类效果，将Iris数据集前2维分别用K-means、K-means++聚类，得到效果如图1。

Figure 1. The clustering effect of three algorithms in Iris data set

图1. Iris数据集三种算法的聚类效果

图中相同的颜色的样本点为一类，叉号为最终聚类簇心。可以看到K-means算法将右下角都聚为一类，左上角分为两类。Iris数据集真实标签为三类均分，每个簇各有50个样本点。就数量而言，K-means算法聚类效果不佳。而K-means++和SK-means算法效果相似，但SK-means算法迭代次数更少且准确率更高。

4.5. 结果分析

由表4可知，与传统K-means聚类算法和K-means++算法相比，改进的算法准确率均有相应的提升，且在大多数数据集提高明显。特别是LED数据集，相较于传统K-means聚类算法和K-means++算法准确率分别提高了15.4%、37.4%。在降低SSE和迭代次数方面，SK-means算法在大部分数据集都有起到一定的作用。但在Wine等数据集本文在提升准确率的情况下，改进的算法迭代次数与K-means++算法相比略有逊色。分析发现这些数据集某些维度数据范围过大，造成每个点R范围内样本点个数都比较少，不易比较哪个点更适合作为初始簇心。于是该算法对于样本点稀疏的数据集可能会造成迭代次数增加。由表4可知SK-means算法在大多数数据集轮廓指数高于K-means、K-means++，且准确率相较于文献[24]提出的算法均有提高。

5. 结束语

随着大数据时代的到来，传统的K-means聚类算法已经不能满足数据挖掘的需求，为了提高聚类效果，本研究在传统K-means聚类算法的基础上，提出了一种数据预处理的算法，通过对高密度差异数据集的处理，成功降低了K-means的迭代次数，提高了聚类的准确率。实验结果表明，SK-means算法排除了传统K-means聚类算法在选取初始簇心的随机性，科学选取初始簇心，降低了陷入局部最优的可能性。通过对比准确率，SK-means算法有着较好的聚类效果。尽管本研究主要关注了初始聚类中心和样本数据密度差异对算法性能的影响，但仍有许多方面值得进一步研究和探索。譬如在SK-means算法步骤4中，剔除样本点的范围可以根据数据集的稀疏程度来选取，以期获得更快的迭代和更优的聚类效果；可以排除掉离群点对内群点单独做聚类，聚类稳定后再将其归为最近的簇。未来的工作将重点关注这两方面以及优化算法的收敛性和复杂度，以期发现更优的方式提高算法的效率和应用范围。