一种基于文本相似关系的紧凑性文本提取方法

摘要

本发明涉及一种基于文本相似关系的紧凑性文本提取方法，其特征在于包括以下步骤：1)根据输入文本集合T计算输入文本相似矩阵；2)标识输入文本中的处理文本和待处理文本；3)采用自回溯凝聚式聚类方法将处理文本集合T

说明书

技术领域

本发明涉及一种基于文本相似关系的紧凑性文本提取方法，涉及信息提取技术应用领域。

背景技术

在云计算、社交网络和移动互联网等新兴技术和新业态不断渗透和广泛应用的背景下，人们生活和企业管理发生了巨大的变化。信息技术的快速发展降低了信息数据的生成和传播成本，推动社会快速进入大数据时代。在大数据时代，人们需要面临大量的信息，这些信息多以文本形式出现。这些文本为人们提供了丰富的信息资源，但过量的文本也会带来极大的不便。人们难以在有限的时间内分析超过其处理能力的大量文本信息，这也是近年来业界和学术界广为关注的一个问题，即信息过载问题。例如，消费者购物过程中需要在做出购物决策之前浏览商品评论，而一个商品的在线评论数量往往可以达到数百条甚至上千条，消费者难以在有限时间浏览足够多的商品评论，导致不能做出理性的购物决策。对于企业管理者而言，在企业内部博客中每天都会有员工发布大量的博文，这些博文反映了员工舆情信息，但是由于数量巨大，这些信息难以被企业管理者分析和利用。因此有必要研究一种有效的信息提取方法，帮助人们处理大量的文本信息，应对大量信息带来的挑战。

解决文本信息过载问题的常用方法是从原始大量的文本信息中提取一个小规模的文本子集，典型方法是Top-k，此类方法根据用户需求，设计不同的计算函数F确定文本信息的排序情况，然后将排序靠前的k个文本提供给用户。当前主要的搜索引擎中均使用Top-k及各种改进方法对搜索结果进行排序。这类方法存在一定的不足：Top-k方法所提供的前k个文本往往非常相似，文本之间存在大量的信息冗余；同时也不能全面的反映原始文本信息内容。随着信息量的不断增多，人们往往希望能够看到更为紧凑的文本子集，即小规模的文本子集能够反映原始文本信息中的绝大多数内容，而文本子集本身具有较低的内容冗余性，这也就是紧凑性文本子集。

现有技术中存在某些方法能够在一定程度上解决紧凑性信息提取问题。有些通过最大覆盖的方法产生一个覆盖性集合，该集合可以覆盖原始信息的内容。但是该方法只能在分布较为均匀的数据集上表现较好的效果；同时该方法只考虑了内容覆盖，而忽略了内容冗余。例如：Hochbaum D.S.,Pathria A.,Analysis of the greedy approach in problems of maximum k-coverage(Naval Research Logistics 1998)。也有一些方法基于交互熵概念提出了一种启发式提取方法，同时对内容覆盖和内容冗余两个方面进行研究，例如：Pan F.,Wang W.,Anthony K.H.T.,Yang J.,Finding representative set from massive data(ICDM 2005)，该方法只能处理属性值为布尔型的数据库信息提取，不能处理紧凑性文本信息的提取问题。

发明内容

针对上述问题，本发明的目的是提供一种基于文本相似关系的紧凑性文本提取方法，可以从内容上覆盖原始文本信息的绝大多数内容，同时该集合内部的冗余度尽量低，通过浏览紧凑性信息集合，人们可以快速的掌握原始大量文本信息的绝大多数内容。

为实现上述目的，本发明采取以下技术方案：一种基于文本相似关系的紧凑性文本提取方法，其特征在于包括以下步骤：

1)根据输入文本集合T计算输入文本相似矩阵M；

2)标识输入文本中的处理文本集合T_process和待处理文本集合T_pending；

3)采用自回溯凝聚式聚类方法将处理文本集合T_process中的文本构造成具有α|T|层的树状结构，构造过程从树状结构的最底层开始，逐层向上，最终到达树状结构的最顶层，其中，α为阈值∈[0,1]；

4)标识待处理文本集合T_pending中文本的类别；

5)根据用户指定的代表性文本个数k提取紧凑性文本；

6)输出紧凑性信息集合。

进一步地，步骤1)根据输入文本集合T计算输入文本相似矩阵M的具体过程为：对于一个输入文本集合T＝{t₁,t₂,...,t_n}，基于向量空间模型计算文本集合T的相似矩阵M＝(e_ij)_n×n，其中，矩阵M为n×n矩阵，e_ij为文本t_i和t_j之间的相似度，记为sim(t_i,t_j)；

进一步地，步骤2)标识输入文本中的处理文本集合T_process和待处理文本集合T_pending，具体过程为：

2.1)对于文本集合T中的每一个文本t_i，计算t_i与T中所有文本之间的平均相似度avgsim_i，计算方法如下：

${\mathrm{avgsim}}_i=\frac{1}{\left|T\right|}{\Sigma }_{j=1}^{n}sim(t_i,t_j)$

式中，|T|表示集合T中包含的文本个数；

2.2)按每个文本t_i的平均相似度从大到小的顺序将文本集合T中的文本进行排序；

2.3)根据用户指定的阈值α∈[0,1]，选取排序结果中前α|T|个文本构成处理文本集合T_process，排序后(1-α)|T|个文本标记为待处理文本构成集合T_pending。

进一步地，步骤3)采用自回溯凝聚式聚类方法将处理文本集合T_process中的文本构造成具有α|T|层的树状结构，具体过程为：

3.1)聚类初始时，每个文本单独构成一个类，这样α|T|个文本构成α|T|个初始类，记为这些初始类构成树状结构的最底层，树状结构的最底层表示为第α|T|层，最顶层表示为第1层，表示第j层的第i个类，第j层中所有类个数表示为n_j；

3.2)在树状结构的每一层j(1≤j≤α|T|)，计算任意两个类之间的相似度，第j层两个类和之间的相似度按如下方式计算：

$sim(C_p^j,C_q^j)=\frac{1}{\left|C_p^j\right|\left|C_q^j\right|}{\Sigma }_{t_x\in C_p^j}\left({\Sigma }_{t_y\in C_q^j}sim\right(t_x,t_y\left)\right);$

3.3)在树状结构第j层，合并相似度最高的两个类和成一个类

3.4)标识新生成的类中的中心文本集合和边缘文本集合其中，依次计算类中每个文本对整个类中所有文本的平均相似度，根据用户指定的阈值β∈[0,1]，平均相似度满足如下条件的文本构成中心文本集合：

$C_{ik-\ker nal}^j=\left\{t_p\right|\frac{1}{\left|C_{ik}^j\right|}{\Sigma }_{t_q\in C_{ik}^j}sim(t_p,t_q)\ge \beta \}$

除去后，中剩下所有文本属于边缘文本集合

3.5)重新标识集合中文本的类别，依次计算中每一个文本t_p对于当前第j层所有类的平均相似度，将t_p划分到与它平均相似度最高的类中；

3.6)如果当前所有文本形成的类个数如果等于1，则停止树状结构的构造过程；如果当前所有文本形成的类个数大于1，则将第j层的类：

$C_1^j,C_2^j,\mathrm{...},C_{i-1}^j,C_{i+1}^j,\mathrm{...},,C_{k-1}^j,C_{k+1}^j,\mathrm{...},C_{n_j}^j,C_{ik}^j$

复制到第j-1层，开始第j-1层迭代，重复步骤3.2)到步骤3.5)，最终将输入处理文本集合T_process构造成一树状结构，该树状结构第一层为一个类，该类囊括所有T_process中的文本；树状结构的最后一层中每个类包含T_process中的一个文本，中间层j包含有n_j个类

进一步地，步骤4)标识待处理文本集合T_pending中文本的类别，具体过程为：

4.1)在树状结构的第j层(1≤j≤α|T|)，对于T_pending中的每一个文本t′_p，依次计算其与的平均相似度，计算方式如下所示：

$sim(t_p^{\prime },C_k^j)=\frac{1}{\left|C_k^j\right|}{\Sigma }_{t_q\in C_k^j}sim(t_p^{\prime },t_q),C_k^j\in \{C_1^j,C_2^j,\mathrm{...},C_{n_j}^j\};$

4.2)将t′_p划分到与它平均相似度最大的类中；

4.3)如当前层为树状结构的最顶层，则结束；反之，则继续开始j-1层的计算，重复步骤4.1)和4.3)。

进一步地，步骤5)根据用户指定的代表性文本个数k提取紧凑性文本截取树状结构第k层，得k个文本集合对于每一个集合依次计算其中每个文本对于该集合的平均相似度，选取平均相似度最高的文本作为该集合的紧凑性文本，所有紧凑性文本形成最终紧凑性信息集合

本发明由于采取以上技术方案，其具有以下优点：1、采用本发明提取的紧凑性信息集合，可以从内容上覆盖原始文本信息的绝大多数内容，同时该集合内部的冗余度尽量低，通过浏览紧凑性信息集合，人们可以快速的掌握原始大量文本信息的绝大多数内容，方便，快捷，同时为后续决策提供依据。2、本发明通过自回溯凝聚式聚类方法将大量文本按照内容相似程度组织成一树状结构，然后根据不同用户需求截取树状结构的相应层面，得到不同粒度的聚类结果，聚类结果的每一类中按平均相似度最高的标准提取相应的紧凑性文本，最后将所有的紧凑性文本构成一个紧凑性信息集合，通过实验证明，通过本发明找到的紧凑性信息集合，比现有常用的信息提取方法具有更好的内容覆盖度和更低的内容冗余度，即能够更好反映原始大量文本信息的内容。本发明可以广泛应用于文本信息提取中。

附图说明

图1是本发明的基于相似关系的紧凑性文本提取方法流程示意图；

图2是本发明的文本树状结构示意图；

图3是本发明的四种方法提取结果内容覆盖度示意图；

图4是本发明四种方法提取结果内容冗余度示意图。

具体实施方式

以下结合附图来对本发明进行详细的描绘。然而应当理解，附图的提供仅为了更好地理解本发明，它们不应该理解成对本发明的限制。

如图1所示，本发明提供一种基于文本相似关系的紧凑性文本提取方法，可以对大量文本信息进行聚类并组织成一树状结构，根据不同用户需求截取树状结构的不同层面，得到相应的紧凑性信息集合，具体包括以下内容：

1、设置一包括有文本分析模块、待处理文本标识模块、自回溯凝聚式聚类模块、分派待处理文本模块和紧凑性文本提取模块的紧凑型文本提取系统；

2、初始化，文本分析模块根据输入文本集合自动计算输入文本相似矩阵，即对于一个输入文本集合T＝{t₁,t₂,...,t_n}，基于向量空间模型计算文本集合T的相似矩阵M＝(e_ij)_n×n，其中，矩阵M为n×n矩阵，e_ij为文本t_i和t_j之间的相似度，0≤e_ij≤1，记为sim(t_i,t_j)，具体处理步骤为：

1)文本分词处理：为将文本转化为结构化形式，需要对文本进行分词处理，将文本切割成一系列具体的关键词。

2)中英文停用词处理：本发明采用Lucene中文分词工具进行文本的中文分词。

3)文本集合词典的构建：在完成分词处理之后，计算每个关键词在整个文本集合出现的频率，即统计整个文本集合中包含该关键词的文档数目，从而得到文档集合的词典；其中，文档集合的词典中记录每一个关键词以及其在文本集合中出现的频率。在文本集合的词典中删除出现频率过低的关键词，本发明在词典中保留出现频率高于5％|T|的关键词。

4)文本向量化表示及文本集合维度的选择：基于文本集合的词典，本发明采用tf-idf模型对文本进行向量化，将每一个文本转化为同样维度的向量。具体而言，词典中每一个关键词作为文本向量的一个维度，文本集合中的一个文本在这个维度上的值为tf×idf。tf为该维度关键词在这一文本中出现的频率，idf＝log(|T|/|T’|+1)，|T|表示文本集合中的文本总数，|T’|表示文本集合中包含该维度关键词的文本数。

5)文本间相似度计算：输入文本集合中的每一个文本均表示为相同维度的向量，如t_i＝(ω_i1,ω_i2,…,ω_it)。通过夹角余弦计算两文本之间的相似度，对于文本t_i＝(ω_i1,ω_i2,…,ω_it)和t_j＝(ω_j1,ω_j2,…,ω_jt)，其相似度计算方法如下式所示：

$e_{ij}=sim(t_i,t_j)=\frac{{\omega }_{i1}\times {\omega }_{j1}+{\omega }_{i2}\times {\omega }_{j2}+...+{\omega }_{it}\times {\omega }_{jt}}{\sqrt{{\omega }_{i1}^2+{\omega }_{i2}^2+...+{\omega }_{it}^2}\times \sqrt{{\omega }_{j1}^2+{\omega }_{j2}^2+...+{\omega }_{jt}^2}}$

通过计算得到文本集合任意两文本的相似度，即求出文本集合的相似矩阵M。

3、待处理文本标识模块根据输入文本集合T通过计算平均相似度标识其中的处理文本和待处理文本。

输入文本集合中包含一些相似度较低的文本，这些文本可能会影响文本集合的聚类精度。为保证聚类精度，本发明在得到相似矩阵M之后，通过计算平均相似度自动标识处理文本和待处理文本。处理文本用于随后的聚类分析中，而待处理文本则在得到聚类结果之后再进行类别的分派。在本发明中，对于输入文本集合T＝{t₁,t₂,...,t_n}，处理文本和待处理文本应具有如下特点：处理文本对于集合T中的文本具有较高的平均相似度；待处理文本对于集合T中文本的平均相似度较低。基于此，本发明将输入文本集合T划分为两个集合，处理文本集合T_process和待处理文本集合T_pending。为更好的反映处理文本和待处理文本之间差异，本发明采用了排序区分的方法，具体方法为：

1)对于文本集合T中的每一个文本t_i，计算t_i与T中所有文本之间的平均相似度avgsim_i，计算方法如下：

${\mathrm{avgsim}}_i=\frac{1}{\left|T\right|}{\Sigma }_{j=1}^{n}sim(t_i,t_j)$

式中，|T|表示集合T中包含的文本个数。

2)按每个文本t_i的平均相似度从大到小的顺序将文本集合T中的文本排序。

3)根据用户指定的阈值α∈[0,1]，选取排序结果中前α|T|个文本构成处理文本集合T_process；排序后(1-α)|T|个文本标记为待处理文本构成集合T_pending。

4、自回溯凝聚式聚类模块通过改进的凝聚式聚类方法将处理文本集合T_process中的文本构造成具有α|T|层的树状结构。构造过程从树状结构的最底层开始，逐层向上，最终到达树状结构的最顶层。具体步骤如下：

1)聚类初始时，每个文本单独构成一个类，这样α|T|个文本构成α|T|个初始类，记为这些初始类构成树状结构的最底层。树状结构的最底层表示为第α|T|层，最顶层表示为第1层，表示第j层的第i个类，第j层中所有类个数表示为n_j。

2)在树状结构的每一层j(1≤j≤α|T|)，计算任意两个类之间的相似度。第j层两个类和之间的相似度按如下方式计算：

$sim(C_p^j,C_q^j)=\frac{1}{\left|C_p^j\right|\left|C_q^j\right|}{\Sigma }_{t_x\in C_p^j}\left({\Sigma }_{t_y\in C_q^j}sim\right(t_x,t_y\left)\right)$

3)在树状结构第j层，合并相似度最高的两个类和成一个类

4)标识新生成的类中的中心文本集合和边缘文本集合其中，依次计算类中每个文本对整个类中所有文本的平均相似度，根据用户指定的阈值β∈[0,1]，平均相似度满足如下条件的文本构成中心文本集合。

$C_{ik-\ker nal}^j=\left\{t_p\right|\frac{1}{\left|C_{ik}^j\right|}{\Sigma }_{t_q\in C_{ik}^j}sim(t_p,t_q)\ge \beta \}$

除去后，中剩下所有文本属于边缘文本集合

5)重新标识集合中文本的类别，依次计算中每一个文本t_p对于当前第j层所有类的平均相似度，将t_p划分到与它平均相似度最高的类中。

6)如果当前所有文本形成的类个数如等于1，则停止树状结构的构造过程；如果当前所有文本形成的类个数大于1，则将第j层的类：

$C_1^j,C_2^j,\mathrm{...},C_{i-1}^j,C_{i+1}^j,\mathrm{...},,C_{k-1}^j,C_{k+1}^j,\mathrm{...},C_{n_j}^j,C_{ik}^j$

复制到第j-1层，开始第j-1层迭代，重复步骤2)到步骤5)。最终将输入处理文本集合T_process构造成一树状结构，该树状结构第一层为一个类，该类囊括所有T_process中的文本；树状结构的最后一层中每个类包含T_process中的一个文本；中间层j包含有n_j个类

传统的凝聚式聚类方法通过自下而上的迭代凝聚，可将T_process中的α|T|个文本聚成一个树状结构，不需要用户提前指定聚类的类别个数，通过一次凝聚操作就可以得到1到α|T|各个层面上的聚类结果。但是这样的方法也有着一定的不足，即在凝聚过程中不能发现异常点，也不能动态的纠正异常点所导致的错误。本发明所采用的自回溯凝聚式聚类方法是针对上述不足的一种改进式凝聚式聚类方法。方法初始时假定所有α|T|个文本各自为一个类，每一次迭代合并平均相似度最高的两个类，直至所有文本最终凝聚成一个类。在凝聚过程的每一步迭代中，新形成的类中绝大多数都是中心文本，少量的为边缘文本。中心文本对于新形成的类中的文本平均相似度高；相反边缘文本位于新类的边缘位置，其对于类中文本的平均相似度底，因此边缘文本的类别需要重新审视。

自回溯凝聚式聚类方法根据用户指定的参数β∈[0,1]判断中心文本和边缘文本。对于平均相似度高于β的文本，标记为中心文本；对于平均相似度低于β的文本，则标记为边缘文本。β数值的大小反映了用户的倾向，如果β较大，反映用户认为只有平均相似度很高的文本才能算作中心文本，此时中心文本的数量较少；反之如果β数值较小，反映用户的标准较为宽泛，满足一定平均相似度条件的文本均可以标记为中心文本，此时中心文本的数量相对较多。

在每一步迭代中，对于边缘文本采用“回溯”操作对其类别标签进行重判断。通过上述步骤，处理文本集合T_process中的所有文本被组织成一树状结构，如图2所示。树状结构中的不同层表示着不同粒度下的聚类结果。

5、分派待处理文本模块标识待处理文本集合T_pending中文本的类别。对于通过步骤4所形成的树状结构，针对每一层j中的n_j个类依次计算T_pending中每个文本t′_p与它们的平均相似度，将t′_p划分到与它平均相似度最大的类中。处理过程从树状结构的最底层开始到最顶层，具体步骤如下：

1)在树状结构的第j层(1≤j≤α|T|)，对于T_pending中的每一个文本t′_p，依次计算其与的平均相似度，计算方式如下所示：

$sim(t_p^{\prime },C_k^j)=\frac{1}{\left|C_k^j\right|}{\Sigma }_{t_q\in C_k^j}sim(t_p^{\prime },t_q),C_k^j\in \{C_1^j,C_2^j,\mathrm{...},C_{n_j}^j\}$

2)将t′_p划分到与它平均相似度最大的类中。

3)如当前层为树状结构的最顶层，则结束；反之，则继续开始j-1层的计算，重复步骤1)和3)。

6、根据用户指定的代表性文本个数k提取紧凑性文本。截取树状结构第k层，得k个文本集合对于每一个集合依次计算其中每个文本对于该集合的平均相似度，选取平均相似度最高的文本作为该集合的紧凑性文本，所有紧凑性文本形成最终紧凑性信息集合

7、输出紧凑性信息集合

下面通过具体实施例验证本发明的紧凑性文本提取方法用于解决大量文本信息的提取和分析的有效性。

本实施例选取一种典型性的大量文本信息提取和分析应用场景，即企业博客作为测试环境。企业博客系统可以看作是一个大量文本集合，每天都会有大量的新增博文发布。从中提取紧凑性文本信息，将有助于用户在较短时间内快速掌握企业博客中的大量文本内容。在测试的企业博客系统中，已有三种博文提取方法，分别是基于阅读次数排名的文本提取方法，为用户提取阅读次数排名前几位的博文(记为阅读次数提取方法)；基于评论次数排名的文本提取方法，为用户提取评论次数排名前几位的博文(记为评论次数提取方法)；以及基于用户评分排名的文本提取方法，为用户提取得分排名前几位的博文(记为精华分数提取方法)。本发明方法与上述三种方法的提取结果进行比较，比较的策略为：四种方法同时从相同的文本中提取相同规模的文本信息，分别比较四种方法提取结果的内容覆盖度和内容冗余度。

测试中所使用的内容覆盖度的测度和内容冗余度的测度为信息提取领域中的经典测度，参见：Ma B.J.,Wei Q.,Chen G.Q.,A combined measure for representative information retrieval in enterprise information systems(Journal of Enterprise Information Management 2011)。给定两个文本集合T’对T，T’对T的内容覆盖度如下式所示：

Coverage(T′,T)＝Σ_t∈T(max_t′∈T′(sim(t′,t)))

给定一个文本集合T，T的内容冗余度如下式所示：

Redundancy(T)＝∑_t∈T(1-1/∑_t′∈Tsim(t′,t))/|T|

上述两式中，sim(t’,t)表示两个文本之间的相似度

测试选取了企业博客系统中的11组博文集合，前10组各自均包含200篇博文，第11组包含239篇博文。使用四种提取方法对这11组数据进行文本提取，每种方法在每组测试数据中均提取10个文本，测试每种方法提取的10个文本的内容覆盖度和内容冗余度。

四种方法提取结果的内容覆盖度如图3所示。测试数据表明在四种方法中，本发明的紧凑性文本提取方法的提取结果内容覆盖度高于其它三种方法所提取的文本。本发明的紧凑性文本提取方法的平均内容覆盖度比精华分数提取方法的提取结果高54.5％，比阅读次数提取方法高58.8％，比评论次数提取方法高70.5％。采用配对样本T检验对测试结果进行显著性检验，统计结果如下：

表1

注：***表明显著性水平为99.9％

统计结果表明，本发明的紧凑性文本提取方法的提取结果内容覆盖度显著高于其它三种方法的提取结果，这说明相比于其它三种方法，本发明的紧凑性文本提取方法的提取结果能更好的反映原始信息中的内容。

四种方法提取结果的内容冗余度如图4所示。测试数据表明在四种方法中，本发明的紧凑性文本提取方法的提取结果内容冗余度低于其它三种方法所提取的文本。本发明的紧凑性文本提取方法的平均内容冗余度比精华分数提取方法低35.4％，比阅读次数提取方法低32.2％，比评论次数提取方法低36.4％。采用配对样本T检验对测试结果进行显著性检验，统计结果如下：

表2

注：***表明显著性水平为99.9％

统计结果表明，本发明的紧凑性文本提取方法的提取结果内容冗余度显著低于其它三种方法的提取结果，这说明相比于其它三种方法，本发明的紧凑性文本提取方法的提取结果的内容冗余度更低，即内容更加不冗余，提取结果便于用户在较短的时间内阅读和浏览。

上述各实施例仅用于说明本发明，其中本发明的各实施步骤等都是可以有所变化的，凡是在本发明技术方案的基础上进行的等同变换和改进，均不应排除在本发明的保护范围之外。