Tag Archives: 聚类

CS224N(2.26)Coreference Resolution

今天介绍的内容是指代消解(Coreference Resolution)。指代(mention)是指句子中出现的名词、名词短语、代词等,指代消解就是把指向同一实体(entity)的指代聚类到一起的过程。比如下面的两句话,蓝色的词就是很多的指代,需要找出来哪些指代是指向同一个实体。比如Barack Obama、his、He都是指奥巴马。

下面的例子是比较简单的情况,事实上,在真实的语言中,情况更加复杂,比如有些指代可能表示多个实体。比如“他们”,可能同时指代了“小明”和“小王”,这种指代对于现在的NLP模型来说比较难,暂时不考虑。

Continue reading

马尔可夫聚类算法

马尔可夫聚类算法(The Markov Cluster Algorithm, MCL)是一种快速可扩展的基于图的聚类算法。它的基本思想为:在一个稀疏图G中,如果某个区域A是稠密的(是一个聚类),则在A中随机游走k步,还在A内的概率很大,也就是说,A内的k步路径(k-length path)很多。所以我们可以在图中随机游走k步,如果某个区域连通的概率很大,则该区域是一个聚类。随机游走的下一步只和当前所处节点有关,也就是说这是一个马尔可夫的随机游走过程。

我们用一个例子来演示马尔可夫聚类算法的过程。

mcl-1 Continue reading