基于遗传算法的文本过滤模型及收敛性分析

朱振方,刘培玉,李少辉,赵 静,王乾龙

(1.山东师范大学信息科学与工程学院,山东济南250014;2.山东省分布式计算机软件新技术重点实验室,山东济南250014)

文本信息过滤[1]是指在大量的文本数据流中寻找满足特定用户需求的文本的过程,当前实现信息过滤的主要方法有合作过滤[2]和内容过滤[3]两类。基于内容的文本信息过滤是目前信息过滤研究的热点,而基于内容的信息过滤又分为基于统计的过滤方法和基于机器学习的过滤方法[3]。在基于机器学习的内容过滤方法中,核心部分是过滤模板的构建和更新。

1 相关背景

遗传算法[4]自20世纪70年代产生以来,很多机构和研究人员对其进行了广泛而深入的研究,取得了很多重要的研究成果,并使其应用领域迅速推广到优化、搜索、机器学习等各个方面,逐渐发展成为一种通过模拟自然进化过程解决最优化问题的计算模型。

基于内容的文本信息过滤是机器学习的重要组成部分,最早将遗传算法应用于机器学习是用来解决一些较为简单的学习问题,例如,Holland和 Reitman提出的CS-1系统[5]中将遗传算法首次应用于求解迷宫问题,Goldberg[6]则将遗传算法应用到工程控制中,这些研究产生了真正意义上的基于遗传算法的机器学习(Genetic-based Machine Learning,GBML)。

研究中发现,将遗传算法引入到文本信息处理特别是中文文本信息过滤的研究很少,主要集中在应用遗传算法进行特征选择以及将遗传算法应用于生成模板的实际应用。2000年,BURNS和 DANYLUK[7]首次将遗传算法应用到特征选择,接着,PAN Li等[8]将基于遗传算法的特征选择引入到文本分类领域,此后很多研究者提出了多种改进方案,文献[9]也提出了一种自适应遗传算法并将其应用到特征选择中。

近年来遗传算法在中文文本信息过滤中的应用研究除了吕志龙[10]等人外,则就是作者所在课题组基于遗传算法的文本分类和过滤模型的构建及其改进[11]。在吕志龙研究中,只是将遗传算法应用到模板优化,并没有直接应用遗传算法生成模板,而在作者所在课题组前期研究则着重于具体实现,并没有从理论上进行相应的证明。

本文针对应用遗传算法解决中文文本信息过滤问题建立了相应的问题模型,并在理论上证明其可行性。同时,还根据在实际应用中存在的问题,引入了自适应策略解决应用过程中存在的问题。

2 问题空间描述

文本信息过滤从一定程度上可以看作是一种二值文本分类,它将待过滤文本映射到一个合法文档集或非法文档集。上述过程可用形式化的数学语言表述如下：

对于每个＜di,ci＞∈D×C,其中D为待过滤文档集,di为D中的一个文档,C为类别集,C中含有两个值c1和c2,分别为过滤文档集和正常文档集,判定其布尔值,若其为真(T),则文档di属于类别c1,否则(F)不属于c2,文本信息过滤过程就是构造函数α：D×C⇒{T,F}。

2.1 文本预处理

基于向量空间模型的信息过滤中,需要首先对训练文档di进行分词,把di表示成一系列特征项序列c1c2c3…ck…cn,并对这些文本计算权重信息wk,从而形成按照类别划分切词和权重计算结果。

2.2 问题编码及初始种群生成

在遗传算法寻优过程中,需要将问题空间进行编码,然后才能运用遗传算法计算。在中文文本信息过滤中,采用一种改进的二进制编码方式。具体方式如下。

1)使用随即发生器随机产生一个二进制序列,该二进制序列长短则代表基因串长度;

2)将该二进制序列同预处理后的类别切词结果进行逻辑与操作;

3)将计算结果作为问题求解的一个个体,依次生成问题空间的个体构成初始种群。

由此生成的基因串长度是有限的,这使得系统中不再需要专门的降维操作,编码同时就等于同时实施了降维。

2.3 个体适应度衡量

适应度函数表明个体对环境适应能力的强弱,不同问题适应度函数的定义方式不同。在求解中文文本信息过滤的遗传算法计算过程中,最终要生成进行内容过滤的模板,该模板应该是能够代表类别空间的最佳个体,因此必然能够与相同类别的待过滤文档具有较大的相似度而与其他类别文档具有较小相似度,因此在应用中把个体之间的相似度作为适应度函数是一种可取方案[11]。

而课题组在应用过程中,通过实验验证和比较各种方案的基础上[11],发现使用适应度差的绝对值作为评价个体优劣的标准更为恰当。

定义1：个体间相似度

individual[i]、individual[j]表示遗传算法中第i和第j个个体,weight[i]、weight[j]分别表示第i和第j个个体的权重。

定义2：平均相似度

其中group_size表示种群大小,其他变量同定义1。

3 收敛性分析

在遗传算法收敛性分析方面,主要有模式定理[12]、随机理论[13]以及动力学原理[14]等几个方面,王丽薇[15]等提出了一种应用集合论的证明方法,本文将借鉴该方法分析上述优化问题的收敛性。

3.1 问题归约

中文文本信息过滤问题在一定程度上属于文本分类问题,解决了文本分类问题则文本信息过滤迎刃而解,但是多类别文本分类属于多维空间判断问题,在多维空间上讨论敛散性具有很大困难。因此,我们可以将中文文本信息分类和过滤问题转化到二维空间讨论其敛散性。

3.2 相关定义

在该收敛性分析中,涉及以下几个定义：

定义1：问题的解

设问题空间为I,C={1,2…n}k是问题解的一个编码结果,针对C中的每一个可能解,在问题空间I都有一个点与之对应。反之不一定成立。

定义2：空间转变函数

用f表示空间转变函数,称为强度函数,令其定义域为问题空间I,值域为目标函数值域,则函数f可定义为一个映射I中的每一个点i,如果i对应于一个解,则令 f(i)等于目标函数在i点的值;否则,令 f(i)等于目标函数的最小值。

通过空间转变函数将问题空间的解转化为强度函数 f的二维空间解集。在该二维空间集合上,我们可以定义相关类的定义,用以讨论在二维空间集合上讨论复杂问题的敛散性。

定义3：类的概念

集合S称为一个类当且仅当S⊆I,类S在种群POP的强度为类S在种群中所有个体平均强度;对于类S,如果存在 f(S,POP)≥f(POP,POP),则成为类S在种群中占优势;如果类S在任何一个种群中都占优势,则称为S为一致类。如果存在强度函数值域V中的一点r,S包含且仅包含问题空间中强度函数大于r的个体,即：

则S成为一个优类。

定义4：一致类判定

类S是一致类当且仅当其是优类。

之所以定义优类,是因为一致类的可操作性太差而定义4给出了一个可操作的直观方法。

3.3 收敛性假设

最优解包含在任何优类中,所有优类的交集就是最优解。由定义4可以看出,优类等价一致类,因此,如果种群中一致类所占的比例不断增加,则搜索空间缩小,其方向就是一致类交集的方向,理论上讲遗传算法能收敛到最优解。

但是这种稳定性很容易被破坏掉。基于这个原因,如果遗传过程能够找到最优解就要保证上述一致类集合不被代替或者消失,因此提出如下假设：

收敛性假设

如果S为一致类,POP为种群,则对任意竞争类S′,如果：

下面两个条件则必有一个成立：

(1)S′中的个体均在S 中,即 S′∩POP⊆S;

(2)S′和S交集(即同属于S′和S的的个体)强度均大于或者等于S′强度,即 f(S′,POP)≥f(S,POP)。

上述收敛假设中无论哪种情况发生,S′在下一代中都不会取代S,而只能一起获得增长,这就保证了一直模式不会被其他类所取代。

从上面定义和假设中可以看出,在遗传操作情况下,如果S在遗传操作中是近乎封闭的,则类是稳定的,那么也就能找到最优解。如果不完全封闭的情况下就要考虑稳定程度,稳定性保证了类在遗传操作中不会被取代,只有这样的类才能在遗传运算中被传递,对遗传算法才有意义。因此,在遗传算法中我们只考虑这种类,而不稳定类,即使它强度再高,也不能被遗传进化,我们不必考虑。

3.4 问题收敛性分析

由上述可以得出这样的收敛性结论：如果一致类具有稳定性,遗传算法就可以收敛到最优解。任何问题空间只要满足这个条件,我们就认为可以用遗传算法进行求解,并有希望获得最优解。

信息过滤特征项是从训练文档中抽取的,而训练文档是静态的,这就决定了用遗传算法求解信息过滤问题是相对封闭的过程,通过本文第2节给出的基于遗传算法的信息过滤模型,并结合本节相关定义我们可以认为本文所给出的基于遗传算法的信息过滤可以收敛。也就是说从理论上来讲本文所给出的模型是有效的。

4 应用分析

课题组将遗传算法应用到网络信息过滤中生成过滤模板,其主要原理在本节加以介绍。

4.1 训练集

训练文档采用了复旦大学计算机信息与技术系国际数据库中心自然语言处理小组李荣陆整理中文文本分类语料,共9804篇文档,分为 20个类别。其中文学、教育等11个类别其文档数不超过100篇,计算机、环境、农业、经济、政治以及体育等六个类别文档数超过1000。由于算法最终要应用于信息过滤,因此项目组又自行收集了暴力、色情两个类别分别276和192篇文档,共计八个类别7947篇文档用于训练。训练文档分布如表1所示：

表1 训练文档分布

4.2 测试集

测试集则主要包括封闭测试集和开放测试集。①封闭测试集：将复旦大学计算机信息与技术系国际数据库中心自然语言处理小组李荣陆整理的中文文本分类语料中不超过100篇文档的11个类别共计502篇文档与从训练集每个类别随机抽取的50篇文档组成训练集共计902篇测试文档。②开放测试集：中国科学院计算技术研究所谭松波整理的中文文本分类语料库-T anCorpV1.0,该语料库分为两个层次,收集文本14150篇,第一个层次为12个类别,本文即从第一层次中与训练文档相关的财经、电脑、体育共三个类别中每个类别随机选取200篇混合组成测试文档。

4.3 开发和运行环境

预设种群规模大小为400,染色体数目为200,最大遗传代数为1000,变异率和交叉率分别预先设置为0.015和0.6。相关实验在一台方正PC上进行,处理器为Intel(R)Core(TM)Duo CPU E7200@2.53HZ,内存为2G,开发环境为Visual Studio2005,开发语言为C#。

4.4 考查参数

1)单类测试方案

目前信息过滤和文本分类中普遍使用的性能评估指标为准确率(Precision,简记为p)、召回率(Recall,简记为r)。对于文档类中的每一个类别,使用列联表(Contingency Table)来计算召回率和准确率。表2为一个列联表实例。

表2 单类列联表(Contingency Table)

此时,准确率(precision)、召回率(recall)定义如下：

2)整体考查策略

上述列联表只能对单个类别分类效果进行评估,如果要对分类性能做一个全面评价,通常引入宏平均[16]概念,其计算方式为对每个类计算 p和r值,然后对所有类求其平均值,即：

4.5 文本分类实验

为保证实验效果,试验中单词切分部分应用河北理工大学经管学院吕震宇根据计算所汉语词法分析系统ICTCLAS改编.net平台下的SharpICTCLAS,该切词程序理论准确率为97.58%,模板生成应用遗传算法进行训练。主要从文本分类和信息过滤两个方面进行比较。

4.5.1 在测试数据1上的测试

如表3所示,为本文所提出的方法在测试数据1上的各个类别准确率。

表3 在测试数据1上的各类准确率

在表3所示的实验数据中,经分析可以发现,在分类效果较差的两种类别中,训练文档中文章存在一些相似之处,如政治类别往往包含到经济、环境、农业等因素,因此造成其准确率较低。

为考查该方法分类效果,应用了上述测试方法中的宏平均评价方式,经计算,上述数据平均准确率为=85.810,我们将该数据同近年来在Reuters-21578上的几种基本方法进行了比较,其比较数据如图1所示。

图1 改进方法平均精度比较

上图中,GA代表文中所叙述方法,NB表示Naive Bayes方法,DT表示 Decision Tree方法,KNN表示最近邻分类方法,而SVM为支持向量机,上述几组数据[15]系近年来报道的在Reuters-21578语料的最好分类效果。

4.5.2 在测试数据2上的测试

上述实验数据中,该改进的计算方法能够取得较好的效果,但是,我们不能排除上述实验结果是在数据1的基础上得到的,可能存在一定的过度拟合问题,因此设计了应用上述第二组测试数据进行了进一步测试,其分析数据如表4所示。

表4 在测试数据2上的准确率比较

上述实验数据中,就准确率来讲,其中电脑财经类与封闭测试虽然略有下降,但是相差不大,而体育类则具有较大差距,究其原因,分析训练文档和测试文档即可发现,原训练文档中有关体育类中均属于体育理论研究,而测试文档则来源于网络,因此二者具有较大差距。

4.5.3 信息过滤实验测试

鉴于研究目的在于应用到基于内容的信息过滤中,因此设计该试验将上述分类器应用于网络信息过滤的测试实验。试验中将实验室测试数据1划分成了两个大类,即合法文档和非法文档,其中的非法文档由测试数据1中的色情和暴力文档组成,而合法文档则由其他六个类别随机选取组成,实验数据构成以及测试结果如表5所示。

表5 过滤效果测试统计数据

我们将上表中的过滤数据同文献[18]进行比较,本文中所给方法不论在哪个类别上,都明显好于文献[18]所给出的数据,因此本文方法具有较好的过滤效果,同时,从表中也可以看出,非法文档等具有鲜明特色的类别具有更好的分类效果,而我们最终要过滤的就是该类不良信息,因此本文方法的应用是有效的。

5 遗传参数的自适应调整

研究过程中发现,遗传算法进化过程随机性太大,而在前面进化较慢而后面进化太快,容易陷入局部最优,通过绘制适应度变化曲线,我们也发现,遗传过程容易反复,这使得局部最优不可避免。

图2给出了类别“体育”在遗传算法运行过程中适应度值随时间变化的曲线。

图2 适应度变化曲线

图2可以看出,训练过程中相似度差越来越小,也就是说适应度值越来越大,即生成的个体越来越好,这也就从实验的角度证明了基于遗传算法的方案的可行性。
但是,上图中也发现选取的数据点中存在一个奇异点,这就是说在训练过程存在反复现象,这是因为遗传算法应用过程中采用了固定交叉和变异操作,针对该问题,很多研究者提出了自适应修改策略[19]。

5.1 参数调整策略

课题组研究过程结合相关研究引入了一种改进的变交叉率和变异率操作。

max_f itness,f itness[i]及max_gen分别是当前代中最大适应度值、待变异个体的适应度值及预设的最大代数,max_pm和min_pm分别是预设的最大变异率和最小变异率,t为当前进化代数,pm为当前代中个体的变异率。x和temp是中间计算变量 ,且

5.2 实验结果比较分析

该部分采用同4.2中实验结果相同的实验设置,其适应度变化曲线图3所示。

从图3可以看出,适应度曲线明显比图2具有更加明显的收敛特性,该改进策略是有效的。

6 结束语

论文通过分析遗传算法以及中文文本信息过滤的特点,从理论以及实验分析了其可行性,并结合实验中存在的问题提出了遗传算子的自适应策略。理论以及实验分析均发现,该方法能够解决中文文本信息过滤问题。

图3 自适应策略适应度变化曲线

下一步主要针对基于遗传算法网络信息过滤模型进行改进,提高其分类准确率,同时考虑结合蚁群算法解决遗传算法在后期存在的遗传速度较慢、容易陷入局部最优问题。

[1]Belkin N.J.,Croft W.B.Information Filtering and Information Retrieval：Two Sides of the Same Coin[J]Communications of the ACM,1992,35(12)：29-38.

[2]崔宝侠,任重,段勇.基于用户兴趣的电子商务推荐方法[J].沈阳工业大学学报,2009,31(5)：573-576.

[3]方娟,梁文灿.一种基于协同过滤的网格门户推荐模型[J].电子与信息学报,2010,32(7)：1585-1590.

[4]John H.Holland.Adaptation in Natural and Artificial System：an Introduction with Application to Biology,Control and Artificial Intelligence[M].Ann Arbor,U-niversity of Michigan Press,1975.

[5]John H.Holland.Adaptation in Natural and Artificial Systems：An Introductory Analysis with Applications to Biology,Control,and Artificial Intelligence[M].The M IT Press,1992.

[6]Goldberg D E.Genetic Algorithms is Search,Optimization,Machine Learning[M].Reading MA：Addison Wesley,1989,29-48.

[7]Burns,Danyluk.Feature Selection vs Theory Reformulation：A Study of Genetic Refinement of Knowledge-based Neural Networks[J].Machine Learning,2000,38,89-107.

[8]PAN Li,ZHENG Hong,ZHANG Zuxun,et al.Genetic Feature Selection for Texture Classification[J].Geospatial Information Science(Quarterly).2004,7(3)：163-173.

[9]LIU Peiyu,ZHU Zhenfang,XU Liancheng,CHI Xuezhi.Optimization of a Subset of Features Based on Fuzzy Genetic Algorithm[C]//Proceedings 2009 IEEE International Symposium on IT in Medicine&Education,2009,2(2)：933-937.

[10]吕志龙.基于遗传算法的自适应文本过滤方法的研究[D].哈尔滨：哈尔滨工程大学,2007.

[11]ZHU Zhen-fang,LIU Pei-yu,ZHAO Li-na,et al.Research of Feature Weights Adjustment Based on Semantic Paragraphs Matching[J].ICIC Express Letters,2010,4(2)：559-564.

[12]Holland J H.Adaptation in Natural and Artificial System：An Introductory Analysis with Application to Biology,Control,and Artificial Intelligence[M].2nd Edition,Cambridge,MA：MIT Press,1992：96-127.

[13]Christopher T.H.Baker,Evelyn Buckwar.Numeri

cal Analysis of Explicit One-Step Methods for Stochastic Delay Differential Equations[J].LMS Journal of Computation and Mathematics,2000,3：315-335.

[14]郭东伟,刘大有,周春光,等.遗传算法收敛性的动力学分析及其应用[J].计算机研究与发展,2002,39(2)：225-230.

[15]王丽薇,洪勇,洪家荣.遗传算法的收敛性研究[J].计算机学报,1996,19(10)：794-797.

[16]Muhammad Arifur Rahman.Performance Evaluation for Question Classification by Tree Kernels using Support Vector Machines[J].Journal of Computers,2010,5(1)：32-39.

[17]苏金树,张博峰,徐昕.基于机器学习的文本分类技术研究进展[J].软件学报,2006,17(9)：1848-1859.

[18]朱振方,刘培玉,王金龙.一种基于语义特征的逻辑段落划分方法及应用[J].计算机科学,2009,36(12)：227-230.

[19]刘胜,赵红.遗传交叉和变异对种群多样性的影响[J].控制与决策,2009,24(10)：1535-1539.