一种基于图划分的无监督汉语指代消解算法

指代消解是自然语言处理领域中的一个重要问题。针对当前中文指代标注训练语料非常缺乏的现状,本文提出一种无监督聚类算法实现对名词短语的指代消解。引入图对名词短语的指代消解问题进行建模,将指代消解问题转化为图划分问题,并引入一个有效的模块函数实现对图的自动划分,使得指代消解过程并不是孤立地对每一对名词短语分别进行共指决策,而是充分考虑了多个待消解项之间的相关性,并且避免了阈值选择问题。通过在ACE中文语料上的人称代词消解和名词短语消解实验结果表明,该算法是一种有效可行的无监督指代消解算法。     

无监督中文名词短语指代消解研究

为减小语料库对中文指代消解的影响,设计一个基于无监督聚类的中文名词短语指代消解平台并给出其预处理、特征选择及聚类过程。采用3种评测工具对中文新闻语料进行评测,在自动情况下,平均F值为59.43%。实验结果表明,该中文指代消解平台能够较好地解决中文缺少语料库的问题。     

语料对中文名词短语指代消解影响研究

指代是自然语言中一种常见的语言现象,对简化语言,减少冗余有很大的作用。指代消解是用计算机找出这些指代现象的一个过程。近几年英文指代消解研究取得了很大的成就,然而,中文指代消解研究目前还较少,一方面是由于中文自然语言处理的研究起步较晚,相关的知识较少,另外一方面就是中文相关的语料库较少,目前已知的仅有ACE2005, OntoNotes等。为了探讨语料库对中文名词短语指代消解的影响,该文实现了一个基于有监督学习方法的中文名词短语指代消解平台和一个基于无监督聚类方法的中文名词短语指代消解平台,在此平台的基础上从语料库的数量和质量两个方面来探讨语料对中文名词短语指代消解的影响。     

基于有监督关联聚类的中文共指消解

共指消解是文本信息处理中的一个重要问题.提出了一种有监督的关联聚类算法以实现对中文实体提及的共指消解.首先将共指消解过程看成图的关联聚类问题,从全局的角度实现对共指等价类的划分,而不是孤立地对每一对名词短语分别进行共指决策;然后给出了关联聚类的推导算法;最后设计了一种基于梯度下降的特征参数学习算法,使得训练出的特征参数能够较好拟合关联聚类的目标.在ACE中文语料上的实验结果显示,该算法优于传统的"分类一聚类"共指消解学习算法.     

指代消解中距离特征的研究

指代消解是自然语言处理中的一个重要问题,包括专有名词、普通名词、代词的指代识别。本文实现了一个基于机器学习的英语名词短语的指代消解平台,通过对原始语料进行命名实体识别和名词短语识别等一系列预处理,选取了多个有效特征及其组合,分别采用最大熵和SVM两种分类算法对名词短语进行分类,在此基础上着重研究了距离特征对指代消解的影响。在传统的基于机器学习的指代消解研究方法中,候选词和先行语的距离被定义为特征,而没有考虑距离在生成训练样例中的作用,本文通过把候选词和先行语的距离作为一个特征加入机器学习算法和作为限制条件用于指代关系候选实例的产生两方面进行详细研究,在MUC-6基准语料库上评测,实验结果表明,合理利用距离特征能够大大提高系统的性能。最终,本文采用最大熵和SVM两种分类器在测试集上分别获得了67.5和68.7的F1值,该结果优于同类型的其他系统。     

基于最大熵模型的英文名词短语指代消解

提出了一种新颖的基于语料库的英文名词短语指代消解算法,该算法不仅能解决传统的代词和名词／名词短语间的指代问题,还能解决名词短语间的指代问题。同时,利用最大熵模型,可以有效地综合各种互不相关的特征,算法在MUC7公开测试语料上F值达到了60．2％,极为接近文献记载的该语料库上F值的最优结果61．8％。     

基于关键名词短语聚类的中文搜索结果聚类

目前,搜索结果聚类方法大多数采用基于文档的方法,不能生成有意义的聚类标签。为了解决这个问题,提出一种基于关键名词短语聚类的中文搜索结果聚类方法,该方法将名词短语、相关搜索词作为候选聚类标签,利用C-Value算法、IDF值筛选标签,然后使用Chameleon算法将标签聚类,最后将搜索结果划分到最相关的聚类簇。实验证明,该方法把关键名词短语和相关搜索词作为聚类标签,有效地提高了标签的描述性,降低了聚类算法的时间复杂度。     

基于SVM的中文名词短语指代消解研究

指代消解是自然语言处理领域中要研究的关键问题之一。在自然语言中,为了使语言简明,减少冗余,往往对同一意思的单词、句子或某一事件用不同的单词来代替。相对于人而言,计算机理解这些指代现象就比较困难,因此近年来关于指代消解的研究越来越多。由于中文指代消解研究起步较晚,因此关于中文名词短语指代消解的研究还比较少,大多研究是关于英文指代消解的。给出了一个基于SVM的中文名词短语指代消解平台并详细介绍了整个实现过程,语料库采用OntoNotes 3.0的中文新闻语料。利用3种评测算法对系统性能进行了评测,结果表明本系统是一个比较好的中文指代消解平台。     

基于深度学习的维吾尔语名词短语指代消解

针对维吾尔语名词短语指代现象,提出了一种利用栈式自编码深度学习算法进行基于语义特征的指代消解方法.通过对维吾尔语名词短语指称性的研究,提取出利于消解任务的13项特征.为提高特征对文本语义的表达,在特征集中引入富含词汇语义及上下文位置关系的Word embedding.利用深度学习机制无监督的提取隐含的深层语义特征,训练Softmax分类器进而完成指代消解任务.该方法在维吾尔语指代消解任务中的准确率为74.5%,召回率为70.6%,F值为72.4%.实验结果证明,深度学习模型较浅层的支持向量机更合适于本文的指代消解任务,对Word embedding特征项的引入,有效地提高了指代消解模型的性能.     

中文指代消解名词短语的识别

指代消解技术是自动文章的关键,介绍了指代消解的研究方式,分析了中文指代消解目前研究现状,并且详细阐述了语料库和所使用的此类标记,同时提出了名词短语识别和标记符号,分析了中文名词短语的确定与英文的不同,对中文指代消解的前期语料的处理和后期应用作了很好的介绍。     

面向实体识别的聚类算法

实体识别是数据质量的一个重要方面,对于大数据处理不可或缺.已有的实体识别研究工作聚焦于数据对象相似度算法、分块技术和监督的实体识别技术,而非监督的实体识别中匹配决定的问题很少被涉及.提出一种面向实体识别的聚类算法来弥补这个缺失.利用数据对象及其相似度构建带权重的数据对象相似图.聚类过程中,利用相似图上重启式随机游走来动态地计算类簇与结点的相似度.聚类的基本逻辑是,类簇迭代地吸收离它最近的结点.提出数据对象排序方法来优化聚类的顺序,提高聚类精确性;提出了优化的随机游走平稳概率分布计算方法,降低聚类算法开销.通过在真实数据集和生成数据集上的对比实验,验证了该算法的有效性.     

基于无向分块加权图的无模式实体识别方法研究

当前利用分块进行实体识别的方案,忽略分块键权重和分块键的歧义,导致精确度较低。提出一个基于无向加权图的无模式实体识别方法,抽取数据源中的分量,利用分量信息熵和TF-IDF方法组合求取聚类分量,建立统一分块方案。通过聚类分量权重与分块键的关系,赋予每组分块键一定的权重,将该权重与边的共现频次进行相乘加权形成无向分块加权图,最后通过修剪方案进行边的修剪,从而解决了数据多分量及分块键歧义问题,提高了精确度。在七个真实数据集上的实验证明了该方法的有效性和可扩展性。     

A reductive approach to hypergraph clustering: An application to image segmentation

In the last few years, hypergraph-based methods have gained considerable attention in the resolution of real-world clustering problems, since such a mode of representation can handle higher-order relationships between elements compared to the standard graph theory. The most popular and promising approach to hypergraph clustering arises from concepts in spectral hypergraph theory [53], and clustering is configured as a hypergraph cut problem where an appropriate objective function has to be optimized. The spectral relaxation of this optimization problem allows to get a clustering that is close to the optimum, but this approach generally suffers from its high computational demands, especially in real-world problems where the size of the data involved in their resolution becomes too large. A natural way to overcome this limitation is to operate a reduction of the hypergraph, where spectral clustering should be applied over a hypergraph of smaller size. In this paper, we introduce two novel hypergraph reduction algorithms that are able to maintain the hypergraph structure as accurate as possible. These algorithms allowed us to design a new approach devoted to hypergraph clustering, based on the multilevel paradigm that operates in three steps: (i) hypergraph reduction; (ii) initial spectral clustering of the reduced hypergraph and (iii) clustering refinement. The accuracy of our hypergraph clustering framework has been demonstrated by extensive experiments with comparison to other hypergraph clustering algorithms, and have been successfully applied to image segmentation, for which an appropriate hypergraph-based model have been designed. The low running times displayed by our algorithm also demonstrates that the latter, unlike the standard spectral clustering approach, can handle datasets of considerable size.     

基于MapReduce的图结构聚类算法

图结构聚类（SCAN）是一种著名的基于密度的图聚类算法。该算法不仅能够找到图中的聚类结构,而且还能发现图中的Hub节点和离群节点。然而,随着图数据规模越来越大,传统的SCAN算法的复杂度为O（m^1.5）（m为图中边的条数）,因此很难处理大规模的图数据。为了解决SCAN算法的可扩展性问题,本文提出了一种新颖的基于MapReduce的海量图结构聚类算法MRSCAN。具体地,我们提出了一种计算核心节点,以及两种合并聚类的MapReduce算法。最后,在多个真实的大规模图数据集上进行实验测试,实验结果验证了算法的准确性、有效性,以及可扩展性。     

谱聚类算法综述

谱聚类算法是近年来国际上机器学习领域的一个新的研究热点.谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点.本文首先介绍了图论方法用于聚类的基本理论,然后根据图划分准则对谱聚类算法进行分类,着重阐述了各类中的典型算法,并对算法进行了比较分析,最后进行总结并提出了几个有价值的研究方向.     

The latest research progress on spectral clustering

Spectral clustering is a clustering method based on algebraic graph theory. It has aroused extensive attention of academia in recent years, due to its solid theoretical foundation, as well as the good performance of clustering. This paper introduces the basic concepts of graph theory and reviews main matrix representations of the graph, then compares the objective functions of typical graph cut methods and explores the nature of spectral clustering algorithm. We also summarize the latest research achievements of spectral clustering and discuss several key issues in spectral clustering, such as how to construct similarity matrix and Laplacian matrix, how to select eigenvectors, how to determine cluster number, and the applications of spectral clustering. At last, we propose several valuable research directions in light of the deficiencies of spectral clustering algorithms.     

On defining affinity graph for spectral clustering through ranking on manifolds

Spectral clustering consists of two distinct stages: (a) construct an affinity graph from the dataset and (b) cluster the data points through finding an optimal partition of the affinity graph. The focus of the paper is the first step. Existing spectral clustering algorithms adopt Gaussian function to define the affinity graph since it is easy to implement. However, Gaussian function is hard to depict the intrinsic structure of the data, and it has to specify a scaling parameter whose selection is still an open issue in spectral clustering. Therefore, we propose a new definition of affinity graph for spectral clustering from the graph partition perspective. In particular, we propose two consistencies: smooth consistency and constraint consistency, for affinity graph to hold, and then define the affinity graph respecting these consistencies in a regularization framework of ranking on manifolds. Meanwhile the proposed definition of affinity graph is applicable to both unsupervised and semi-supervised spectral clustering. Encouraging experimental results on synthetic and real world data demonstrate the effectiveness of the proposed approach.     

A graph model for mutual information based clustering

We propose a graph model for mutual information based clustering problem. This problem was originally formulated as a constrained optimization problem with respect to the conditional probability distribution of clusters. Based on the stationary distribution induced from the problem setting, we propose a function which measures the relevance among data objects under the problem setting. This function is utilized to capture the relation among data objects, and the entire objects are represented as an edge-weighted graph where pairs of objects are connected with edges with their relevance. We show that, in hard assignment, the clustering problem can be approximated as a combinatorial problem over the proposed graph model when data is uniformly distributed. By representing the data objects as a graph based on our graph model, various graph based algorithms can be utilized to solve the clustering problem over the graph. The proposed approach is evaluated on the text clustering problem over 20 Newsgroup and TREC datasets. The results are encouraging and indicate the effectiveness of our approach.