基于Jaccard Distance的K-Means++算法

发表于 | 分类于 ， |
字数统计: 937

本文的内容以基于Jaccard Distance的K-Means算法为基础，将原始K-Means算法随机选择初始向量的方法修改为K-Means++的概率选择方法，同样本文K-Means++算法的距离计算同样是基于Jaccard Distance距离的。

理论基础

  原始K-Means算法通过贪心策略，迭代化求解最小平方化误差（K-Means算法的求解过程实际上就是求解最小平方化误差）。但是由于其初始均值向量的选择具有随机性、不确定性，其算法不够稳定，有可能会造成迭代次数较多，算法时间复杂度较高。针对K-Means算法的问题，David Arthur等人提出了K-Means++算法.

  K-Means++算法与K-Means算法的主要差异在于初始均值的选取。选取初始均值向量算法如下：

  1. 随机从 $ D = \left[\vec x_1, \vec x_2,…,\vec x_m \right] $ 选取一个元素作为初始向量 $ \vec \mu_1 $.

  2. 按概率分布 $ \frac {D(\vec x)^2} {\sum_{\vec x \in D} D(\vec x)^2} $，从样本集D中随机选取新的初始均值向量$ \vec \mu_i $.

  3. 重复步骤2，直到选出k个初始均值向量。

  上述算法中的$ D(x) $表示样本与均值向量集合的最短距离。

  由上述算法可以看出，K-Means++算法的核心思想是：在初始均值向量选择时，尽可能选择相距较远的点。直观上理解即相聚越远的点位于不同簇的可能性越高，后续迭代优化的次数显然越少。

算法过程

  由于在基于Jaccard Distaance的K-Means中没有均值向量的计算，因此需要对原始K-Means++算法提出的初始向量选择方式进行改造。其算法流程如图。

  图中Seeds表示初始均值向量集合；DistanceMatrix存储所有样本与初始向量集合的最短距离；SumDist为DistanceMatrix的距离和；Seed为遍历Seeds集合指针；Probability为根据DistanceMatrix和SumDist计算出的每个样本的概率。
  图中算法流程为先将初始均值向量集合Seeds初始化为空集，再随机从样本集中选择一个样本作为初始均值向量加入到Seeds中，在整个流程中，仅有第一个初始均值向量是随机选择的。之后进入到计算新初始均值向量的循环中，每次循环都需要对DistanceMatrix、SumDist进行初始化，Seed指向集合Seeds中的第一个值。该循环的出口条件为Seeds集合元素个数大于k，即生成了k个初始均值向量时。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

def KMeansPPChooseSeeds(self):
    """K-Means++算法，用于选择初始均值向量"""
    #1a. Take one center c1, chosen uniformly at random from Tweets.（the english annotations are from D.Arthur paper ）
    seed = random.choice(list(self.tweets.keys()))

    #Take a new center ci, choosing x from X with probability D(x)^2 / Sum(D(xi)^2)
    seeds = set([seed])
    while len(seeds) < self.k:
        DistanceMatrix = {}
        SumSqrDist = 0
        for seed in seeds:
            #V1 = set(self.tweets[seed].strip(' ').split(' '))
            for ID in self.tweets:
                if ID == seed:
                    continue
                #V2 = set(self.tweets[ID].strip(' ').split(' '))
                Dist = self.JaccardDistance(self.tweets[seed], self.tweets[ID])
                if ID not in DistanceMatrix or Dist < DistanceMatrix[ID]:
                    DistanceMatrix[ID] = Dist
        ProbabilityDict = {}
        for ID in DistanceMatrix:
            SumSqrDist += DistanceMatrix[ID] * DistanceMatrix[ID]
        for ID in DistanceMatrix:
            ProbabilityDict[ID] = DistanceMatrix[ID] * DistanceMatrix[ID] / SumSqrDist ##可以优化

实验结果

实验结果与上一篇（基于Jaccard Distance的K-Means算法）基本相同。

参考

[1] Arthur D, Vassilvitskii S. k-means++:the advantages of careful seeding[C] Eighteenth Acm-Siam Symposium on Discrete Algorithms, New Orleans, Louisiana. Society for Industrial and Applied Mathematics, 2007:1027-1035.
[2] https://github.com/findkim/Jaccard-K-Means

文中代码链接： https://github.com/zhaohuang123/sentiment-analysis/tree/master/blog/K-Means%2B%2B