关系分类算法

2024-09-26

关系分类算法（精选7篇）

关系分类算法篇1

0 引言

Vapnik等人提出的统计学习理论SLT(Statistical Learning Theory)[1]是一种针对小样本情况研究统计学习规律的理论,该理论的核心思想是通过引入结构风险最小化准则来控制学习机器的容量,从而刻画了过度拟合与泛化能力之间的关系。在这一理论基础上产生的支持向量机SVM(Support Vector Machines[2,3])学习方法近来受到广泛重视,该方法不但引入了结构风险的概念,还采用了核映射的思想,与传统方法相比,支持向量机所具有的优势体现在:即克服了传统方法的大样本要求,还有效地克服了维数灾难及局部极小问题,并在处理非线性问题时显示了其卓越的优越性。支持向量机以其出色的学习性能已经广泛用于解决分类与回归问题,随着其应用领域的不断扩大以及在应用中遇到的问题也反过来要求支持向量机本身不断完善和发展。支持向量机分类算法通过求两类样本之间的最大间隔来获得最优分离超平面,其几何意义相当直观,而回归算法的几何意义就不那么直观了。另外,有一些适用于分类问题的快速优化算法却不能用于回归算法中,因此,研究分类与回归之间的关系就显得很有意义。本文讨论了分类与回归算法之间的关系,利用回归样本集因变量的上下平移将回归问题转化为分类问题,然后从理论上证明了分类与回归问题的等价性。

1 从回归到分类

文献[4]通过变量代换给出了支持向量机分类与回归之间的关系,并指出分类是一种特殊的回归。下面直接给出非线性情况下的分类与回归算法。这里采用一个非线性映射ϕ将数据映射到一个高维特征空间,然后在高维特征空间中进行线性分类与回归运算,其中涉及到的高维内积运算用一个核函数来代替,这也正是支持向量机在处理非线性问题时的巧妙所在。

给出训练样本集为:

(xi,yi) xi∈Rni=1,…,l

对于分类情况,yi∈{+1,-1},对于回归情况,yi∈R。

分类问题是解下面的二次规划:

$\min \frac{1}{2}$ w2+C $\sum_{i = 1}^{l}$ ξi (1)

约束为:

yi(〈w,ϕ(xi)〉+b)≥1-ξii=1,…,l (2)

ξ1≥0 i=1,…,l (3)

在回归问题求解中,设回归函数为:

f(x)=〈w,ϕ(x)〉+b (4)

回归问题归结为解下面的二次规划:

$\min \frac{1}{2}$ w2+C $\sum_{i = 1}^{l}$ (ξi+ξi*) (5)

约束为:

在支持向量回归中,y取连续的实值,而不是二元值。但实际上并没限制y取二元值。假设y∈{+1,-1},在训练样本集上进行回归操作,可以得到下面的定理。

定理1 设在规划参数C下分类问题(1)的最优解是(w,b),则存在一个a∈(0,1),对于∀ε∈[a,1)时,回归问题(5)在规划参数(1-ε)C下的最优解是(1-ε)(w,b)。

该定理的证明可以参考文献[4],这也表明分类问题完全可以通过回归方法来求解,分类是一种特殊的回归。

2 从分类到回归

文献[5]从另外一个角度给出了一种基于闭凸包收缩的最大边缘分类算法,其优化问题的几何意义清楚、明确,并且还将该分类算法应用于函数回归中[6],从而能很好地给出回归问题的几何意义。该方法首先通过样本集因变量的上下平移ε将回归问题转化为分类问题,然后求两类集合收缩闭凸包之间的最小距离,最后根据最小距离点求得的最大间隔分离超平面得出回归函数,从而建立了分类与回归之间的关系。下面应用前面的思想将支持向量机回归问题转化为分类问题,并从理论上证明这种转化的等价性。

标准的支持向量机回归算法引入两个参数ξ、ξ*来控制误差的大小,如优化模型(5)。文献[7]采用一个参数来控制误差,进而给出单参数约束下的支持向量回归算法。

在ε-不敏感损失函数下,采用一个参数来控制误差项,可得下面的优化问题:

$\min \frac{1}{2}$ w2+C $\sum_{i = 1}^{l}$ ξi (9)

约束为:

f(xi)-yi≤ξi+ε i=1,…,l (10)

ξi≥0 i=1,…,l (11)

则有下面的定理。

定理2 优化问题(9)与优化问题(5)的最优解是等价的。

该定理表明单参数约束下的回归模型与标准回归模型是等价的,下面建立单参数约束下的回归模型与分类之间的关系。将单参数回归模型的约束条件的绝对值符号去掉,优化问题为:

$\min \frac{1}{2}$ w2+C $\sum_{i = 1}^{l}$ ξi (12)

约束为:

yi-〈w,ϕ(xi)〉-b≤ε+ξii=1,…,l (13)

〈w,ϕ(xi)〉+b-yi≤ε+ξii=1,…,l (14)

ξi≥0 i=1,…,l (15)

为了建立回归与分类之间的关系,下面通过因变量的上下移动ε+1获得两个集合:

D+={(ϕ(xi),yi+ε+1),i=1,…,l}

D-={(ϕ(xi),yi-ε-1),i=1,…,l}

当ε充分大时,D+和D-显然是线性可分的。当然不必要保证完全线性可分,可以通过引入松弛变量ξ允许一定的误差存在。

对上面两个集合进行SVM分类,优化问题为:

$\min \frac{1}{2}$ $\bar{w}$ 2+C $\sum_{i = 1}^{l}$ ξi (16)

约束为:

$〈 \bar{w} ‚ z_{i} 〉 + \bar{b} - ξ_{i} \leq - 1 z_{i} \in D^{+}$ (17)

$〈 \bar{w} ‚ z_{i} 〉 + \bar{b} + ξ_{i} \geq + 1 z_{i} \in D^{-}$ (18)

ξi≥0 i=1,…,l (19)

令 $\bar{w} = (\bar{w}_{1} ‚ \bar{w}_{2})$ ,按照超平面的函数表示习惯,不妨设 $\bar{w}_{2} = - 1$ ,则优化问题(16)成为:

$\min \frac{1}{2}$ $\bar{w}_{1}$ $+ \frac{1}{2} + C$ $\sum_{i = 1}^{l}$ ξi (20)

约束为:

$〈 \bar{w}_{1} ‚ ϕ (x_{i}) 〉 - y_{i} - ε - 1 + \bar{b} - ξ_{i} \leq - 1$ (21)

$〈 \bar{w}_{1} ‚ ϕ (x_{i}) 〉 - y_{i} + ε + 1 + \bar{b} + ξ_{i} \geq + 1$ (22)

ξi≥0 i=1,…,l (23)

经整理,优化(20)与优化(12)是等价的,这就证明了优化问题(16)和优化问题(12)是等价的。再由定理2知优化(12)与优化(5)是等价的。于是可得下面的定理。

定理3 将回归问题的训练样本的因变量上下平移ε+1得到两个集合D+和D-,则优化问题(16)和优化问题(5)是等价的。

该定理说明了回归问题可以通过分类方法来求解。

3 结论

本文讨论了支持向量机分类与回归算法之间的关系,通过对回归样本的上下平移将回归问题转化成分类问题求解,并证明了支持向量机分类算法与回归算法之间的等价性,这将为快速分类算法与回归算法之间的融合提供一定的理论基础。

参考文献

[1]Vapnik VN.Statistical Learning Theory[M].NewYork,Wiley,1998.

[2]Burges C J C.A Tutorial on Support Vector Machines for Pattern Rec-ognition[J].Knowledge Discovery and Data Mining,1998,2(2):121-167.

[3]Smola A J,Scholkopf B.A tutorial on support vector regression[R].NeuroCOLT TR NC-TR-98-030.Royal Holloway College University ofLondon,UK,1998.

[4]Pontil M,Rifkin R,Evgeniou T.From Regression to Classification inSupport Vector Machines.http://www.dice.ucl.ac.be/Proceedings/esann/esannpdf/es1999-462.pdf.

[5]Bennett K,Bredensteiner E.Duality and Geometry in SVMClassifiers.In P Langley,eds.Proc.of Seventeenth Intl.Conf.on MachineLearning,Morgan Kaufmann,San Francisco,2000,57-64.

[6]Bi J,Bennett K P.Duality,Geometry and Support Vector Regression.http://citeseer.nj.nec.com/543126.html.

[7]孙德山,吴今培,侯振挺,等.单参数支持向量回归算法[J].系统工程学报,2005,20(1):109-112.

关系分类算法篇2

关系数据挖掘是近年来快速发展的重要的数据挖掘领域之一,分类是数据挖掘中最重要的任务之一。传统的朴素贝叶斯算法[1.2]运行在单表上,关系数据挖掘中的一个用户感兴趣的个体是由分布在不同表中的多个、异种的数据对象描述的。如何利用多个表中的信息来分类个体是多关系数据挖掘分类算法的关键。

1 扩展算法的基本思路

设t是目标表,目标表中的每一条记录都代表一个要预测类标号的个体。s是可以与t连接的另一个表。对于目标表与非目标表不同的联系类型采用不同的扩展策略。

(1)1∶1和N∶1类型可以采用直接相连的形式,因为这种类型的联系相连后得到的表并没有增加要分析记录的数目,仍然等于目标表中记录的数目。例如一位导演可以导演多部影片,但一部电影只有一位导演,两个表相连后,仍然等于要分析的目标个体电影的记录数目。

(2)1∶N和M∶N类型假设t′表示将1∶1类型和N∶1类型联系连接后得到的表,s是可以与t连接的另一个表。现在t′已经有n个属性,表s有m个属性。对于在表t′中的一个元组X:(a1,a2,…,an),在s表中有L个元组能够与X相连。这L个元组可以表示为(B1,B2,…,BL)(向量用大写字母表示)每个元组Bi可以由m个属性描述:Bi=(bi1,bi2,…,bim),(i=1,…,m)。那么元组X的类标号Cpre可以根据下面公式来预测:

Cpre=argmaxxP(C=c|D=d)=

argmaxcP(c|a1,…,an,B1,…,BL)=

argmaxc∏ P(c|a1,…,an,b11,…,b1m,…,bL1,…,bLm) (1)

按照第二节分析的朴素贝叶斯分类中的假设:一个表中的属性是相互独立的。为了简化计算,同时也假设在s表中能于t表中的元组连接的元组之间也是独立的,并且这些元组属性之间也是独立的。那么公式可以简化成:

$\begin{array}{l} C_{p r e} = a r g m a x_{c} \prod Ρ (a_{1}, \dots, a_{n}, b_{11}, \dots, b_{1 m}, \dots, b_{L 1}, \dots, b_{L m}) Ρ (c) = \\ a r g m a x_{c} \prod_{i = 1}^{n} p (a_{i} | c) \prod_{i - 1}^{L} \prod_{j}^{m} p (b_{i j} | c) Ρ (c) 。 \end{array}$

虽然公式并不是某个类c的概率,但是通过比较每个类公式的大小,可以预测对象X更倾向于哪个类。虽然与目标元组连接的元组数目不固定,但是只要有能连接的元组,这个元组的每个属性值关于它的类标号的概率都会考虑。这样,在非目标表中有不同数目的元组相连也不影响最后要分类的结果。对于每个类C1,C2,…,Cm,分别计算在X条件下的后验概率。P(C|X)取最大值时,C的取值Ci作为实例X的类标记。

2 实例演算

通过实例,介绍RNBC算法的运作。该实例由三个表构成,其中研究者信息表是目标表,它包含的属性“status”是目标属性,用来指示“该研究者是否为领域专家”,是这次的分类任务,另外两个表2和表3是背景知识表。

现在假定有一个待分类元组u=(r5,F,30,u2,p7)。下面采用两种方式对这个元组进行分类。第一种方式采用将三个表连接成为一个表作为训练集,然后采用朴素贝叶斯分类方法;第二种方式采用RBC算法对三个表进行分别处理。为了简化计算,在两种方法中对数值属性都先进行离散化。对于研究者信息表中的“age”属性,大于等于50的为一个区间,小于50的为另一个区间。

将上述三个表连接起来,得出一个表作为分类的训练集。如表4、表5所示。

利用贝叶斯分类算法的概率计算公式,分别对表5中status为“Y”和“N”的两个类别进行计算,得出结果如下式所示。

上面式子中计算的前六个值分别为六个属性的概率值。显然,第一个计算结果大于第二个计算结果。因此,样本u的类标号应该为Y。

第二种方法是采用MRNBC算法,分别对三个表进行分析和处理。先通过类标号传递技术得出背景知识表中元组的类标号,然后计算概率。利用多关系朴素贝叶斯分类的计算公式可以得出结果,如式(2)和式(3)所示。

前六个值仍然为六个属性的概率值,要注意的是属性“type”的概率值对应式(2)中的1/4和式(2)中的3/4是使用了于拉普拉斯矫正公式得到的。从给出的p7的level是2,按照类标号传递技术得到类标号为“Y”的三篇论文中没有level是2的,类标号为“N”的三篇论文中有两篇level是2的。为了避免0概率问题,要利用式(1)来计算,增加两个元组,一个为类标号为“Y”的论文,一个为类标号为“N”的论文,且level均是2。

综上所述,后一个计算结果大于前一个计算结果,因此,样本u应该被赋予类标号N。

利用两种方法进行分类的结果是不同的。在第一个方法中,由于要将三个表连接到一个表中,研究者信息表和大学信息表中有些元组在连接完成以后都重复出现了几次,产生了冗余。连接完成后,元组中显示的研究人员从原来的4个达到了6个。因此,每个属性值所计算得出的概率并不能正确的反映出真实的统计信息。对样本u的语义信息人工进行分类,显然其类标号应该为N,因此,第二种分类方法的结果才是正确的。

在上述实例中,对比了两种方法:传统的朴素贝叶斯分类方法以及本文提出的RNBC算法。从精确度上来讲,传统的朴素贝叶斯方法由于要将几个表连接到一个表中进行分析[3],在连接过程中丢失了很多语义信息,导致最后结果正确性较低。

摘要：关系朴素贝叶斯分类算法对于目标关系表和背景关系表中不同的记录关联方式采用不同的策略,灵活运用连接和元组ID传播技术,高效地实现了将背景关系表中的信息加入到目标关系表中一起考虑来进行分类,提高了分类正确率。该算法采用关系数据库的数据表示方式,解决了传统的朴素贝叶斯算法不能支持关系数据库的问题。

关键词：关系分类算法,朴素贝叶斯分类,关系朴素贝叶斯分类

参考文献

[1]Pompe U,Kononenko I.Naive Bayesian classifier within ILP-R.In:Proceeding of the5th International Workshop on Inductive Logic Pro-gramming,University Leuven,1995:417—436

[2]Kersting,K.De Raedt,L.Kramer.S.Interpreting Bayesian logic pro-grams.In:Proceedings of the AAAI-2000Workshop on Learning Sta-tistical Models from Relational Data,AAAI Press,2000:29—35

关系分类算法篇3

组合分类器算法是现在比较流行的分类器算法, 基本思想是利用组合的很多个单分类器来弥补单分类器对数据分类器的不足, 从而提高分类器的分类性能。而属性选择分类器算法是WEKA平台上的一种传统分类器算法, 本文在WEKA平台上用这两种算法对草药数据集进行分类, 然后再对这两种算法的分类精度进行对比, 实验表明:在实验数据集为输入样本集的情况下, 属性选择分类器算法的分类精度比adaboost M1算法的分类精度高。

二、Ada Boost算法介绍

1988年, Kearns等在研究PAC学习模型时提出了一个有趣的问题:弱可学习是否等价于强可学习, 即Boosting问题。如果这一问题有肯定的回答, 意味着只要找到比随机猜测略好的弱学习算法, 就可以将其提升为强学习算法, 而不必直接去寻找通常情况下很难获得的强学习算法, 这对学习算法的设计有着重要的意义。在更深入的研究中, Freund等发现:在线分配问题与Boostin问题之间存在着很强的相似性, 引入在线分配算法的设计思想, 有助于设计出更实用的Boosting算法。他们将加权投票的相关研究成果与在线分配问题结合, 并在Boostin问题框架下进行对应推广, 得到了著名的Ada Boost算法。该算法不再要求预知弱学习算法的任何先验知识, 在实践中获得了极大的成功[1]。

三、在Weka上用Ada Boost算法及几种单分类算法对草药数据进行分类

本文所进行的实验在Weka3-7-1平台上完成, 用三种草药三七、人参、西洋参的指纹图谱数据作为实验的数据集。对输入的三种草药数据集采用5重交叉验证, 取其分类精度来表现它们的分类性能, 分类精度越高表示分类性能越好。

属性选择分类器的参数设置如下:

基分类器为decisionstump, evaluator是classifiersubseteval, search为linearforwardselection。

Adaboost M1的参数设置如下:

基分类器为decisionstump, numiteration为10, seed为1, weight Thresold为100。

之后执行RUN界面的START指令, 再进入ANAL-YSE界面载入文件选择分析分类精度, 可得到这些算法的平均分类精度如表1所示。

四、实验结果与分析

从表1可以看出, 在实验的中草药数据集中, 属性选择分类器算法的分类精度大于adaboost M1算法的分类精度。

五、结论

综上所述, 在中草药分类领域, 在与adaboost M1算法比较下, 可以利用属性选择分类器算法来提高传统分类器算法的分类精度, 也说明了在特定的数据集中, 一些单分类器算法的分类性能可能会比组合分类器算法高的。

摘要：讨论了在中草药数据分类应用中两种分类器算法:属性选择分类器算法和adaboostM1算法的分类性能的问题, 在WEKA平台上实验可知, 这两种经典组合分类器算法中属性选择分类器算法的分类精度比较高。

关键词：中草药,AdaBoostM1,WEKA

参考文献

关系分类算法篇4

因此，本文在对现有几种SVM多类问题[3]的分类算法进行简单总结的基础上，提出了一种新的基于遗传算法[4]的SVM多类分类方法，并通过仿真和数据分析，得出新算法的结构特点及性能的优越性。

1 多类支持向量机

当前较为通用的方法是通过组合多个二值分类器来实现多类分类器的构造，而SVM扩展方法并不唯一，且目前没有一种方法在性能上明显优于其他方法。常见的构造方法[5,6]有:分解法、纠错输出编码支持向量机、基于决策树的支持向量机等。

1.1 分解法

(1)一对多算法[7]。该算法将一个n类分类问题转化为n个二分类问题。当类别数较大时，某一类的训练样本将远少于其他训练样本总和，这种样本不均衡将对测试精度产生明显的影响。

(2)一对一算法[8]。该算法将一个n类问题转化为个二分类问题。

该方法每个SVM只考虑两个样本，避免了样本数据不均衡问题。但当单个两类分类器不规范时，存在着不可分区域，分类器数目随类数增加而迅速增加，决策速度减慢。

1.2 纠错输出编码支持向量机

纠错编码被用于分类器输出的解码，能够解决多分类中的不可分区域问题[9]。如何根据问题确定码本、选择排练顺序及分类效果受错误码相关性影响大仍有待进一步探究，且对于类别较多的问题，处理效果不佳。

1.3 基于决策树的支持向量机

(1)有向无环图支持向量机。将多个二元分类器组合成多元分类器。对于一个n元的分类问题，经过n-1次排除可得到样本所属的类别。DDAG的结构具有冗余性，但分类结果对节点排序依赖性很大，不同的排列顺序与根节点选取会使分类结果产生不确定性。

(2)二叉树支持向量机。在每个节点上进行聚类，首先将所有类别分成两个子类，再将子类划分成两个次级子类，如此循环得到一个倒立的二叉分类树[10]。然而，若在某节点上发生分类错误，则会将分类错误延续到该节点的后续节点上。因而，分类错误在越靠近根节点的地方发生，分类性能就越差。

2 支持向量机分类算法的设计

遗传算法[11]是一类借鉴生物界的进化规律演化而来的随机化搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，无需确定的规则。

基于遗传算法以上特点，因而将其引入到支持向量机多类问题的分类当中。其分类过程如图1所示，依照遗传算法的流程，可分为以下几个步骤:

(1)个体编码。遗传算法的运算对象是表示个体的符号串，本题中采用的表示形式为无符号的位操作，每位都代表一个类别，低位表示基数小的类。例如:x=10110011，则表明选择了1、2、5、6、8这些类。同理，其它类数的情况也按照上述规则进行相应编码。

(2)初始群体的产生。遗传算法是对群体进行进化操作，需要准备搜索点的初始群体的数据。以8类数据样本为例，群体规模取为2，则取为互补的两种分类，即x1(11110000)和x2(00001111)，必须确保每种数据类都被包含在分类的并集中。若总类别数为奇数类，则生成规则如图2所示。

两个个体交集不为空集，可根据实际需要选取交集所包含的类。图4选取的交集为第4类。因支持向量机分类必有结果，若省略其中一类，则该类失去判定过程，直接导致该类失效，因而将每一类都包含是有必要的，且需要兼顾避免数据出现不均衡的问题，这均是产生初始群体所需考虑的重要规则。

(3)适应度计算。适应度计算是用于评价个体优劣程度与遗传概率的一个过程。对于适应度函数，不需要满足连续可微等条件，要求是对于输入能够计算出能加以比较的非负的结果。

本文采用的适应度函数为所有类的编码值的和，若个体为y8,y7，…，y1，则适应度函数为(i为总的样本类数);其中最优准则为适应度A(x)能取到最小值1，此时余下的类为样本数据所归属的类。

(4)选择运算。本文为确保分类准确度，不采取概率传递的形式进行复制遗传，而是通过支持向量机的二分类判定，对于判定结果继续进行适应度计算，若A(x)值不为1，继续对其编码并进行下一步操作。

(5)交叉运算。本文选取的交叉概率为1，初始群体经过支持向量机二分类，会剔除一个个体，假设样本所属的个体为11110000，此时与00000000进行交叉，可生组样本，即可得到11000000、00110000,10010000、01100000,10100000、01010000这3组子类群体。确保类数的相等以保证样本数据能够平衡，在此基础上对以上几组数据进行等概率遗传。

对于总类别数为奇数类的个体，采用与初始群体分类一样的规则。例:当个体为1110000时，与0000000交叉后产生的两类子类个体，选取一组:1100000、01100000。

(6)变异运算。对于11000000与00110000并集11110000之外的低四位所属的类进行变异，变异概率采取自适应[12]的方式，算法运行前期由于类数收敛较快，采取较高的变异概率规避错分的风险，算法后期则采取较低的变异概率以达到算法最终的收敛。可利用函数模型或模糊控制的模糊规则建立变异概率的数学模型。

变异操作用以减少其他支持向量机分类方法中容易出现的错分情况，对分类结果能够进行多次验证，提高了算法的冗余性和判别准确率。

3 实验与结果分析

对SVM多类问题分类方法不仅与样本数据本身有关，还与SVM中核函数形式以及其他参数的选取有关，本文数据选取UCI数据库中不同类别数、样本数及特征向量数的不同样本，使实验数据更加有代表性。并统一选取相同的SMO训练方法，选取RBF径向基核函数进行训练。

(1)首先以D组数据为例，分析算法的运算过程。针对D组数据，采用无符号编码，选用的交叉概率为1，即交叉是必然发生的，对变异概率则依表2所示，采用简单的对应规则。

针对其他多类情况，也可根据具体情况设计隶属度函数对变异概率进行模糊分类。将D组数据进行3次重复调用到新算法中运行，可得到3组算法运行次数与适应度的值。图4相对应的变异情况与表3相对应，相同数据3次运行步数不相同，但最终均在A(x)=1时算法结束。

表3中，1表示变异;0表示未发生变异;“-”表示算法运行结束。

由图4和表3可得:1)对相同样本数据进行分类，分类次数受变异次数的影响而不同，进而使算法运行次数、运行时间有所差异;2)分类结果相同，均将收敛到适应度为1，但其分类的过程不同;3)第3次曲线在适应度值为2时陷入局部极小值，因此在算法分类后期，即剩余类别数较少时，降低变异的概率是非常有必要的。

(2)对A、B、C、D这4组测试数据进行测试。为保证实验结果的可靠性，对每组测试进行重复性测试，本文对每组测试均进行了6次重复测试，采集实验结果并取其均值，测试集所得测试时间长短即可反映出算法测试速度的快慢。

表4中数据为A/B格式，其中A表示判定分类时长，B表示用百分制统计的算法的准确度。“-”表示判定类别时间过短，给予忽略。

根据实验结果，对数据进行分析可得:1)OVR测试速度较慢，OVO在类别多的情况下测试速度也较慢;2)DAG算法测试速度最快，且准确率也相对较高;3)基于遗传算法的向量机兼顾了速度与准确率。分类速度快，且准确率高，因而在类别数多、对准确率要求高的场合中具有一定的优越性。

综上所述，基于遗传算法支持向量机充分利用了遗传算法结构的优点，将其运用到分类当中，且分类具有较好的精度及速度等优势。

4 结束语

针对支持向量机多类一些分类算法在分类过程中存在的数据不均衡及对分类结构依赖重且缺乏纠错的能力，对这些原因进行分析，考虑到支持向量机二分类的特点，本文结合遗传算法的一些特性，并将其交叉、变异的结构特性，合理地运用到支持向量机多类问题的分类当中，避免了分类过程对算法结构的依赖性。

根据实验仿真证明，基于遗传算法的支持向量机分类算法结构具为灵活的特点，在保证运行速度的同时，确实能使分类准确度更高，分类结果更为可靠。

摘要：针对现有部分支持向量机在多类分类过程中存在的数据不均衡性、对算法结构依赖性强的问题,提出一种新的基于遗传算法的支持向量机多类分类算法。以遗传算法中的交叉作为支持向量机中类的选择,以变异改善分类过程中的纠错能力,以适应度函数作为最优分类结果的确定。在不同特性的样本集上进行仿真测试,结果证明,该算法在类数较多的情况下,有更好的数据均衡性,在分类速度及准确度上均有一定的优越性。

关系分类算法篇5

面对如今信息技术的飞快发展, 各种电子文档和电子邮件都爆炸式的增长, 为了从海量文本中及时准确的获得有效的知识和信息, 就需要处理大量的文本。由于互联网上大部分信息都是以文本的形式存在, 文本的识别就构成了高效信息获取的基础。利用文本分类识别技术可以把数量巨大但缺乏结构的文本数据组织成规范的文本数据, 帮助人们提高检索信息、利用信息的效率。文本分类已经成为组织和管理文本数据的重要形式。为了能在海量的文本中及时准确地获得有效的知识和信息, 文本表示技术以及文本自动分类技术受到了广泛的关注。

(二) 文本分类算法

分类方法是文本分类系统的核心内容, 文本分类方法用一个已标好类别的文本数据集 (即训练集) 来训练分类器, 然后用训练好的分类器对未标识类别的文本进行分类。文本分类方法通过构造某种分类模型 (分类器) , 并依此判断样本所属的类别空间。研究文本分类的关键问题是如何构造分类函数 (分类器) , 分类函数需要通过某种算法进行学习获得。

文本分类大致有两种方法:一种是基于训练集的文本分类方法;另一种是基于分类词表的文本分类方法。两种方法出自不同角度的研究者, 训练集法更多的来自计算机或人工智能研究领域, 而分类词表法则更多地来自突出情报领域。基于训练集的文本分类方法主要分为训练和分类两个阶段。训练阶段和分类如图1和图2所示。

根据决策结果类别的不同, 可以把分类方法分为两类问题和多类问题。两类分类问题 (binary classification) 是指待分类对象的目标类别只有两类, 即“是”和“不是”。多类问题是 (multi-classification) , 即类别主题较多, 也是实践中使用较多的分类, 它的结果往往是一个按相关度大小排序的类别集合。这样的类别分类器称为多类别分类器, 类中心分类算法是常用的分类算法, 算法思路清晰, 是有监督训练的文本分类算法。本文在传统类中心分类算法的基础上提出了改进, 从而达到提高分类的准确度。

传统类中心分类算法:是从训练集中得到类别的中心向量, 它对训练集依赖性比较大, 对训练集的集中程度和规模非常敏感, 通常训练集文本代表性越强, 规模越大分类效果会越好。

KNN (K-近邻算法) KNN法即K最近邻法, 最初由Cover和Hart于1968年提出的, 。该算法的基本思路是:在给定新文本后, 考虑在训练文本集中与该新文本距离最近 (最相似) 的K篇文本, 根据这K篇文本所属的类别判断新文本所属的类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

朴素贝叶斯 (Naive Bayes) 算法的基本思路是计算文本属于类别的概率, 文本属于类别的概率等于文本中每个词属于类别的概率的综合表达式。它假设文本中的词汇在分类中的作用是相互独立的。, 缺点是, 当数据训练集越大时, 处理得越精确, 但是, 如果数据训练集小, 分类就不是很准确了。优点是, 理论比较简单, 可操作性比较强, 在大多数的情况下都可行, 分类准确性比较好。

支持向量机算法的基本实现思想是:通过某种事先选择的非线性映射把输入向量x映射到一个高维特征空间Z, 在这个空间中构造最优分类超平面。

(三) 优化的类中心分类算法

在基于类中心的文本分类算法中, 类别的中心向量是由该类别文本特征向量的简单算术平均得到。在训练集中, 对与各个类别, 其文档往往有可能很分散, 在空间上很可能与其它类有重叠的区域, 这样, 如果直接用这些文档来计算各个类别的中心向量, 往往会有模型偏差, 以至于不能得到很好的分类效果。本文针对上述模型偏差, 提出了一种改进的类中心分类算法, 用当前的中心向量对训练集进行分类, 然后用训练错误文档来更新中心向量, 并假设文档集中的每一篇文档都只属于一个类别。算法的基本思想是:在每一次迭代中, 用当前的规范化中心向量对训练文本进行分类, 找出所有的训练错误文档。并对训练错误文档进行归类:对于类别i, misout-ofi是那些实际属于类别i, 但被误分到其它类中的文档。misin-ofi是那些实际不属于类别i, 但被误分到类别i中的文档。利用这两类分类错误的文档, 我们可以对中心向量进行优化。其中, misout-ofi是应该属于类别i的文本, 但由于文档分散, 这些文档被错误的分到别的类别, 可以适当增加中心向量中这些文档特征权重大的特征项的权重, 相反, 应该减少中心向量中misin-ofi的各文档特征权重大的特征项的权重。利用这些分类错误文档, 更新类中心向量, 并规范化, 得到本次迭代后的规范化中心向量。

算法具体描述如下:

IterationNum表示迭代次数, Rate为参数。加载训练数据, 以及IterationNum和Rate。

步骤一:计算训练集中每个类别Ci的和中心向量Sci和规范化中心向量iCN, 计算公式如下:

在计算新的待分类文档与中心向量的相似度时, 用的是规范化后的中心向量CiN。计算中心向量时, 应用预选处理好的数据, 包括每个文档的向量表示, 词表等, 具体流程如图3所示:

步骤二:进行IterationNum次迭代, 对于每一次迭代:

出所有的训练错误文档。

2. 对于每一个训练错误文档d或者属于misout-ofi或

者属于misin-ofi, 利用这些分类错误文档对类中心向量进行优化, 得到优化后的类和中心向量CiS, *。具体优化公式如下:

如果的得到的和中心向量某一特征项的权重小于零, 就把此特征项的权重设为零, 公式如下:

其中, CiS, , j*表示第i个类别的第j个特征项的权重。

3. 计算优化后的类iC的规范化中心向量iCN

步骤三:输入待分类文本d, 用向量空间模型将其表示成duv然后利用公式C=arg mcajx (cos (ud v, uCjuNuv) ) 返回的就是分离器判断的d的类别。优化后的类中心分类算法在分类过程中, 将新文本与所有中心向量做比较, 所以它的时间复杂度与经典基于类中心的分类算法的时间复杂度相同, 都为O (Lm) , 其中L是文档集中类别的个数, m是等分类文档中出现的特征数。在训练阶段, 因为优化后的算法要找到所有训练文档与每个类别的相似度, 所以多了L×N次比较。N为训练集中的文档数。

步骤四:中心向量优化

在训练集中, 对与各个类别, 其文档往往有可能很分散, 在空间上很可能与其它类有重叠的区域, 这样计算出来的中心向量会有偏差, 因此要对计算出来的中心向量进行优化。利用中心向量对训练集中的文本进行分类, 找出所有的训练错误文档。并对训练错误文档进行归类:对于类别i, misout-ofi是那些实际属于类别i, 但被误分到其它类中的文档。misin-ofi是那些实际不属于类别i, 但被误分到类别i中的文档。基本公式如下:

CA*=CA+Rate× (n∑dn∑d) 公式 (1)

CA**, i=0 IF C*A*, i≤0公式 (2)

优化过程:

1) 加载训练数据和参数每个文件的tf (已经写入硬盘) 词表 (Hashtable) , 存放的是特征项与每个特征项对应的df利用特征权重计算公式得到每个文本的向量表示, 并得到和质心对质心进行规范化, 得到规范化质心, 并将规范化后的质心保存在一个二维数组double[][]中加载训练数据和参数。

2) 对于每一类计算中心向量iCS和规范化中心向量CiN。

用iCN对所有的训练文档进行分类。

用公式 (1) ~ (3) 来更新质心。

参数说明:

Rate是参数, 用来控制每次更新的强度;misout-ofA是那些实际属于类A, 但被误分到其它类中的文档, misin-ofA是那些实际不属于A, 但被误分到类A中的文档;IterationNum是更新的次数。

(四) 实验及分析

在文本自动分类系统中, 通常将用于实验的文本集分为两个部分:训练集和测试集在这个语料中有共有35000篇文本, 分为政治、军事、教育、体育、健康、财经、娱乐、彩票、科技、汽车、手机等11个类别。经过去重后, 剩下的26128篇中每个文本都只属于一个类别。表1列出了各个类别数据及其分布。

结果评测标准:

评估分类准确程度的依据是通过专家对文本的正确分类结果的比较, 与人工分类结果越相近, 分类的准确程度就越高。

文本分类中常用的评测指标有:准确率和查全率。本文使用如下的评估标准:

查准率:第i类的查准率是所有输入系统进行分类处理的文本中与专家分类结果完全吻合的文本所占的比率, 其数学公式表示如公式:

被正确分到类别i的文本数

查准率 (p i) =

所有被分到类别i的文本数

查全率:第i类的召回率是所有文本中分类系统分类正确的文本所占的比率, 其数学公式表示如下:

被正确分到文本类别i的文本数

查全率 (Ri) =

实际属于类别i的文本数

微平均和宏平均有一个根本的不同, 微平均给每个文件以相同的权重, 而宏平均是给每个类别以相同的权重。因而宏平均和微平均可能得出完全不同的结果, 特别是当文档集中类别的分布有较大不同的时候。

查准率和查全率反映了分类质量的两个不同方面, 两者必须综合考虑, 不可偏废, 因此, 存在一种新的评估指标, Fl测试值, 其数学公式如下:

除以上的评估标准以外, 还有微平均值 (Micro-Averaging) 和宏平均值 (Macro-Averaging) 两种计算准确率、查全率的方法。

应用优化的类中心分类算法与Naïve Bayes、KNN以及类中心分类算法作对比。表2给出了在语料集上各个分类器的分类结果 (F1指标, %) 。

从对比中可以看到, 优化后的类中心分类算法在任何类别的分类效果都比类中心分类算法要好。优化的类中心分类算法在政治、军事、大众媒体、交通运输、咨询科技、家居、手机电讯这些类别中, 分类效果比其他的分类算法的分类效果要好。该算法的宏平均值比其它算法最高的宏平均值高出1.23个百分点, 微平均值比其它算法最高的微平均值高出1.53个百分点。

摘要：为了能在海量的文本中及时准确地获得有效的知识和信息, 文章表示技术以及文本自动分类技术受到了广泛的关注。文章介绍了文本分类的过程和相关的技术, 利用向量空间模型构建文本表示模型, 介绍了常用的文本分类算法, 由于传统类中心分类算法训练文档分散, 不能准确的表示各类别的中心向量, 提出了优化算法, 从而提高了分类准确度。

关键词：文本分类,分类算法,向量空间模型,中心向量

参考文献

[1]张东礼, 汪东升, 郑伟民.基于VSM的中文文本分类系统的设计与实现[J].清华大学学报 (自然科学版) , 2003, 9:1288-1291.

[2]Fabrizio Sebastiani.Machine Learning in automated text categorization.ACM ComputingSurveys.2002, 34 (1) :1-47.

[3]John M.Pierre.On the Automated Classification of Web Sites, Linkoping UniversityElectronic Press, Sweden, 2001.

[4]S.Cost, S.Salzberg.A Weighted Nearest Neighbor Algorithm for Learning with SymbolicFeatures.Machine Learning, 1993, 10 (1) :57-58.

分类算法的研究进展篇6

一、分类算法概述

为了提高分类的准确性、有效性和可伸缩性, 在进行分类之前, 通常要对数据进行预处理, 包括: (1) 数据清理, 其目的是消除或减少数据噪声处理空缺值。 (2) 相关性分析, 由于数据集中的许多属性可能与分类任务不相关, 若包含这些属性将减慢和可能误导分析过程, 所以相关性分析的目的就是删除这些不相关的或兀余的属性。 (3) 数据变换, 数据可以概化到较高层概念, 比如连续值属性“收入”的数值可以概化为离散值:低、中、高。又比如, 标称值属性“市”可概化到高层概念“省”此外, 数据也可以规范化, 规范化将给定的值按比例缩放, 落入较小的区间, 比如【0, 1】等。

二、常见分类算法

2.1决策树

决策树是用于分类和预测的主要技术之一, 决策树学习是以实例为基础的归纳学习算法, 它着眼于从一组无次序、无规则的实例中推理出以决策树表示的分类规则。构造决策树的目的是找出属性和类别间的关系, 用它来预测将来未知类别的记录的类别。它采用自顶向下的递归方式, 在决策树的内部节点进行属性的比较, 并根据不同属性值判断从该节点向下的分支, 在决策树的叶节点得到结论。

2.2贝叶斯分类

贝叶斯分类是统计学分类方法, 它足一类利用概率统计知识进行分类的算法。在许多场合, 朴素贝叶斯 (Naive Bayes, NB) 分类算法可以与决策树和神经网络分类算法相媲美, 该算法能运用到大型数据库中, 且方法简单、分类准确率高、速度快。由于贝叶斯定理假设一个属性值对给定类的影响独立于其它属性的值, 而此假设在实际情况中经常是不成立的, 因此其分类准确率可能会下降。为此, 就出现了许多降低独立性假设的贝叶斯分类算法, TAN (tree augmented Bayes network) 算法。

2.3神经网络

神经网络是大量的简单神经元按一定规则连接构成的网络系统。它能够模拟人类大脑的结构和功能, 采用某种学习算法从训练样本中学习, 并将获取的知识存储在网络各单元之间的连接权中。神经网络主要有前向神经网络、后向神经网络和自组织网络。在数据挖掘领域, 主要采用前向神经网络提取分类规则。包括替换的误差函数、网络拓扑的动态调整、学习率和要素参数的动态调整。近年来, 从神经网络中提取规则受到越来越多的关注。这主要有以下二种倾向: (1) 网络结构分解的规则提取; (2) 由神经网络的非线性映射关系提取规则。未来神经网络的发展可向进一步降低算法的复杂度、提高所提取规则的可理解性及算法的适用性方向发展。

2.4遗传算法

遗传算法是模拟生物进化过程的全局优化方法, 将较劣的初始解通过一组遗传算子 (繁殖——即选择、交叉——即重组、变异——即突变) , 在求解空间按一定的随机规则迭代搜索, 直到求得问题的最优解。遗传算法在数据挖掘领域的主要应用有: (1) 用它和BP算法结合训练神经网络, 然后从网络提取规则; (2) 分类系统的设计, 如编码方式、信任分配函数的设计以及遗传算法的改进等。遗传算法用于数据挖掘存在的问题是: (1) 算法较复杂, (2) 收敛于局部极小的过早收敛等难题未得到解决。

2.5 KNN算法

最临近分类KNN是基于要求的或懒散的学习法, 即它存放所有的训练样本, 并且直到新的 (未标记) 的样本需要分类时才建立分类。这与诸如决策树和神经网络这样的急切学习法形成鲜明对比。懒散学习法在训练时比急切学习法快, 但在分类时慢, 特别是当与给定的无标号样本比较的可能的临近者 (即存放的训练样本) 数量很大时, 懒散学习可能引起很高的计算开销。

参考文献

[1]Quinlan J R.Induction of decision trees.Ma—chine Learning.1986:1—356.

[2]Quinlan J R.C4.5 Programs for machine learning.Morgan Kauffman.1993:81—106.

[3]毛国君, 段立娟, 王实等.数据挖掘原理与算法[M].北京:清华大学出版社, 2005:123—127.

关系分类算法篇7

1 实验背景

早期手工分类,从粗到细,完全由分类员完成。主要工具是查阅专利分类表。随着计算机应用的发展,分类表由书籍变成电子版,又经历了网络版、网页版变迁。2010年以后才真正标志性地实现了自动分类技术的应用,将研究变为实用。一种基于历史文献的分类方法至今占据着主导位置。

1.1 基于历史文献的分类方法

以历史文献作训练空间,构建语料库,通过数学模型运算获得相似度评分,提供备选方案。其中数学模型可以多种。如SVM、KNN、Naive Bayes等等[1]。其优点是对已分类文献分类效果良好。其缺点是需配备海量装备,代价大。

这种方法后来也受到两点质疑。

1)发明专利的创新性

由于专利文献由两类构成:一类是开创性发明,另一类是改进性发明。对于开创性发明,其新技术方案所依据的基本原理与已有技术有质的不同。这类专利之间相似度很低。因此基于历史的方法,问题会出在参照物信息不充分上。

2)IPC分类的渐变性

在专利审查流程中有一种预警机制。当某个时期某个领域专利案件量增长超出预期就会报警。同时引起两个部门的注意。A)宏观战略研究部门,主要观测是否将有引领潮流的革命性技术到来,例如:纳米。预测5到10年将进入市场,对宏观经济产生影响。B)审查业务管理部门,检测到案件量当超过某个数量级的阀值时,就要考虑审查增员问题,或者考虑该分类是否需要再细分。一种变化是增加小组细目,另一种变化停止原小组细目,重新分配一个新的大组,然后再分到各个小组细目。因此,专利分类表会根据需要随时调整。因此基于历史的方法问题会出在参照物信息不确定上。

1.2 基于分类表的分类方法

分类表作为指导性工具,曾经是手工时代的产物,早已被自动化工具所取代,目前只剩备忘录作用。笔者以为分类表不仅有良好层级结构,还有规则指向,交叉参考等。如能充分利用,可以开发出分类导航(XML- Xslt版已初具导航作用)产品;将括弧中规则指向和交叉参考与人工智能相结合,自动分类可以达到极高准确率,当然引入规则会变得相当复杂。分类表简单使用,已经具备可计算性。这恰恰是轻量级分类方法须采用的重要手段之一,不可或缺。这种方法也有许多困难需要面对。例如:

1)专利文献语言文化差异

专利文献格式严格,结构特征明显。作者撰写文档,须通过形式审查才能进入审批流程。由于对撰写具体内容不作限定,说明书的撰写水平受作者的语言文化背景、地域差异、学识和规范习惯等因素影响,因人而异。发明标题中的词素非常重要,需要抓住主题重点;权利要求书的描述是树形结构,可以程式化固定。例如:“一种”(独立权利要求),“根据”(从属权利要求),可以构成林、树、杈关系。这对主分类和相关分类分析有参考价值。笔者曾抽样分析,结果令人失望。严格按统一规范来撰写的并不多,失去利用价值。要求文字术语统一规范,更是难事。

2)专利分类表术语不统一规范

电子版分类表中符号混乱,文字缺乏统一规范。通过取样几个近义词,便可略见一斑。参见表1。

某些词语意思相近,复杂而繁多,分布在不同分类中,给解析带来困难。

3)抽象专利分类表与具象专利文献之间术语差异

该差异是两者不在一个层面自然形成的,需要一个沟通机制。由此,引出基于同义词的术语分类方法。

1.3 基于同义词的分类方法

专利文献加工中人工标引主要的工作就是标注文献的关键词和同义词。该方法主要作为提高专利检索查准率、查全率的必要手段之一。而对于文档自动分类来说,利用分词技术来获取文档中有限高频词。两者目标一致,方法有别,一个人工,一个计算技术。由于计算技术缺乏模糊识别、灵活和准确的理解力。因此,最终还是需要适当植入人工标引关键词来弥补计算技术的缺陷,提高准确性。

其哲学思想也与数学方法论不相矛盾。如果把专利文献和专利分类看作向量空间模型,文档空间被看成是被简化了的一组能够代表文档的高频正交词条有限特征向量空间,词条频度权重,看作特征轴上的投影。IPC分类也是有限特征向量空间子集,由不同的特征排列组合而成。某些特征被不同的分类空间所共用。像星座群一样,每个星座对不同的分类群起的作用不同,有些分类群整体很耀眼,有些分类群整体有些黯淡,甚至没有光芒。如果文档空间向量与ipc空间向量存在交集,在ipc某些特征轴上能够直接找到投影;否则,就相离。如果,某些特征通过变换折射也可以找到投影,那么认为,两者之间间接存在交集。这里折射变换的原理也就是同义词和上位词植入的基本原理。

如果直接用分类表来解析文献,寻求的分类目标可能会发散。因为文档空间与IPC分类空间不直接在一个层面上,坐标没有对应关系,投影回到原点。有人会提出按照文档结构分类方法,认为标题或文摘部分很重要,通过增加整个标题或文摘的权重来施加影响力。这对于空间的形状会有所改善,但并未发生质的改变。也只是改变了投影形状量的大小。只有,真正将文档空间中不在同一个层面的那些高频特征词,通过上位词或同义词的折射变换,才可以改善其在分类空间中的投影,以突显或还原其真实形态。

利用这一方法,通过逐一折射扫描,捕捉分类空间的投影。不仅可以原型再现,还可以通过局部放大,来达到逐一捕获主IPC和或其他相关IPC的目的。分类会因同义词强化效果大大改善,达到很好的收敛性。

因此,建立一个完善的同义词库意义重大。提供捡拾同义关系词的入口,是基于同义词分类方案进入一个良性循环的必要手段。这是需要全员参与的工作,需要群体的智慧。同样,提供一个可植入关键词的入口,对于不依赖于现有或历史,也是设计者需要考虑的。

建立同义词或上位词关系词方法其实简单。例如:蛋白质是由肽构成的,肽是由氨基酸构成的。那么建立“肽→蛋白质”关系,肽是上位词,蛋白质是下位词。文献中使用了“…蛋白质”,就植入上位的“蛋白质”和“肽”;又例如:文献用“英文/英语”,那么就植入其上位词“外语”,建立“外语→英语”关系。新建立的关系词被积累保存到同义词库,一劳永逸。

与基于历史文献语料库相比,同义词库无疑是轻量级的。同义词库可以弥补专利分类表中词语抽象的不足,用来化解专利文献中词语具象的复杂性。在专利分类表和专利文献之间搭建起沟通的桥梁。

2 IPC自动分类的技术实现

IPC自动分类的实现,其专利文献自动分类实验流程图,如图1所示。

专利分类流程图分为两个部分,可以分开实现,IPC分类表语料库加工层最终得到的是分类表语料库。由{ipc,wj,cc,idf}构成,内容参见定义1。

定义1:ipci,用以表示IPC分类表中的某个专利分类号;wij,用以表示ipci分类描述文字切分出的某个特征词;cc(wij)表示,特征词wij在IPC分类表中有多少分类与之有关;N,用以表示IPC分类表中总共有多少分类条目;idf(wij) ,用以表示IPC分类条目中的词条相对于总体分类的反文档数,是wij的重新评估的权重,idf(wij)=log(N/ cc(wij))。

原始文档加工层,最终得到文档目标语料。由{wi,dn,tf}构成,内容参见定义2。

定义2:D,用以表示原始文献;wk,用以表示D中切分出的词条;dn(wk),用以表示wk的重复数;n,用以表示D中的总词条数,n=∑dn(wk);tf(wk),用以表示wk的词频,tf(wk)= dnk/ n;

计算相似度层,用三种算法分别计算相似度排名。参见自动分类算法。

2.1 IPC自动分类的算法

本文给出自定义的两种算法和一种已有算法进行对比。即:

WHZ算法——一个自定义算法

Tf-Idf算法——一个已有算法

Hit-Rate算法——一个自定义算法

2.1.1 WHZ算法

whz算法属于自定义算法,用来抑制版权争端,与Tf-Idf和BM25算法相当。

定义3:

文档D与分类条目ipci相似度,用whz(D,ipci)表示。

whz(D,ipci)=∑(dn(wj)/cc(wij))dn(w)w

其中,dn(wj)代表文档词条wj重复度权重,cc(wij)代表ipci条目中wj词条被多少个其他ipc分类条目所共用或分享。

2.1.2 Tf-Idf算法

Tf-Idf算法属于已有算法,其标准形式的定义有BM25算法[略]。

定义4:

文档D与分类条目ipci相似度,用Tf-Idf (D, ipci)表示,或sim(D, ipci)表示。

其中,dn(wj)代表词条wj重复数,cc(wij)代表词条wj逆文档数,亦即词条与其他ipc分类也相关的ipc条目数。

2.1.3 Hit-Rate算法

由于whz自定义算法,与tf-idf算法总体趋势接近。为防止前两种算法接近重叠,我们又从另外角度给出了一种自定义的算法。其主旨是,将ipc条目其所涉及分词,与专利文献中高重复度的词相匹配,匹配占比越大,得分越高,与ipc条目越相似。

定义5:

函数has(wij)如果wij出现在文献D中,则取值1,如果没有出现在文献D中,则取值0;Hit-r(D,ipci),用于表示命中率或占比。

其中j=1..m,则∑j(1)=m。

文档D与分类条目ipci相似度,用Hit-Rate(D, ipci)表示。

3 实验效果(The experiment effect)

抽样考察4个发明公开专利文献。取试验样本4个发明公开专利的“标题+文摘”,参见表2。

专利文献切分分词,参见表3。

观测实验结果,植入关键词对自动分类的三种算法排名的影响,参见表5。

直接通过分类表计算自动分类相似度排名,收敛性较差。参见表4 左部结果。植入同义词调整后,分类效果明显改善,基本收敛。参见表4右部结果。

笔者通过植入同义词和上位词来改善分类表解析不收敛的问题。如果调整得不到希望的分类,亦即,分类不收敛,就要重新调整其他同义词方向,来改变策略,直至得到与文献内容相符合且最接近的分类为止。

从实验效果看,本文所用的分类表与同义词修正相结合的分类方法,收敛效果明显。与实际采用何种算法无关,要发散都发散,要收敛都收敛。无疑TF-IDF优于自定义。

4 结论

IPC自动分类技术作为计算机辅助工具来使用,可为人们提供一种具有参考价值的分类信息,供使用者选择。本文所述分类方法是一种基于分类表和同义词相结合的方法,不依赖于历史信息也不受限于历史信息的不足,不需要大量训练数据的方法。其优点是:能将专利文献中的不同权重的高频词,通过同义词库的扩充,与分类表直接比对,不需要花费大量资源收集专利文献语料库,只需借助有限同义词植入来调整分类运算,来解决分类不收敛的问题。该方法在存储量和运算量方面属于轻量级的,且运算速度快,加工一篇文献不到1秒,需要的资源不多。通过植入同义词或上位词调整权重,可以改变某些分类的发散或收敛方向,来达到逐一捕获主ipc和每一个相关ipc的目的。可作为半自动的简单灵活的分类捕捉工具。其缺点是算法受限于同义词库的建立,取决于植入同义词的经验,调整植入词,改变某些分类的发散或收敛方向,需要使用者自己凭经验来掌握和控制。初期需花费一些时间将分类表作一个初步同义词整理,然后通过工作进行中不断来扩充同义词库,使之趋于完善。该方法对CPC自动分类的实现有借鉴意义。

参考文献

【关系分类算法】推荐阅读：

数据分类算法06-23

决策树分类算法09-24

数据流分类算法分析06-27

医疗废物的分类及分类要求08-29

Discuz!如何开启使用HTML、主题分类、分类信息07-06

分类依据07-15

景观分类07-16

流量分类07-18

音乐分类07-20

武术分类05-11