由于文本属于非结构化数据,为了将聚类算法应用在文本对象上,必须先对文本进行预处理。中文文本预处理的步骤一般包括分词、去停用词以及词性标注,本文利用中国科学院计算技术研究所分词系统ICTCLAS 5.0,在基本词库的基础上,加载中华烹饪文化本体中对应的词典,以完成上述三个步骤。

文本表示是将非结构化的数据转换为计算机可处理形式的过程。目前,常用的文本表示模型主要有向量空间模型、布尔模型与概率模型^{[ 23]}。本文借鉴VSM将文本表示为由特征项及特征项的权值组成的向量。其中,将基于概念的文本表示为公式(1),将基于非概念特征词的文本表示为公式(2):

以下将对上述公式中概念的映射与概念权值的计算方法、非概念特征词选择与其权值计算方法进行详细的介绍。

(1)基于概念的文本表示

①概念的映射

经过预处理后的文本可以看作词的集合,本文通过词与本体概念间的匹配,将词转换为概念,从而将文本表示为基于概念的向量模型。然而,由于中华烹饪文化本体中所包含的菜肴名、食材名常常包含许多同义词,如菜名“番茄炒蛋”又可叫做“西红柿炒蛋”、“西红柿炒鸡蛋”、“番茄炒鸡蛋”等,因此,如果将分词后的文本直接与本体概念/实例进行匹配,将会遗漏许多概念/实例。为解决这一问题,本文对中华烹饪文化本体中的各实例加注了标签(如“番茄炒蛋”包含label“西红柿炒蛋”、“西红柿炒鸡蛋”、“番茄炒鸡蛋”),通过将词与标签进行匹配来优化概念映射。具体匹配规则如下:

1)将词与大类下的概念(类)进行匹配,如果匹配,将词转换为相应的概念;如果不能匹配,执行步骤2);

2)将词与大类下的属性进行匹配,如果匹配,将词转换为属性所属的概念;如果不能匹配,执行步骤3);

3)将词与大类下的实例进行匹配,如果匹配,将词转换为实例所属的最低位概念;如果不能匹配,执行步骤4);

4)将词与大类下的各实例标签进行匹配,如果匹配,将词转换为相应实例所属的最低位概念;如果不能匹配,继续遍历下一个大类下的所有概念、属性、实例及实例标签,直至完成所有遍历后,执行步骤5);

5)将各文本中未能匹配的词标记为“未转换”,保存到新的向量中VT_i = {t₁, t₂,…, t_n},以待后续特征选择。

②高层级概念映射

在将词映射为本体概念后,为了实现不同粒度的聚类,进一步基于本体结构将低层级的概念映射为高层级的概念。在选择高层级概念时,可以根据领域本体结构与用户需求进行确定。鉴于中华烹饪文化本体所包含的概念层级较少,选用根节点下的第一层概念作为高层级概念,对该层之下的概念进行转换。

③特征概念的权值计算

在对高层级特征概念与所有层级特征概念进行权值计算时,为了消除文本长短对概念出现频次的影响,本文借鉴文献[24]的归一方法,将概念的权值定义为该概念在文本中出现的次数与该文本包含的所有概念出现次数的比值,公式如下所示:

其中,feq(c_ij) 为概念c_j在文本D_i中出现的次数。

(2)基于非概念特征词的文本表示

①非概念特征词选择

在将文本表示为基于概念的向量后,本文对未能转换为概念的词进行了进一步的特征选择。首先,根据词性标注筛选出其中的名词;其次,利用文档频率(DF)算法过滤无效高频词及出现次数过少的词,最终保留在2%-90%的文本中出现过的名词作为特征词。

②非概念特征词的权值计算

本文采用经典的TF-IDF算法对非概念特征词加以权值,用词频和文档频率共同表示非概念特征词对文本的贡献,公式如下所示:

其中,tf_ij是特征词t_j在文本D_i中出现的次数,df_j是文本集中含有特征词t_j的文档数目,N是文本集中文本的数目。

文本相似度是用来衡量两个文本之间的相似程度的度量,是后续文本聚类计算的基础。在上述基于高层级概念、所有层级概念与非概念特征词文本表示的基础上,本文分别计算了各自所表征的文本间相似程度。以基于高层级概念的文本相似度来表示第一层级文本相似度,以基于所有层级概念的文本相似度来表示第二层级文本相似度,并综合基于所有层级概念与非概念特征词的文本相似度结果,来表示第三层级的文本相似度,以更充分地表征文本内容,如图2所示:

图2

	Figure Option ViewDownloadNew Window
	图2 各层级文本相似度计算方法

为了充分利用本体包含的语义优势,在计算基于高层级概念与所有层级概念的文本相似度时,本文借鉴了近年来学者普遍的研究思路^{[ 5, 6, 21]},进一步考虑了特征概念间的相似度,以削弱传统文本相似度计算中词与词之间相互独立、缺乏语义关系的弊端。

(1)本体概念间语义相似度计算

在利用基于概念的文本表示计算文本间相似度时,除了对特征项权值进行运算外,本文进一步融入了本体概念间的语义相似度。在4类语义相似度计算方法中,借鉴了基于距离的语义相似度算法,通过计算两个概念在本体树状结构中的最短路径长度来量化它们之间的语义距离^{[ 14]},如公式(5)所示。同时,考虑到概念在本体层次树中的位置(所在深度),对各路径边加以权值^{[ 25]},如公式(6)和公式(7)所示:

其中,Length表示本体树状结构的最大深度,令根节点的层级为1,Length即树状结构中最底层节点的最大层级数。Dis(c_i,c_j)表示概念c_i和c_j之间最短路径的长度,Weight_i表示连接c_i和c_j的最短路径上第i条边的权值,Depth表示边所连接的上位概念所在的层级数。

此外,除了考虑概念间的上下位关系,本文对概念间具有的对象属性(Object Properties)关系也加以考虑,设其路径权值为1,如图3所示,进一步完善了概念间的相似度。

图3

	Figure Option ViewDownloadNew Window
	图3 本体概念间距离示意图

根据上述算法,“食材”与“餐馆”间的语义相似度为0.666 7,“食材”与“菜肴”间的语义相似度为0.833 3,高于其与“餐馆”间的相似度,与实际情况相似;“食材”与“禽肉”间的语义相似度为0.861 1,“食材”与“肉食”间的语义相似度为0.916 7,“肉食”与“禽肉”间的语义相似度为0.944 4,高于前两者,也与实际情况相似。从而可见,上述概念间语义相似度算法能够较好地运用于该领域本体。

(2)基于概念的文本相似度计算

基于概念的文本相似度是指借助于概念向量间的相似度来表示的文本内容间的相关程度。在三个层级的文本相似度计算中,无论是基于高层级概念还是所有层级概念,都涉及此基于概念的文本相似度算法。

本文借鉴Basili等^{[ 19]}提出的文本相似核(Document Similarity Kernel)算法,结合上述概念间的语义相似度,对基于概念的文本相似度进行了计算,具体算法如下所示:

其中,wc_ip是文本d_i中概念c_p的特征权值,wc_jq是文本d_j中概念c_q的特征权值,sim(c_p,c_q)是概念c_p与c_q间的语义相似度。

为了避免不同文本长短对计算结果的影响,需要进一步对公式(8)进行归一化处理,如下所示:

(3)基于非概念特征词的文本相似度计算

在第三层级文本相似度计算中,本文进一步考虑了非概念特征词对文本间相似度的影响,采用余弦相似度算法对基于非概念特征词的文本向量进行了相似度计算,具体算法如下所示:

其中,wt_ik是文本d_i中特征词t_k的特征权值,wt_jk是文本d_j中特征词t_k的特征权值。如果某篇文本中未能包括任何被选择的特征词,则将这篇文本与其他文本间的相似度置为0。

(4)各层级文本间相似度计算

由于第一层级与第二层级文本相似度计算都仅仅基于概念的文本相似度。因此,第一层级与第二层级的文本间相似度算法皆如下所示:

在第三层级的文本相似度计算中,本文综合考虑了基于概念的文本相似度与基于非概念特征词的文本相似度结果,第三层级的文本间相似度算法如下所示:

其中,α为调节因子,用以调节文本中概念与非概念特征词对文本相似度的影响,可通过实验或经验取得。

聚类算法主要可分为基于划分的方法、基于层次的方法、基于密度的方法等^{[ 23]}。其中,基于层次的聚类算法可分为自下而上的凝聚式和自上而下的分裂式两种类型。鉴于本实验样本量较少,基于层次的聚类算法能取得更精确的结果,本文在三个层级的文本聚类中皆选择了自下而上的凝聚式层次聚类算法。

在凝聚式层次聚类过程中,类间相似度是聚类的依据。类间相似度是指两个类中所有文本两两间相似度之和的平均值^{[ 24]}。具体算法如下所示:

其中,d_m是类cluster_i中的文本,d_n是类cluster_j中的文本,n_i和n_j分别是类cluster_i和cluster_j中包含的文本数。具体层次聚类过程如下:

输入:各层级文本间相似度矩阵Matrix_sim,希望达到的最终聚类数m。

输出:各层级聚类分析结果C₁=(c₁,c₂,…,c_m);C₂=(c₁₁,…,c_1p,c₂₁,…,c_2p,…,c_m1,…,c_mp);C₃=(c₁₁₁,…,c_11q,…,c_1p1,…,c_1pq,…,c_m11,…,c_m1q,…,c_mp1,…,c_mpq)。

①基于第一层级文本相似度对所有文本进行聚类;

②将每个文本看作一个类,构成类集(cluster₁,cluster₂,…,cluster_n);

③利用公式(13)计算每个类间的相似度;

④选择最大相似度的类对(cluster_i, cluster_j),将cluster_j中的文本合并入cluster_i中,构成新的类集(cluster₁,cluseter₂,…,cluster_n－1);

⑤不断重复步骤③和步骤④,直至剩余类数到达要求的第一层级聚类数目m;

⑥在第一层级聚类结果的基础上,利用第二层级文本相似度依次对第一层类下的文本进行第二次聚类,不断重复步骤③和步骤④,直至剩余类数到达要求的第二层级聚类数目p(当p大于各类中所含的文本数量n’时,聚类数目取n’-1);

⑦在第二层级聚类结果的基础上,利用第三层级文本相似度依次对第二层类下的文本进行第三次聚类,不断重复步骤③和步骤④,直至剩余类数到达要求的第三层级聚类数目q(当q大于各类中所含的文本数量n’’时,聚类数目取n’’-1)。

本文以《基于领域本体的专题库构建——以中华烹饪文化知识库为例》一文中所介绍的中华烹饪文化领域本体与其知识资源为例,从“菜谱”、“食材介绍”、“美食故事”、“各地美食攻略”4类文本集合中随机各抽取出50篇文本,构成实验数据,以验证上文所述聚类方法的有效性。

在对聚类质量评价中,本文选用熵的方法^{[ 26]},以度量各类中包含相关语料库中已分好的类别的程度,如下所示:

其中,n_j为类C_j中文本的数目,n_ij为第i个语料库内类别L_i被划分到第j个类C_j的文本对象的数目,即n_ij=|L_i∩C_j|;n为所有实验样本的个数。熵值越小,表示类内部一致性越高,聚类结果越好。

首先对实验文本开展第一层级与第二层级的聚类,聚类结果如表1所示:

表1

表1

表1 第一层级与第二层级文本聚类结果 类簇 所含样本数 文本概念结构 主题 C1 53 食材+菜肴+技法 菜谱 C2 52 菜肴+餐馆+食材 美食攻略 C3 52 名人+菜肴+食材 文化故事 C4 43 食材+少许其他概念 食材简介 C11 28 其他菜系+各类食材 除川菜外其他菜系菜谱 C12 25 川菜+各类食材 川菜菜谱 C21 27 菜系+各类食材 推荐各地著名菜肴的美食攻略 C22 25 餐馆+各菜系 推荐各地著名餐馆的美食攻略 C31 28 名人+各菜系 与名菜相关的文化故事 C32 24 名人+各类食材 与各地饮食相关的文化故事 C41 23 非蔬菜类食材 非蔬菜类食材简介 C42 20 蔬菜类食材 蔬菜类食材简介

表1 第一层级与第二层级文本聚类结果

表2

表2

表2 聚类结果熵值对比(a) 第一层聚类结果(类簇为4) 评价指标 熵值 类簇中所含样本数 C1 C2 C3 C4 基于领域本体的文本聚类 90.013 53 52 52 43 基于特征词的文本聚类 214.62 161 29 8 2

表2 聚类结果熵值对比(a)

表2

表2

表2 聚类结果熵值对比(b) 第二层聚类结果(各类类簇为2) 评价指标 熵值 类簇中所含样本数 C11 C12 C21 C22 C31 C32 C41 C42 基于领域本体的文本聚类 73.154 28 25 27 25 28 24 23 20 C1 C2 C3 C4 C5 C6 C7 C8 基于特征词的文本聚类 134.436 101 46 21 13 11 6 1 1

表2 聚类结果熵值对比(b)

从表2可见,本文所提出的基于领域本体的文本聚类效果较好,与原始的知识库分组情况相似,能有效提高文本的聚类精度。

此外,在进行第三层级文本聚类时,为获得最好的聚类结果,笔者对第三层级文本间相似度算法中调节因子α的取值进行了研究。聚类数目为3、α取不同值时的基于领域本体的文本聚类算法的聚类效果如图4所示:

图4

	Figure Option ViewDownloadNew Window
	图4 调节因子与熵值对应关系

图4显示随着α取值的增大,熵值呈缓慢下降趋势,即聚类效果越来越好;当α取0.8时熵值最小,聚类效果最好;然而,随着α进一步增大,熵值呈上升趋势,聚类效果降低。可以发现,在第三层级聚类的过程中,基于概念的文本相似度对文本聚类效果的影响较大,然而非概念特征词的引入对聚类效果起到了较明显的优化作用,因此,综合概念及非概念特征词的算法对提高文本聚类精度确实能起到较好的效果。