一种K-means聚类的初值选择方法

摘要

一种K-means聚类的初值选择方法，解决了K-means容易陷入局部极值、聚类结果不稳定、严重依赖初始聚类中心的问题。K-means聚类的初值通常是采用抽样的方法从数据集中获取。为了提高K-means的稳定性，需要为K-means提供质量更好的抽样。传统的解决方法计算复杂度偏高，而且总是拒绝最优的抽样结果。本发明充分考虑理想抽样的空间分布特点，采用样本之间距离的总体水平结合最小距离来评价随机抽样的质量。通过多次抽样，选择评价指标相对最优的抽样结果作为K-means的初值。新的K-means初值选择方法计算复杂度低，能够很容易捕捉到多次采样中随机出现的最好结果，从而为K-means提供相对更好的初值所需的数据对象，有效降低K-means陷入局部最优的概率，最终提高K-means聚类结果稳定性。

主权项

一种K‑means聚类的初值选择方法，其特征在于以下步骤：(1)选择k个初始聚类中心：从包含有n(n∈N)个数据对象的数据集X＝{x^t}ⁿ_t＝1中选择包含有k个数据对象的子集S＝{xⁱ}^k_i＝1作为K‑means聚类的初值；x^t表示数据集中第t个数据对象，k≥2；做M次规模为k的随机抽样，0<M且M∈N，组成M个样本集；每个样本集包含k个样本；(2)根据式(2‑1)计算每个样本集S_m对应的质量函数Q_m(d)，1≤m≤M，以此评价样本集S_m的质量；(3)按照式(2‑2)选择具有最大Q(d)值的样本集S_g，1≤g≤M，作为K‑means的初值；$Q\left(d\right)=\frac{2}{k(k-1)}\underset{i=1}{\overset{k}{\Sigma }}\underset{j=1}{\overset{k}{\Sigma }}\left(d_{ij}\right)\times \underset{i,j}{min}\left\{d_{ij}\right\},i\ne j---(2-1)$式(2‑1)中的Q(d)是样本集的质量评价函数，d_ij表示第i个和第j个样本之间的欧氏距离，d_ij＝||xⁱ‑x^j||²，1≤i≤k，1≤j≤k，i≠j，是计算样本间欧氏距离的期望，min_i,j{d_ij}是计算样本间的最小距离。$S_g=\arg \underset{m}{max}{Q}_m\left(d\right)---(2-2)$式(2‑2)中的S_g代表具有最大Q(d)值的样本集。