基于频繁模式半结构化数据的模式抽取

李 颖，张晓贤，孙佳慧

（1.吉林师范大学计算机学院，吉林四平136000;2.长春工程学院软件学院，长春130012;3.空军航空大学基础部，长春 130022）

0 引 言

数据挖掘最早出现在20世纪80年代后期，是多学科领域的范畴，有很多独有的特征[1]。频繁模式的挖掘[2]，在数据挖掘领域中占有重要的地位，频繁模式挖掘的过程是搜索给定的数据集中多次出现的联系。笔者提出一种基于这种模式的OEM（Object Exchange Model）模型，并实现了半结构化数据的模式抽取。

1 OEM模型

OEM模型[3]是用来描述半结构化数据[4]的模型，他是一种自描述性模型。为了让数据交换在异构的数据源之间顺利进行，必须找到一个高度灵活并且同时能表达大多数不同类型数据的高速模型，因而OEM模型受到了研究人员的关注。

OEM模型由表示对象的节点以及表示层次关系的带标签（label）的有向边构成，即可看成一个图。通常每个对象用四元组表示（id，label，type，value），对特殊情况也可以特殊处理。其中id是对象的唯一标识。label是对象的标签描述。type是对象类型，有两类：原子的和复杂的。原子代表不可分割，也是这类数据的特点;复杂对象是引用（object references）的集合，每个对象引用指向另一个子对象。value是该对象的值域。

OEM模型可用一个有向图表示（见图1）。

图1 OEM例子Fig.1 OEM example

为描述算法，给出必要的特殊定义：每条边记作〈oi.ln.om〉，该表示从对象oi通过标签为ln的边指向对象 om。如果图1中存在〈o1.l1.o1〉，〈o2.l2.o2〉，〈o3.l3.o3〉，…，〈on.ln.on〉，则称 OEM 模型图中存在环路。

简单路径Psp（simple path），是标签l的序列，用“·”隔开，记做Psp=l1.l2.l3.…ln，其中n为路径长度。

Psp=club.name.official是长度为3的简单路径。

为方便算法的描述，特给予以下定义。

频繁Psp，先说明支持度，某个简单路径Psp的支持度就是该简单路径出现的次数，记做Ssup（Psp）。

当Ssup（Psp1）≥minsup（最小支持度阀值）时，此Psp被称为频繁Psp，记做Pfsp，否则是非频繁Psp。

对于简单路径表达式Psp=l1.l2.l3.…ln，其包含的一个特殊有序子序列Psp1=l1.l2.l3.…ln-1，称为其极大真子集简单路径表达式，而Psp称为Psp1的极小超级简单路径表达式。

性质1 如果某路径Psp是频繁的，则其任何的非空子集也全是频繁的。

性质2 如果某路径Psp是非频繁的，则其任何超集（集合B是集合A的真子集，则集合A就是集合B的超集）也是非频繁的。

性质3 如果路径Psp是频繁的Psp1，并且在相关的OEM图中没有超集，则此Psp称作是最大频繁路径表达式，记做Pmfsp。

2 算 法

模式抽取算法的目的是对OEM模型树进行处理，输出全部最长频繁简单路径。目前有很多研究者在该领域进行研究，并且有了很多研究成果[5，6]。笔者提出的算法是对模式抽取算法的改善，主要是功能上的改进。克服了同一类型算法的支持度计算的分支和环路问题，下面给出主要改进部分的伪代码描述。

算法1 求某条路径的支持度。

sup算法是以根为参数，实现时此项可忽略，因为所有路径都是从根开始。第2个参数用来求支持度的路径。设置集合A和B，集合B存放每步所求的临时结果，之后再赋值给A，清空集合B重新开始，最后B先有最终结果，此时只要返回B集合的个数即可结束。

其中如果求sp=l1.l2.…ln，则从根开始，沿着该路径一步一步地往下扫描。每个中间结果都是li所指向的所有对象（OEM图的结点）。每次扫描时，遍历标签所指对象的所有标签，判断是否是所求路径的一部分。当扫描到最后的ln时，集合B存放的是所有标签所指的对象结点，则结点数代表完整的路径数，即表示其支持度。所以，结果返回的是集合B的元素个数。

算法2 环路判断

bool judgecycle算法中用到了两个域，value和id。其中value是标签的名字，当发现标签的名字相同时不能断言重复，id存放位置信息，需要逐层编号（从左到右）。找到同一层同一位置时则为环路。

3 实验结果

实验表明，可以得到一个最频繁出现的时间数，精确到毫秒。有时，会频繁出现两组数据。对于图1中，min_sup（最小支持度阀值）的值分别为1，2，3时，时间分别为171 ms，125 ms和32 ms。出现两组数据是因为处理时间足够短时受硬件，比如cache替换算法的影响。这一数据对比其他算法处理同类型的OEM模型树时相差无几，但功能上更加完善。实现的运行结果如图2和图3所示，支持度分别定义为2和3。

图2 实验结果1Fig.2 Result of experiment 1

图3 实验结果2Fig.2 Result of experiment 2

4 结 语

笔者提出一个模式抽取算法的改进，采用了简单路径表达式，用来构建OEM模型图的数据模式的基础，把基于半结构化模型的频繁模式的模式抽取变成在OEM图中找最长频繁简单路径表达式的问题。

改进部分是支持度计算的分支处理和环路处理。加入了环路后，时间上与没有加环路并没有显著区别，但时间稳定在一个固定的区间，可见增加功能的高效性。有标准C实现后，输出结果经仔细验证无误。其中在实现时，OEM树固定输入在程序中，最小支持度也需要事先设定。

：

[1]何月顺，汤彬，丁秋林.基于Web的数据挖掘技术的应用研究[J].计算机系统应用，2005（5）：59-62.HE Yue-shun，TANG Bin，DING Qiu-lin.Research and Application of Data Mining Based on Web[J].Applications of the Computer Systems，2005（5）：59-62.

[2]刘先锋，李钒.基于半结构化数据模型的频繁模式挖掘研究[J].计算机工程与应用，2007，43（36）：173-176.LIU Xian-feng，LI Fan.Frequent Patterns Mining Based on Semi-Structured Data Model[J].Computer Engineering and Applications，2007，43（36）：173-176.

[3]PAPAKONSTANTINOU Y，GARCIA-MOLINA H，WIDOM J.Object Exchange Across Heterogeneous Information Sources[C]∥Eleventh International Conference on Data Engineering.Taipei：IEEE Computer Society Press，1995：251-260.

[4]SERGE ABITEBOUL.Querying Semi-Structured Data[C]∥The 6th International Conference on Database Theory.London：Springer-Verlag，1997：1-18.

[5]吕橙，魏楚元，张翰韬.基于OEM模型的半结构化数据的模式发现[J].计算机工程与应用，2006（34）：162-165.L¨U Cheng，WEI Chu-yuan，ZHANG Han-tao.Schema Discovery of Semi-Structured Data Based on OEM Model[J].Computer Engineering and Applications，2006（34）：162-165.

[6]刘芳，胡和平，路松峰.半结构化、层次数据的模式发现[J].小型微型计算机系统，2001，22（1）：84-88.LIU Fang，HU He-ping，LU Song-feng.Schema Discovery for Semi-Structured Hierarchical Data [J].Mini-Micro Systems，2001，22（1）：84-88.