Categories

漫谈 Clustering (2): k-medoids

Samoyed

Samoyed

本文是“漫谈 Clustering 系列”中的第 2 篇,参见本系列的其他文章

上一次我们了解了一个最基本的 clustering 办法 k-means ,这次要说的 k-medoids 算法,其实从名字上就可以看出来,和 k-means 肯定是非常相似的。事实也确实如此,k-medoids 可以算是 k-means 的一个变种。

k-medoids 和 k-means 不一样的地方在于中心点的选取,在 k-means 中,我们将中心点取为当前 cluster 中所有数据点的平均值:

$\displaystyle \mu_k=\frac{\sum_n r_{nk}x_n}{\sum_n r_{nk}}$

Rough Collie

Rough Collie

并且我们已经证明在固定了各个数据点的 assignment 的情况下,这样选取的中心点能够把目标函数 $J$ 最小化。然而在 k-medoids 中,我们将中心点的选取限制在当前 cluster 所包含的数据点的集合中。换句话说,在 k-medoids 算法中,我们将从当前 cluster 中选取这样一个点——它到其他所有(当前 cluster 中的)点的距离之和最小——作为中心点。k-means 和 k-medoids 之间的差异就类似于一个数据样本的均值 (mean) 和中位数 (median) 之间的差异:前者的取值范围可以是连续空间中的任意值,而后者只能在给样本给定的那些点里面选。那么,这样做的好处是什么呢?
一个最直接的理由就是 k-means 对数据的要求太高了,它使用欧氏距离描述数据点之间的差异 (dissimilarity) ,从而可以直接通过求均值来计算中心点。这要求数据点处在一个欧氏空间之中。

然而并不是所有的数据都能满足这样的要求,对于数值类型的特征,比如身高,可以很自然地用这样的方式来处理,但是类别 (categorical) 类型的特征就不行了。举一个简单的例子,如果我现在要对犬进行聚类,并且希望直接在所有犬组成的空间中进行,k-means 就无能为力了,因为欧氏距离 $\|x_i-x_j\|^2$ 在这里不能用了:一只 Samoyed 减去一只 Rough Collie 然后在平方一下?天知道那是什么!再加上一只 German Shepherd Dog 然后求一下平均值?根本没法算,k-means 在这里寸步难行!

在 k-medoids 中,我们把原来的目标函数 $J$ 中的欧氏距离改为一个任意的 dissimilarity measure 函数 $\mathcal{V}$:

\[ \displaystyle\tilde{J} = \sum_{n=1}^N\sum_{k=1}^K r_{nk}\mathcal{V}(x_n,\mu_k) \]

最常见的方式是构造一个 dissimilarity matrix $\mathbf{D}$ 来代表 $\mathcal{V}$,其中的元素 $\mathbf{D}_{ij}$ 表示第 $i$ 只狗和第 $j$ 只狗之间的差异程度,例如,两只 Samoyed 之间的差异可以设为 0 ,一只 German Shepherd Dog 和一只 Rough Collie 之间的差异是 0.7,和一只 Miniature Schnauzer 之间的差异是 1 ,等等。

除此之外,由于中心点是在已有的数据点里面选取的,因此相对于 k-means 来说,不容易受到那些由于误差之类的原因产生的 Outlier 的影响,更加 robust 一些。

扯了这么多,还是直接来看看 k-medoids 的效果好了,由于 k-medoids 对数据的要求比 k-means 要低,所以 k-means 能处理的情况自然 k-medoids 也能处理,为了能先睹为快,我们偷一下懒,直接在上一篇文章中的 k-means 代码的基础上稍作一点修改,还用同样的例子。将代码的 45 到 47 行改成下面这样:

45
46
47
48
49
50
        for j in range(k):
            idx_j = (labels == j).nonzero()
            distj = distmat(X[idx_j], X[idx_j])
            distsum = ml.sum(distj, axis=1)
            icenter = distsum.argmin()
            centers[j] = X[idx_j[0][icenter]]

可以看到 k-medoids 在这个例子上也能得到很好的结果:

iter_06

而且,同 k-means 一样,运气不好的时候也会陷入局部最优解中:

iter_08

如果仔细看上面那段代码的话,就会发现,从 k-means 变到 k-medoids ,时间复杂度陡然增加了许多:在 k-means 中只要求一个平均值 $O(N)$ 即可,而在 k-medoids 中则需要枚举每个点,并求出它到所有其他点的距离之和,复杂度为 $O(N^2)$ 。

看完了直观的例子,让我们再来看一个稍微实际一点的例子好了:Document Clustering ——那个永恒不变的主题,不过我们这里要做的聚类并不是针对文档的主题,而是针对文档的语言。实验数据是从 Europarl 下载的包含 Danish、German、Greek、English、Spanish、Finnish、French、Italian、Dutch、Portuguese 和 Swedish 这些语言的文本数据集。

N-gram-based text categorization 这篇 paper 中描述了一种计算由不同语言写成的文档的相似度的方法。一个(以字符为单位的) N-gram 就相当于长度为 N 的一系列连续子串。例如,由 hello 产生的 3-gram 为:hel、ell 和 llo ,有时候还会在划分 N-gram 之前在开头和末尾加上空格(这里用下划线表示):_he、hel、ell、llo、lo_ 和 o__ 。按照 Zipf’s law

The nth most common word in a human language text occurs with a frequency inversely proportional to n.

这里我们用 N-gram 来代替 word 。这样,我们从一个文档中可以得到一个 N-gram 的频率分布,按照频率排序一下,只保留频率最高的前 k 个(比如,300)N-gram,我们把叫做一个“Profile”。正常情况下,某一种语言(至少是西方国家的那些类英语的语言)写成的文档,不论主题或长短,通常得出来的 Profile 都差不多,亦即按照出现的频率排序所得到的各个 N-gram 的序号不会变化太大。这是非常好的一个性质:通常我们只要各个语言选取一篇(比较正常的,也不需要很长)文档构建出一个 Profile ,在拿到一篇未知文档的时候,只要和各个 Profile 比较一下,差异最小的那个 Profile 所对应的语言就可以认定是这篇未知文档的语言了——准确率很高,更可贵的是,所需要的训练数据非常少而且容易获得,训练出来的模型也是非常小的。

不过,我们这里且撇开分类(Classification)的问题,回到聚类(Clustering)上,按照前面的说法,在 k-medoids 聚类中,只需要定义好两个东西之间的距离(或者 dissimilarity )就可以了,对于两个 Profile ,它们之间的 dissimilarity 可以很自然地定义为对应的 N-gram 的序号之差的绝对值,在 Python 中用下面这样一个类来表示:

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Profile(object):
    def __init__(self, path, N=3, psize=400):
        self.N = N
        self.psize = psize
        self.build_profile(path)
 
    sep = re.compile(r'\W+')
    def build_profile(self, path):
        grams = {}
        with open(path) as inf:
            for line in inf:
                for tok in self.sep.split(line):
                    for n in range(self.N):
self.feed_ngram(grams, tok, n+1)
        self.create_profile(grams.items())
 
    def create_profile(self, grams):
        # keep only the top most psize items
        grams.sort(key=itemgetter(1), reverse=True)
        grams = grams[:self.psize]
 
        self.profile = dict()
        for i in range(len(grams)):
            self.profile[grams[i][0]] = i
 
    def __getitem__(self, key):
        idx = self.profile.get(key)
        if idx is None:
            return len(self.profile)
        return idx
 
    def dissimilarity(self, o):
        dis = 0
        for tok in self.profile.keys():
            dis += abs(self[tok]-o[tok])
        for tok in o.profile.keys():
            dis += abs(self[tok]-o[tok])
        return dis
 
    def feed_ngram(self, grams, tok, n):
        if n != 0:
            tok = '_' + tok
        tok = tok + '_' * (n-1)
        for i in range(len(tok)-n+1):
            gram = tok[i:i+n]
            grams.setdefault(gram, 0)
            grams[gram] += 1

europarl 数据集共有 11 种语言的文档,每种语言包括大约 600 多个文档。我为这七千多个文档建立了 Profile 并构造出一个 7038×7038 的 dissimilarity matrix ,最后在这上面用 k-medoids 进行聚类。构造 dissimilarity matrix 的过程很慢,在我这里花了将近 10 个小时。相比之下,k-medoids 的过程在内存允许的情况下,采用向量化的方法来做实际上还是很快的,并且通常只要数次迭代就能收敛了。实际的 k-medoids 实现可以在 mltk 中找到,今后如果有时间的话,我会陆续地把一些相关的比较通用的代码放到那里面。

最后,然我们来看看聚类的结果,由于聚类和分类不同,只是得到一些 cluster ,而并不知道这些 cluster 应该被打上什么标签,或者说,在这个问题里,包含了哪种语言的文档。由于我们的目的是衡量聚类算法的 performance ,因此直接假定这一步能实现最优的对应关系,将每个 cluster 对应到一种语言上去。一种办法是枚举所有可能的情况并选出最优解,另外,对于这样的问题,我们还可以用 Hungarian algorithm 来求解。

我们这里有 11 种语言,全排列有 11! = 39916800 种情况, 对于每一种排列,我们需要遍历一次 label list ,并数出真正的 label (语言)与聚类得出的结果相同的文档的个数,再除以总的文档个数,得到 accuracy 。假设每次遍历并求出 accuracy 只需要 1 毫秒的时间的话,总共也需要 11 个小时才能得到结果。看上去好像也不是特别恐怖,不过相比起来,用 Hungarian algorithm 的话,我们可以几乎瞬间得到结果。由于文章的篇幅已经很长了,就不在这里介绍具体的算法了,感兴趣的同学可以参考 Wikipedia ,这里我直接使用了一个现有的 Python 实现

虽然这个实验非常折腾,不过最后的结果其实就是一个数字:accuracy ——在我这里达到了 88.97% ,证明 k-medoids 聚类和 N-gram Profile 识别语言这两种方法都是挺不错的。最后,如果有感兴趣的同学,代码可以从这里下载。需要最新版的 scipymunkres.pymltk 以及 Python 2.6 。

44 comments to 漫谈 Clustering (2): k-medoids

  • marshall

    很久没搞这个了,记得还有一些不需要K的算法吧

  • @marshall
    有,比如 hierarchical clustering 就不需要 k ,但是从最终的结果里获取信息的话,你还是需要直接或间接地取一个 k 值啊。

  • roby

    你好,请问你有K中心点算法的MATLAB源码吗,如果有的话可以发到我的邮箱吗,劳驾,多谢~~

  • Bill

    你好,最近正在研究k-medoids聚类算法。请指教一般都是怎样提高其聚类效果,有无具体的实验支撑。觉得你比较内行,能把你的思路或已有的实验报告什么的发给我研究研究吗?
    邮箱:monkey228@163.com

  • @Bill
    你好,不好意思,我做过的 k-medoids 调研数据和结果全都写在这里了,其他是没有做过专门调研的。

  • Bill

    多谢楼主了,学习了:)

  • Liang Bai

    k-medoids 虽然有时比kmeans好,但是它不一定收敛,也就是说它破坏了kmeans的数学特性和算法的安全性去换取精度,其实我觉得这样的改进没有多大意思,我只是一家之言,呵呵

  • Xiaoyan

    你好,我没搞明白的是,对document集合进行聚类时,到底是在document-by-word矩阵上运行kmeans算法,(document-by-word矩阵中每行代表一个document,行元素是word在这个document中的TFIDF值)?还是在document-to-document similarity matrix上运行kmeans算法?两者有什么区别?哪个是正确的呢?

  • Xiaoyan

    为什么要在正确二字上面加引号呢?你的意思是在document-to-document similarity matrix上也可以运行kmeans算法?

    • 不能直接运行,但是可以从 similarity 矩阵中推演出其他信息,再构造出适合 kmeans 的条件来,比如 spectral clustering 就是这样的。

  • […] K-medoids 类似,Spectral Clustering 只需要数据之间的相似度矩阵就可以了,而不必像 […]

  • […] Gaussian Distribution 中生成出来的。实际上,我们在 K-means 和 K-medoids 两篇文章中用到的那个例子就是由三个 Gaussian […]

  • […] 的集合)按照 N-gram 分割(N-gram 在 讲 K-medoids 的那篇文章中介绍过)为 ,形成一个最初的辞典,而模型 的参数 […]

  • teloon

    写得很不错~
    一个小疑问:博主提到的k-means的局限性,即欧式空间,但其实可以扩展距离的定义,如博主提到的狗之间的差异度,把他作为扩展的“欧氏距离“

    • 如果不是在欧氏空间,就不能用欧氏空间中的运算了,比如如果你重新定义了距离,求平均值就不一定能“相加除以 n”,除非你再定义“加法”,但是这是 nontrivial 的。

  • zhu2006021423

    你好,我现在得到了相似性矩阵,可以直接采用k中心算法聚类吗? 另外提到的谱聚类算法,也同样可以直接对相似性矩阵进行聚类得到结果? 关于相似性矩阵的聚类我也尝试过apcluster算法,但是数据集不是很到,得到的聚类效果很差。

  • kelvin

    你的倒数第二段,也就是聚类完了以后,给每一类贴标签那个地方不太明白.
    首先,要贴标签的话必须要有明确知道是哪种语言的文档,这里需要11份.对这11分当然也要做n-gram,然后将聚类结果的每一类中心的profile与这11分的作比较就可以贴上标签了吧.
    不太明白你说的关于全排列的那一段

    • 需要全排列是因为并不知道哪个对应哪个。

      你这种做法相当于对 11 个中心进行了分类,当然也可以算一种可行的做法,不过不知道效果如何,首先仅看中心的 profile 并不能完全代表所有文档,其次只选 11 份标准文档出来每个类型只有一个文档,做出来的一个相当于 1NN 的分类起其分类精度估计也不一定好。

      • kelvin

        恩,我一开始理解有误,现在知道你是怎么做的了.
        不过就还有有个问题:在聚类结果贴标签的时候,你应该是有11份明确已知是哪种语言的文档了.这个时候,我们可以拿英语的那片文档跟我们聚类结果中的11类进行逐个比较,如果跟第一类中的文档匹配的accuracy大,则认为第一类是英语,依次下去就可以贴上标签了吧.这样应该比全排列要好一些吧. 而且个人觉得就算这11份文档不明确知道是哪种语言也无所谓,像上面一样,accuracy大则为这个类贴上文档一的标签.

        • 我前面说的那样啊,你这种做法相当于用 11 个文档本身作为分类起来进行分类,不失为一种可行的办法,但是另一方面实际上是无法保证这 11 份文档足够典型,能够(被)识别出是哪种语言的啊。

  • 请问一下博主,这句话是啥意思: “因此直接假定这一步能实现最优的对应关系,将每个 cluster 对应到一种语言上去。”,是说每个document有真实的label可以用来测试么?
    另外,Hungarian algorithm 那里我怎么感觉是带权匹配。。谢谢 😀

    • 那句话的意思是我们目前只关心将不同的类别分开,而不关心各个类别应该 assign 的标签是什么——这又是另一个问题了,所以这里我们可以直接用暴力枚举直接取最优的解。

      Hungarian 算法的细节我也不是很清楚,所以没法回答你的问题了。

  • […] Gaussian Distribution 中生成出来的。实际上,我们在 K-means 和 K-medoids 两篇文章中用到的那个例子就是由三个 Gaussian […]

  • […] K-medoids 算法,我在以前的 blog 中也介绍过。简单地来说就是 K-means […]

  • 给小狗分类还是可以用k-means吧,因为算的是feature values之间的距离啊~

  • […] K-medoids 算法,我在以前的 blog 中也介绍过。简单地来说就是 K-means […]

  • […] 和 K-medoids 类似,Spectral Clustering 只需要数据之间的相似度矩阵就可以了,而不必像 K-means 那样要求数据必须是 N 维欧氏空间中的向量。 […]

  • Typhoon

    看了有收获就顶一个,谢谢楼主分享。

  • KK

    樓主,
    categorical data你確定是用medoid嗎?
    我怎麼覺得是K-mode呢?

  • ml

    能否提供程序运行需要的文件呢,比如docs.txt,非常感谢!!

    • systolic

      我也想要docs.txt
      到europarl数据上看了一下,并行语料有很多,不知道用哪个,做些什么预处理

  • Plex

    >k-means 和 k-medoids 之间的差异就类似于一个数据样本的均值 (mean) 和中位数 (median) 之间的差异:前者的取值范围可以是连续空间中的任意值,而后者只能在给样本给定的那些点里面选。

    这里有点不严谨吧,中位数可能不是样本给定的点,比如有偶数个样本,且中间两个样本点不同时,中位数是二者的均值

    当然,这里的比喻还是很贴切的,只是顺便说一下而已:)

  • LEELA

    我们可以应用数字电路作为输入于K medoid clustering.if所以告诉我简单

  • J0ker

    学长你好,我有几个问题想私下请教您,不知道是否可以给您发个邮件?

  • caicaifish

    大神,你好。这个文本聚类的例子,为啥不能用k-means了?我觉得可以。
    你文章说,dissimilarity是对应N-gram序号之差的绝对值,既然每个文档用的是钱300个N-gram来就相当于一篇文章用300维的向量来表示,然后计算中心点(也是300维)。这样子用k-means就可以了。不知道我这样子理解有问题吗?
    另外,你最后的聚类accuracy评估,是相当于计算11!种情况下的文本划分的正确性,然后取最大的就是最后的你得到的88.97%?我很想测试下效果,但是数据集貌似已经变了,变得更大了。
    期待收到你的回复。谢谢

    • 你好,可以用 kmeans 啊,取决于你的数据用什么样的 representation,以及你用什么样的距离/相似度函数来衡量数据之间的差异。如果你把数据表示成向量并用欧氏距离之类的常见的距离,当然也是可以直接用 kmeans 的。关于 accuracy,结果上来说确实是那个意思。

  • caicaifish2013

    您好,我还有点不太理解后面的accuracy。如果accuracy 是我之前描述的那样,那这样子感觉是为了聚类而聚类。因为都已经有一些文本的类别号。或者说,您本来的意思就是为了用来验证这样子聚类效果的好坏。

  • […] 的集合)按照 N-gram 分割(N-gram 在 讲 K-medoids 的那篇文章中介绍过)为 ,形成一个最初的辞典,而模型 的参数 […]