分类算法在范例推理中的研究与应用

刘连喜，邢 彤，徐 浩，王 伟，高 凯

（1.河北科技大学财务处，河北石家庄 050018；2.河北化工医药职业技术学院，河北石家庄 050026；3.河北科技大学信息科学与工程学院，河北石家庄 050018）

分类算法在范例推理中的研究与应用

刘连喜1，邢 彤1，徐 浩2，王 伟3，高 凯3

（1.河北科技大学财务处，河北石家庄 050018；2.河北化工医药职业技术学院，河北石家庄 050026；3.河北科技大学信息科学与工程学院，河北石家庄 050018）

将范例推理中的范例初步匹配看作文本分类的特殊情形，提出基于类别中心向量的分类算法。通过确定待处理案例的归属类别，缩小范例检索范围，减少在范例精确匹配阶段的计算量，提高案例初步匹配的准确性。在此基础上，将上述算法应用在对交通事故案例的处理与交通信息预警系统中。实验与使用表明，该算法能较为准确地判断事故类型并给出相应的预警信息。

人工智能；自然语言处理；分类；信息检索；范例推理

范例推理（case－based reasoning，CBR）作为基于规则推理技术的一个重要补充，是当前人工智能及机器学习领域中的热门课题与前沿研究方向之一。CBR的执行过程如图1所示，主要包括检索相似案例、重用相似案例并推断新案例解决方案、修订解决方案、保存新案例以备后用等。由于CBR具有信息的完全表达、增量式学习、形象思维的准确模拟、求解效率高等特点，因此能够应用在那些没有很强的理论模型和领域知识不完全的决策环境中［1］。目前，关于范例推理的研究主要集中在以下几个方面：范例的索引及检索技术，范例修正技术及其修正规则的获取方法，范例库的维护技术及其性能的研究，范例工程的自动化，范例推理的理论基础，范例推理与其他方法（包括学习技术、多Agent技术、推理方法、数据挖掘、数据仓库技术）的集成技术，范例推理的应用，研制CBR开发平台，CBR融合及大规模并行处理，基于Web的分布式CBR系统，可视化CBR技术及对话式CBR模型等［2－5］。

图1 CBR执行过程Fig.1 Process of CBR

由于交通事故发生的原因和案发现场的勘察结果之间往往有着一定的因果联系，因此通过对事故勘查的特征提取，并通过相应的匹配算法，将所抽取出来的新案例特征与范例库中典型事故案例——指那些已成功处理、具有某些典型的特征属性进行比较，检索那些较符合的事故案例，找出相应事故的解决方案，并由分析得出相应的预警信息是可行、可信的。基于CBR的交通事故处理及其预警机制研究，可为处理类似的交通事故案件提供决策参考。但一般的范例推理过程在检索源范例时，往往存在着检索结果不准确、检索效率低下等问题。如果能在检索范例之前，通过适当的分类算法，确定新案例最可能归属的类别，然后再在其所属类别范围里通过相似度查找最近似的部分范例，就可以有效缩小范例检索的范围，提高范例检索的效率和准确率。在此将范例的初步匹配问题看作文本分类问题的特殊情形，提出基于类别中心向量的分类算法，并将其应用到范例推理的初步匹配阶段。从空间几何角度看，计算平均向量的过程就是计算多维空间中1个点集群中心的过程，只要1个点处于以这个中心和一定半径所划定的空间区域里，就可以认为该点所代表的案例归属于这个中心向量所代表的类别。在前期工作基础上，通过分类算法首先确定待处理案例的归属类别，减少了在范例精确匹配阶段的计算量，提高了范例推理系统整体性能。通过对公路车辆监控与交通事故处理（数据分析）的应用表明，该算法能较为准确地判断事故类型并给出相应的预警信息。

1 范例的组织及其向量化表示

在CBR及其推理过程中，首先要明确范例库及其组织方式。在本应用中，范例库中所有交通事故范例按事故原因被分成8个类存储，相同类别的范例保存在以类别名称命名的文件夹中，各种信息用不同字段标志符表示出来。当有新的案例到来时，首先依据类别中心向量分类算法确定新范例的归属类别，然后计算新范例与其归属类别中每个范例的语义相似度，如果相似度大于阈值，就认为新范例与已有范例相似，不再储存，否则将新案例的信息数据以文本文件的形式保存到所属类别的文件夹里。

当完成了范例的向量化表示后，就构建起了范例库的向量空间模型，之后才能在这个向量空间里实现分类算法。为了便于将范例内容映射入向量空间，使用中科分词模块ICTCLAS对范例的正文文本进行分词处理。即首先将范例正文中的所有非中文字符替换为空格符，使用分词模块对预处理的范例正文进行分词，根据停用词词典去除分词结果中的停用词。要想实现范例的向量化表示，须首先建立向量模板，之后可以依据向量模板实现范例的向量化。向量模板的构建过程大致分如下4个步骤。

1）逐篇扫描范例库每个范例正文的分词结果，分别统计各词项在所属范例正文中出现的词频（TF）和各词项在所属范例类别中出现的文档数（DF）。

2）选择特征词。采用TFIDF算法作为特征词权值的计算方法，计算公式如式（1）所示，其中IDF是词条t的逆文档频率，m是某一类别文档中包含词条t的文档数，n是包含词条t的文档总数。

3）将所有词项按照IDF值从大到小排列，再根据预先设定的最大向量维数k选取IDF最大的前k个词项作为特征词项。为了统一所有特征词项的分布概率，需要对特征词的IDF值进行归一化处理，具体方法如式（2）所示，式中IDFi表示第i项特征词的IDF值，max（·）函数表示所有特征词项中最大的IDF值。

在构建了向量模板以后，就可以依据向量模板实现范例的向量化表示了，主要步骤如下。

1）将范例正文中的非中文字符替换为空格，用分词模块对其进行分词。

2）统计每个范例中各词项的文档频率TF。考虑到范例正文长度的差异，须依据范例正文长度对每个词项的文档频率进行归一化处理，计算公式如式（3）所示，其中TFi是范例中词项i的文档频率，li是范例正文长度。

为了统一范例中词项的分布概率，还需要对词项的TF值进行归一化处理，见式（4），式中max（·）是范例正文所有词项中最大的TF值：

在完成向量归一化后，扫描范例分词结果中的每个词项。当把一个范例正文分词结果中所有词项扫描完毕后，就得到了该范例的空间向量。

2 类别中心向量的分类算法及其应用

类别中心向量是用各个类别的中心向量来代表相应类别，并且根据新来的案例向量与各类别中心向量的相似程度来判别新案例所归属的范例类别。算法处理流程见图2。

图2 类别中心向量分类算法流程图Fig.2 Flow chart of the class－center vector based category algorithm

在建立了范例的向量空间模型以后，各范例都表示为向量的形式。笔者采用算数平均的方法来计算各类别的中心向量，计算公式如式（5）所示，式中Vcenter为某文档类别的中心向量，W1为范例向量中第1维向量的权重，Wj为范例向量中第j维向量的权重，ni为文档类别i中包含的文档数：

通过上述步骤计算得到了各范例类别的中心向量、中心向量常数以及各类别的分类阈值后，就可以着手生成类别中心向量分类算法中的分类器模型。为了便于各种类型数据的统一存储，采用XML文件格式保存分类器模型。当某个类别的中心向量需要动态修正时，XML文件可以方便地读取和保存相应类别的中心向量。图3是分类流程。范例推理系统的输入数据就是待处理的交通案例，输出就是交通事故的处理方案和某一时段的交通预警信息。在得到（或者用户输入）新案例后，首先将新案例的数据进行向量化处理，然后应用提出的分类算法来确定新案例所属的类别，从而实现案例的初步匹配。之后，就可以在新案例所属的类别内利用向量的相似度算法为新案例找到最为相似的范例，从而实现案例的匹配，最终实现交通事故案例的范例推理过程，并借助它辅助交通处理事故。

3 实验分析与测试

图3 分类流程Fig.3 Flow of the category

分别在不同的训练和测试样本集中，在不同的兼取类别情况下，对类别中心向量分类算法在交通范例推理系统中的应用性能进行了测试。表1是在封闭性测试情况下，测试兼取类别数对分类器性能的影响。

表1 封闭性不同兼取类别测试Tab.1 Colse test on different compatibility numbers of the category

从表1数据可以看出，兼取类别数增加后，分类器的性能得到了显著提高。可见在对交通案例进行初次匹配时，必须考虑兼类的情况，这也是符合客观事实的。

在交通案例的选取上，基础案例的缺乏是一个不可避免的问题。由于行业数据的保密性，这里采用的是从网上收集的一些案例来充当范例库的素材。尽管本文提出的算法有效实现了案例的初步匹配，但是该分类算法的性能还有提升空间，所以下一步还要在改进分类算法性能上再做一些工作。

4 结 语

将范例的初步匹配问题看作文本的分类问题，提出基于类别中心向量的分类算法，并将其应用到范例推理系统的初步匹配阶段。通过分类算法首先确定待处理案例的归属类别，有效缩小了范例检索的范围，减少了在范例精确匹配阶段的计算量，提高了范例推理系统整体性能。实验与使用表明，该算法能较为准确地判断事故类型并给出相应的预警信息。

［1］ 刘 芳.基于CBR的智能决策支持系统研究与应用［D］.兰州：兰州大学，2008.

［2］ 陆汝钤.世纪之交的知识工程与知识科学［M］.北京：清华大学出版社，2001.

［3］ 陈文伟.决策支持系统及其开发［M］.北京：清华大学出版社，2000.

［4］ 周 勇，贾瑞玉.范例推理在智能决策系统中的应用研究［J］.电脑知识与技术（学术交流）（Computer Knowledge and Technology（Academic Exchange）），2007（3）：824－829.

［5］ 王 伟，许云峰，高 凯.基于哈希表的动态向量降维方法的研究及应用［J］.河北科技大学学报（Journal of Hebei University of Science and Technology），2011，32（4）：360－365.

Study on catagory algorithm and its application in cased－based reasoning

LIU Lian－xi1，XING Tong1，XU Hao2，WANG Wei3，GAO Kai3
（1.Finance Department，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China；2.Hebei Chemical and Pharmaceutical College，Shijiazhuang Hebei 050026，China；3.College of Information Science and Engineering，Hebei University of Science and Technology，Shijiazhuang Hebei 050018，China）

This paper presents the class－centre vector based category algorithm，which is regarded as the basis of the text classification in case－based reasoning application.On the basis of the proposed algorithm，this method can be used to determine those cases＇affiliation，and as a result this can reduce the retrieval scope so as to reduce the calculation and improve the precision.We use the proposed algorithm in the traffic accident analysis and the corresponding early warning system.The experimental results and the analysis prove the feasibility of the approach，and the existing problems and further works are also discussed in the end.

artificial intelligence；natural language understanding；category；information retrieval；case－based reasoning

TP274

A

1008－1542（2012）02－0150－04

2011－11－17；责任编辑：李 穆

河北省科技支撑计划资助项目（074572172）

刘连喜（1965－），女，河北高邑人，高级会计师，主要从事信息管理、会计理论与电算化技术等方面的研究。

高 凯副教授。E－mail：gaokao68＠163.com