近年的研究表明,概念格可以应用于解决频繁闭项集的挖掘问题.针对已有渐进式概念格构造算法中存在的问题,提出了一种基于概念格的频繁闭项集增量挖掘新算法——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个事务共同包

分布式环境下闭频繁项集全局挖掘算法. 此算法利用 Iceberg 概念格的半格以及可... 其也可以用来增量式构造 Iceberg 概念格; 2007 年 Hu 等人〔4〕 使用改进后...
基于iceberg概念格并置集成的闭频繁项集挖掘算法_专业资料。由于概念格的完备性,在基于概念格的数据挖掘过程中,构造概念格的时间复杂度和空间复杂度一直是影响其...
基于概念格的频繁闭项集增... 2人阅读 5页 2.00元 一种挖掘频繁闭项集...挖掘出频繁闭项集,根据CHARM算法提出了一种基于频繁闭项集挖掘的增量式维护算法...
基于Iceberg概念格叠置半集成的全局闭频繁项集挖掘算法_专业资料。研究专有的分布式数据挖掘算法是提高分布式数据库下数据分析和挖掘的有效方法.结合Iceberg概念格对于...
主要研究工作包括: 1) 提出一种基于概念格的增量...一般一种发现算法不可能适合所有的挖掘问题的需要。 ... 找出所有的频繁项目集及其支持率; 根据找到的频繁...
基于概念格的集中式数据挖...繁概念直乘分布 的全 局 闭频繁 项 集挖 掘算法 柴玉梅 张卓 王黎明 ( ...
基于概念格的组规则产生集的算法研究李 勃1, 刘... 数据挖掘中传统的关联规则生成算法产生的关联规则...(FP 表示, 所有非频繁伪封闭项集的集合用 IP ...
基于概念格的组规则产生集的算法研究 数据挖掘中传统的关联规则生成算法产生的关联规则集合相当庞大,其中很多规则可由其它规则导出。使用闭项集可以减少规则的数目,...
一种关联规则增量式挖掘算法研究_专业资料。现有关联规则更新算法都是基于支持度.置信度框架而提出的,仅针对大于最一J、支持度闭值的频繁项集进行挖掘。为了提高...
近似概念格及其增量构造算法研究_专业资料。针对传统概念格处理不完备信息的局限... 基于概念格的频繁闭项集... 4人阅读 5页 2.00 概念特化的概念格更新...
热门文档