基于Jaccard Distance的K-Means算法

本文主要是介绍如何以Jaccard Distance(JD)为基础，对Twitter的推文数据进行数据聚类。

理论基础

性能度量方式

  聚类性能度量级聚类 即聚类有效性指标（vlidity index），该指标可以分为两类：外部指标（external index），将聚类结果与某个“参考模型”比较；内部指标（internal index），直接分析聚类结果，不利用外部参考模型，以下给出两个内部指标度量方式：Dunn指数（Dunn Index，DI）以及误差平方和（Sum Of The Squared Errors，SSE）。

• DI值
  在介绍DI值计算前，先需要计算以下两个值: $$diam(C) = max_{1 \leq i \leq j \leq |C| } dist(x_i,x_j)$$ $$d_{min} (C_i,C_j) = min_{x_i \in C_i,x_j \in C_j} dist(x_i, x_j)$$ 其中$dist(.,.)$用于计算两个样本间的距离；$diam(C)$为簇$C$内样本的最远距离；$d_{min} (C_i,C_j)$为簇$C_i$与簇$C_j$最近样本间的距离。
  基于上述两个公式，DI值计算公式如下： $$DI = min_{1 \leq i \leq k} \left\{min_{j=i}\left(\frac {d_{min}(C_i,C_j)} {max{1 \leq l \leq k} diam(C_l)}\right)\right\}$$ 若要满足“簇间相似度低，簇内相似度高”，DI应越大越好
• SSE值
  SSE值计算公式如下: $$SSE = \sum^k_{i=1} \sum^{|C_i|}_{p \in C_i}dist(p,\mu_i)^2$$ SSE值判断聚类好坏的核心思想是：随着k参数的增大，样本的划分会更加精细，即“簇内相似度会增高”，因此，SSE值将随k参数递减。但当k参数小于真实聚类数时，k的增加会大幅度增加“簇内相似”程度，所以SSE值下降率会减小，图像上对应的曲线即是SSE值将会随着k的增加趋于平缓。综上，最合适的k值最可能为拐点处的k值。

距离计算方式

在聚类计算中，距离计算函数$dsit(.,.)$需要满足以下四条性质：

• 非负性：$ dist(\vec x_i, \vec x_j) \geq 0 $
• 同一性：$ dist(\vec x_i, \vec x_j) = 0 $ 当且仅当$ \vec x_i = \vec x_j $
• 对称性：$ dist(\vec x_i, \vec x_j) = dist(\vec x_j, \vec x_i) $
• 直递性：$ dist(\vec x_i, \vec x_j) \leq dist(\vec x_i, \vec x_k) + dist(\vec x_k, \vec x_j) $

Jaccard Distance 定义

Jaccard系数（Jaccard Coefficient，JC）定义如下：

$$J(A,B) = \frac {|A \bigcap B|}{|A \bigcup B|} = \frac {|A \bigcap B|}{|A| + |B| - |A \bigcap B|}$$

Jaccard距离定义如下：

$$d_J(A,B)=1-J(A,B)$$

其中A,B为两个任意的集合

可行性证明

由之前的JD定义可知，JD显然满足非负性、同一性、对称性这三种距离度量的基本性质，第四种性质“直递性”证明过程如下：

---

JD直递性证明：
假设有任意三个集合A,B,C，直递性要求有以下不等式成立：

$$d_J(A,B) \leq d_J(A,C)+d_J(C,B)$$

利用反证法证明上式，即假设有不等式：
假设：$d_J(A,B) > d_J(A,C)+d_J(C,B)$
成立，则根据假设不等式，A,B,C三个集合也满足如下不等式：

$$d_J(A,C) > d_J(A,B)+d_J(B,C)$$

对上述两个不等式进行迭代，则可以得到下式：

$$d_J(A,B) > d_J(A,C) + d_J(C,B) > d_J(A,B) + d_J(B,C) + d_J(C,B)$$

即有不等式：

$$0 > d_J(C,B) + d_J(B,C) = 2d_J(C,B)$$

显然上式不满足JD所具有的非负性条件，因此假设不成立，原不等式成立。
综合上述分析，JD直递性成立，满足四种距离计算的四种性质，JD可以作为距离度量方式

---

算法过程

原始K-Means算法可以分为两个步骤，即外层控制聚类迭代次数以及新旧聚类簇对比，即若聚类簇不再更新或达到最大迭代次数，则推出外层循环，程序结束；内层循环控制新聚类簇的计算。算法流程如图。


基于JD的K-Means算法与原始K-Means算法存在的差异为：

• 在基于JD的算法中，每轮迭代没有初始均值向量的再计算，则是直接计算新簇。
• 基于JD的K-Means算法没有样本向量化，而是直接使用样本集合的方式，以JD计算样本距离。

基于JD的K-Means算法计算新簇的流程如图

上图中完整的计算过程包括三层循环，整体逻辑为：遍历样本每一个元素，对每一个元素遍历原始聚类中的每一个簇，计算每一个簇与样本的距离，将与样本距离最小的簇作为该样本的新簇。具体相关变量意义见代码实现。

代码实现

#!/usr/bin/python
# -*- coding: UTF-8 -*-

"""基于jaccard 距离的迭代K-Means算法实现
"""

#   一些功能函数
import os

def CreateDir(FilePath):
    if not os.path.exists(FilePath):  # 目录不存在时，创建目录
        os.mkdir(FilePath)


def WriteFileLine(FilePath, DataList, style):
    try:
        f = open(FilePath, style)
        for DataLine in DataList:
            f.write(DataLine)
        f.close()
    except Exception as e:
        print('Create File ERROR' + str(e))


def ReadFile(FilePath):
    """读取预处理文件，返回值为Dict"""
    try:
        f = open(FilePath)
    except IOError:
        print("Can't find the file")
        return
    tweets = {}
    while True:
        line = f.readline()
        if not line:
            break
        try:
            ID = line.split('|')[0]
            Text = line.split('|')[1].strip('\n')
            tweets[ID] = set(Text.strip(' ').split(' '))
        except IndexError:
            continue
    return tweets


import copy
import random as Inrandom
from numpy import random
import time

class KMeans:
    def __init__(self, tweets, k, MaxIterations):
        """初始参数，tweets为推文，数据类型为Dict，键：tweetID，值：分词后的tweet，以集合的形式保存
        k为聚类簇数，MaxIterations为最大迭代次数'"""
        self.tweets = tweets
        self.k = k
        self.MaxIterations = MaxIterations

        self.seeds = []#随机选取的初始均值向量的ID
        self.Clusters = {}#用户存放聚类结果，字典之中的每一个键对应一簇
        self.RevClusters = {}#反向索引，字典之中键为tweets向量ID，值为簇序号
        self.JaccardMatrix = {}#设置为矩阵，用于存储每一对向量的jaccard距离
        self.LenTwitter = len(tweets)#推文的长度

        #运行初始均值向量随机选取函数
        self.InitializeChooseSeeds()
        #运行初始化聚类函数
        self.InitializeClusters()
        #运行计算Jaccard距离矩阵函数，修改：由于增加了LoadJaccardMatrix矩阵，所以不在__init__中直接运行，
        if self.LenTwitter <= 1500:
            self.InitializeJaccardMatrix()

    def JaccardDistance(self, SetA, SetB):
        """计算Jaccard距离函数，SetA 和 SetB为两个集合"""
        try:
            return 1 - float(len(SetA.intersection(SetB))) / float(len(SetA.union(SetB)))
        except TypeError:
            print('Error, SetA or SetB is none.')

    def InitializeChooseSeeds(self):
        """kmeans算法，选取初始均值向量，利用sample函数，从tweets键中随机选取k个ID"""
        self.seeds = Inrandom.sample(list(self.tweets.keys()), self.k)

    def InitializeClusters(self):
        """对聚类进行初始化"""
        #对反向索引进行初始化，由于当前没有进行聚类，反向索引置为-1
        for ID in self.tweets:
            self.RevClusters[ID] = -1

        #对聚类簇字典进行初始化，初始化使用随机选取的初始均值向量
        for i in range(self.k):
            self.Clusters[i] = set([self.seeds[i]]) #将tweet的ID以集合形式存储起来，i为簇序号也是字典键
            self.RevClusters[self.seeds[i]] = i #初始均值向量对应的簇序号已经确定，对反向索引进行赋值

    def InitializeJaccardMatrix(self):
        """计算出每一对tweet的Jaccard距离,动态规划思想，以空间换时间
        数据量过大时，可能会发生memoryerror的错误
        """
        #利用两层循环进行每一对ID的匹配
        k = 0 #调试变量
        try:
            for ID1 in self.tweets:
                self.JaccardMatrix[ID1] = {}
                for ID2 in self.tweets:
                    if ID2 not in self.JaccardMatrix:
                        self.JaccardMatrix[ID2] = {}
                    Distance = self.JaccardDistance(self.tweets[ID1], self.tweets[ID2])#计算出jaccard距离
                    self.JaccardMatrix[ID1][ID2] = Distance#距离赋值
                    self.JaccardMatrix[ID2][ID1] = Distance
                    k += 1
        except MemoryError:
            print(k)

    def LoadJaccardMatrix(self, FilePath):
        """导入已经计算好的Jaccard矩阵
        数据格式为：ID1 | ID2 | Value
        """
        try:
            f = open(FilePath, 'r')
        except IOError:
            print("Error! The file don't exist")
            return
        while True:
            line = f.readline()
            if not line:
                break
            try:
                #读出当前行的ID1 ID2 Distance
                ID1 = line.split('|')[0]
                ID2 = line.split('|')[1]
                Distance = float(line.split('|')[2])
                #若不存在啊ID1 ID2等相关键，则进行创建
                if ID1 not in self.JaccardMatrix:
                    self.JaccardMatrix[ID1] = {}
                if ID2 not in self.JaccardMatrix:
                    self.JaccardMatrix[ID2] = {}
                self.JaccardMatrix[ID1][ID2] = Distance  # 距离赋值
                self.JaccardMatrix[ID2][ID1] = Distance
            except IndexError:
                continue
        f.close()

    def CalcNewClusters(self):
        """计算新的聚类"""
        #初始化
        NewClusters = {}#新的聚类
        NewRevCluster = {}#新的反向索引
        for i in range(self.k):
            NewClusters[i] = set()#初始化为空集

        #遍历tweets中每一个元素，通过之前的聚类簇，构造出新的聚类
        k = 0   #调试变量
        for ID1 in self.tweets:
            MinDist = float("inf")  #将最小距离初始化为无穷小，保证存在出口
            MinCluster = self.RevClusters[ID1]

            #遍历每一个簇，计算出对于元素ID具有最小的簇数
            for j in self.Clusters:
            #for j in SampleResult:
                Dist = 0
                Count = float(0)
                #遍历当前簇之中的所有元素，计算出ID与其他元素的Jaccard之和
                #计算当前ID与当前簇的距离
                for ID2 in self.Clusters[j]:
                    if self.LenTwitter <= 1500:
                        Dist += self.JaccardMatrix[ID1][ID2]
                    else:
                        Dist += 1 - \
                                float(len(self.tweets[ID1].intersection(self.tweets[ID2]))) \
                                / float(len(self.tweets[ID1].union(self.tweets[ID2])))  # 计算当前选定元素ID与该类之中其他元素的距离和
                    #Dist += self.jaccardMatrix[ID1][ID2]
                    Count += 1 #计算当前类里元素的数量
                    k += 1  #调试变量
                if Count > 0:#若之前遍历的簇不为空，则进行距离判定
                    AvgDist = Dist / Count
                    if MinDist > AvgDist: #如果当前最小距离小于当前元素与该类的距离，则修改最小距离
                        MinDist = AvgDist
                        MinCluster = j
            NewClusters[MinCluster].add(ID1)#将当前元素添加到具有最小距离的类中
            NewRevCluster[ID1] = MinCluster#添加反向索引
        return NewClusters, NewRevCluster#返回新的聚类结果

    def Converge(self):
        """聚类顶层函数"""
        #初始化运行赋值
        NewClusters, NewRevCluster = self.CalcNewClusters()
        self.Clusters = copy.deepcopy(NewClusters)
        self.RevClusters = copy.deepcopy(NewRevCluster)

        #开始进行迭代，直至收敛或达到最大迭代次数
        Interations = 1
        while Interations < self.MaxIterations:#循环出口条件，小于最大迭代次数
            NewClusters, NewRevCluster = self.CalcNewClusters()
            Interations += 1
            if self.RevClusters != NewRevCluster: #当最新的迭代结果与之前结果不一致时，对聚类结果进行更新
                self.Clusters = copy.deepcopy(NewClusters)
                self.RevClusters = copy.deepcopy(NewRevCluster)
            else:#若结果收敛，则循环结束，聚类完成
                print(Interations)
                return Interations
        print('Get the Max!')
        return self.MaxIterations + 1

    def OneClusterSSE(self, Cluster):
        """计算每一簇聚类之中的误差平方"""
        OneClusterSSE = 0
        Len = len(Cluster)
        for ID1 in Cluster:
            S = 0
            for ID2 in Cluster:
                if self.LenTwitter <= 1500:
                    S += self.JaccardMatrix[ID1][ID2]
                else:
                    S += self.JaccardDistance(self.tweets[ID1], self.tweets[ID2])
            S /= Len
            #S = S*S
            OneClusterSSE += S*S

        return OneClusterSSE

    def CalculateSSE(self):
        """用于计算误差平方和，Sum Of The Squared Errors, SSE"""
        SSE = 0 #误差平方和
        for Ci in self.Clusters:
            SSE += self.OneClusterSSE(self.Clusters[Ci])
        return SSE

    def CalculateMinValue(self, Cluster1, Cluster2):
        MinValue = float("inf")#表示值为无穷大
        for ID1 in Cluster1:
            for ID2 in Cluster2:
                if self.LenTwitter <= 1500:
                    Dist = self.JaccardMatrix[ID1][ID2]
                else:
                    Dist = self.JaccardDistance(self.tweets[ID1], self.tweets[ID2])
                if MinValue > Dist:
                    MinValue = Dist
        return Dist

    def CalculateDiam(self,Cluster):
        """
        计算聚类之中元素的最大距离
        :param Cluster: 输入聚类
        :return: 返回最大值
        """
        Max = float('-inf')#令初始最大值为无限小，保证存在出口
        for ID1 in Cluster:
            for ID2 in Cluster:
                if self.LenTwitter <= 1500:
                    dist = self.JaccardMatrix[ID1][ID2]
                else:
                    dist = self.JaccardDistance(self.tweets[ID1], self.tweets[ID2])
                if dist > Max:
                    Max = dist

        return Max


    def CalculateDI(self):
        """
        计算DI指数
        :return:
        """
        #先计算分子
        DMin = float("inf")  # 表示值为无穷大
        for i in self.Clusters:
            for j in self.Clusters:
                if self.Clusters[i] is self.Clusters[j]:
                    continue
                else:
                    dist = self.CalculateMinValue(self.Clusters[i], self.Clusters[j])
                    if dist < DMin:
                        DMin = dist

        #在计算分母
        DMax = float('-inf')#令初始最大值为无限小，保证存在出口
        for l in self.Clusters:
            dist = self.CalculateDiam(self.Clusters[l])
            if dist > DMax:
                DMax = dist

        return DMin / DMax

    def PrintCluster(self):
        for i in self.Clusters:
            print('\n\nCluster ' + str(i))
            for ID in self.Clusters[i]:#遍历簇中每一个ID以及ID对应的tweet
                print(str(ID) + ' | ' + ' '.join(self.tweets[ID]) + '\n')

    def PrintJaccardMatrix(self):
        for ID in self.tweets:
            for ID2 in self.tweets:
                print(ID, ID2, self.JaccardMatrix[ID][ID2])

    def SaveClusterFile(self, FilePath):
        """以文件的形式保存聚类结果，FilePath为文件路径"""
        #若目录不存在，则创建路径
        CreateDir(FilePath)
        #遍历每一个簇
        for i in self.Clusters:
            TempCache = []#设置缓冲，存储当前簇中所有tweets
            for ID in self.Clusters[i]:#遍历簇中每一个ID以及ID对应的tweet
                #TempCache.append(str(ID) + '|' + self.tweets[ID] + '\n')    #还需要修改了这一部分东西
                TempCache.append(str(ID) + '|' + ' '.join(self.tweets[ID]) + '\n')  # 还需要修改了这一部分东西
            WriteFileLine(FilePath + 'C' + str(i) + '.txt', TempCache, 'w')

    def SaveJaccardMatrix(self, FilePath):
        """以文件的形式保存Jaccard矩阵计算结果，便于下次计算加速"""
        TempCache = []#设置缓冲
        #遍历矩阵之中的每一个元素
        for ID1 in self.tweets:
            for ID2 in self.tweets:
                TempCache.append(str(ID1) + '|' + str(ID2) + '|' + str(self.JaccardMatrix[ID1][ID2]) + '\n')
        #写入文件
        try:
            WriteFileLine(FilePath + 'JaccardMatrix.txt', TempCache, 'w')
        except IOError:
            print("Error! The file fail to create!")

def main():
    tweets = ReadFile('ClusterTest.txt')
    k = 27 #设置k参数
    MaxIterations = 50 #设置最大迭代次数
    kmeans = KMeans(tweets, 27, MaxIterations)
    Iterations = kmeans.Converge()  #方法返回最大迭代次数
    kmeans.SaveClusterFile("ClusterResult/")
    SSE = kmeans.CalculateSSE() #计算SSE
    DI = kmeans.CalculateDI() #计算DI
    print("MaxIterations: " + str(MaxIterations) + "\n" + "SSE: " + str(SSE) + '\n' + "DI: " + str(DI))


if __name__ == "__main__":
    time_start = time.time()  # time.time()为1970.1.1到当前时间的毫秒数
    main()
    time_end = time.time()  # time.time()为1970.1.1到当前时间的毫秒数
    print("the K-Means algorithm time:")
    print (str((time_end - time_start) / 60) + 'min')

实验结果

针对1231条，时间在2013年4-5月的Boston地区的推文，运行聚类算法，实验结果如下：

聚类结果中某一簇文件内容如下：

324772985196126208|dennis pen bombing oped lehane marathon
330771754412818433|confronted bombing bomber suspect lol alleged news texted fox marathon
326814744168235008|targeted racism yet balanced solidarity understands one marathon
327104038778859520|mile dont runwalk april thursday arizona ims forget honorary marathon
324887245570048000|bill running rodgers went champ beauty cant http time away take sportyou marathon
325132502140329984|caught bombing firefight offi police another suspect loose watertown one marathon
324190727141728256|take bombing terror marathon
58361655649779712|trying figure townim strugglin get got
324532692496551937|bombing keep calm marathon via carry
323884448380776448|gi know pm running comment sarah area info pas anyone schulz someone marathon
332630562231681026|pd bombing world suspect news abc fire didnt tell fbi marathon
333606268113649665|wake bombing come event wacky bay area even antiterror campaign marathon

上述簇文件基本是包含的Boston爆炸事件的相关内容，可以看出，聚簇效果还是较为理想的。

参考

[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