使用概念描述的中文短文本分类算法

针对短文本特征较少而导致使用传统文本分类算法进行分类效果并不理想的问题,提出了一种使用了概念描述的短文本分类算法,该方法首先构建出全局的语义概念词表;然后,使用概念词表分别对预测短文本和训练短文本概念化描述,使得预测短文本在训练集中找出拥有相似概念描述的训练短文本组合成预测长文本,同时将训练集内部的短文本也进行自组合形成训练长文本;最后,再使用传统的长文本分类算法进行分类。实验证明,该方法能够有效挖掘短文本内部隐含的语义信息,充分对短文本进行语义扩展,提高了短文本分类的准确度。     

基于特征词向量的短文本聚类算法

针对互联网短文本特征稀疏和速度更新快而导致的短文本聚类性能较差的问题,本文提出了一种基于特征词向量的短文本聚类算法。首先,定义基于词性和词长度加权的特征词提取公式并提取特征词代表短文本;然后,使用Skip-gram模型（Continous skip-gram model）在大规模语料中训练得到表示特征词语义的词向量;最后,引入词语游走距离（Word mover′s distance,WMD）来计算短文本间的相似度并将其应用到层次聚类算法中实现短文本聚类。在4个测试数据集上的评测结果表明,本文方法的效果明显优于传统的聚类算法,平均F值较次优结果提高了56.41%。     

改进特征权重的短文本聚类算法

短文本的研究一直是自然语言处理领域的热门话题,由于短文本特征稀疏、用语口语化严重的特点,它的聚类模型存在维度高、主题聚焦性差、语义信息不明显的问题.针对对上述问题的研究,本文提出了一种改进特征权重的短文本聚类算法.首先,定义多因子权重规则,基于词性和符号情感分析构造综合评估函数,结合词项和文本内容相关度进行特征词选择;接着,使用Skip-gram模型（Continuous Skip-gram Model）在大规模语料中训练得到表示特征词语义的词向量;最后,利用RWMD算法计算短文本之间的相似度并将其应用K-Means算法中进行聚类.最后在3个测试集上的聚类效果表明,该算法有效提高了短文本聚类的准确率.     

一种结合上下文语义的短文本聚类算法

短文本因具有特征信息不足且高维稀疏等特点,使得传统文本聚类算法应用于短文本聚类任务时性能有限。针对上述情况,提出一种结合上下文语义的短文本聚类算法。首先借鉴社会网络分析领域的中心性和权威性思想设计了一种结合上下文语义的特征词权重计算方法,在此基础上构建词条-文本矩阵;然后对该矩阵进行奇异值分解,进一步将原始特征词空间映射到低维的潜在语义空间;最后通过改进的K-means聚类算法在低维潜在语义空间完成短文本聚类。实验结果表明,与传统的基于词频及逆向文档频权重的文本聚类算法相比,该算法能有效改善短文本特征不足及高维稀疏性,提高了短文的本聚类效果。     

结合语义改进的K-means短文本聚类算法

针对短文本聚类存在的三个主要挑战,特征关键词的稀疏性、高维空间处理的复杂性和簇的可理解性,提出了一种结合语义改进的K-means短文本聚类算法。该算法通过词语集合表示短文本,缓解了短文本特征关键词的稀疏性问题;通过挖掘短文本集的最大频繁词集获取初始聚类中心,有效克服了K-means聚类算法对初始聚类中心敏感的缺点,解决了簇的理解性问题;通过结合TF-IDF值的语义相似度计算文档之间的相似度,避免了高维空间的运算。实验结果表明,从语义角度出发实现的短文本聚类算法优于传统的短文本聚类算法。     

基于Word2Vec的中文短文本分类问题研究

针对短文本中固有的特征稀疏以及传统分类模型存在的“词汇鸿沟”等问题, 我们利用Word2Vec模型可以有效缓解短文本中数据特征稀疏的问题, 并且引入传统文本分类模型中不具有的语义关系. 但进一步发现单纯利用 Word2Vec模型忽略了不同词性的词语对短文本的影响力, 因此引入词性改进特征权重计算方法, 将词性对文本分类的贡献度嵌入到传统的TF-IDF算法中计算短文本中词的权重, 并结合 Word2Vec 词向量生成短文本向量, 最后利用SVM实现短文本分类. 在复旦大学中文文本分类语料库上的实验结果验证了该方法的有效性.     

基于混合策略的中文短文本相似度计算

为提高中文短文本相似度计算的准确率,提出一种新的基于混合策略的中文短文本相似度计算方法。首先,根据词语的语义距离,利用层次聚类,构建短文本聚类二叉树,改进传统的向量空间模型（VSM）,计算关键词加权的文本相似度。然后,通过提取句子的主干成分对传统的基于语法语义模型的方法进行改进,得到文本主干的语义相似度;最后,对两种相似度进行加权,计算最终的文本相似度。实验结果表明,提出的方法在短文本相似度计算方面准确性更高,更加适合人们的主观判断。     

融合词性位置特征的多任务汉老双语短文本相似度计算方法

老挝语属于低资源语言,在有限的语料中获取更多的语义信息可以有效解决汉语和老挝语短文本相似度计算不准确的问题。多任务学习是有效获取语义信息的一种方法,该文对汉语和老挝语短文本特点进行研究后,提出一种融合词性位置特征的多任务汉老双语短文本相似度计算方法：首先,通过词性位置特征权重和TF-IDF权重加权表征双语短文本的同时,使用改进后的TextRank算法获取双语短文本的核心句;然后,通过带有自注意力机制的双向长短时记忆网络分别计算双语短文本的相似度与双语短文本对应核心句的相似度;最后,使用多任务学习方法,将双语短文本的核心句相似度计算作为辅助任务,获取更多的语义信息进行共享以提升汉老双语短文本相似度计算模型的性能。实验结果表明,该文提出的方法在有限的训练语料下取得了更好的效果,F₁值达76.16%。     

一种基于复杂网络的短文本语义相似度计算

将传统的文本相似度量方法直接移植到短文本时,由于短文本内容简短的特性会导致数据稀疏而造成计算结果出现偏差。该文通过使用复杂网络表征短文本,提出了一种新的短文本相似度量方法。该方法首先对短文本进行预处理,然后对短文本建立复杂网络模型,计算短文本词语的复杂网络特征值,再借助外部工具计算短文本词语之间的语义相似度,然后结合短文本语义相似度定义计算短文本之间的相似度。最后在基准数据集上进行聚类实验,验证本文提出的短文本相似度计算方法在基于F-度量值标准上,优于传统的TF-IDF方法和另一种基于词项语义相似度的计算方法。     

基于加权融合字词向量的中文在线评论情感分析

随着社交网络平台的广泛使用,涌现出大量蕴涵丰富情感信息的在线评论文本,分析评论中表达的情感对企业、平台等具有重要意义。为了解决目前针对在线评论短文本情感分析中存在特征提取能力弱以及忽略短文本本身情感信息的问题,提出一种基于文本情感值加权融合字词向量表示的模型——SVW-BERT模型。首先,基于字、词级别向量融合表示文本向量,最大程度获取语义表征,同时考虑副词、否定词、感叹句及疑问句对文本情感的影响,通过权值计算得到文本的情感值,构建情感值加权融合字词向量的中文短文本情感分析模型。通过网络平台在线评论数据集对模型的可行性和优越性进行验证。实验结果表明,字词向量融合特征提取语义的能力更强,同时情感值加权句向量考虑了文本本身蕴涵的情感信息,达到了提升情感分类能力的效果。     

基于基本操作序列的编辑距离顺序验证

两字符串的编辑距离是从一个串转换到另一个串所需要的最少基本操作数。编辑距离广泛应用于字符串近似匹配、字符串相似连接等领域。动态规划法利用编辑距离矩阵来计算两个串的编辑距离,需要计算矩阵中的所有元素,时间效率低。改进的方法改变了矩阵中元素的计算次序,减少了需要比对的元素,但仍需要比对一半以上的元素,时间效率还有待提高。提出基于基本操作序列的编辑距离顺序验证方法。首先,分析了基本操作序列的可列性,给出了列举基本操作序列的方法。然后依次顺序验证基本操作数从小到大的基本操作序列直到某一序列通过验证,得到其编辑距离。在阈值为2的字符串近似搜索实验中发现,所提方法比动态规划类方法具有更高的效率。     

CASM: a VLSI chip for approximate string matching

The edit distance between two strings a1, ..., a_m and b ₁, ..., b_n is the minimum cost s of a sequence of editing operations (insertions, deletions and substitutions) that convert one string into the other. This paper describes the design and implementation of a linear systolic array chip for computing the edit distance between two strings over a given alphabet. An encoding scheme is proposed which reduces the number of bits required to represent a state in the computation. The architecture is a parallel realization of the standard dynamic programming algorithm proposed by Wagner and Fischer (1974), and can perform approximate string matching for variable edit costs. More importantly, the architecture does not place any constraint on the lengths of the strings that can be compared. It makes use of simple basic cells and requires regular nearest neighbor communication, which makes it suitable for VLSI implementation. A prototype of this array has been built at the University of South Florida     

一种基于语义词典的本体对齐框架

提出一种基于语义词典的本体对齐框架.首先抽取出代表本体元素的字符串,这些字符串包括本体中的概念、实例、关系等,并利用现有的词典和语义资源将字符串变为词的集合;然后将本体对齐转换为单词集合间的映射,通过多相似度的匹配算法来进行相似度计算,从而实现本体对齐.实验结果表明,所提出的方法是有效的且较之以前的对齐方法有一定的提高.     

Parametric Sequence Alignment with Constraints

Approximate matching techniques based on string alignment are important tools for investigating similarities between strings, such as those representing DNA and protein sequences. We propose a constraint based approach for parametric sequence alignment which allows for more general string alignment queries where the alignment cost can itself be parameterized as a query with some initial constraints. Thus, the costs need not be fixed in a parametric alignment query unlike the case in normal alignment. The basic dynamic programming string edit distance algorithm is generalized to a naive algorithm which uses inequalities to represent the alignment score. The naive algorithm is rather costly and the remainder of the paper develops an improvement which prunes alternatives where it can and approximates the alternatives otherwise. This reduces the number of inequalities significantly and strengthens the constraint representation with equalities. We present some preliminary results using parametric alignment on some general alignment queries.     

Markov edit distance

Edit distance was originally developed by Levenstein several decades ago to measure the distance between two strings. It was found that this distance can be computed by an elegant dynamic programming procedure. The edit distance has played important roles in a wide array of applications due to its representational efficacy and computational efficiency. To effect a more reasonable distance measure, the normalized edit distance was proposed. Many algorithms and studies have been dedicated along this line with impressive performances in recent years. There is, however, a fundamental problem with the original definition of edit distance that has remained elusive: its context-free nature. In determining the possible actions, i.e., insertion, deletion, and substitution, no systematic consideration was given to the local behaviors of the string/pattern in question that indeed encompass great amount of useful information regarding its content. In this paper, inspired by the success of the Markov Random Field theory, a new edit distance called Markov edit distance (MED) within the dynamic programming framework is proposed to take full advantage of the local statistical dependencies in the pattern in order to arrive at enhanced matching performance. Within this framework, two specialized distance measures are developed: The reshuffling MED to handle cases where a subpattern in the target pattern is the reshuffles of that in the source pattern, and the coherence MED which is able to incur local content based substitution, insertion, and deletion. The applications based on these two MEDs in string matching are then explored, whereof encouraging empirical results have been observed.     

一种有效的编辑距离和编辑路径求解技术

给定字符串Ｔ．Ｐ，将Ｔ转换成Ｐ所需的插入，删除，替代序列称为Ｔ到Ｐ的编辑路径，其最短编辑路径所需的插入，删除替代总数称为Ｔ到Ｐ的编辑距离，本文提出一种有效的编辑距离和编辑路径求解技术，该技术首先通过一有效的字符串相似匹配算法计算出编辑距离，而后仅通过简单的二进制字位运算正确计算出编辑路径。     

基于加权二部图的汉日词对齐

高效的自动词对齐技术是词对齐语料库建设的关键所在。当前很多词对齐方法存在以下不足: 未登录词问题、灵活翻译问题和全局最优匹配问题。针对以上不足,该文提出加权二部图最大匹配词对齐模型,利用二部图为双语句对建模,利用词形、语义、词性和共现等信息计算单词间的相似度,利用加权二部图最大匹配获得最终对齐结果。在汉日词语对齐上的实验表明,该方法在一定程度上解决了以上三点不足,F-Score为80%,优于GIZA₊₊的72%。     

支持块编辑距离的索引结构

在近似字符串匹配中,传统的编辑距离不能很好地衡量诸如人名、地址等数据的相似关系,而块编辑距离可以很好地衡量两个字符串的相似性.如何有效地支持块编辑距离,进行近似字符串查询处理具有重要的意义.计算两个字符串的块编辑距离是一个NP完全问题,因此希望提供有效的方法可以增强过滤能力,并减少假通过率.设计了一种支持移动编辑距离的新颖的索引结构SHV-Trie,通过研究移动编辑距离的操作特性,使用字母出现的频率作为支持移动编辑距离操作的一个下界,并且提出相应的查询过滤算法,同时,针对索引SHV-Trie的空间开销过大的问题,提出一种优化字母排列的索引结构和一种压缩的索引结构及相关查询过滤算法.真实数据集上的实验结果与分析显示了所提出的索引结构具有良好的过滤能力,并通过减少效率假通过率提高查询的效率.     

Fast approximate matching of words against a dictionary

A new algorithm for string edit distance computation is given. The algorithm assumes that one of the two strings to be compared is a dictionary entry that is known a priori. This dictionary word is converted in an off-line phase into a deterministic finite state automaton. Given an input string and the automaton derived from the dictionary word, the computation of the edit distance between the two strings corresponds to a traversal of the states of the automaton. This procedure needs time which is only linear in the length of the input string. It is independent of the length of the dictionary word. Given not only one butN different dictionary words, their corresponding automata can be combined into a single deterministic finite state automaton. Thus the computation of the edit distance between the input word and each dictionary entry, and the determination of the nearest neighbor in the dictionary need time that is only linear in the length of the input string. However, the number os states of the automation is exponential.     

Graph edit distance from spectral seriation

This paper is concerned with computing graph edit distance. One of the criticisms that can be leveled at existing methods for computing graph edit distance is that they lack some of the formality and rigor of the computation of string edit distance. Hence, our aim is to convert graphs to string sequences so that string matching techniques can be used. To do this, we use a graph spectral seriation method to convert the adjacency matrix into a string or sequence order. We show how the serial ordering can be established using the leading eigenvector of the graph adjacency matrix. We pose the problem of graph-matching as a maximum a posteriori probability (MAP) alignment of the seriation sequences for pairs of graphs. This treatment leads to an expression in which the edit cost is the negative logarithm of the a posteriori sequence alignment probability. We compute the edit distance by finding the sequence of string edit operations which minimizes the cost of the path traversing the edit lattice. The edit costs are determined by the components of the leading eigenvectors of the adjacency matrix and by the edge densities of the graphs being matched. We demonstrate the utility of the edit distance on a number of graph clustering problems.