文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 基于概念格的频繁闭项集增量挖掘算法研究
侵权投诉

基于概念格的频繁闭项集增量挖掘算法研究

近年的研究表明,概念格可以应用于解决频繁闭项集的挖掘问题.针对已有渐进式概念格构造算法中存在的问题,提出了一种基于概念格的频繁闭项集增量挖掘新算法——FIPT-I算法.新算法利用模式树对概念格进行组织,并利用模式树压缩数据库中的事务,在渐进式构造概念格的同时实现了事务的批处理,减少了概念格的调整操作时间.实验结果表明,与其他同类算法相比,FIPT-I算法对于增

维普资讯 doc.guandang.net

第 2期

战立强,:于概念格的频繁闭项集增量挖掘算法研究等基

规则可以表示为 X y,里 X和 y是 I i中的项 这 -s lt

含的模式. G中结点内涵对应的项目集为格结称 L点模式 .

集, Xny一规则 X y的支持度记为 sp ot且 . upr

( xUy,的可信度为 sp otXUY/ u p r( . )它 upr ( ) sp otX) 满足下面条件的项目集 x被称为是闭项集: V,i Y f XC Y,t e u or (< s p t X ) h n

s pp t Y) up or ( .

2模式树及其操作 模式树是与 F—re6同的一种数据结构, P te[相]只是不需要它的头表和结点链 .式树在 F P -算法模 IT I中有 2种用途: )于将 D压缩于内存,为 T 1用称 _ te; )于表示 G称为 C te.于模式树的操 re 2用 L,—re关作主要有树的构建、分和 C树投影.拆 在模式树上,根结点外的每个结点均含有 2除

关联规则挖掘的第一步,是关键的一步,也是从 D中找出所有的频繁项集.验表明,用 F I实使 C可

以减少提交给用户的规则的冗余度.年来的研究近 表明,果将寻找频繁项集改为寻找 F I可以在不如 C,

丢失信息的前提下,幅度提高算法的效率 .大 12概念格 .

个域: b l和 cu t域,别纪录结点所代表项 l e域 a on分目的名称和支持度值 . -re和 C t e的构造算法 T te—e r 稍有不同: Fu c i n M a— r e m o,£ n to ke t e ( de )

在形式概念分析中,式背景 (oma c n e t形 fr l o tx) 被定义为一个三元组 K一( A,,中 0和 A分 0, R)其别是对象集合和属性集合, R是 0与 A之间的一个二元关系, R 0×A.即 如果 0∈0,∈A, o: n则 Ra ̄ 0具有属性 n在 0的幂集 P(和 A的幂集 P( . 0) A)之间可以定义如下 2映射:个 厂 P( ) P(,X∈ P(,厂 X){∈ A 1∈: 0一 A) 0) (一 n 0 X,o Ra},

//*mo e d决定模式树的类型,是被添加的模式, t 且其中项目已按字典排序 */ / {

i树{ f空

创建根结点 ro; ot 指针 T指向 ro o t} J Lnt/— e ()/* J为 t长度 */ 的/ fr o一 1t{ oJ

g: A) P(, P(一 0) Y∈ P(, (一{∈0I∈ Y, A) g y) 0 n o Ra} .

厂 X) g y)以用 3和 Y表示,样 g (和 (可 7 同 厂 X) f (可以用和表示 .个形式概 (和 g y)一念是一个二元组 (,,中 X∈ P(, P(, x y)其 0) Y∈ A)

iT f有一个标号 P

的孩子节点{ imo e T te”;/*构造 T te */ f d=“— e/ r—re/ P . o n= P . o n+ t. o n; c u t c u t c u t

X=Y, y—X .和 y分别被称为概念 ( y) X X,的外 延和内涵 .由形式背景 K一 ( A,包含的概念集 0, R)

/ * tc u t/ . o n表示 t中第 i个项目的计数 *// es/ le/造 C te f—r e f P ou= ma p . o t。 c u ) .c nt x( c un,t. o nt;

合记为 C ( . C (中存在一种偏序关系, S K)在 S K)这种偏序关系是由概念之间内涵和外延的包含关系形 成的: (, )≤ K(, ) X1 X1 Y1 X2 Y2甘 X2 y2 ( Y1 . )

T指向该标号为 P的节点; } le{ Es

有序集 C ( S K)构成一个完全格,为概念格或 Ga称— li格,为 GL一 ( S K )≤ ) os记 C (, .

创建一个新孩子节点 ( t c u t,指向新 , .o n ) T 节点;} } }

概念格提供了一种关于 x和 y对的层次结构. 可以将 I看成是 A,看成是 0来构造概念格 GL D .

显然, GL中的每一个结点都是 D中的一个 c I (lsdi mst, C相当于概念的内涵 . co e e e)即 I t由于这里使用概念格的目的是挖掘 F I可以将 C被数据 C, I库包含的次数, C的基数作为概念的外延 .即 I

例如, 1是一个事务数据库,~8是数据库表 1 中包含的原事务,新增事务数据库 A为{ C,、 D A, E}{ B,、A, D, . 1是由新增事务建立的 A, D}{ B, E}图 T te, 2是由原事务中的格结点模式构造的 C - e图 r _ te. re模式树上 Ro t的子结点称为子根结点, o具有多于 1子结点的结点称为分支结点 .的拆分是个树

从概念格的定义不难得到如下 2个结论: 1如果 G由 D构造,对于 VT∈ D, X, ) L则 ](

y)∈GL,足 T—Y.满 2如果 G由 D构造, ) L则对于 VT, T∈D,若 M—T1 2 M≠,]( Y) T, n则 X,∈G L,满足 M— y.

指将 Ro t点

下的子树拆分成单分支模式或单一 o结 模式的集合.分支模式是一棵没有分支结点的模单

式树,而单一模式是所有结点的 c u t都相同的 on值单分支模式.于一条从子根结点到叶结点的路径对 P,函数 ds se l te得到单分支模式 P (数 iasmbe re -参

2个事务或模式的交运算得到 2个事务共同包

基于概念格的频繁闭项集增量挖掘算法研究

上一页第2页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email