数据分析与挖掘实验报告

1、数据挖掘实验报告目录1. 关联规则的基本概念和方法. 1 1.1 数据挖掘 . 1 1.1.1 数据挖掘的概念 . . 1 1.1.2 数据挖掘的方法与技术 . . 1 1.2 关联规则 . 2 1.2.1 关联规则的概念 . . 2 1.2.2 关联规则的实现 apriori算法 . 3 2. 用 matlab 实现关联规则 . 5 2.1matlab 概述 . 5 2.2 基于 matlab 的 apriori算法. . 6 3. 用 java 实现关联规则 . 10 3.1java 界面描述 . 10 3.2java 关键代码描述 . . 13 4、实验总结 . 18 4.1 实验的不足

2、和改进 . . 18 4.2 实验心得 . 19 1 1.关联规则的基本概念和方法1.1 数据挖掘1.1.1数据挖掘的概念计算机技术和通信技术的迅猛发展将人类社会带入到了信息时代。在最近十几年里， 数据库中存储的数据急剧增大。数据挖掘 就是信息技术自然进化的结果。数据挖掘可以从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的，人们事先不知道的但又是潜在有用的信息和知识的过程。许多人将数据挖掘视为另一个流行词汇数据中的知识发现（kdd ）的同义词，而另一些人只是把数据挖掘视为知识发现过程的一个基本步骤。知识发现过程如下：数据清理（消除噪声和删除不一致的数据）数据集成（多

3、种数据源可以组合在一起）数据转换（从数据库中提取和分析任务相关的数据）数据变换（从汇总或聚集操作，把数据变换和统一成适合挖掘的形式）数据挖掘（基本步骤，使用智能方法提取数据模式）模式评估（根据某种兴趣度度量，识别代表知识的真正有趣的模式）知识表示（使用可视化和知识表示技术，向用户提供挖掘的知识）。1.1.2数据挖掘的方法与技术数据挖掘吸纳了诸如数据库和数据仓库技术、统计学、机器学习、高性能计算、模式识别、神经网络、 数据可视化、信息检索、图像和信号处理以及空间数据分析技术的集成等许多应用领域的大量技术。数据挖掘主要包括以下方法。神经网络方法：神经网络由于本身良好的鲁棒性、自组织自适应性、并行处

4、理、分布存储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。典型的神经网络模型主要分3 大类：以感知机、bp 反向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网络模型；以hopfield的离散模型和连续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以art 模型、 koholon 模型为代表的， 用于聚类的自组织映射方法。神经网络方法的缺点是黑箱 性，人们难以理解网络的学习和决策过程。遗传算法：遗传算法是一种基于生物自然选择与遗传机理的随机搜索算法，是一种仿生全局优化方法。 遗传算法具有的隐含并行性、易于和其它模型结合等性质使得

5、它在数据挖掘中被加以应用。 sunil已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。 遗传算法的应用还体现在与神经网络、粗糙集等技术的结合上。如利用遗传算法优化神经网络结构，在不增加错误率的前提下，删除多余的连接和隐层单元；用遗传算法和bp 算法结合训练神经网络，然后从网络提取规则等。但遗传算法的算法较复杂，收敛于局部极小的较早收敛问题尚未解决。决策树方法：决策树是一种常用于预测模型的算法，它通过将大量数据有目的分类，从2 中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特

6、别适合大规模的数据处理。粗糙集方法：粗糙集理论是一种研究不精确、不确定知识的数学工具。粗糙集方法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。粗糙集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起来的数据仓库管理系统， 为粗糙集的数据挖掘奠定了坚实的基础。但粗糙集的数学基础是集合论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在的。因此连续属性的离散化是制约粗糙集理论实用化的难点。覆盖正例排斥反例方法：它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一个种子，到反例集合中逐个比较。与字段取值构成的选择子相

7、容则舍去，相反则保留。按此思想循环所有正例种子，将得到正例的规则( 选择子的合取式) 。比较典型的算法有michalski的 aq11 方法、洪家荣改进的aq15 方法以及他的ae5 方法。统计分析方法：在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性关系 ) 和相关关系 ( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析可采用统计学方法，即利用统计学原理对数据库中的信息进行分析。可进行常用统计( 求大量数据中的最大值、 最小值、总和、平均值等 ) 、 回归分析 ( 用回归方程来表示变量间的数量关系) 、相关分析 ( 用相关系数来度量变量间的相关程度) 、差异分

8、析 ( 从样本统计量的值得出差异来确定总体参数之间是否存在差异) 等。模糊集方法：即利用模糊集合理论对实际问题进行模糊评判、模糊决策、 模糊模式识别和模糊聚类分析。系统的复杂性越高，模糊性越强， 一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。李德毅等人在传统模糊理论和概率统计的基础上，提出了定性定量不确定性转换模型- 云模型，并形成了云理论。还有接下来重点介绍的关联规则方法。1.2 关联规则1.2.1关联规则的概念关联规则的一个典型例子是购物篮分析。它是由著名的全国五百强沃尔玛发现的，沃尔玛有着世界最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进

9、行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。一个意外的发现是：跟尿布一起购买最多的商品竟是啤酒！ 经过大量实际调查和分析，揭示了一个隐藏在尿布与啤酒 背后的美国人的一种行为模式： 在美国， 一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30% 40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。关联规则由此进入人们的视野。关联规则挖掘被定义为假设i 是项的集

10、合。给定一个交易数据库d，其中每个事务(transaction)t 是 i 的非空子集，即每一个交易都与一个唯一的标识符tid(transaction id) 对应。关联规则在d 中的 支持度 (support)是 d 中事务同时包含x、y 的百分比，即概率；置信度 (confidence)是包含 x 的事务中同时又包含y 的百分比，即条件概率。下面举个例子来更好地说明关联规则。3 给定 allelectronics关系数据库，一个数据挖掘系统可能发现如下形式的关联规则age（ x,“20.29” ）income（x, “20,000.29,000” ）？ =buys(x, “ cd-play

11、er ”) support=20%,confident=60% 其中 x 是变量，代表顾客，该关联规则表示所研究的allelectronics数据库中，顾客有20%在 20-29 岁，年收入在20,000-29,000 之间，并且购买cd 机；这个年龄和收入组的顾客购买cd 机的可能性有60%。1.2.2关联规则的实现 apriori算法1.2.2.1算法描述apriori算法在发现关联规则领域具有很大影响力。算法命名源于算法使用了频繁项集性质的先验（prior）知识。在具体实验时，apriori算法将发现关联规则的过程分为两个步骤：第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不

12、低于用户设定的阈值的项集； 第二步利用频繁项集构造出满足用户最小信任度的规则。其中， 挖掘或识别出所有频繁项集是该算法的核心，占整个计算量的大部分。apriori 算法使用一种称作逐层搜索的迭代方法，k 项集用于搜索（k+1）项集。首先，通过扫描数据库， 累积每个项的计数， 并收集满足最小支持度的项，找出频繁 1 项集的集合。该集合记作l1 。然后， l1 用于寻找频繁2 项集的集合l2，l2 用于寻找l3，如此下去，直到不能再找到频繁k 项集。为提高频繁项集逐层产生的效率，一种称作apriori的重要性质用于压缩搜索空间。apriori 性质：频繁项集的所有非空子集也必须是频繁的。如何在算法

13、中使用apriori 性质？主要有两步过程组成：连接步 和剪枝步 。(1) 连接步 ：为找 lk，通过将l(k-1)与自身连接产生候选k 项集的集合。该候选项集合记作 ck。设 l1 和 l2 是 lk-1中的项集。记号lij 表示 li中的第 j 项。执行l(k-1)连接 l(k-1)，如果它们的前（ k-2）项相同的话，其中l(k-1)的元素是可连接的。(2) 剪枝步 ：为压缩ck，可以用apriori的性质：任何非频繁的（k-1）项集都不是频繁 k 项集的子集。因此，如果候选k 项集的（ k-1 ）项子集不在l(k-1)中，则该候选也不可能是频繁的，从而可以从ck中删除。1.2.2.1算

14、法举例apriori 算法的伪代码input: db, min_sup output: result = 所有频繁项集的他们的支持度方法：result: = ; k: =1; c1: = 所有的 1-项集while(ck)do begin 为每一个ck中的项集生成一个计数器; for（i=1; i=sup); % 查找候选项集c1中支持度 2 的项集 , 生成频繁项集l1 temp = 1 2 3 4 5 col=col(temp);count_col_sup=count_sup(temp);l1=col count_col_sup;l1 = 1 6 2 7 3 6 4 2 5 2 %产生 2

15、 项集i=0;j=0;co2=nchoosek(col,2); %产生候选项集c2 co2 = 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 8 4 5 m2,n2=size(co2); count_co2_sup=zeros(m2,1);for i=1:m2for j=1:m1if (shw(j,co2(i,1)=1) & (shw(j,co2(i,2)=1) count_co2_sup(i)=count_co2_sup(i)+1;end j=j+1;endend temp=find(count_co2_sup=sup); %查找候选项集c2支持度 2 的项

16、集 , 生成频繁项 l2co2=co2(temp,:);count_co2_sup=count_co2_sup(temp,:);l2=co2 count_co2_sup;l2 = 1 2 4 1 3 4 1 5 2 2 3 4 2 4 2 2 5 2 %寻找 3项集a=co2(:,1) co2(:,2); a = 1 2 1 3 1 5 2 3 2 4 2 5 ma,na=size(a);b(1)=a(1);k=2;for i=1:mafor j=1:naif(a(i,j)=b(1:end) %查找重复出现的商品号 b(k)=a(i,j); k=k+1; %b=1 2 3 5 49 end j

17、=j+1;end i=i+1;endco3=nchoosek(b,3); %产生候选项集c3co3 = 1 2 3 1 2 5 1 2 4 1 3 5 1 3 4 1 5 4 2 3 5 2 3 4 2 5 4 3 5 4 m3,n3=size(co3);count_co3_sup=zeros(m3,1);for i=1:m3for j=1:m1if(shw(j,co3(i,1)=1) & (shw(j,co3(i,2)=1) & (shw(j,co3(i,3)=1) count_co3_sup(i)=count_co3_sup(i)+1;end j=j+1;endm3=m3+

18、1;endtemp=find(count_co3_sup)=sup); %查找候选项集 c3支持度 2 的项集 , 生成频繁项 l3co3=co3(temp,:);count_co3_sup=count_co3_sup(temp,:);l3=co3 count_co3_sup;l3 = 1 2 3 2 1 2 5 2 %寻找 4项集c=co3(:,1) co3(:,2) co3(:,3);mc,nc=size(c);d(1)=c(1);10 k=2;for i=2:ncif(c(i)=d(1:end) %查找重复出现的商品号 d(k)=c(i); k=k+1;end i=i+1;end co4

19、=nchoosek(d,4);m4,n4=size(co4);count_co4_sup=zeros(m4,1);for i=1:m4for j=1:m1if(shw(j,co4(i,1)=1) & (shw(j,co4(i,2)=1) & (shw(j,co4(i,3)=1) & (shw(j,co4(i,4)=1) count_co4_sup(i)=count_co4_sup(i)+1;end j=j+1;endendtemp=find(count_co4_sup)=sup);co4=co4(temp,:);count_co4_sup=count_co4_sup(t

20、emp,:);l4=co4 count_co4_sup; c4 = empty matrix: 0-by-5 上述基于 matlab的 apriori 算法的结果与上节的图6.2一致，由于 c4是空集，所以算法终止，共找到频繁项集l1，l2，l3。3.用 java 实现关联规则3.1java 界面描述运行程序 apriori ，进入关联规则主界面，如图3.1 所示11 图 3.1 关联规则主界面点击“载入”选择“g:/1.txt” ，选择“打开” ，载入到java 界面中，如图3.2 所示图 3.2 载入界面12 载入完成后的界面，如图3.3 所示图 3.3 载入完成界面输入最小支持度阈值，如

21、2，点击“生成频繁项集”，生成所有频繁项集，如下图3.4 所示图 3.4 频繁项集13 输入最小可信度的值，如0.6，点击生成关联规则，结果如下图3.5 所示图 3.5 关联规则3.2java 关键代码描述1、删除小于支持度的键2、创建并返回l1的结果集14 3、创建并返回l2的结果集15 4、创建并返回l3的结果集5、在健集keyset 里查找健值为a,b,c 的健16 6、判断在健集keyset 里是否已经包含了健值为a,b,c 的健7、创建关联规则，返回关联规则表17 8、求 a 与 l 的差集，并返回差集9、获取 setn 的子集。假设setn=a,b,c ，则生成的子集为xxx 18

22、 4、实验总结4.1 实验的不足和改进在上述基于matlab 和 java的 apriori 算法的编写中均存在以下不足：(1) 在生成候选项集的时候会产生许多最后证明不是频繁项集的候选项集,如果能在生成候选频繁项集之前能判断出某些候选集不是频繁项集,则这样可以避免在扫描数据库时的开销；(2) 连接程序中相同的项目重复比较的太多,如果能避免这些重复的比较,则可以提高算法的效率；(3) 有些事务项在一次扫描之后可以判断出下次不必再扫描,但结果又被多次扫描。如果能避免这些稍描 ,则可以提高算法效率。可以改进的方面有：(1)基于散列 (hash)的技术这种散列的技术可用于压缩候选k-项集 ck。在由 c1 中的候选1-项集产生频繁1-项集l1 时 ,可使用散列函数将每个事务的所有项集散列到不同的桶中,并对对应的桶进行计数,通过