sentence2api的层次聚类

实验室需要做一个对比试验,关于api的使用推荐。我这边需要用Lucene+聚类的方法进行实验。Lucene是用elasticSearch搜索引擎保存的,对于一个sentence我们在搜索引擎中找出得分最高的那几个usage,然后进行聚类求出最好的一个。接下来就总结一下聚类。

起初打算用python现成的库,了解了下python下的工具包scipy.cluster,它是scipy下的一个做聚类的package, 共包含了两类聚类方法:

  1. 矢量量化(scipy.cluster.vq):支持vector quantization 和 k-means 聚类方法
  2. 层次聚类(scipy.cluster.hierarchy):支持hierarchical clustering 和 agglomerative clustering(凝聚聚类)

聚类方法一般可以分为层次聚类与非层次聚类两种。其中层次聚类算法又可以分为合并法与分解法;同样非层次聚类算法也可以分为多种,常用的有K-means算法。笔者这篇博客主要用的是Agglomerative Hierarchical Clustering, 也就是合成聚类算法(自下而上),也叫做凝聚式层次聚类。

层次聚类分为凝聚式层次聚类和分裂式层次聚类。

凝聚式层次聚类,就是在初始阶段将每一个点都视为一个簇,之后每一次合并两个最接近的簇,当然对于接近程度的定义则需要指定簇的邻近准则。

分裂式层次聚类,就是在初始阶段将所有的点视为一个簇,之后每次分裂出一个簇,直到最后剩下单个点的簇为止。

我们在这篇文章里主要使用的是层次聚类hierarchical clustering,它主要包括如下的几种:

SingleLinkage:又叫做 nearest-neighbor ,就是取两个类中距离最近的两个样本的距离作为这两个集合的距离,也就是说,最近两个样本之间的距离越小,这两个类之间的相似度就越大。容易造成一种叫做Chaining 的效果,两个 cluster 明明从“大局”上离得比较远,但是由于其中个别的点距离比较近就被合并了,并且这样合并之后Chaining 效应会进一步扩大,最后会得到比较松散的 cluster.

CompleteLinkage:这个则完全是 Single Linkage 的反面极端,取两个集合中距离最远的两个点的距离作为两个集合的距离。其效果也是刚好相反的,限制非常大,两个cluster 即使已经很接近了,但是只要有不配合的点存在,就顽固到底,老死不相合并,也是不太好的办法。这两种相似度的定义方法的共同问题就是指考虑了某个有特点的数据,而没有考虑类内数据的整体特点。

AverageLinkage:这种方法就是把两个集合中的点两两的距离全部放在一起求一个平均值,相对也能得到合适一点的结果。

原理方面差不多就是这回事,然后我也在python下试了,不过由于之前都是用java开发的,再把之前写的在python写一遍有点费事,就索性自己在java实现了层次聚类算法。

考虑到我使用的这篇paper采取的是CompleteLinkage的聚类方法,也就是两个类中所有点的最大值作为聚类出发点。我们需要对多个api的sentence进行层次聚类,我们定义两个cluster的距离是其中的两两元素中距离最大的,这里可以看到我们用的是CompleteLinkage的方法。而两个句子的相似度的定义如下,最终用距离的是sqrt(1-s1*s1),因为两个句子越相似其距离应该要小,另外提一下这个函数是参考的是这篇paper,之前我自己用的是1-s1,其实差不多就是把后面阈值的阈值稍微改了下。
《sentence2api的层次聚类》

就是用两个句子的相同的部分除以总的部分,也就是交的个数除以并的个数。

关于层次聚类停止的边界条件的问题,paper里是先设定一个处置然后不断无脑迭代判断效果的做法,我经过了几次尝试大概设置在0.9999(也就是有一点点相似就合并,因为我们的usage有控制结构,而且比较长,所以相似度普遍比较低,如果设置成0.9那基本都是一个usage一类,起不到任何效果)

这里在具体使用中有几个需要注意的地方,首先层次聚类在众多聚类算法中时间复杂度是比较高的,尤其是相比于k-means。所以当如果我遇到一个长度超过1000单词的usage时,我是直接选择跳过的,因为要计算两个句子的距离这个复杂度就达到了O(L^2),效率很低。

项目源代码:https://github.com/ZhaoYi1031/api-cluster

参考paper: Mining Succinct and High-CoverageAPI UsagePatternsfrom SourceCode

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注