基于领域知识地图社区结构的文档主题划分方法

摘要

本发明公开了一种基于领域知识地图社区结构的文档主题划分方法，主要解决与学科或领域知识相关的文档资源的划分问题，以便于将主题相关的文档存储在相近的逻辑位置，提高学习效率。其特征在于：提出了基于Fast Geedy算法和GN算法的层次社区发现算法构建主题结构树；特征提取过程将知识单元直接作为特征向量，由于知识单元具有语义完整性，相对于传统的基于分词的方法更能够体现特征向量的主题特性；计算特征向量值的过程提出度中心度和知识单元文档频相结合的方法，其中度中心度的概念反映了知识单元在知识地图全局中的地位。通过以上方法，有效提高文档主题划分的准确率，适用于通用场景下基于知识地图社区结构的文档主题划分。

说明书

技术领域

本发明涉及在领域知识地图社区结构的基础上进行文档主题划分，主要解决与学科或领域知识相关的文档资源的划分问题，以便于将主题相关的文档存储在相近的逻辑位置，提高存储和访问效率。

背景技术

随着网络课程平台的扩展，网络课程各个学科文档规模不断扩大，将主题相近的文档存储在相近的逻辑位置，当学习者学习某个资源时，可以对与其主题相关联的其他资源进行预取，减小读取文件的时间开销，提高存储和访问效率。

针对文档的主题划分方法，以下3篇专利文献提供了不同的技术方案：

1.基于领域知识的文本分类特征选择及权重计算方法（CN101290626）

2.基于修正的K近邻文本分类方法（CN102033949A）

3.一种新的面向文本分类的特征向量权重的方法及装置（CN1719436A）

文献1的方法包括：（1）收集领域文本和非领域文本作为训练语料和测试语料；（2）文本的预处理，包括分词处理及统计词频和文档频；（3）选取分类特征空间并用改进的TF-IDF方法计算特征权值；（4）在步骤（3）的基础上选取特征空间并扩展领域术语到特征空间；（5）选取分类特征空间，利用改进的TF-IDF算法对特征权重进行计算和调整；（6）用SVM机器学习方法，训练文本划分器，构建领域文本划分模型，并对领域文本进行实验验证。

文献2的方法包括（1）文本预处理：首先对训练文本集合中的每个文档进行分词，去除停用词，将文本进行项目化表示；（2）文本特征选择：然后对文本向量降维，构造特征函数对特征词进行打分，选择尽可能少且与文档主题概念密切相关的文档特征；（3）文本分类：最后利用基于偏差的K近邻文本分类算法构建分类器进行分类，得到分类结果。

文献3的方法包括：（1）按领域收集训练语料和测试语料；（2）去除网页文本的“垃圾”、分词、词性标注；（3）从训练语料中提取每个领域的词表，并提取总词表；（4）根据总词表和领域词表建立用于分类的具有不同关键词数目的信息词表；（5）使用TF-IWF-DBV算法对测试文本进行分类，优化得到最优阈值；（6）根据分类结果确定最优关键词数目。由于TF-IDF和TF-IWF方法都过分倚重词频，同时又无法表示出向量元素在类别之间分布的不均衡性，所以文献3提出一种新的权重计算方法（TF-IWF-DBV），在TF-IWF方法中引入了DBV和TF的n次方根弥补了方法的不足。

以上文献所述方法主要集中在文本分类的特征提取方法的优化上，然而仍是基于传统分词方式选取术语为特征项，并未充分考虑到特征项的主题特性，导致分类准确率欠佳。

发明内容

本发明为了解决现有大规模网络课程中各个学科文档的主题划分问题，提供了一种将领域知识地图社区结构和文档主题划分相结合的划分方法，以划分出主题相近的文档。

为达到以上目的，本发明是采取如下技术方案予以实现的：

一种基于领域知识地图社区结构的文档主题划分方法，其特征在于，包括下述步骤：

一、领域知识地图社区结构树构建：

（1）领域知识地图预处理过程，将领域知识地图转换为简单无向图，并将转换后的领域知识地图作为社区结构树的根社区节点，将其加入到待分析节点队列CAQ中；社区节点的形式化表示如下：

CNode(V_C,Children,Parent)    (1)

其中，V_C表示社区节点包含的知识单元集合，Children表示社区节点的子节点集合，Parent表示社区节点的父节点；

（2）领域知识地图层次社区划分过程，从CAQ中取出队首节点CH，分别使用Fast Greedy和GN算法对CH对应的领域知识地图或其子图进行社区划分，并引入模块度阈值若上述两种算法得到的社区划分结果对应的模块度值均小于则划分无效，执行步骤（3）；否则，对比上述两种算法划分结果对应模块度值，选取其中较大的模块度值对应的社区划分结果，创建其中每个社区对应的社区节点，作为CH的子社区节点，并将其加入CAQ队列；

（3）对CAQ中的所有节点进行步骤（2），直到CAQ队列为空，从而得到领域知识地图对应的社区结构树C-Tree，其形式化表示如下：

C-Tree(CNodeSet,croot,n)    (2)

其中，CNodeSet表示社区结构树的社区节点集合，croot表示社区结构树的根社区节点，n表示社区节点数，即网络中存在的社区个数；

二、通过对步骤一所得的领域知识地图对应的社区结构树进行社区主题辨识，构建领域主题结构树，实现社区结构到主题结构的映射；

三、文档特征向量提取：

（1）构造特征空间，将领域知识地图中的所有知识单元作为特征项，构成多维度的特征空间；

（2）文档的预处理过程，将文档转换为纯文本形式，提取每个文档的文本段，使用基于向量空间模型的TF-IDF算法将文档的文本段与领域知识地图库的知识单元ku对应的文本段内容进行相似度匹配，若相似度达到阈值μ，则认为文档包含ku，据此提取出文档包含的所有知识单元；

（3）利用公式（3）计算特征空间中知识单元在领域知识地图中的度中心度，结合文档中知识单元的出现频次，将文档抽象为如下形式：

X_j={W₁,W₂,...,W_i,...,W_n}，其中n表示特征向量的维度，W_i表示第i个特征项的权重，其形式化表示如下：

W_i=C_deg(ku_i)*kuf(ku_i,d)      （7）

其中，kuf(ku_i,d)表示知识单元在文档d中出现的频次，C_deg(ku_i)表示知识单元ku_i的度中心度；

四、文档主题划分模型构建：

（1）构造训练数据集，对于给定的训练数据集D中的每一个文档，使用步骤三所述方法提取其特征向量，结合步骤一中的领域知识地图社区结构树C-Tree和步骤二中领域主题结构树T-Tree，将训练数据集抽象为如下形式：

D={(X₁,Y₁),(X₂,Y₂),...,(X_j,Y_j),...,(X_m,Y_m)}      （8）

其中，X_j(j=1,2,...,m)表示第j个文档的特征向量，Y_j(j=1,2,...,m)表示第j个文档的主题标签集合，其形式化表示如下：

Y_j={L₁,L₂,...,L_i...,L_k}       （9）

其中，m为训练集文档个数，k为社区主题个数；

（2）训练过程选择BR-SVM算法，采用交叉验证方式，基于训练文档集D，训练得到文档主题划分模型M；

五、文档主题划分：对待划分的文档，提取文档包含的知识单元，使用步骤三方法得到文档特征向量表示，使用步骤四得到的文档主题划分模型实现文档主题划分。

上述方法中，所述的构建领域主题结构树具体步骤为：

（1）社区中心点分析，计算C-Tree中的每个社区节点所包含知识单元在社区对应的领域知识地图子图中的度中心度，选取中心度较大的节点集作为社区中心节点组CCNS；知识单元在社区对应的领域知识地图子图中的度中心度计算方法如下：

$>C_{\mathrm{deg}}\left({\mathrm{ku}}_i\right)=\frac{\mathrm{deg}\left({\mathrm{ku}}_i\right)}{\underset{i=1}{\overset{n}{\Sigma }}\mathrm{deg}\left({\mathrm{ku}}_i\right)},{\mathrm{ku}}_i\in \mathrm{KU}---\left(3\right)$>

其中，deg(ku_i)表示知识单元ku_i社区内的度，KU表示领域知识地图或其子图包含的知识单元集合；

（2）对CCNS中的知识单元，查找领域知识地图库，得到CCNS包含的核心术语集，结合知识单元的度中心度和核心术语在CCNS中知识单元出现的频次，计算核心术语的中心性权重W_Central，其形式化表示如下：

$>W_{\mathrm{Central}}^{\mathrm{term}}={\Sigma }_{\mathrm{ku}}^{\mathrm{CCNS}}C\left(\mathrm{ku}\right)*\delta (\mathrm{term},\mathrm{ku})---\left(4\right)$>

其中，C(ku)表示CCNS中知识单元的中心度，δ(term,ku)表示term在ku中出现的频次，选取中心性权重最大的核心术语作为社区的主题；

（3）对于C-Tree每个社区节点进行步骤（2），从而构建领域主题结构树T-Tree，实现社区结构到主题结构的映射，T-Tree形式化表示如下：

T-Tree(CTopicSet,troot，n)    （5）

其中，CTopicSet表示社区主题节点集合，troot表示主题结构树的根节点，n表示主题个数；社区主题节点形式化表示如下：

CTopic(Y_C,SubTopics,PTopic)      （6）

其中，Y_C表示社区主题标号，SubTopics表示主题节点的子节点集合，PTopic表示主题节点的父节点。

与现有技术相比，本发明方法的优点在于：构建主题结构树的过程中，提出了基于Fast Geedy算法和GN算法的层次社区发现算法构建社区结构树；特征提取过程将知识单元直接作为特征向量，由于知识单元具有语义完整性，相对于传统的基于分词的方法更能体现特征向量的主题特性；计算特征向量值的过程提出度中心度和知识单元文档频相结合的方法，其中度中心度的概念反映了知识单元在知识地图全局中的地位。通过上述改进，相对于传统方法有效提高了文档主题划分的准确率。

附图说明

以下结合附图及具体实施方式对本发明作进一步的详细说明。

图1是本发明基于知识地图社区结构文档主题划分流程图。

图2是图1中领域知识地图主题体系构建流程图。

图3是图1中特征向量提取流程图。

具体实施方式

所述领域知识地图是描述某一个领域（课程或学科）内的知识以及这些知识之间的关联的复杂网络；知识单元指知识地图中具有完备表达能力的基本知识片段；领域知识地图库是存储领域内知识单元的数据库，记录了知识单元的详细信息，如知识单元名称、知识单元对应文本段、知识单元包含核心术语及知识单元之间的关系等。通常一门学科的知识地图是从该学科的文档资源中构建产生，表示为知识单元及其关联关系的网络；使用复杂网络社区发现算法将领域知识地图划分为社区结构后，每个社区具有相对独立的主题。因此，知识单元社区结构可以作为文档主题划分的依据。

基于知识地图社区结构的文档主题划分的实现过程如图1所示，可以分为两个部分：文档主题划分模型的构建和待划分文档的主题划分。

文档主题分类模型的构建分为三个步骤：

1、领域知识地图主题体系构建：首先，提出基于Fast Greedy算法（FastGreedy算法是由Newman等人提出的一种凝聚式社区发现算法，初始时每个节点都是一个社区，然后计算网络中任意两个社区聚合后的社区模块度增量，选取其中增量最大的两个社区进行合并；该过程递归进行，直到模块度不再增大）和GN算法(GN算法是由Girvan和Newman提出的一种分裂式社区发现算法，执行过程中不断计算网络中边的边介数；每次选取边介数最大的边从网络中删除，直到模块度不再增大）的层次社区发现算法，对领域知识地图进行社区划分，得到领域知识地图的社区结构树；社区结构树的每个节点表示领域知识地图的一个社区，同一社区的知识单元表现出主题一致性；其次，通过分析社区中心节点（即社区中使用知识单元的度中心度刻画的某种重要节点）确定社区主题，从而构建领域主题结构树，实现社区结构到主题结构的映射；

2、构建特征空间，计算各维度的特征向量值：将领域知识地图的所有知识单元作为特征项，构建特征空间；提取文档包含的知识单元，结合知识单元的度中心度，计算各维度的特征向量值；

3、构造训练数据集，训练主题划分模型：构造训练数据集，选择BR-SVM多标签分类算法，对训练数据集进行训练，得到文档主题划分模型。

对待划分的文档进行文档主题划分具体步骤如下：

1、文档特征向量表示：对于待划分文档d，应用文档主题分类模型的构建部分中步骤2所述方法，提取文档知识单元，得到待划分文档的特征向量X_d；

2、文档主题划分：将待划分文档的特征向量X_d作为领域文档主题划分模型M的输入，模型的输出即为文档的主题标签Y_d，根据Y_d和领域主题结构树T-Tree之间的对应关系，得出文档d的主题划分。

如图2所示，领域知识地图主题体系构建过程的具体实施步骤如下：

（1）领域知识地图预处理过程，将领域知识地图转换为简单无向图，并将转换后的领域知识地图作为社区结构树的根社区节点，将其加入到待分析节点队列CAQ中。社区节点的形式化表示如下：

CNode(V_C,Children,Parent)    （1）

其中，V_C表示社区节点包含的知识单元集合，Children表示社区节点的子节点集合，Parent表示社区节点的父节点；

（2）领域知识地图层次社区划分过程，从CAQ中取出队首节点CH，分别使用Fast Greedy和GN算法对CH对应的领域知识地图或其子图进行社区划分，并引入模块度阈值（缺省值为0.35）；若上述两种算法得到的社区划分结果对应的模块度值均小于0.35，则划分无效，执行步骤（3）；否则，对比上述两种算法划分结果对应模块度值，选取其中较大的模块度值对应的社区划分结果，创建其中每个社区对应的社区节点，作为CH的子社区节点，并将其加入CAQ队列；

（3）对CAQ中的所有节点进行步骤（2），直到CAQ队列为空，从而得到领域知识地图对应的社区结构树C-Tree，其形式化表示如下：

C-Tree(CNodeSet,croot,n)    （2）

其中，CNodeSet表示社区结构树的社区节点集合，croot表示社区结构树的根社区节点，n表示社区节点数，即网络中存在的社区个数；

（4）社区中心点分析，计算C-Tree中的每个社区节点所包含知识单元在社区对应的领域知识地图子图中的度中心度，选取中心度较大的节点集作为社区中心节点组CCNS；知识单元在社区对应的领域知识地图子图中的度中心度计算方法如下：

$>C_{\mathrm{deg}}\left({\mathrm{ku}}_i\right)=\frac{\mathrm{deg}\left({\mathrm{ku}}_i\right)}{\underset{i=1}{\overset{n}{\Sigma }}\mathrm{deg}\left({\mathrm{ku}}_i\right)},{\mathrm{ku}}_i\in \mathrm{KU}---\left(3\right)$>

其中，deg(ku_i)表示知识单元ku_i社区内的度，KU表示领域知识地图或其子图包含的知识单元集合；

（5）对CCNS中的知识单元，查找领域知识地图库，得到CCNS包含的核心术语集，结合知识单元的度中心度和核心术语在CCNS中知识单元出现的频次，计算核心术语的中心性权重W_Central，其形式化表示如下：

$>W_{\mathrm{Central}}^{\mathrm{term}}={\Sigma }_{\mathrm{ku}}^{\mathrm{CCNS}}C\left(\mathrm{ku}\right)*\delta (\mathrm{term},\mathrm{ku})---\left(4\right)$>

其中，C(ku)表示CCNS中知识单元的中心度，δ(term,ku)表示term在ku中出现的频次。选取中心性权重最大的核心术语作为社区的主题；

（6）对于C-Tree每个社区节点进行步骤（2），从而构建领域主题结构树T-Tree，实现社区结构到主题结构的映射，T-Tree形式化表示如下：

T-Tree(CTopicSet,troot，n)    （5）

其中，CTopicSet表示社区主题节点集合，troot表示主题结构树的根节点，n表示主题个数。社区主题节点形式化表示如下：

CTopic(Y_C,SubTopics,PTopic)      （6）

其中，Y_C表示社区主题标号，SubTopics表示主题节点的子节点集合，PTopic表示主题节点的父节点。

如图3所示，构建特征空间，计算各维度的特征向量值的具体实施步骤如下：

（1）构造特征空间，将领域知识地图中的所有知识单元作为特征项，构成多维度（每个知识单元即为一个维度）的特征空间；

（2）文档的预处理过程，将文档转换为纯文本形式（即txt文件），提取每个文档的文本段，使用基于向量空间模型的TF-IDF算法（基于向量空间模型的TF-IDF算法使用TF-IDF算法将文本表示为以术语为特征项的特征向量形式，借助向量之间夹角余弦来表示文档间的相似度）将文档的文本段与领域知识地图库的知识单元ku对应的文本段内容进行相似度匹配，若相似度达到阈值μ（缺省值为0.8），则认为文档包含ku，据此提取出文档包含的所有知识单元；

（3）计算特征空间中知识单元在领域知识地图中的度中心度（计算方法参见公式（3）），结合文档中知识单元的出现频次，将文档抽象为如下形式：X_j={W₁,W₂,...,W_i,...,W_n}，其中n表示特征向量的维度，W_i表示第i个特征项的权重，其形式化表示如下：

W_i=C_deg(ku_i)*kuf(ku_i,d)     （7）

其中，kuf(ku_i,d)表示知识单元在文档d中出现的频次，C_deg(ku_i)表示知识单元ku_i的度中心度。

构造训练数据集，训练主题划分模型的具体步骤包括：

（1）构造训练数据集，对于给定的训练数据集D中的每一个文档，使用步骤4所述方法提取其特征向量，结合领域知识地图社区结构树C-Tree和领域主题结构树T-Tree，将训练数据集抽象为如下形式：

D={(X₁,Y₁),(X₂,Y₂),...,(X_j,Y_j),...,(X_m,Y_m)}     （8）

其中，X_j(j=1,2,...,m)表示第j个文档的特征向量，Y_j(j=1,2,...,m)表示第j个文档的主题标签集合，其形式化表示如下：

Y_j={L₁,L₂,...,L_i...,L_k}      （9）

其中，m为训练集文档个数，k为社区主题个数；

（2）训练过程选择BR-SVM算法（BR-SVM方法采用“一对多”策略将多标签问题转化为多个二分类问题，并用成熟的二分类问题训练方法SVM对这一系列二分类问题进行训练），采用交叉验证方式，基于训练文档集D，训练得到文档主题划分模型M。