《数据仓库算法总结》由会员分享，可在线阅读，更多相关《数据仓库算法总结（31页珍藏版）》请在金锄头文库上搜索。
1、数据仓库算法总结事务处理环境不适宜DSS应用的原因：(1) 事务处理和分析处理的性能特性不同(2) 数据集成问题(3) 历史数据问题(4) 数据的综合问题数据仓库数据的四个基本特征:(1) 数据仓库的数据是面向主题的(2) 数据仓库的数据是集成的(3) 数据仓库的数据是不可更新的(4) 数据仓库的数据是随时间不断变化数据仓库定义： 数据仓库是在企业管理和决策中面向主题的、集成的、与时间相关的(时变的)、不可修改的 (非易失的)数据集合，用于支持管理决策。支持度若D中的事务包含AQ包即和和元二者)的百分比为s ,贝y称关联规则AB的支持度为 s。即：support (AnB)=P(A元组总、数可
2、信度/置信度若D中包含A的事务同时也包含B的百分比为c ,则称关联规则AnB的置信度/可信度为 c。即：confidence(AnB)=P(BIA) = support(AUB)/support(A)频繁项集 项集的出现频率是包含项集的事物数,简称项集的频率。项集满足最小支持度阈值minsup：如果项集的出现频率大于或等于minsup与D中事物总数 的乘积。满足最小支持阈值的项集就称为频繁项集(或大项集)。频繁k项集的集合记为Lk。定理( Apriori 性质)频繁项集的所有非空子集都必须也是频繁的。 任何非频繁项集的超级一定也是非频繁的Apriori 算法具体做法：对于所研究的事务数据库D,
3、首先找出频繁1-项集的集合，记为L1 ；再用L1 找频繁2-项集的集合L2 ；再用L2找L3如此下去，直到不能找到频繁k-项集为止。找 每个Lk需要一次数据库扫描。如何实现用Lk-1找Lk.连接步：为找Lk,通过Lk-1与Lk-1连接产生候选k-项集的集合。该候选项集的集合记作Ck,执行Lk-1与Lk-1的连接：如果他们前（k-2）个项相同，则可连接。剪枝步：任何非频繁的（k-1）项集都不可能是频繁k-项集的子集。因此，进行剪枝。HD项m的列左T1M!nr 12. isT20014T300I2r 131400II， 12, 14TSim/，F砂J2, A?T7miHr /.?T800Il, 1
4、2, 13, 15T900II, 12. 13例1：该例基于某商店的事务DB。DB中有9个事务, Apriori假定事务中的项按字典次序存放。（1）在算法的第一次迭代，每个项都是候选1-项集的集合C1 的成员。算法简单地扫描所有的事务，对每个项的出现次数计 数。扫描D,对每 个候选计数（2）设最小支持计数为2,可以确定频繁1-项集 的集合L1。它由具有最小支持度的候选1-项集组成。比较候选支持度计数与最小支持度计数（3）为发现频繁2-项集的集合L2，算法使用（4）扫描D中事务，计算C2中每个候选项集的支持计 数。扫描D,对每 个候选计数顶集支持度计数旳6127O6网2152项集支持度计数116
5、阳7136何2IS2顶集支持度计数f仏 124何134阿吗1(11. is2 (i2r 13412, f42i2r 15 n2140阿冏 11i4.网0(5)确定频繁2-项集的集合L2，它由具有最小支持度的 C2中的候选2-项集组成。项渠支持度i卜数的働411. 134” 15212. 134阻14212. 15)2比较候选支持度计数 与最小支持度计数(6)候选3-项集的集合C3的产生如下:连接:C3 =LZL211,12,13的 2-项子集是I1,I2, 11,12,15的 2-项子集是I1,I2, 11,13,15的 2-项子集是I1,I3, 由 C3 中删除11,13,15。12,13,
6、14的 2-项子集是I2,I3, 的，由C3中删除12,13,14。12,13,15的 2-项子集是12,13, 的，由C3中删除12,13,15。12,14,15的 2-项子集是I2,I4, 的，由C3中删除12,14,15。扫描D,对每 个候选计数=I1,I2, I1,I3, I1,I5, I2,I3, I2,I4, I2,I5X I1,I2，I1,I3，I1,I5, I2,I3, I2,I4, I2,I5=I1,I2,I3, I1,I2,I5,I1,I3,I5, I2,I3,I4, I2,I3,I5, I2,I4,I5 利用Apriori性质剪枝：频繁项集的所有子集必须是频繁的。存在候选
7、项集，判断其子集 是否频繁。11,13和I2,I3,它们都是L2的元素。因此保留11,12,13。11,15和I2,I5,它们都是L2的元素。因此保留11,12,15。 11,15和I3,I5,I3,I5不是L2的元素，因而不是频繁的，12,14和I3,I4,其中13,14不是L2的元素，因而不是频繁12,15和I3,I5,其中13,15不是L2的元素，因而不是频繁12,15和I4,I5,其中14,15不是L2的元素，因而不是频繁这样，剪枝后 C3 = 11,12,13, 11,12,15。(7)扫描D中事务，以确定L3，它由具有最小支持度的C3中的候选3-项集组成。由E产生候选C238)算法
8、使用L- L3产生候选4-项集的集合C4。尽管连接产生结果11,12,13,15,这个项集被剪去，因为它的子集12,13,15不是频繁的。则C4 =空集，因此算法终止，找出了 所有的频繁项集。关联规则的生成：根据上面介绍的关联规则挖掘的两个步骤，在得到了所有频繁项目集后，可以按照下面的步 骤生成关联规则：对于每一个频繁项目集l生成其所有的非空子集；对于 l 的每一个非空子集 X,计算 Conference(X)，若 Confidence(X)三minconfidence, 则 “Xn(l- X)” 成立。由于规则由频繁项集产生，每个规则都自动满足最小支持度。例2：71DID列表T10011,1
9、2,15T200I2J4T3DOI2J3T400I1J2J4T500I1J3T60012,13T700I1J3T8OT11,12,13.15T90011,12,13基于例1的结果，假定数据包含频繁项集l=Il, I2, I5。可以由l产生哪些关联规则?L (L)的非空子集有Il，I2、Il，I5、12, I5、Il、12 和15关联规则如下：11 a 12 n I5,confidence = 2； 4= 50%11 a 15 n I2,confidence = 2；:2= 100%12 a I5 n 11,confidence = 2；2= 100%11 n I2 a I5,confidenc
10、e = 2； 6= 33%12 n 11 a I5,confidence = 2；7= 29%I5 n 11 a I2,confidence = 2:；2 -100%如果最小置信度阈值为70%，那么只有第2、3、6个规则可以作为最终的输出，因为只有 这些是产生的强规则。序列关联规则收集到的数据中常常存在某种顺序关系，通常是基于时间的先后顺序。对象时间戳事件A11, 2, 4A22, 3A35B11, 2B22, 3, 4C11, 2C22, 3, 4C32, 4, 5D12D23, 4D34, 5对于识别动态系统的重要特征，或预测特定事件的未来发生，序列信息将是很有价 值的。每一行记录与一个特
11、定的对象相关联的一些事件在 给定时刻的出现。时间戳不是一个具体的时间，而是一个象征性的时 间，表示时间上的先后次序。将与对象A有关的所有事件按时间戳增序排列就得 到对象A的一个序列(sequence)o数据序列(data sequence)是指与单个数据对象相关 联的事件的有序列表。如表中显示的数据集包含四个数 据序列，对象A, B, C, D各一个。设 D 是包含一个或多个数据序列的数据集序列s的支持度是包含s的所有数据序列所占的比例。如果序列s的支持度大于或等于用户给定的最小支持度阈值(minsup),则称s是- 个频繁序列。以前面给定的包含4个数据序列的数据集为例，序列的支持度等于75%
12、。 假定minsup=50%，则至少出现在2个数据序列中的任何序列都是序列模式：minsup=50%序列模式的例子:s=75%，除D外s=75%，除D外序列合并规则序列S1和序列S2合并，仅当从S1中去掉第一个事件后得到的子序列与从S2中去掉最后 一个事件后得到的子序列相同，结果候选是序列S1和序列S2的最后一个事件连接，S2的 最后一个事件可以作为最后一个事件合并到S1的最后一个元素中，也可以作为一个不同的 元素，这取决于如下条件：如果S2的最后两个事件属于相同的元素，则S2的最后一个事件在合并后的序列中 是 S1 的最后一个元素的一部分如果S2的最后两个事件属于不同的元素，则S2的最后一个事件在合并后的序列中 成为连接到 S1 的尾部的单独元素序列关联算法的连接和剪枝步骤的例子(其中，每个是指一个元素， 1， 2， 3， 4， 5是指 事件)产生候选4序列 候选4序列剪枝 a 频繁3序列 对于给定的序列s，,形如s n t的表达式就是序列关联规则。 序列关联规则s n t的置信度是支持序列s和t的数据序列数 与仅支持s的数据序列数之比。例如， n 的置信度为：s()/s()=1只凭支持度和可信度阈值未必总能找到符合实际的或有意义的规则, 应该在关联规则XnY的置信度超过某个特定的度量标准时，定义它为有意义。在此引入Lift值（增益）:
