数据挖掘理论与技术实验指导书

0知识挖掘理论与技术实验指导书魏玮河北工业大学计算机科学与软件学院2008年12月9日1目录实验一完全立方体的计算..................................................................................................2实验二Apriori算法发现频繁项集......................................................................................4实验三使用FP增长算法挖掘频繁项集............................................................................6实验四贝叶斯分类算法.......................................................................................................9实验五后向传播分类算法.................................................................................................11附录一实验报告书写格式...................................................................................................15附录二MATLAB编程简介.................................................................................................16附录三参考程序...................................................................................................................262实验一完全立方体的计算一、实验目的和要求1)熟悉Matlab编程算法；2)掌握由基本立方体聚集产生各层方体的方法，即完全物化技术。二、实验原理数据仓库和OLAP工具基于多维数据模型，这种模型将数据看作数据立方体形式也就是对n维数据建模。在OLAP服务器实时回答决策支持查询时，对数据立方体的计算速度有较高的要求。为解决这个问题，常采用对数据立方体预计算的方法。给定基本方体，数据立方体的物化有三种选择：1)不物化：不预计算任何“非基本”方体2)完全物化：预计算所有方体；3)部分物化：有选择地计算整个可能的方体集中一个适当的子集。三、实验内容和步骤1、实验内容1)由AllEllectronics销售在time、item和location维的3-D数据编程建立相应的3-D数据立方体表示；2)将得到的3-D数据立方体视为基本立方体，并编程对它进行完全物化，即预计算所有方体；3)在实验报告中画出程序框图；4)在实验报告中画出相应的方体格。2、实验步骤编程实现如下功能：1)将AllEllectronics销售数据用Matlab语言表示成3维矩阵的形式记为tim_ite_loc；32)分别沿time、item和location聚集，得到2-D方体；3)再对2-D方体聚集，得到1-D方体；4)对1-D方体聚集，得到顶点方体。四、实验数据Location=“芝加哥”itemLocation=“纽约”itemtime家庭娱乐计算机电话安全家庭娱乐计算机电话安全Q1Q2Q3Q485494310321129882890924992896459636236987898701087113010341142968102410481091384145548729251002984Location=“多伦多”itemLocation=“温哥华”itemtime家庭娱乐计算机电话安全家庭娱乐计算机电话安全Q1Q2Q3Q48188949409787467697958644352585959168272878460568081292782595210231038143130384005125015804实验二Apriori算法发现频繁项集一、实验目的和要求1)进一步熟悉Matlab编程算法；2)掌握使用Apriori算法从事物数据库中挖掘频繁项集的方法。二、实验原理1、Apriori算法Apriori使用一种称作逐层搜索的迭代方法，k项集用于探索（k+1）项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记作L1。然后，L1用于找频繁2项集的集合L2，L2用于找L3，如此下去，直到不能再找到频繁k项集。找每个Lk需要一次数据库全扫描。2、提高频繁项集逐层产生的效率Apriori性质：频繁项集的所有非空子集也必须是频繁的。三、实验内容和步骤1、实验内容1)使用Apriori算法编程实现对实验数据中提供的AllElectronics某分店的事物数据库挖掘频繁项集，并在实验报告中写出程序框图；2)产生全部频繁模式，保留其中的闭频繁项集。3)在实验报告中写明各主要程序片段的功能和作用。2、实验步骤1)算法第一次迭代，每项都是候选1项集的集合C1的成员，简单的扫描所有的事物，对每项的出现次数计数；2)按先验的最小支持度计数阈值min_sup=2，确定频繁1项集的集合L1，令i=1，Ni是Li中项的数量；3)调用子函数Join_Prune(Li,min_sup)，存储频繁项集Li；5子函数Join_Prune(Li,min_sup)：a)对频繁i项集Li执行连接步，产生候选i+1项集Ci+1；b)对候选i+1项集Ci+1执行剪枝步，产生频繁i+1项集Li+1；c)返回频繁i+1项集Li+1。4)如果Ni+10，则令i=i+1，转到步骤3)；否则，算法结束。四、实验数据AllElectronics某分店的事物数据TID商品ID的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I36实验三使用FP增长算法挖掘频繁项集一、实验目的和要求1)进一步熟悉Matlab编程环境；2)掌握使用频繁模式（FP）增长算法从事物数据库中挖掘频繁项集的方法。二、实验原理1、建立频繁模式（FP）树先对事物数据集扫描，得到频繁1项集的集合和支持度计数，并按支持度计数递减对频繁1项集中的各项排序；按每条事物再次扫描事物数据集，依照上次扫描的支持度计数递减排序，从根节点对每个事物创建一条分支（尽量共享已存在的前缀，共享一次节点计数加1），得到频繁模式（FP）树。2、频繁模式树的挖掘过程由每个长度为1的频繁模式（初始后缀模式）开始，构造它的条件模式基（一个“子数据库”，由FP树中与后缀模式一起出现的前缀路径集组成），然后，构造它的条件FP树，并递归地进行数据挖掘。模式增长通过后缀模式与条件FP树产生的频繁模式连接实现。三、实验内容和步骤1、实验内容1)使用AllElectronics某分店的事物数据编程建立频繁模式树，并写出程序框图；2)递归地对频繁模式（FP）树进行挖掘，或在编程的基础上对FP树进行挖掘；3)产生全部频繁模式，保留其中的闭频繁项集，或分别说明重点程序片段的功能。2、实验步骤(1)按以下步骤构造FP树：71)扫描事物数据库D一次。收集频繁项集的集合F和它们的支持度计数。对F按支持度计数降序排序，结果为频繁列表L；2)创建FP树的根节点，以“null”标记它。对于D中的每个事物Trans，执行：选择Trans中的频繁项，并按L中的次序排序。排序后的Trans中频繁项列表为[p|P]，其中，p是第一个元素，而P是剩余元素的列表。如果P非空，递归的调用子函数insert_tree([p|P],T)；否则对下一个事物Trans执行上述过程。子函数insert_tree([p|P],T)执行情况如下：如果树T有一个子女N使得N.item-name=p.item-name，则N的计数增加1；否则创建一个新的节点N，将其计数设置为1，链接到他的父节点T，并通过节点链结构将其连接到具有相同item-name的节点。(2)FP树的挖掘通过调用FP_growth(FP_tree,null)实现。该过程实现如下：procedureFP_growth(Tree,α)1)ifTree含单个路径Pthen2)foreach路径P中节点的每个组合（记作β）3)产生模式β∪α，其支持度计数support_count等于β中节点的最小支持度计数；4)elseforTree的头表中的每个αi{5)产生模式β=αi∪α，其支持度计数support=αi.support_count；6)构造β的条件模式基，然后构造β的条件FP树Treeβ；7)ifTreeβ≠∅then8)调用FP_growth(Treeβ,β)；}四、实验数据AllElectronics某分店的事物数据TID商品ID的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I48T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I39实验四贝叶斯决策分类算法一、实验目的和要求1)对AllElectronics顾客数据库查询得到先验概率和类条件概率密度；2)使用朴素贝叶斯分类对任意元组分类。二、实验原理1、先验概率和类条件概率先验概率：先验概率定义为训练样本集中属于Ci类的样本（元组）数Ni与总样本数N之比，记为()NNCPii=。类条件概率：类条件概率定义为训练样本集中属于Ci类中的具有特征X的样本（元组）的个数ni与属于Ci类的样本（元组）数Ni之比，记为()iiiNnCXP=|。2、贝叶斯决策贝叶斯决策（分类）法将样本（元组）分到Ci类，当且仅当()()()()jjiiCPCXPCPCXP||，对1≤j≤m，j≠i其中，训练样本集中的样本（元组）可被分为m类。三、实验内容和步骤1、实验内容用贝叶斯分类器对已知的特征向量X分类：1)由AllElectronics顾客数据库类标记的训练样本集（元组）编程计算先验概率P(Ci)和类条件概率P(X|Ci)，并在实验报告中指出关键代码的功能和实现方法；2)应用贝叶斯分类法编程对特征向量X分类，并在实验报告中指出关键程序片段的功能和实现方法；3)用检验样本估计分类错误率；104)在实验报告中画出程序或例程的程序框图。2、实验步骤由于该分类问题是决定顾客是否倾向于购买计算机，即C1对应于buys_computer=yes，C2对应于buys_computer=no，是两类的分类问题。实验步骤如下：1)根据AllElectronics顾客数据库类标记的训练样本集（元组）计算先验概率P(Ci)，i=1，2；2)设特征（属性）向量为X，编程计算类条件概率P(X|Ci)，i=1，2；3)应用贝叶斯决策（分类）法进行分类。四、实验数据AllElectronics顾客数据库类标记的训练样本集（元组）RIDageincomestudentcredit_ratingClass:buys_computer1youthhighnofairno2youthhighnoexcellentno3middle_agedhighnofairyes4seniormediumnofairyes5seniorlowyesfairyes6seniorlowyesexcellentno7middle_agedlowyesexcellentyes8youthmediumnofairno9youthlowyesfairyes10seniormediumyesf