数据挖掘基本算法

第6章数据挖掘基本算法本章内容：6.1分类规则挖掘6.2预测分析与趋势分析规则6.3数据挖掘的关联算法6.4数据挖掘的聚类算法6.5数据挖掘的统计分析算法6.6数据挖掘的品种优化算法6.7数据挖掘的进化算法6.1分类规则挖掘6.1.1分类与估值1分类为了理解事物特征并做出预测使用历史数据建立一个分类模型（即分类器）的过程。应用于信用卡系统中的信用分级、市场调查、疗效诊断、寻找店址等实践应用参照课本6.1分类规则挖掘6.1.1分类与估值2估值估值（estimation）与分类类似，不同之处在于，分类描述的是离散型变量的输出，而估值处理连续值的输出；分类的类别是确定的数目，估值的量是不确定的。3分类方法与步骤方法：决策树归纳、贝叶斯分类、贝叶斯网络、神经网络。还有K-最临近分类、基于案例的推理、遗传算法、粗糙集和模糊集方法。步骤：模型创建、模型使用6.1分类规则挖掘6.1.1分类与估值4评估分类方法要考虑的指标：预测准确率、速度、创建速度、使用速度、鲁棒性、处理噪声和丢失值、伸缩性、对磁盘驻留数据的处理能力、可解释性、对模型的可理解程度、规则好坏的评价、决策树的大小和分类规则的简明性。6.1分类规则挖掘6.1.2决策树父节点子节点子节点叶节点子节点子节点子节点根节点图6.1一般决策树结构叶节点父节点6.1分类规则挖掘6.1.2决策树•1．决策树的构造过程ID3算法应用如下：)(log21pipmii)(log21pipmii)(log21pipmii)(log21pipmii),..,1(1)/)..21((smjjsImjssmjjsjs)(log21pipmii信息量计算公式：I(s1,s2,…sm)=-（6.1）其中，pi为si占整个类别的概率利用属性A划分当前样本集合所需要的信息（熵）的计算公式为：E（A）=(6.2)信息增益公式：Gain（A）=I(s1,s2,…sm)-E（A）（6.3）例如：一个销售的顾客数据库（训练样本集合）,对购买计算机的人员进行分类：字段为：（年龄（取值：30,30~40,40）；收入(高，中，低)；学生否（Y，N）；信用（一般，很好）；购买计算机否（Y，N））记录为14个，具体数据如下：X1=(30,高,N,一般,N)；X2=(30,高,N,很好,N)X3=(30~40,高,N,一般,Y)；X4=(40,中,N,一般,Y)X5=(40,低,Y,一般,Y)；X6=(40,低,Y,很好,N)X7=(30-40,低,Y,高,Y)；X8=(30,中,N,一般,N)X9=(30,低,Y,一般,Y)；X10=(40,中,Y,一般,Y)X11=(30,中,Y,很好,Y)；X12=(30~40,中,N,很好,Y)X13=(30~40,高,Y,一般,Y)；X14=(40,中,N,很好,N)6.1分类规则挖掘6.1.2决策树1．决策树的构造过程决策树的构造算法：决策树的构造算法可通过训练集T完成，其中T={x,cj}，而x=(a1,a2,…,an)为一个训练实例，它有n个属性，分别列于属性表(A1,A2,…,An)中，其中ai表示属性Ai的取值。Cj∈C={C1,C2,…,Cm}为x的分类结果。从属性表中选择属性Ai作为分类属性；若属性Ai的取值有ki个，则将T划分为ki个子集，T1,…,Tki，其中Tij={x,C|x,C}∈T，且x的属性取值A为第i个值；接下来从属性表中删除属性Ai；对于每一个Tij(1≤j≤K1)，令T=Tij；如果属性表非空，返回第1步，否则输出。6.1分类规则挖掘6.1.2决策树2．分类器定义：输入的数据含有千万个记录，每个记录又有很多个属性，其中有一个特别的属性叫做类（例如信用程度的高，中，低）。具体步骤：1）树的建立。2）树的修剪,SLIQ采用了MDL（最小叙述长度）的方法来修剪树。6.1分类规则挖掘6.1.2决策树3．决策树的可扩展性4．基于决策树方法的数据挖掘工具KnowledgSEEKER6.1分类规则挖掘6.1.3贝叶斯分类1．贝叶斯信任网络如何工作边缘主区域手机呼叫服务区域noyes外界图6.3简单的贝叶斯网图6.1分类规则挖掘6.1.3贝叶斯分类2．贝叶斯定理与朴素贝叶斯分类贝叶斯定理:P(H|X)=P(X|H)P(H)/P(X)其中，P(H|X)表示条件X下H的概率，也称为条件概率或称为后验概率(posterioriprobabilities)。朴素贝叶斯分类：假定有m个类C1,…Cm,对于数据样本X,分类法将预测X属于类Ci,当且仅当P(Ci|X)P(Cj|X),6.2预测分析与趋势分析规则6.2.1预言的基本方法预言（prediction）是一门掌握对象变化动态的科学，它是对对象变动趋势的预见、分析和判断，也是一种动态分析方法。预测的基本步骤：确定预测目标，包括预测对象、目的、对象范围；收集分析内部和外部资料；数据的处理及模型的选择；预测模型的分析、修正；确定预测值。6.2预测分析与趋势分析规则6.2.2定量分析预测时间序列法回归预测非线性模型灰色预测模型GM（1，1）组合预测6.2预测分析与趋势分析规则6.2.3预测的结果分析预测的结果分析要考虑到的因素：相反的预测结果胜出裕度成本收益分析6.2预测分析与趋势分析规则6.2.4趋势分析挖掘分析时间序列数据需要注意以下方面：长时间的走向周期的走向与周期的变化季节性的走向与变化不规则的随机走向6.3数据挖掘的关联算法6.3.1关联规则的概念及分类1．关联规则的概念定义1设I={i1、i2、i3，…,im}是由m个不同的数据项目组成的集合，其中的元素称为项(item)，项的集合称为项集，包含k个项的项集称为k项集,给定一个事务（交易）D，即交易数据库，其中的每一个事务（交易）T是数据项I的一个子集，即，T有一个惟一的标积符TID；当且仅当时，称交易T包含项集X；那么关联规则就形如“X=Y”的蕴涵式；其中，，，Ф，即表示满足X中条件的记录也一定满足Y。关联规则X=Y在交易数据库中成立,具有支持度s和具有置信度c。这也就是交易数据集D中具有支持度s，即D中至少有s%的事务包含,描述为：support(X=Y)=比如Support(X=Y)=同时购买商品X和Y的交易数总交易数同时交易数据集D中具有置信度c，即D中包含X的事务至少有c%同时也包含Y,描述为：confidence(X=Y)=比如购买了商品X，同时购买商品Y可信度，confidence(X=Y)=同时购买商品X和Y的交易数购买了商品X的交易数一般称满足一定要求的规则为强规则。通常称满足最小支持度和最小置信度的关联规则为强关联规则（strong）。一般将最小支持度简记为minsup和最小置信度简记为minconf。6.3数据挖掘的关联算法6.3.1关联规则的概念及分类2关联规则的分类分类标准类别规则中所处理的值布尔关联规则，量化关联规则规则中所涉及的数据维单维关联规则和多维关联规则规则中所涉及的抽象层单层关联规则和多层关联规则规则中的扩充最大的模式和频繁闭项集关联特性分类分析与相关分析6.3数据挖掘的关联算法6.3.2简单形式的关联规则算法（单维、单层和布尔关联规则）1．简单形式的关联规则的核心算法找到所有支持度大于最小支持度的项集,即频集,有k个数据频集称为k项频集.找出所有的频集由apriori算法实现。Apriori性质具有一个频集的任一非空子集都是频集。使用第1步找到的频集产生期望的规则apriori算法的详细介绍见课本。6.3数据挖掘的关联算法6.3.2简单形式的关联规则算法（单维、单层和布尔关联规则）2频集算法的几种优化方法基于划分的方法基于hash的方法基于采样的方法减少交易的个数6.3数据挖掘的关联算法6.3.2简单形式的关联规则算法（单维、单层和布尔关联规则）3其他的频集挖掘方法FP-growth方法min_hashing(MH)和locality_sensitive_hashing(LSH)6.3数据挖掘的关联算法6.3.3多层和多维关联规则的挖掘多层关联规则多维关联规则关联规则价值衡量的方法6.3.4货篮子分析存在的问题详见课本6.3数据挖掘的关联算法6.3.5关联分析的其他算法发现关联的更好方法统计相关以外的理解关联有效可行的市场篮子分析6.3.6挖掘序列模式序列模式的概念及定义序列模式挖掘的主要算法GSP算法描述PrefixSpan算法关联规则挖掘—一个例子交易ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度{A}75%{B}50%{C}50%{A,C}50%最小值尺度50%最小可信度50%对于AC：support=support({A、C})=50%confidence=support({A、C})/support({A})=66.6%Apriori的基本思想:频繁项集的任何子集也一定是频繁的关键步骤：挖掘频繁集频繁集:是指满足最小支持度的项目集合频繁集的子集也一定是频繁的如,如果{AB}是频繁集，则{A}{B}也一定是频繁集从1到k（k-频繁集）递归查找频繁集用得到的频繁集生成关联规则Apriori算法连接:用Lk-1自连接得到Ck修剪:一个k-项集，如果他的一个k-1项集（他的子集）不是频繁的，那他本身也不可能是频繁的。伪代码:Ck:CandidateitemsetofsizekLk:frequentitemsetofsizekL1={frequentitems};for(k=1;Lk!=;k++)dobeginCk+1=candidatesgeneratedfromLk;foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedintLk+1=candidatesinCk+1withmin_supportendreturn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}2如何生成候选集假定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-1q.itemk-1第二步:修剪forallitemsetscinCkdoforall(k-1)-subsetssofcdoif(sisnotinLk-1)thendeletecfromCk如何计算候选集的支持度计算支持度为什么会成为一个问题？候选集的个数非常巨大一笔交易可能包含多个候选集方法:用hash-tree存放候选集树的叶子节点of存放项集的列表和支持度内部节点是一个hash表Subset函数:找到包含在一笔交易中的所有候选集生成候选集的例子L3={abc,abd,acd,ace,bcd}自连接:L3*L3abc和abd得到abcdacd和ace得到acde修剪:ade不在L3中，删除acdeC4={abcd}提高Apriori效率的方法基于