Apriori算法在词性标注规则获取中的应用

2016-11-30马如义

计算机时代 2016年10期

马如义

摘要：人工方法获取的规则准确率有待验证，所以从数据挖掘的角度运用Apriori算法对词性标注规则的获取进行研究。用户根据需求自定义支持度与置信度，在满足规定支持度的前提下，先从候选集模式中挑选出高于支持度的模式，再挖掘出高于置信度的产生式规则，获取的规则是隐含在数据中不易被发现的，其表达上是明确的。实验表明，自动获取的标注规则具有很好的利用价值，可以提高词性标注的正确率。

关键词：数据挖掘； Apriori算法；词性标注；规则

中图分类号：TP391 文献标志码：A 文章编号：1006-8228（2016）10-32-04

Application of Apriori algorithm to obtain part-of-speech tagging rules

Ma Ruyi

（Computer Department Qinghai University for Nationalities， Xining， Qinghai 810007， China）

Abstract： The correct rate of the artificially obtained rules need to be verified， so from the point of view of data mining， using Apriori algorithm to obtain the rules of part-of-speech tagging is researched in this paper. User defines their support and confidence according to the requirements， in the premise of meeting the support provided， a mode that is higher than the support is selected from the candidate mode set， and the production rule that is higher than the confidence is dug out， the rule is hidden in the data and not easy to be found， but its expression is clear. Experiments show that the tagging rules automatically obtained have a good utility value， and can improve the correct rate of part-of-speech tagging.

Key words： data mining； Apriori algorithm； part-of-speech tagging； rule

0 引言

数据挖掘[1]是从大量的数据中提取或“挖掘”知识。具体来说，数据挖掘就是从大量的、随机的、模糊的、不完全的、有噪声的数据中，提取隐含在其中的、潜在有用的、事先不为人知道的知识和信息的过程[2]。词性标注是自然语言处理的一个重要环节，其任务是为句子中的每一个词标注一个正确的词性，此环节出现的错误，将在后续的句法分析、机器翻译等处理中被放大[3]。词性标注迄今为止已经有很多方法，有基于规则、统计以及规则与统计相结合的方法[4]。

规则的获取一般由人工整理集成，但这存在以下两方面的问题[5]：①从规则的应用范围上看，靠人工的方法只可能产生一些共性规则，不可能产生针对个别情况的个性规则，而个性规则尽管应用范围小，但也是提高正确率的重要手段；②由于人工方法获取的规则准确率有待验证，因此在基于统计方法正确率不易再提高的前提下，能否自动高效地获取规则是实现词性标注中的关键问题。

本文对于词性标注规则的获取不需要进行维数与层次分析，也不需要采用分而治之的方法，而是采用了最基本的Apriori算法，从人工已标注好的语料中来研究词性及词的模式序列对词性的影响。该方法与人们利用语料上下文中的词、词性等信息来对词性进行判断的方法是一致的。在统计语料规模较大的情况下，给定最小支持度及最小可信度后，首先挖掘大于最小支持度的常用模式集，然后生产关联规则，若此规则的可信度大于最小可信度，则得到词性规则。如果最小可信度定义的足够高，则获得的规则能够作为概率方法的补充，从而较好地解决词性标注问题。但由于该规则的挖掘是在文本数据中进行的，同时它又依赖于词性与词的各种组合，这使得其挖掘过程较数据库中的数据挖掘复杂得多[5]。

1 Apriori算法及问题描述

1.1 Apriori算法

Agrawal等人[6]于1993年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，设计了基于频繁集理论的Apriori算法[7]。Apriori算法是一种最有影响力的挖掘布尔关联规则频繁项集的算法。其核心是基于两个阶段频繁项集思想的递推算法，该算法的设计分解为两个子问题：①找到所有支持度大于最小支持度的项集（itemset），这些项集称为频繁集（frequent itemset）；②根据最小的置信度和找到的频繁项集产生关联规则。

关联规则的一般形式为[8]：X=>Y，其含义为X的出现同时也导致Y的出现。对于关联规则X=>Y，其支持度的表现形式为sup（X=>Y）=P（X∪Y）=sup（X∪Y），即交易集中同时包含X、Y的交易总数在所有交易总数中所占的比值；置信度的表现形式为conf（X=>Y）=P（Y|X）=sup（X∪Y）/sup（X），即同时包含X、Y的交易总数与只包含X的交易总数的比值。其中支持度是对关联规则重要性的一种表示，而置信度又可称为可信度，是对关联规则准确度的一种表示，其取值范围在0到1之间。它们都由用户根据需求自己进行设置。

Apriori算法的第二步比较容易，一般经过第一步筛选后的频繁项集都不会很多，通过子集产生法就可以产生关联规则。而第一步需要在大量的事务数据集中寻找出现频率较高的项集Itemset，这可能要求多次扫描交易较大的数据库，所以就需要一个比较高效的搜索方法。故可能产生大量的候选集，以及需要重复扫描数据库，是Apriori算法的两大缺点。

1.2 问题描述

为了使词性标注的规则能够更好的在语料中被挖掘出来，本文给出了以下描述。

⑴ 词性标记集Tags={Tagi|i=1，2，…，m}，词集Dwords={Wordi|i=1，2，…，n}，项集I=DwordsUTags，其中Wordi、Tagi分别为某个词和词性标记。

⑵ 已标记的文本T={（Wordi，Tagi）|Wordi∈Dwords，Tagi∈Tags}，Tagi是词Wordi在该标记文本中对应的词性标记。

⑶ 模式集D={d|d∈I}，表示由词与词性标记组合构成的串。

⑷ 若X∈D，且长度Lenth（X）=K，则模式X为K模式。

⑸ 若X∈D，F={Y|Y∈D，且Lenth（X）=Lenth（Y）}，则为模式X的支持度，它反映了该模式在同长度模式中所占的比例。其中freq（X）表示模式X出现的频率，total（F）表示长度为Lenth（X）的模式出现的总频率。

⑹ 令min_sup为用户最小支持度，则集合C={X|X∈D，sup（X）≥min_sup}，称X为频繁项目集。

⑺ 若X，Y为大模式，且X，Y之间的关联，记为规则X=>Y，该规则的可信度，其支持度为sup（X∪Y）。其中freq（XY）表示模式X，Y同现的频率。

⑻ 令min_conf为用户规定的最小可信度，若，则规则是值得该用户信赖的产生式规则。

⑼ 取k模式，并且ak∈Tags，ak是词k的词性标记，则在文本中采取的规则形式为：，它表明若前k-1个词、标记构成的模式等于a1，a2，…，ak-1，则第k个词（词k）的词性标记用该为ak。

2 Apriori算法的实现及应用

2.1 Apriori算法的实现

基于Apriori算法的数据挖掘与数据库中的数据挖掘不同，训练集中仅长度为i（i模式）的子串，其词与词性的组合就有2i个，由此可见随着模式长度的不断增加，其对应长度的模式总数也急剧增加，所以最小支持度和可信度不应该是一成不变的，它们应随模式长度的增加而减少，但对最小可信度的要求，不但不因模式长度的增加而减少，而且由于长模式应用范围较小，必须保证其可信度比短模式的可信度高，否则将得不偿失[5]。

由于该数据挖掘是在文本数据的基础上进行操作的，所以，为了提高操作效率，本文对数据仅扫描一遍，其操作如下：首先，基于模拟数据集，用户自己设置最小支持度，找出符合条件的频繁项目集；然后，再定义一个衡量置信度的阈值，基于上一步产生的频繁项目集，运用Apriori算法挖掘出支持度和置信度分别大于用户给定的最小支持度（min_sup）和最小置信度（min_conf）的关联规则。该算法的操作实现步骤如下。

Step1：选取模拟数据集，并设置项目集为I={“前一词”，“前一词词性”，“当前词”，“当前词词性”，“后一词”，“后一词词性”}，用Apriori算法实现频繁项集、关联规则的获取。

Step2：基于该模拟数据集，输入最小的支持度阈值为10（经多次实验选取），扫描项目集，对每个候选集进行计数，丢弃小于最低支持度的候选集，进而得到频繁1-项集的集合L1。L1中的数据表示各个词、词性出现的次数。

Step3：由L1连接、剪枝产生候选C2，扫描项目集。对C2中每个候选集计数，小于最低支持度的候选数据集将会被丢弃，从而产生频繁2-项集的集合L2。L2中的数据表示词、词性两两连接后出现的次数。以此类推求解候选C3、C4、C5、C6，进而得到频繁项集集合L3、L4、L5、L6。

Step4：基于频繁6-项集，输入最小可信度值生成关联规则。对于每一个频繁项集L，找出其中所有的非空子集；然后，根基置信度计算公式confidence（A?B）=P（B|A）=support_count（AUB）/support_count（A），计算每一个子集a的置信度，如果support（L）与support（a）的比值大于最小可信度，则存在规则a==>（L-a），否则不存在关联。

2.2 模型程序设计

本设计项目集为6-itemset，即L6={“前一个词”，“前一个词的词性”，“当前词”，“当前词词性”，“后一个词”，“后一个词的词性”}，并根据Apriori算法设计了相应的模型程序，其模型程序架构如图1所示。

图1 模型程序架构

⑴ Main函数负责程序的整体运行，如调用程序初始化、项目集计算、关联规则算法、相关信息的输出操作等。

⑵ Apriori（）构造函数用于创建图形用户界面。

⑶ print（）函数用于返回需要输出的相关信息。

⑷ createTransRule（）函数用于创建关联规则。

⑸ createL1（）、createL2（）、createL3（）、createL4（）、createL5（）、createL6（）六个函数用于创建频繁集。

⑹ removeNotSupportKey（）函数用于删除键值小于最小支持度的键。

⑺ findKey（Set keyset，String a， String b， String c，String d， String e， String f）函数用于在健集keyset里查找健值为a，b，c，d，e，f的健。

⑻ contain（Set keyset，String a，String b，String c，String d，String e，String f）函数用于判断在健集keyset里是否已经包含了健值为a，b，c，d，e，f的健。

⑼ getMinusCollect（String[] a， String[] L）函数用于求a与L的差集。

⑽ getSubSet（String setN[]）函数用于获取setN的子集。

3 实验结果与分析

语料使用《新疆日报》维语版，题材涉及政治、经济、体育、卫生、文化、艺术、娱乐等。目前该语料已完成词干切分、词缀提取，以及部分词性标注。

根据数据挖掘中的Apriori方法，从本文获取的模拟数据集中，分别对各长度模式进行挖掘，并对最终的模式设置最小支持度和置信度，从中挖掘出词性标注的规则。从挖掘出的规则可以看出，词、词性及词与词性的组合对当前词词性的影响。下面对部分长度模式进行说明。

模式一：表示单个词或词性的出现次数，其中出现次数前三位的为：n，v，adj。由于一模式中未利用上下文信息，因而不构成规则。

模式二：表示前一词或前一词性对当前词性的影响。

获取的标注规则为：if（wordi，adv） then（word2，n），这说明若前一词词性为副词，则其后一词的词性为名词。

模式三：表示前两词或词性的组合对当前词的词性的影响。

获取的规则为：if（词性1，v）and（词2，“”）then（词3，n）。

模式六：表示{“前一个词”，“前一个词的词性”，“当前词”，“当前词词性”，“后一个词”，“后一个词的词性”}出新的次数。

通过对不同长度模式的比较可以清楚的看出词在模式中的限制作用。

从实验数据可以看出：每种模式的组合随着模式长度的不断增加其组合的绝对数量也不断增加。由于受到较多的上下文制约，模式的支持度降低、可信度增加，而且词性能够被惟一确定的可能性也增加了。

由于词及其对应的词性出现的次数远远没有一个词性单独出现的次数要多，所以，用词上下文信息中的词性做制约对应的情况更多、更复杂，不利于对兼类词词性进行消歧，而词作为上下文的因素之一对词性的影响更大，即对词性的限制更加精确。一般来说，模式中词对词性的影响更大一些，故含词的模式的支持度要更小一些。

为了进行实验比较，本文先用最大熵的方法对上述语料进行标注，准确为92.01%。根据获取的标注规则，在最大熵模型标注的基础上，对标注结果进行了优化，准确为93.13%，优于单纯用基于统计的最大熵方法标注的结果。

4 结束语

本文采用数据挖掘方法，对词性规则的自动获取进行了有益尝试，获取的规则能够对词性的正确标注起到很好的辅助作用。该方法是一种从语料库中以规则的形式获取知识的新方式，较适用于大规模语料库，为后续数据挖掘方法在自然语言处理中的应用提供了新思路。该方法的缺点是，一定程度上依赖于训练语料的规模，而且对于多次扫描的效率较低，这些问题有待进一步研究。

参考文献（References）：

[1] 蒋海昆.数据挖掘过程的研究[J].福建电脑，2007.3：67-74

[2] ZhaoHui Tang.数据挖掘原理与应用[M].清华大学出版社，

2007.

[3] 买合木提·买买提.基于统计的维吾尔语词性标注研究与实

现[D].新疆大学，2009.

[4] Liu S，Chen L et al.Automatic part-of-speech tagging for

Chinese corpus.Computer progressing of Chinese and Oriental Languages，1955.9（1）：31-47

[5] 李晓黎，史忠植.用数据采掘方法获取汉语词性标注规则[J].

计算机研究与发展，2000.37（2）：1409-1414

[6] 许娅.关联规则更新算法研究与应用[D].合肥工业大学，

2009.