null第五章 关联挖掘第五章 关联挖掘 5.1 概述
一.关联规则挖掘:
在交易数据、关系数据或其他信息载体中,查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。
null 关联规则与传统的分类规则的区别:
在某条规则中以前提条件出现的属性可以出现在第二条规则的结论中。
传统的分类规则通常将规则的结果限定为一个单一的属性值,关联规则生成器允许其结果包含一个或多个属性值。
null举例:
规则形式: “Head ® Body[support, confidence]”.
buys(x, “diapers”) ® buys(x, “beers”) [0.5%, 60%]
major(x, “CS”) ^ takes(x, “DB”) ® grade(x, “A”) [1%, 75%]
null应用:
顾客购物分析、目录设计、商品广告邮寄分析、追加销售、商品货架设计、仓储规划、网络故障分析以及根据购买模式对用户进行分类
null给定: (1)交易数据库
(2)每笔交易是:一个项目列表 (消费者一次购买活动中购买的商品)
查找: 所有描述一个项目集合与其他项目集合相关性的规则
应用
* 护理用品 (商店应该怎样提高护理用品的销售?)
家用电器 * (其他商品的库存有什么影响?)规则度量:支持度与可信度规则度量:支持度与可信度 查找所有的规则 X & Y Z 具有最小支持度和可信度
支持度 s:
一次交易中包含{X 、 Y 、 Z}的可能性
可信度 c, 包含{X 、 Y}的交易中也包含Z的条件概率设最小支持度为50%, 最小可信度为 50%, 则可得到
A C (50%, 66.6%)
C A (50%, 100%)买尿布的客户二者都买的客户买啤酒的客户null二、关联规则挖掘分类
1、 根据规则中所处理的值类型划分:
如果规则考虑的关联是项的在与不在,则它是布尔关联规则(Boolean association rule)。
例如,规则
Buys(X,”computer”)Buys(X,”financial_management_software”)
[ support=2%,confidence=60%] [5.1]
是由购物篮分析得到的布尔关联规则。null 如果规则描述的是量化的项或属性之间的关联,则它是量化关联规则(quantitative association rule)。
如: age(X,“30...39”) income(X,“42K...48K”)
buys(X,“computer”) (5.2)
注意,量化属性age和income已离散化。
null2、根据规则中涉及的数据维划分:
如果关联规则中的项或属性每个只涉及一个维,则它是单维关联规则
(5.1)是单维关联规则,因为它只涉及一个维buys。
如果规则涉及两个或多个维,则它是多维关联规则,
(5.2)是一个多维关联规则,因为它涉及三个维age,,income和buys。
age(X,“30...39”) income(X,“42K...48K”)
buys(X,“car”)
null 3、根据规则集所涉及的抽象层划分:
有些挖掘关联规则的方法可以在不同的抽象层发现规则。例如,假定挖掘的关联规则集包含下面规则:
age(X,“30...39”) buys( X, ”notebook_computer”)
age(X,“30...39”) buys( X, ” computer”), (5.3)
购买的商品涉及不同的抽象层 ,所挖掘的规则称为
-------多层关联规则。
反之,如果在给定的规则集中,规则不涉及不同抽象层的项或属性,则该集合包含单层关联规则null5.1null三. 购物分析
作为商家主管,想更加了解顾客的购物习惯。尤其希望了解在一次购物过程中,那些商品会在一起被购买,这就需要进行市场货物分析 ,即对顾客在商场购物交易
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
数据进行分析。所分析的结果可帮助商家制定有效的营销策略null 如果把商店中所有销售商品设为一个集合,则每种商品(Item)可看成一个布尔变量,表示该商品是否被购买。每次购物可用一个布尔向量表示。
这样就可以分析布尔向量,得到反映商品频繁关联或同时购买的购买模式。这些模式可以用关联规则的形式表示。例如,购买计算机也趋向于同时购买财务管理软件可以用以下关联规则表示:
nullBuys(X,”computer”)
Buys(X,” financial_management_software”) [ support=2%,confidence=60%] [5.1]
规则的支持度和置信度是两个规则兴趣度度量,分别反映发现规则的有用性和确定性。
如果关联规则满足最小支持度阈值和最小置信度阈值,则该关联规则被认为是有趣的。
null另外有趣的模式:
(1)规则显示出某个商品的销售额上升,而销售额的上升是与一个或多个其它商品关联的结果。可利用这个信息来促销因相互关联而销售额增加的商品
(2 )规则显示出某个关联的置信度低于所期望的值
--------关联规则列出的商品在争夺同一市场null 典型的关联规则算法是R.Agrawal等1994年提出的Apriori算法。 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。
5.2 由事务数据库挖掘单维布尔关联规则null一、基本概念(表示)
设I={i1,i2,…im}是数据项的集合。
D是数据库中与任务相关的事务的集合,其中每个事务T是数据项I的子集,即 TI
每一个事务有一个标识符,称作TID。
关联规则是形如 “A B”的蕴含式,
其中 “A I,B I, 且AB=Ø “。
规则“A B”在事务集D中成立,且具有支持度s和信任度c.
null其中s是D中事务包含 (A B)的百分比。这是条件概率。
即是:null5-2null项的集
合同
劳动合同范本免费下载装修合同范本免费下载租赁合同免费下载房屋买卖合同下载劳务合同范本下载
时满足最小支持度阈值(min_sup)和最小置信度阈值(min_conf)的规则称作强规则。
项的集合称为项集(itemset)。包含k个项的项集称为k-项集。
集合{computer,financial_management_software}是一个2-项集。
项集的出现频率是包含项集的事务数(支持计数或计数)。 null 如果项集的出现频率大于或等于min_sup 与D中事务总数的乘积,则称该项集满足最小支持度min_sup。
如果项集满足最小支持度,则称它为频繁项集(frequent itemset)。频繁k-项集的集合通常记作Lk。
关联规则挖掘—一个
例子
48个音标大全附带例子子程序调用编程序例子方差分析的例子空间拓扑关系例子方差不存在的例子
关联规则挖掘—一个例子对于 A C:
support = support({A 、C}) = 50%
confidence = support({C})/support({A}) = 66.6%最小支持度 50%
最小可信度 50%null二、 Apriori算法
1、 Apriori算法分两步进行:
(1) 找出所有频繁数据项集,即找出所有支持度超过指定阈值的数据项集
(2)利用频繁数据项集,生成侯选的关联规则,并验证其可信度。
如果可信度超过指定阈值,则该侯选关联规则为要找的关联规则
null2、Apriori的基本思想:
频繁项集的任何子集也一定是频繁的
频繁项集性质的先验知识(priori)
null3、 Apriori算法:使用候选项集找频繁项集
Apriori使用一种称作逐层搜索的迭代方法,利用k-项集来产生(k+1)-项集。
首先,找出频繁1-项集的集合。该集合记作L1。
然后利用L1找频繁2-项集的集合L2,如此不断循环下去,直到不能找到频繁k-项集。
每挖掘一层Lk, 就需要扫描整个数据库。
null 为提高频繁项集逐层产生的效率,Apriori算法利用Apriori性质压缩搜索空间。
Apriori性质:频繁项集的所有非空子集都必须也是频繁的。
根据定义,如果项集I不满足最小支持度阈值min_sup,则I不是频繁的,即P( I )< min_sup。
如果项A添加到I,则结果项集(A I)不可能比I更频繁出现。因此,也不是频繁的,即P (A I) < min_sup。
根据逆反公理:如果一个集合不能通过测试,则它的所有超集也都不能通过相同的测试 。
即:任何非频繁的(k-1)-项集都不可能是频繁k-项集的子集。
null(1)连接步:为找Lk ,通过Lk-1 与自己连接产生候选k-项集的集合。该候选项集的集合记作 Ck。
设l1和l2是Lk-1中的两个项集。
记号l i (j)表示l i的第j项
为方便,假定交易数据库中的交易记录已按字典次序排序。把 Lk-1的连接操作记为: Lk-1 Lk-1
其中元素可连接的条件是,它们前(k-2)个项相同(k>=2)。
即:
l1[1]= l2[1] l1[2]= l2[2] ….l1[k-2]= l2 [k-2]
l1[k-1] l2 [k-1] null(2) 剪枝步(删除):
Ck是Lk的超集;即其中的各元素不一定都是频繁项集,但所有的频繁k-项集都包含在其中。
即: Lk Ck
扫描数据库,可以确定Ck中每个候选项集的支持频度,从而确定Lk 中各元素(频繁k-项集,即所有频度不小于最小支持度)。
null 然而Ck 中的项集可能很大,这样所涉及的计算量就很大。为压缩,可以使用
如果一个候选k-项集的(k-1)-子集不属于Lk-1,
则该候选不可能成为频繁k-项集Lk是的元素,
从而可以由中删除。
可以利用HASH表来保存所有频繁项集以便能快速完成这一子集测试工作。
null例5.1 交易记录事务数据库有9个事务。用Apriori算法寻找D中的频繁项集。
5-3null1)计算C1并计数.
在算法的第一次迭代,每个项都是候选1-项集的集合的成员。扫描所有的事务,对每个事务出现次数计数。
2)确定L1.
假定最小事务支持计数为2(即min_sup=2/9=22%)。可以确定频繁1-项集的集合L1。它由具有最小支持度的候选1-项集组成。
nullnull3)生成C2
为发现频繁2-项集的集合,算法使用产生候选2-项集的集合。由个2-项集组成。
4)计算C2中成员出现的次数
扫描D中事务,计算中每个候选项集的支持计数,
5)由C2确定L2
确定频繁2-项集的集合,它具有最小支持度的中的候选2-项集组成。
6)候选3-项集的集合的产生如下表5-2所示:
null表5-2null 7)扫描D中事务,以确定L3,它由具有最小支持度的C3中的候选3-项集组成
8)算法使用L3 L3 产生候选4-项集的集合C4。 C4={{I1,I2,I3,I5}},因为它的子集{I2,I3,I5}不是频繁的,这个项集被剪去,这样
C4= Ø , 因此算法终止,找出了所有的频繁项集。
null算法5.1给出了Apriori算法和它的相关过程的伪代码。
null4.14.1nullnull三、 由频繁项集产生关联规则
对于置信度,可以用下式计算,其中条件概率用项集支持度计数表示:
5.4null产生关联规则的步骤
(1) 对于每个频繁项集l,产生l的所有非空子集。
(2)对于l的每个非空子集s,
如果,
则输出规则
其中,min_conf 是最小置信度阈值。
null 由于规则是通过频繁项集直接产生的,因此关联规则涉及的所有项集都自动满足最小支持度。频繁项集连同它们的支持度可预先存放在散列表(HASH表)中,使得它们可以快速被访问。
null例5.2 假定数据包含频繁集l={I1,I2,I5} (计数2),可以由l产生哪些关联规则?
l的非空子集有:
{I1,I2},{I1,I5},{I2,I5},{I1},{I2}和{I5},其频繁数分别为:
4,2,2,6,7,2
null 结果关联规则如下,每个都列出置信度
(1) I1I2I5 , confidence=2/4=50%
(2) I1I5I2 , confidence=2/2=100%
(3) I2I5I1 , confidence=2/2=100%
(4) I1 I2 I5 , confidence=2/6=33%
(5) I2 I1 I5 , confidence=2/7=29%
(6) I5 I2 I1 , confidence=2/2=100%
如果最小置信度阈值为70%,则只有第2、3和最后一个规则可以输出,因为只有这些是产生的强规则。
null四、描述关联规则的属性
1、可信度(confidence)
设事务集W中支持物品集A的事务中,有c%的事务同时也支持B, c%称为关联规则A--》B的可信度
2、支持度(support)
设事务集W中有s%的事务同时支持物品集A和B, s%称为关联规则A--》B的支持度
null3、期望可信度
设事务集W中有e%的事务支持支持物品集B, e% 称为关联规则 A--》B 的期望可信度
4、作用度(lift)
作用度(lift)是可信度与与期望可信度的比值
四个参数的计算
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
四个参数的计算公式null 可信度是对关联规则准确性的度量
支持度是对关联规则重要性的度量
支持度说明这条规则在所有的事务中有多大的代表性。
显然支持度越大,关联规则越重要,应用范围就越广。
有些关联规则可信度虽然很高,但支持度却很低,说明该关联规则实用的机会很少,因此也不重要null期望可信度描述了在没有物品A的作用下,物品集B本身的支持度;作用度描述了物品集A 对物品集B 的影响。
一般情况下,有用的关联规则的作用度都应该大于1,只有关联规则的可信度大于期望可信度,才说明A的出现对B有促进,也说明它们之间某种程度的相关性。null五、 Apriori算法的改进
1、对数值性属性的处理
----将连续数据离散化,从而把数量属性的关联规则的问题转换成布尔型关联规则的问题进行讨论。
(1)将属性的论域划分为不重叠的区间,再将数据库中的离散数据映射到这些区间中。
(2)将属性的论域划分为重叠的区间
null 定义属性论域上的模糊集来软化边界
陆建江等“数据库中广义模糊关联规则的挖掘”(工程数学学报)
模糊集可以在集合元素和非集合元素之间提供平滑的变迁,使得几乎所有边界附近的元素不会再被排斥在外,同时也不会被过分强调
Apriori算法 — 例子(数值属性离散化)Apriori算法 — 例子(数值属性离散化)数据库 D扫描 DC1L1L2C2C2扫描 DC3L3扫描 Dnull2、非事务数据库中关联规则的挖掘
有些数据不像售货数据那样很容易就能看出一个事务是许多物品的集合,但其本质上仍可以像对售货数据一样处理。
比如人寿保险。
一个保单就可看成一个事务。
保单记录:
年龄、性别、健康状况、工作单位、工作地址、工资水平、是否索赔等。
这些信息就可以看作是事务中的物品。关联规则在保险业中的应用举例关联规则在保险业中的应用举例null 这 是 一 份 保 单 数 据, 一 条 记 录 存 储 了 一 个 投 保 人 的 一 些 基 本 信 息 以 及 其 索 赔 次 数。
通 过 数 据 挖 掘 找 出 索 赔 过 的 投 保 人 有 什 么 特 征, 没 索 赔 过 的 投 保 人 有 什 么 特 征。
主 要 关 心 索 赔 次 数 以 及 与 此 相 关 的 信 息, 可 以 认 为 保 单 号、 单 位 代 号、 单 位 名 称 是 一 些 无 关 信 息, 因 此 从 源 数 据 中 挑 选 年 龄、 年 工 资、 单 位 类 别、 单 位 地 区、 索 赔 次 数 这 几 列 做 进 一 步 的 分 析。 null 注 意 到 年 龄、 年 工 资 是 数 值 数 据( 连 续 数 据)
为 了 离 散 化, 我 们 根 据 数 据 值 的 范 围 对 数 据 进 行 分 组:
年 龄 分 为(,40〗,(40,50〗,(50,60〗,(60,70〗,(70...〗 五 个 组, 年 工 资 分 为(,6000〗,(6000,10000〗,(10000, ∞) 三 个 组。 nullnull 关 联 规 则 挖 掘 的 任 务 是:
给 定 一 个 事 务 数 据 库D, 求 出 所 有 满 足 最 小 支 持 度 和 最 小 可 信 度 的 关 联 规 则。
需 要 指 定 最 小 支 持 度 和 最 小 可 信 度。
默 认 的 最 小 支 持 度 为1 %。 要 求 的 最 小 支 持 度 越 高, 挖 掘 出 的 规 则 越 少, 挖 掘 的 过 程 也 越 快。
默 认 的 最 小 可 信 度 为50 %。 这 里 最 小 支 持 度 和 最 小 可 信 度 都 取 默 认 值.null----- 单 位 类 别=3 是 否 索 赔=0;
----此 规 则 的 四 个 参 数 的 具 体 数 值 分 别 是:
支 持 度 为60.77 %, 可 信 度 是85.18 %, 期 望 可 信 度 是84.00 %, 作 用 度 是1.03。
----这 条 规 则 告 诉 我 们: 在 所 有 的 投 保 人 中, 60.77 % 的 投 保 人 单 位 类 别 是3 并 且 没 有 索 赔 过;
有84.00 % 的 投 保 人 没 有 索 赔 过;
在 单 位 类 别 是3 的 投 保 人 当 中, 共 有85.18 % 的 投 保 人 没 有 索 赔 过;
作 用 度 是1.03, 说 明“ 单 位 类 别=3” 这 个 条 件 对 投 保 人 是 否 索 赔 没 有 太 大 的 影 响, 因 为 有 没 有 这 个 条 件, 投 保 人 的 索 赔 率 并 没 有 太 大 的 区 别。null------ 以 上 挖 掘 得 到 的 关 联 规 则,LHS 和RHS 中 都 只 包 含 一 种 物 品( 条 件), 是1 对1 的 单 路 规 则;
如 果 允 许LHS 和 RHS 中 包 含 多 种 物 品, 用 同 样 的 数 据 和 限 制 条 件 可 以 得 到 多 路 规 则, 用 记 录 浏 览 器 来 观 察 结 果, 如 表3 所 示。 其 中, 行 是 一 条 关 联 规 则, 各 列 分 别 给 出 了 关 联 规 则 的LHS、RHS 及 四 个 参 数 的 值。 nullnull 从 表3 可 以 看 出:
单 位 类 别 是3 并 且 年 龄 在40 岁 到50 岁 的 投 保 人 当 中,93.1 % 没 有 索 赔 过, 明 显 高 于 期 望 可 信 度; 。
如 果 有 客 观 原 因 存 在( 例 如,3 这 种 类 别 的 单 位 可 能 压 力 不 大, 不 很 疲 劳, 故 而 发 病 率 不 高), 那 么 保 险 公 司 就 可 以 多 针 对 满 足 这 些 条 件 的 潜 在 客 户 开 展 工 作, 从 而 可 以 减 少 风 险, 提 高 公 司 盈 利。 null3、算法效率的改进
算法Apriori
Input :DB,minsup
Output: Result=所有的频繁项集,和它们的支持度
方法
nullResult:={ };
k:=1;
C1:=所有的1项集
While (Ck) do
begin
为Ck每一个中的项集生成一个计数器;
for (i=1;i<=|DB|;i++)
begin / *所有DB中的记录T* /
对第i个记录T支持的每一个Ck中的项集,其计数器加1;
end
Lk:= Ck中满足大于minsup的全体项集;
保留Lk 的支持度;
Result:= Result∪Lk
Ck+1:=所有的(k+1) 项集中满足其k子集都在L里的全体;
k:=k+1
enddo
Apriori 够快了吗? — 性能瓶颈Apriori 够快了吗? — 性能瓶颈Prior算法的核心:
用频繁的(k – 1)-项集生成候选的频繁 k-项集
用数据库扫描和模式匹配计算候选集的支持度
Apriori 的瓶颈: 候选集生成
巨大的候选集:
104 个频繁1-项集要生成 107 个候选 2-项集
要找尺寸为100的频繁模式,如 {a1, a2, …, a100}, 你必须先产生2100 1030 个候选集
多次扫描数据库: 提高Apriori效率的方法提高Apriori效率的方法减少交易记录: 不包含任何频繁k-项集的交易也不可能包含任何大于k的频繁集
分割: 一个项集要想在整个数据库中是频繁的,那么他至少在数据库的一个分割上是频繁的。
采样: 在给定数据的子集上挖掘,使用小的支持度+完整性验证方法
动态项集计数: 在添加一个新的候选集之前,先估计一下是不是他的所有子集都是频繁的。null(1)基于散列(HASH表)的技术(散列项集计数):
实验发现查找频繁项集的主要计算是生成L2,Park利用HASH表技术可以帮助有效压缩候选k-项集Ck(k>1)所占用的空间null 例如,当扫描数据库中每个事务以便从候选l-项集C1产生频繁l-项集L1时,就可以为每个事务产生所有的2-项集,将它们散列(即映射)到散列表结构的不同桶(栏目)中,并增加对应的桶计数null5-45-3null 在散列表中对应的桶计数低于支持度阈值的2—项集不可能是频繁2—项集,因而应当由候选项集中删除。这种基于散列的技术可以大大压缩要考察的A-项集(特别是当k=2时)。
null(2)事务压缩(压缩进一步迭代扫描的事务数):
减少在后面的循环中所需要扫描的交易记录数
不包含任何k-项集的事务不可能包含任何(k+1)-项集。这样,这种事务出现时,可以加上标记或删除,因为以后产生j-项集(j>k),扫描数据库时不再需要它们。
null(3)划分数据
该思想是先把数据库从逻辑上分成多个互不相交的块,每次单独考虑一个分块并对其生成所有局部频繁项集(1ocal frequent itemset)。然后合并生成所有可能的频繁项集,最后计算其支持度。
块大小的选择是要使每个分块可放入内存。这个方法高度并行,把每一块分别分配给某一个处理器生成频繁集。产生频繁集的每一个循环结束后,处理器之间通过通信产生k项集。
通信过程是执行时间的主要瓶颈,另外,每个独立处理器生成频繁集的时间也是一个瓶颈
null图5-5null(4)选样(在给定数据的一个子集挖掘):
选样方法的基本思想是:选取给定数据库D的随机样本S,然后,在S而不是在D中搜索频繁项集。
牺牲精度换取有效性。样本S的大小可以放入在内存null (5)动态项集计数(在扫描的不同点添加候选项集):
Apriori仅在每次完整的数据库扫描之前确定新的候选。
该技术动态地评估已被计数的所有项集的支持度,如果一个项集的所有子集已被确定为频繁的,则添加它作为新的候选。结果算法需要的数据库扫描比Apriori少。
5.3 多层关联规则5.3 多层关联规则一、 多层关联规则
对于许多应用,由于数据在多维空间的多样性,在低层或原始层的数据项之间很难找出强关联规则。在较高的概念层发现的强关联规则可能提供普遍意义的知识。多层关联规则多层关联规则项通常具有层次
底层的项通常支持度也低
某些特定层的规则可能更有意义
交易数据库可以按照维或层编码挖掘多层关联规则挖掘多层关联规则自上而下,深度优先的方法:
先找高层的“强”规则:
牛奶 ® 面包 [20%, 60%].
再找他们底层的“弱”规则:
酸奶 ® 黄面包 [6%, 50%].
多层关联规则的变种
层次交叉的关联规则:
酸奶 ® 挪亚面包房 黄面包
不同种分层方法间的关联规则:
酸奶 ®挪亚面包房面包多层挖掘的例子多层挖掘的例子5-3null5-6null 表5-3中的项在图5-6概念分层的最低层。在这种原始层很难找出有趣的购买模式。
例如,“IBM desktop computer”和“Sony b/w(黑白) printer” 每个都在很少一部分事务中出现,可能很难找到涉及它们的强关联规则。很少有人同时购买它们,使得“{IBM desktop computer, Sony b/w printer}” 不太可能满足最小支持度 null 然而,若将“Sony b/w printer”概化到“b/w printer”, 则在“IBM desktop computer” 和“b/w printer”之间比在“IBM desktop computer”和 “Sony b/w printer” 可望更容易发现强关联。类似地,许多人同时购买“computer”和“printer”,不是同时购买特定的“IBM desktop computer”和“Sony b/w printer”。null 换句话说,包含更一般项的项集,如“{IBM desktop compute, b/w printer}” 和“{computer, printer}”,比之于仅包含原始层数据的项集,如“{IBM desktop computer,Sony b/w printer}”,更可能满足最小支持度。因此,在多个概念层的项之间找有趣的关联比仅在原始层数据之间更容易找。
null二、挖掘多层关联规则的方法
一般地,可以采用自顶向下策略,由概念层l开始向下,到较低的更特定的概念层,对每个概念层的计算频繁项集累加计数,直到不能再找到频繁项集。
即:一旦找出概念层1的所有频繁项集,就开始在第2层找频繁项集,如此下去。对于每一层,可以使用发现频繁项集的任何算法,如Apriori或它的变形。
null多层关联规则基本上可以沿用“支持度—可信度”的框架,只是在支持度的设置上有一些特殊的要考虑的
内容
财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容
。
多层关联规则可以分为如下规则
1、同层关联规则
null(1)支持度不变: 在各层之间使用统一的支持度
对于所有层使用一致的最小支持度(称作一致支持度):在每一层挖掘时,使用相同的最小支持度阈值。
例如,在图5-7中,整个使用最小支持度5%(对于从“computer”到“laptop computer”)。发现“computer”和“laptop computer”都是频繁的,但“desktop computer”不是。
null图5-7null支持度不变的优缺点
优点:
一个最小支持度阈值.
如果一个项集的父项集不具有最小支持度,那它本身也不可能满足最小支持度。
缺点:
底层项不会成为频繁集,如果支持度
太高 丢失底层关联规则
太低 生成太多的高层关联规则
null(2)在较低层使用递减的最小支持度(称作递减支持度):
每个抽象层有它自己的最小支持度阈值。抽象层越低,对应的阈值越小。例如,在图5—8,层1和层2的最小支持度阈值分别为5%和3%,用这种方法,“computer”、“laptop computer”和“desktop computer”都是频繁的。
null图5-8null支持度递减: 随着层次的降低支持度递减
4种搜索策略:
层与层独立
用k-项集跨层过滤
用项跨层过滤
用项进行可控跨层过滤
null● 逐层独立:这是完全的宽度搜索,不任何利用频繁项集的背景知识来帮助剪去项集。无论该节点父节点是否频繁,都要对每个结点进行检查。
null● 利用单项进行垮 层过滤:
当且仅当父结点在第(i-1)层是频繁的,才检查个第i层的项。换句话说,如果一个节点是频繁的,它的子孙将被考察;否则,它的子孙将由搜索中剪枝。
例如,在图5—9中,若第一层的min-sup=10%,则 “computer”的后代节点(即“laptop computer”和“desktop computer”)将不被考察,因为“computer”不是频繁的。
null图5--910%null2、层间关联规则
按较低层次的最小支持度来确定.
单维和多维(维间和混合维)
符号型和数值型的处理
(1)分成一些预定义的层次结构---静态数量关联规则
(2)根据数据分布分成一些布尔字段--布尔数量关联规则
(3)分成一些能体现其含义的区间---基于距离的关联规则
(4)使用一些统计方法直接分析原始数据,并且结合多层关联规则的概念,在多个层次之间进行比较得出—多层数量关联规则
null作业:
1、查找Aprior算法实现和应用的文献
2、查找多层关联规则应用的文献
3、结合实际,找出一个可用关联规则挖掘的实际例子