data 数据挖掘培训1ppt课件

数据挖掘DataMining 2020 2 24 三 数据挖掘技术1 1 基本概念2 有效的和可伸缩的频繁项集挖掘方法3 挖掘各种类型的关联规则4 由关联挖掘到相关分析5 分类与预测基本概念6 决策树技术 挖掘动机 什么产品经常被一同购买 啤酒和尿布 买了PC后接下来会买什么 哪类DNA对新药敏感 能否对web文档自动分类 频繁项集 闭项集和关联规则 概率论基本知识 P A B 发生A或发生B的概率P B A A条件下B发生的概率事件相关性相互独立事件 datamining 3 3 1基本概念 频繁模式与关联规则 项集X x1 xk 每个事务T是项的集合关联规则是形如X Y的蕴涵式 满足最小支持度和置信度支持度s 事务中同时包含项X Y的概率置信度c 事务包含项X时也包含项Y的条件概率 关联规则挖掘的一般步骤 1 找出所有的频繁项集 support X supmin 2 由频繁项集产生强关联规则 从大型数据库中挖掘频繁项集的主要困难在于将产生大量的频繁项集频繁k项集 含k个频繁项一个长项集包含大量的频繁子项集的组合 n个频繁1项集 可能组合出的频繁项集C1n C2n Cnn 2n 1 基本概念 闭项集和极大项集 解决办法 挖掘闭项集和极大项集闭 频繁 项集 若不存在真超项集Y Y X 使得Y与X在数据集S中有相同的支持度计数 则称项集X在S中是闭的 极大 频繁 项集 如果X是频繁的 并且不存在频繁的超项集Y使得Y X 称X是极大项集 闭项集包含了频繁项集的完整信息减少了频繁项集和规则的数量 关联规则挖掘 一个例子 对于规则A C support support A C 50 confidence support A C support A 66 6 Min support50 Min confidence50 思考 怎样编程提取关联规则 步骤 基本概念 闭项集和极大项集 练习 min sup为4数据库TIDitem1abc2abcd3bce4acde5de频繁项集 b c 3 2挖掘方法 Apriori使用候选项生成频繁项集 Apriori算法是最有影响的挖掘关联规则频繁项集的算法 使用逐层搜索的迭代方法找到1到K项频繁项集 即由k项集搜索生成 k 1 项集 为提高频繁项集逐层产生的效率 利用Apriori性质 Apriori性质 反单调性 Apriori性质 频繁项集的所有非空子集也必须是频繁的 i e 如果 AB 是频繁项集 A 和 B 都应该是频繁项集反单调性 如果一个集合不能通过测试 则它的所有超集也都不能通过相同的测试 Apriori算法思想 1 扫描数据库 累积每个项的支持度计数 生成频繁1项集集合L1 2 扫描数据库 由L1构造 搜索频繁2项集L2 3 同理 生成L3 直到不能生成频繁k项集 注 每次搜索都要扫描一遍数据库 TheAprioriAlgorithm 算法伪码 Ck CandidateitemsetofsizekLk frequentitemsetofsizekL1 frequentitems for k 1 Lk k dobeginCk 1 candidatesgeneratedfromLk foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk 1thatarecontainedintLk 1 candidatesinCk 1withmin supportendreturn kLk Apriori算法怎样产生候选项 连接步 为找Lk 通过将Lk 1与其自身连接产生候选k项集集合Ck 例如 设l1和l2是Lk 1中的项集 如果它们的前 k 2 个项相同的话 则是可连接的 剪枝步 Ck是Lk的超集 即Ck中的成员可能是频繁的 也可能不是 但所有的频繁k项集都包含在Ck中 为压缩Ck 剪枝 任何非频繁的 k 1 项集都不是频繁k项集的子集 产生候选项的例子 设L3 abc abd acd ace bcd 自连接 L3 L3abcdfromabcandabdacdefromacdandace剪枝 删acde 因为ade不在L3中 即非频繁C4 abcd Apriori算法示例 DatabaseD ScanD C1 L1 L2 C2 C2 ScanD C3 L3 ScanD 怎样产生候选项 假设Lk 1中的项集都按序排列第一步 自连接Lk 1insertintoCkselectp item1 p item2 p itemk 1 q itemk 1fromLk 1p Lk 1qwherep item1 q item1 p itemk 2 q itemk 2 p itemk 1 q itemk 1第二步 剪枝 第二步 剪枝forallitemsetscinCkdoforall k 1 subsetssofcdoif sisnotinLk 1 thendeletecfromCk 课堂练习 设最小支持度为50 使用Aprioir找出全部频繁项集 画出生成频繁项集的详细过程 Apriori算法示例 DatabaseD ScanD C1 L1 L2 C2 C2 ScanD C3 L3 ScanD datamining 23 Apriori是否足够快 性能瓶颈 Apriori算法的核心 使用频繁 k 1 项集来产生候选频繁k项集使用数据库扫描和模式匹配来对候选集计数Apriori算法的瓶颈 候选集的产生和检测它可能需要产生大量候选项集 104个频繁1项集将产生107候选2项集为发现长度为100的频繁模式 如 a1 a2 a100 必须产生多达2100 1030个候选多次扫描数据库代价高 需要 n 1 次扫描 n是最长的模式长度 Challengesof频繁模式挖掘 Chanllenges多遍扫描事务数据库庞大的候选集数量冗长乏味的工作量 统计候选集支持度计数改进Apriori 通常的想法减少数据库扫描次数压缩候选集数量改进候选集支持度计数的统计方法 提高Apriori算法的效率 1 基于散列 hash 的技术选择一个散列函数 散列项集到对应的桶中删去桶计数低于支持度阈值的桶2 事务压缩压缩未来迭代扫描的事务数即删除不包含任何频繁k项集的事务 因为它们不能产生 k 1 项集 故可加标记或删除 提高Apriori算法的效率 3 划分 只需扫描2次 阶段1 将D中事务划分成不重叠的n个部分 对每个划分 找出该划分中所有的局部频繁项集 第1次扫描 阶段2 合并局部频繁项集 形成全局候选项集 扫描数据库D 确定全局频繁项集 第2次扫描 提高Apriori算法的效率 4 抽样在一个较小的随机抽样样本集内挖掘降低最小支持度阈值 以减少被遗漏的频繁项集可能需要第二次扫描数据库 以找出被遗漏的频繁项集 5 动态项集计数在扫描的不同点添加候选项集扫描数据库的次数比Apriori少 挖掘频繁模式不需要候选集 将一个大型数据库压缩到一棵Frequent Patterntree FP tree 树的结构中高度的压缩 但是保持完全的频繁模式挖掘避免高消耗的数据库扫描形成一种高效 基于FP 树的频繁模式挖掘方法一种分治策略 分解挖掘任务成一些小的挖掘任务避免候选项的产生 只对子数据库挖掘 无需候选集地挖掘频繁模式 根据局部频繁项 将短模式增长为长模式 abc 是频繁模式获取包含 abc 的全部事务集 DB abc d 是DB abc中的局部频繁项 生成频繁模式abcd min support 0 5 TIDItemsbought ordered frequentitems100 f a c d g i m p f c a m p 200 a b c f l m o f c a b m 300 b f h j o f b 400 b c k s p c b p 500 a f c e l p m n f c a m p 为什么要给1 项集排序 挖掘FP 树的主要步骤 思想 通过模式和数据库划分 递归地增长频繁模式为FP 树的每一个基点构造一个条件模式基从每个条件模式基来构造条件FP树像这样不断的挖掘频繁模式基和条件FP树如果条件FP 树只包含一条路径 就简单的列出所有的模式即可 FP 树结构的带来的优点 完全 不会破坏任何事务的长模式为频繁模式挖掘保持完整的信息简洁 紧密 减少不相关的信息 去掉非频繁项频繁项的降序排序 越频繁越可能被共享永远不会比初始数据库大例 压缩率甚至可以超过100 FP Growth是否快 性能表明FP Growth比Apriori算法快一个数量级 也比树 投影算法快原因没有候选集产生 没有候选测试使用压缩的数据结构没有过多的数据库的扫描基本操作是计算和FP tree的构造 FP Growthvs Apriori 用支持度阈值来度量 DatasetT25I20D10K FP Growthvs Tree Projection 用支持度阈值来度量 DatasetT25I20D100K 其他方法 挖掘闭项集和最大模式CLOSET DMKD 00 挖掘序列模式FreeSpan KDD 00 PrefixSpan ICDE 01 基于约束的频繁模式挖掘Convertibleconstraints KDD 00 ICDE 01 用复杂度量计算冰山立方体H treeandH cubingalgorithm SIGMOD 01 挖掘频繁闭合模式 CLOSET Flist listofallfrequentitemsinsupportascendingorderFlist d a f e c分割搜索空间PatternshavingdPatternshavingdbutnoa etc 递归发现频繁闭合模式Everytransactionhavingdalsohascfa cfadisafrequentclosedpatternJ Pei J Han R Mao CLOSET AnEfficientAlgorithmforMiningFrequentClosedItemsets DMKD 00 Min sup 2 CHARM MiningbyExploringVerticalDataFormat Verticalformat t AB T11 T25 tid list listoftrans idscontaininganitemsetDerivingclosedpatternsbasedonverticalintersectionst X t Y XandYalwayshappentogethert X t Y transactionhavingXalwayshasYUsingdiffsettoaccelerateminingOnlykeeptrackofdifferencesoftidst X T1 T2 T3 t XY T1 T3 Diffset XY X T2 Eclat MaxEclat Zakietal KDD 97 VIPER P Shenoyetal SIGMOD 00 CHARM Zaki Hsiao SDM 02 CLOSET MiningClosedItemsetsbyPattern Growth Itemsetmerging ifYappearsineveryoccurrenceofX thenYismergedwithXSub itemsetpruning ifY X andsup X sup Y XandallofX sdescendantsinthesetenumerationtreecanbeprunedHybridtreeprojectionBottom upphysicaltree projectionTop downpseudotree projectionItemskipping ifalocalfrequentitemhasthesamesupportinseveralheadertablesatdifferentlevels onecanpruneitfromtheheadertableathigherlevelsEfficientsubsetchecking 三 数据挖掘技术 1 基本概念2 有效的和可伸缩的频繁项集挖掘方法3 挖掘各种类型的关联规则4 由关联挖掘到相关分析5 分类与预测基本概念6 决策树技术 多层关联规则 数据项经常形成层次关系在低层的数据项希望有较低的支持度根据恰当层的数据集得到的规则结果是非常有用的事务数据库能在不同的维和层被编码浏览共享的多层挖掘结果 多层关联规则挖掘 从上到下 逐步接近 先发现高层的强规则 milk bread 20 60 然后发现底层的弱规则 2 milk wheatbread 6 50 多层关联规则的挖掘的各种变种层交叉关联规则 2 milk Wonderwheatbread多层 可选的层次关联规则 2 milk Wonderbread 多层关联规则 统一支持度vs 逐减支持度 一致支持度 所有层使用相同的最小支持度 一个最小支持度 不需要检查项集那些不满足的项 低层的项不会频繁的发生 如果支持度的限度 太高 失去了低层的关联规则太低 产生太多的高层关联规则递减支持度 顺着层数的降低 最小支持度也减小有4种搜索策略 每层独立k项层交叉过滤单项层交叉过滤受控的层交叉单项过滤策略 一致的最小支持度 一致支持度挖掘 Milk support 10 2 Milk support 6 脱脂Milk support 4 Level1min sup 5 Level2min sup 5 Back 递减支持度 递减支持度的多层挖掘 2 Milk support 6 脱脂Milk support 4 Level1min sup 5 Level2min sup 3 Back Milk support 10 多层挖掘 冗余的过滤 一些规则因为祖先的关系可能是冗余的例子 milk wheatbread support 8 confidence 70 2 milk wheatbread support 2 confidence 72 这里我们说第一个规则是第二个规则的祖先假如一个规则基于这个规则的祖先 它的支持度和预料的差不多 那么这个规则是多余的 挖掘大型数据库中的关联规则 由关系数据库和数据仓库挖掘多维关联规则 多维关联挖掘 概念 单维规则 buys X milk buys X bread 多维规则 2维或者2个谓词维间关联规则 没有重复的谓词 age X 19 25 occupation X student buys X coke 混合维关联规则 有重复的谓词 age X 19 25 buys X popcorn buys X coke 分类属性具有有限个不同的值 值间没有顺序量化属性是数值 并在值之间具有一个隐含的序 挖掘多维关联规则的技术 搜索频繁的k 项谓词集 例子 age occupation buys 就是一个3 谓词集这技术能被用来分类 比如通过怎么被age处理 1 使用量化属性的静态离散化量化属性能够通过预先的概念分层进行静态的离散化2 量化关联规则量化属性基于分布式的数据 能够动态的离散化为到箱 3 基于距离的关联规则这也是动态的离散化过程 过程中考虑数据点之间的距离 使用量化属性的静态离散化挖掘多维关联规则 使用概念分层在挖掘之前进行离散化数字值被范围代替在相联系的数据库中 找到所有的频繁k项谓词集 它需要k或者k 1扫描数据表数据立方体更适合数据挖掘一个n 维的单元立方体和谓词集相一致 从数据立方体进行挖掘能够更加的快速 三 数据挖掘技术 1 基本概念2 有效的和可伸缩的频繁项集挖掘方法3 挖掘各种类型的关联规则4 由关联挖掘到相关分析5 分类与预测基本概念6 决策树技术 感兴趣的衡量 客观的衡量两个最常用的衡量手段 支持度置信度主观的衡量 Silberschatzand or可控的 使用者能够利用他做一些事情 强关联规则 一定有趣吗 强关联规则不一定有趣 例子1 Aggarwal Yu PODS98 在5000学生中3000打篮球3750吃谷物2000都打篮球和吃谷物打篮球 吃谷物 40 66 7 是误导的 因为学生吃谷物的全部百分比是75 高过66 7 打篮球 不吃谷物 20 33 3 更精确 尽管它的支持度和置信度比较低 支持度和置信度的不足 例2 XandY 肯定的联系 XandZ 否定的联系X Z的支持度和置信度都占优势我们需要一个方法来度量事件的依赖性和相关性P B A P B 是关联规则A B的提升度 lift 兴趣度衡量方法 Interest Interest correlation lift 同时考虑P A andP B 如果A和B是独立事件的画 P A B P B P A 1如果值小于1 则A和B是负相关 否则是正相关的 回顾 三 数据挖掘技术1 1 基本概念2 有效的和可伸缩的频繁项集挖掘方法3 挖掘各种类型的关联规则4 由关联挖掘到相关分析5 分类与预测基本概念6 决策树技术 分类 预测分类标号预测 建立连续值函数模型典型应用 3 5分类与预测 数据分类 一个两步过程 模型建立 描述预定的数据类集模型使用 为将来或未知的对象分类即用模型预测 分类过程 1 模型建立 训练数据 分类算法 IFrank professor ORyears 6THENtenured yes 分类规则 分类过程 2 在预测中使用模型 分类规则 测试数据 新数据 Jeff Professor 4 Tenured 分类法准确性 估计错误概率 划分 训练与测试交叉验证10折交叉验证 10 foldcrossvalidation 将数据集分成十份 轮流将其中9份做训练1份做测试 10次的结果的均值作为对算法精度的估计 一般还需要进行多次10折交叉验证求均值 例如 10次10折交叉验证 以求更精确一点交叉验证有时也称为交叉比对 讨论 经过训练的模式 是否准确率越高越好 Supervisedvs UnsupervisedLearning 监督学习 Supervisedlearning 分类 监督 训练数据的分类标号已知 通过观察 度量等 根据训练数据集对新数据分类无监督学习 Unsupervisedlearning 聚类 训练数据的分类标号未知要学习的类或集合的个数也可能未知用聚类尝试确定 相似的组群 什么是预测 预测和分类的相似点首先 构建一模型其次 用模型预测未知值预测和分类的不同点分类指预测分类标号预测模型化连续值函数 线性函数 Y X多元回归 Y b0 b1X1 b2X2 非线性回归和其他回归模型 预测中的回归分析和线性模型 分类和预测的问题 1 数据准备 数据清理消除 减少噪声 处理缺失值相关分析分析强相关的冗余属性和不相关属性 探查对分类无用的属性数据变换与归约规范化 概念分层 分类和预测的问题 2 比较分类方法 分类的准确率评估分类器的预测准确率需要用测试数据而不是训练数据来检测 避免过拟合 overfit 速度鲁棒性 能适应噪声和数据缺失可伸缩性可解释性 分类与预测不同 数值 预测没有 类标号 因为处理的属性值是连续值构建模型的方法不同 三 数据挖掘技术1 1 基本概念2 有效的和可伸缩的频繁项集挖掘方法3 挖掘各种类型的关联规则4 由关联挖掘到相关分析5 分类与预测基本概念6 决策树技术 3 6用决策树归纳分类 决策树一个类似流程图的树结构每个内部节点表示在一个属性上的测试每个分支代表一个测试输出每个树叶节点代表类或类分布决策树的产生包含两个方面树的构造树的剪枝决策树的使用 对未知样本分类样本的属性值在决策树上测试 训练数据集 输出 概念 buys computer 的决策树 age overcast student creditrating no yes fair excellent 30 40 no no yes yes yes 30 40 决策树归纳算法 基本算法 贪心算法 1 如何划分训练集自顶向下递归的分治法构造决策树开始 所有的训练样本在根部属性分类 假如是连续值 属性首先离散化 基于选定的属性递归的形成每个划分选择属性基于启发式或统计式策略 比如 信息增益 2 如何停止 停止条件 给定节点的所有样本属于同一类没有剩余属性可以用来进一步划分样本 使用majorityvoting没有样本剩余 划分方式 离散属性 BinarySplit Multi waysplit 划分方式 连续值属性 需离散化 决策树归纳 创建决策树 算法基本框架 Hunt算法 通过将训练集相继划分为较纯的子集 以递归方式创建决策树设Dt是与结点t相关联的训练集 y y1 y2 yc 是类标号算法递归定义如下 决策树归纳 创建决策树 1 如果Dt中所用元组都属于同一个类yt 则t是叶结点 用yt标记 递归结束条件 2 若Dt中包含属于多个类的元组 则根据分裂准则找出最好的分裂属性 将数据划分成较小的子集 为测试条件的每个输出 创建一个子女结点 含相应元组 3 对每个子女结点 递归调用该算法 Hunt sAlgorithm Don tCheat 分裂准则 哪个属性是最佳的分类属性属性选择度量 选择最佳划分的度量 理想的 希望每个划分都是 纯 的即 落在给定划分的所有元组都属于相同的类信息增益InformationGain增益率gainratioGini指标 信息增益 ID3 C4 5 选择具有最高信息增益的属性期望信息 熵Entropy 对D中元组分类所需的期望信息为 pi是D中任意元组属于类Ci的概率 假定有两类 P和N样本集合D包含类P的p个元素 类N的n个元素D中的任意样本属于类P和N 所需的期望信息 ExamplesforcomputingEntropy P C1 0 6 0P C2 6 6 1Entropy 0log0 1log1 0 0 0 P C1 1 6P C2 5 6Entropy 1 6 log2 1 6 5 6 log2 1 6 0 65 P C1 2 6P C2 4 6Entropy 2 6 log2 2 6 4 6 log2 4 6 0 92 何时熵为1 信息增益 ID3 C4 5 用属性A将训练集D划分成v个部分后 为得到准确的分类 还需要的信息为 还需要的期望信息越小 划分的纯度越高信息增益Informationgain一个属性A的信息增益就是由于使用这个属性划分数据后导致的期望熵降低 训练数据集 通过信息增益选择属性 ClassP buys computer yes ClassN buys computer no Computetheentropyforage 通过信息增益选择属性 Computetheentropyforage HenceSimilarly选取age作为决策树根节点的分裂属性 用增益率gainratio选择属性 C4 5 信息增益倾向于选择具有大量的值的属性将导致大量划分 极端的 每个值都是一个划分 每个划分都是纯的C4 5算法采用增益率来克服该问题用 分裂信息 来规范化信息增益 用增益率gainratio选择属性 C4 5 增益率定义为GainRatio A Gain A SplitInfo A Ex gain ratio income 0 029 0 926 0 031选择具有最大增益率的属性作为分裂属性 Gini指标 CART IBMIntelligentMiner 设数据集D中样本有n个类 Gini指标 度量不纯度 pj是D中元组属于类j的概率若属性A将D划分为D1andD2 则gini指标为不纯度的降低为 选取Gini指标最小 或者等价的 不纯度降低最多的属性来分裂数据 比较三种度