数据挖掘常用算法概述

关联分析关联规则挖掘的提出关联规则挖掘的典型案例：购物篮问题在商场中拥有大量的商品（项目），如：牛奶、面包等，客户将所购买的商品放入到自己的购物篮中。通过发现顾客放入购物篮中的不同商品之间的联系，分析顾客的购买习惯哪些物品经常被顾客购买？同一次购买中，哪些商品经常会被一起购买？一般用户的购买过程中是否存在一定的购买时间序列？具体应用：利润最大化商品货架设计：更加适合客户的购物路径货存安排：实现超市的零库存管理用户分类：提供个性化的服务其他典型应用相关文献的收集购物篮=文档（Document）项目=单词（Word）相关网站的收集购物篮=词句（Sentences）项目=链接文档（Document）什么是关联规则挖掘?关联规则挖掘简单的说，关联规则挖掘发现大量数据中项集之间有趣的关联在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。应用购物篮分析、交叉销售、产品目录设计、loss-leaderanalysis、聚集、分类等。关联规则挖掘形式化定义给定:交易数据库每笔交易是：一个项目列表(消费者一次购买活动中购买的商品)查找:所有描述一个项目集合与其他项目集合相关性的规则应用*护理用品(商店应该怎样提高护理用品的销售？)家用电器*(其他商品的库存有什么影响?)在产品直销中使用附加邮寄其它相关概念包含k个项目的集合，称为k-项集项集的出现频率是包含项集的事务个数，称为项集的频率、支持计数或者计数关联规则的基本形式：前提条件结论[支持度,置信度]buys(x,“diapers”)buys(x,“beers”)[0.5%,60%]major(x,“CS”)^takes(x,“DB”)grade(x,“A”)[1%,75%]关联规则兴趣度的度量值：支持度推导出的数据间的相关性可称为规则（或模式），对规则兴趣度的描述采用支持度、置信度概念。支持度（Support）：规则XY在交易数据库D中的支持度是交易集中包含X和Y的交易数与所有交易数之比，记为support(XY)，即support(XY)=|{T:XYT，TD}|/|D|，它是概率P（XY），具体表示为：S=总交易数同时包含项目集X和Y的交易数购买商品Y的交易同时购买商品X和Y的交易购买商品X的交易关联规则兴趣度的度量值：置信度置信度（Confidence），规则XY在交易集中的置信度是指包含X和Y的交易数与包含X的交易数之比，记为confidence(XY)，即confidence(XY)=|{T:XYT，TD}|/|{T:XT，TD}|，它是概率P（X|Y），具体表示为：最小支持度和最小置信度用户（分析员）不关心可信程度太低的规则，因而用户需要输入两个参数：最小支持度和最小置信度。C=购买商品X的交易数同时购买商品X和Y的交易数购买商品Y的交易同时购买商品X和Y的交易购买商品X的交易支持度和置信度举例零售商场销售分析：数据项为商品，记录集合为交易记录集合规则为：“购买商品X的顾客，同时购买商品Y”，即XY；设最小支持度为0.3；最小置信度也为0.3。分析结果：Item1Item2置信度C支持度SAB10.33BA0.330.33BC0.330.33BD0.660.66CB10.33CD10.33DB10.66DC0.50.33交易号顾客号商品号数量日期1甲A143/4/95甲B33/4/952乙C25/6/95乙B35/6/95乙D135/6/953乙B108/6/95乙D128/6/95频繁项集及其基本特征频繁项集的定义如果项集满足最小支持度，则称之为频繁项集（高频项集）频繁项集的基本特征任何频繁项集的子集均为频繁项集。例如：ABC是频繁项集，则AB、AC、BC均为频繁项集在数据库表分区的情况下，一个项集是频繁的，则至少在一个分区内是频繁的关联规则挖掘的种类布尔vs.数值型关联(基于处理数据的类型)性别＝“女”职业＝“秘书”[1%,75%]布尔型关联规则性别＝“女”收入=2000[1%,75%]数值型关联规则单维vs.多维关联age(x,“30..39”)^income(x,“42..48K”)buys(x,“PC”)[1%,75%]buys(x,“Book”)^buys(x,“Pen”)buys(x,“Ink”)[1%,75%]单层vs.多层分析那个品种牌子的啤酒与那个牌子的尿布有关系?各种扩展相关性、因果分析关联并不一定意味着相关或因果最大模式和闭合相集添加约束如,哪些“小东西”的销售促发了“大家伙”的买卖？关联规则挖掘的基本过程找出所有的频繁项集F，其中对于任何的ZF，在交易集合D中至少s%的事务包含Z根据置信度和频繁项集F,产生关联规则。具体方法如下：conf(XY)=supp(X)/supp(XY)如果conf(XY)c成立，则产生XY的规则,因为:supp(XY)=supp(XY)s且conf(XY)c因此关联规则的挖掘可以转换为频繁项集的挖掘和频繁项集之间的关联。关联规则挖掘：一个例子对于AC：support=support({A、C})=50%confidence=support({A、C})/support({A})=66.6%交易ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度{A}75%{B}50%{C}50%{A,C}50%最小值尺度50%最小可信度50%关联规则挖掘的优缺点优点它可以产生清晰有用的结果它支持间接数据挖掘可以处理变长的数据它的计算的消耗量是可以预见的缺点当问题变大时，计算量增长得厉害难以决定正确的数据容易忽略稀有的数据查找频繁项集—Apriori算法查找具有最小支持度的频繁项集是关联规则挖掘最为重要的步骤Apriori算法是目前最有影响力的一个算法，在1994年，由R.Agrawal,S.Srikant提出该算法基于频繁项集的特征：如果项集l={i1,i2,…,in}是频繁的，当且仅当项集的所有子集均为频繁项集.也就是说，如果supp(l)s，当且仅当supp(l’)s,l’l因此，我们可以采用层次顺序的方法来实现频繁项集的挖掘。首先，挖掘一阶频繁项集L1。在此基础上，形成二阶候选项集，挖掘二阶频繁项集。依此类推。Apriori算法连接:用Lk-1自连接得到Ck剪枝:一个k-项集，如果它的一个k-1项集（它的子集）不是频繁的，那他本身也不可能是频繁的。伪代码:Ck:长度为k的候选项集Lk:长度为k的频繁项集L1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=从Lk生成候选项集;对于数据库中的任一交易tdo如果t中包含Ck+1中所包含的项集，则计数加1Lk+1=Ck+1中超过最小支持度的频繁项集endreturnkLk;Apriori算法—例子TIDItems100134200235300123540025数据库Ditemsetsup.{1}2{2}3{3}3{4}1{5}3itemsetsup.{1}2{2}3{3}3{5}3扫描DC1L1itemset{12}{13}{15}{23}{25}{35}itemsetsup{12}1{13}2{15}1{23}2{25}3{35}2itemsetsup{13}2{23}2{25}3{35}2L2C2C2扫描DC3L3itemset{235}扫描Ditemsetsup{235}2Apriori够快了吗?—性能瓶颈Apriori算法的核心:用频繁的(k–1)-项集生成候选的频繁k-项集用数据库扫描和模式匹配计算候选集的支持度Apriori的瓶颈:候选集生成巨大的候选集:104个频繁1-项集要生成107个候选2-项集，并且累计和检查它们的频繁性要找长度为100的频繁模式，如{a1,a2,…,a100},你必须先产生21001030个候选集重复扫描数据库：如果最长的模式是n的话，则需要(n+1)次数据库扫描关联规则结果显示(TableForm)关联规则可视化UsingRuleGraph扩展知识：多层关联规则项通常具有层次底层的项通常支持度也低某些特定层的规则可能更有意义交易数据库可以按照维或层编码可以进行共享的多维挖掘食品面包牛奶脱脂奶光明统一酸奶白黄TIDItemsT1{111,121,211,221}T2{111,211,222,323}T3{112,122,221,411}T4{111,121}T5{111,122,211,221,413}扩展知识：多维关联规则单维关联规则（维内关联规则）关联规则中仅包含单个谓词（维）通常针对的是事务数据库buys(X,“milk”)buys(X,“bread”)多维关联规则：规则内包含2个以上维/谓词维间关联规则(不重复谓词)age(X,”19-25”)occupation(X,“student”)buys(X,“coke”)混合维关联规则(存在重复谓词)age(X,”19-25”)buys(X,“popcorn”)buys(X,“coke”)分类与预测本章内容分类与预测的基本概念决策树分类实例：移动通信客户流失分析系统神经网络其他分类方法预测（回归）建立模型过程历史数据模型建模记录集合预测数学公式规则集合分类为一个事件或对象进行归类预测分类标签（离散值）基于训练集形成一个模型，训练集中的类标签是已知的。使用该模型对新的数据进行分类分类模型：分类器（分类函数、分类规则等）预测:对连续或者有序的值进行建模和预测（回归方法）典型应用客户/用户分类信用评分目标营销医疗诊断…………分类和预测分类的相关概念训练集（TrainingSet）：由一组数据库记录或者元组构成，每个记录由有关字段值组成特征向量，这些字段称为属性。用于分类的属性称为标签属性。标签属性也就是训练集的类别标记。标签属性的类型必须是离散的，而且标签属性的可能值的数目越少越好。分类的两个步骤模型创建:对一个已经事先确定的类别创建模型每个元组属于一个事先确定的类别，使用分类标签属性予以确定用于创建模型的数据集叫:训练集。单个元组称为训练样本模型可以用分类规则，决策树，或者数学方程的形式来表达。模型使用:用创建的模型预测未来或者类别未知的记录估计模型的准确率使用创建的模型在一个测试集上进行预测，并将结果和实际值进行比较准确率：测试集和训练集是独立的。分类过程：模型创建（学习过程）训练集NAMERANKYEARSTENUREDMikeAssistantProf3noMaryAssistantProf7yesBillProfessor2yesJimAssociateProf7yesDaveAssistantProf6noAnneAssociateProf3no分类算法IFrank=‘professor’ORyears6THENtenured=‘yes’模型分类过程:使用模型模型测试集NAMERANKYEARSTENUREDTomAssistantProf2noMerlisaAssociateProf7noGeorgeProfessor5yesJosephAssistantProf7yes未知数据(Jeff,Professor,4)Tenured?本章内容分类与预测的基本概念决策树分类实例：移动通信客户流失分析系统神经网络其他分类方法预测（回归）使用决策树进行分类决策树一个树型的结构内部节点上选用一个属性进行分裂（决策节点）每个分叉都是分裂的一个部分叶子节点表示一个分布节点的子节点个数跟算法相关age?student?creditrating?noyes