知识发现与数据挖掘实验报告.docx

知识发现与数据挖掘实验报告.docx

《知识发现与数据挖掘实验报告.docx》由会员分享，可在线阅读，更多相关《知识发现与数据挖掘实验报告.docx（42页珍藏版）》请在冰点文库上搜索。

知识发现与数据挖掘实验报告

知识发现与数据挖掘实验报告

姓名：

xxx

专业：

xxxxxx

学号：

xxxxx

2013年8月15日

实验一、频繁模式挖掘算法Apriori算法

一、实验目的

加强对Apriori算法的理解。

二、实验内容

编程实现Apriori算法，加深对其理解。

三、实验原理

该算法的基本思想是：

首先找出所有的频繁项目集，这些项集出现的频繁性至少和预定义的最小支持度一样。

然后由频繁项目集产生的强关联规则，这些规则必须满足最小支持度和最小可信度。

然后使用第1步找到的频繁项目集产生的期望的规则，产生只包含集合的项的所有规则，其中每一条规则的右部只有一项，这里采用的是中规则的定义。

一旦这些规则被生成，那么只有那些大于用户给定的最小可信度的规则才被留下来。

为了生成所有频繁项目集，使用了递推的方法。

（一）、Apriori（发现频繁项目集）

输入：

数据集D；最小支持数minsup_count。

输出：

频繁项目集L。

（1）L1={large1-itemsets};//所有支持读不小于minsupport的1-项目集

（2）、FOR（k=2;Lk-1≠Φ;k++）DOBEGIN

（3）Ck=apriori-gen（Lk-1,min_sup）;//Ck是k个元素的候选集

（4）FORalltransactiont∈DDOBEGIN

（5）Ct=subset（Ck,t）;//Ct是所有t包含的候选集元素

（6）FORallcandidatec∈CtDOc.count++;

（7）END

（8）Lk={c∈Ck|c.count≥minsup_count}

（9）END

（10）L=∪kLk;

（二）、apriori-gen（Lk-1）（候选集产生）

输入：

（k-1）-频繁项目集Lk-1。

输出：

k-候选项目集Ck。

（1）FORallitemsetp∈Lk-1DO

（2）FORallitemsetq∈Lk-1DO

（3）IFp.item1=q.item1，p.item2=q.item2，…，p.itemk-2=q.itemk-2，p.itemk-1=q.itemk-1THENBEGIN

（4）c=p∞q;

（5）IFhas_infrequent_subset（c,Lk-1）THEN

（6）deletec;

（7）ELSEaddctoCk;

（8）END

（9）ReturnCk;

（三）、has_infrequent_subset（c,Lk-1）（候选集产生）

输入：

一个k-候选项目集c,（k-1）-频繁项目集Lk-1。

输出：

c是否从候选集中删除的布尔判断。

（1）FORall（k-1）-subsetsofcDO

（2）IFS∉Lk-1THENReturnTRUE；

（3）ReturnFALSE;

四、代码实现

（一）算法数据：

对给定数据集用Apriori算法进行挖掘，找出其中的频繁集并生成关联规则。

对下面数据集进行挖掘：

I1I2I5

I1I2

I2I4

I1I2I4

I1I3

I1I2I3I5

I1I2I3

I2I5

I2I3I4

I3I4

对于数据集，取最小支持度minsup=2，最小置信度minconf=0.8。

（二）算法步骤：

（1）、首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度闵值，得到一项频繁集L1。

（2）、然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再与最小支持度比较。

得到二项频繁集L2。

（3）、如此进行下去，直到不能连接产生新的候选集为止。

（4）、对于找到的所有频繁集，用规则提取算法进行关联规则的提取。

（三）C++算法的简单实现

（1）、首先要在工程名文件夹里自己定义date.txt文档存放数据，然后在main函数中用FILE*fp=fopen（"date.txt","r"）;将数据导入算法。

（2）、定义intcountL1[10];找到各一维频繁子集出现的次数。

定义charcurL1[20][2];实现出现的一维子集。

由于给出的数据最多有4个数，所以同样的我们要定义到4维来放数据。

intcountL2[10];//各二维频繁子集出现的次数

charcurL2[20][3];//出现的二维子集

intcountL3[10];//各三维频繁子集出现的次数

charcurL3[20][4];//出现的三维子集

charcur[50][4];

（3）、定义intSizeStr（char*m）得到字符串的长度。

实现代码如下：

intSizeStr（char*m）

{

inti=0;

while（*（m+i）!

=0）

{

i++;

}

returni;

}

（4）、比较两个字符串，如果相等返回true,否则返回false

boolOpD（char*x,char*y）

{

inti=0;

if（SizeStr（x）==SizeStr（y））

{

while（*（x+i）==*（y+i））

{

i++;

if（*（x+i）==0&&*（y+i）==0）

returntrue;

}

}

returnfalse;

}

（5）、通过voidLoadItemL1（char**p）得到所有1元的字串和各自出现的次数

voidLoadItemL1（char**p）

{

inti,j,n=0,k=0;

charch;

char*s;

intf;

memset（cur,0,sizeof（cur））;

for（i=0;i<20;i++）

{

curL1[i][0]=0;

curL1[i][1]=0;

}

for（j=0;j<10;j++）

countL1[j]=0;

for（i=0;i<10;i++）

for（j=0;j<4;j++）

{

ch=*（*（p+i）+j）;

if（ch==0）

break;

cur[n][0]=ch;

n++;

}

curL1[0][0]=cur[0][0];

curL1[0][1]=cur[0][1];

k=0;

for（i=0;i<50;i++）

{

if（cur[i]==0）

break;

s=cur[i];

f=1;

for（j=0;j<=k;j++）

{

if（OpD（s,curL1[j]））

{

f=0;

break;

}

}

if（f==1）

{

++k;

curL1[k][0]=cur[i][0];

curL1[k][1]=cur[i][1];

}

}

for（i=0;i<20;i++）

for（j=0;j<50;j++）

{

char*m;

m=curL1[i];

if（*m==0）

break;

if（OpD（m,cur[j]））

countL1[i]++;

}

printf（"L1:

\n"）;

printf（"项集支持度计数\n"）;

for（i=0;i<10;i++）

{

if（curL1[i]==0）

break;

if（countL1[i]>=2）

printf（"{I%s}:

%d\n",curL1[i],countL1[i]）;

}

}

（6）、通过voidSubItem2（char**p）得到所有的2元子串

voidSubItem2（char**p）

{

inti,j,k,n=0;

char*s;

memset（cur,0,sizeof（cur））;

for（i=0;i<20;i++）

{

curL2[i][0]=0;

curL2[i][1]=0;

curL2[i][2]=0;

}

for（i=0;i<10;i++）

countL2[i]=0;

for（k=0;k<10;k++）

{

s=*（p+k）;

if（SizeStr（s）<2）

continue;

for（i=0;i

for（j=i+1;j

{

if（*（s+j）==0）

break;

*（cur[n]+0）=*（s+i）;

*（cur[n]+1）=*（s+j）;

*（cur[n]+2）=0;

*（cur[n]+3）=0;

n++;

}

}

}

（7）、通过voidLoadItemL2（char**p）得到各个2元频繁子串出现的次数

voidLoadItemL2（char**p）

{

intk,i,j;

char*s;

intf;

SubItem2（p）;

curL2[0][0]=cur[0][0];

curL2[0][1]=cur[0][1];

curL2[0][2]=cur[0][2];

k=0;

for（i=0;i<50;i++）

{

if（cur[i]==0）

break;

s=cur[i];

f=1;

for（j=0;j<=k;j++）

{

if（OpD（s,curL2[j]））

{

f=0;

break;

}

}

if（f==1）

{

++k;

curL2[k][0]=cur[i][0];

curL2[k][1]=cur[i][1];

curL2[k][2]=cur[i][2];

}

}

for（i=0;i<20;i++）

for（j=0;j<50;j++）

{

s=curL2[i];

if（*s==0）

break;

if（OpD（s,cur[j]））

countL2[i]++;

}

printf（"L2:

\n"）;

printf（"项集支持度计数\n"）;

for（i=0;i<10;i++）

{

if（curL2[i]==0）

break;

if（countL2[i]>=2）

printf（"{I%c,I%c}:

%d\n",curL2[i][0],curL2[i][1],countL2[i]）;

}

}

（8）通过定义voidSubItem3（char**p）得到所有3元的子串

voidSubItem3（char**p）

{

char*s;

inti,j,h,m;

intn=0;

memset（cur,0,sizeof（cur））;

for（j=0;j<20;j++）

{

curL3[j][0]=0;

curL3[j][1]=0;

curL3[j][2]=0;

curL3[j][3]=0;

}

for（i=0;i<10;i++）

countL3[i]=0;

for（m=0;m<10;m++）

{

s=*（p+m）;

if（SizeStr（s）<3）

continue;

for（i=0;i

for（j=i+1;j

{

for（h=j+1;h

{

if（*（s+h）==0）

break;

*（cur[n]+0）=*（s+i）;

*（cur[n]+1）=*（s+j）;

*（cur[n]+2）=*（s+h）;

*（cur[n]+3）=0;

n++;

}

}

}

}

（9）同样我们要得到得到各个3元频繁子串出现的次数

voidLoadItemL3（char**p）

{

intk,i,j;

char*s;

intf;

SubItem3（p）;

curL3[0][0]=cur[0][0];

curL3[0][1]=cur[0][1];

curL3[0][2]=cur[0][2];

curL3[0][3]=cur[0][3];

k=0;

for（i=0;i<50;i++）

{

if（cur[i]==0）

break;

s=cur[i];

f=1;

for（j=0;j<=k;j++）

{

if（OpD（s,curL3[j]））

{

f=0;

break;

}

}

if（f==1）

{

++k;

curL3[k][0]=cur[i][0];

curL3[k][1]=cur[i][1];

curL3[k][2]=cur[i][2];

curL3[k][3]=cur[i][3];

}

}

for（i=0;i<20;i++）

for（j=0;j<50;j++）

{

s=curL3[i];

if（*s==0）

break;

if（OpD（s,cur[j]））

countL3[i]++;

}

printf（"L3:

\n"）;

printf（"项集支持度计数\n"）;

for（i=0;i<10;i++）

{

if（curL3[i]==0）

break;

if（countL3[i]>=2）

printf（"{I%c,I%c,I%c}:

%d\n",curL3[i][0],curL3[i][1],curL3[i][2],countL3[i]）;

}

}

（10）、定义voidLoadItemL4（char**p）得到各个3元子串出现的次数

voidLoadItemL4（char**p）

{

inti;

char*s;

intj=0;

for（i=0;i<10;i++）

{

s=*（p+i）;

if（SizeStr（s）==4）

j++;

}

printf（"四维子集出现的次数:

%d\n",j）;

printf（"没有四维的频繁子集，算法结束!

\n"）;

}

（11）、通过voidSupport（char*w,intg）得到关联规则，并输出结果

voidSupport（char*w,intg）

{

inti,j,k,n=0;

char*s;

floatc=0.8,d=0;

memset（cur,0,sizeof（cur））;

s=w;

for（i=0;i

{

*（cur[n]+0）=*（s+i）;

*（cur[n]+1）=0;

*（cur[n]+2）=0;

*（cur[n]+3）=0;

n++;

}

for（i=0;i

for（j=i+1;j

{

if（*（s+j）==0）

break;

*（cur[n]+0）=*（s+i）;

*（cur[n]+1）=*（s+j）;

*（cur[n]+2）=0;

*（cur[n]+3）=0;

n++;

}

for（i=0;i<10;i++）

{

if（SizeStr（cur[i]）==1）

{

for（j=0;j<10;j++）

{

if（OpD（cur[i],curL1[j]））

{

d=countL3[g]/（float）countL1[j];

if（d>=c）

printf（"{I%s}:

%f",curL1[i],d）;

break;

}

}

}

if（SizeStr（cur[i]）==2）

{

for（j=0;j<10;j++）

{

if（OpD（cur[i],curL2[j]））

{

d=countL3[g]/（float）countL2[j];

if（d>=c）

printf（"{I%c,I%c}:

%f\n",curL2[j][0],curL2[j][1],d）;

break;

}

}

}

}

}

（12）、最后通过main函数完成整过程序

intmain（intargc,char*argv[]）

{

inti=0,j=0,k;

charbuf[10][6];

char*p[10];

charch;

memset（buf,0,sizeof（buf））;

FILE*fp=fopen（"date.txt","r"）;

if（fp==NULL）

return0;

ch=fgetc（fp）;

while（ch!

=EOF）

{

if（ch==0xa||ch==0xd）

{

i++;

ch=fgetc（fp）;

j=0;

continue;

}

buf[i][j]=ch;

j++;

ch=fgetc（fp）;

}

for（k=0;k<10;k++）

{

*（p+k）=buf[k];

}

LoadItemL1（p）;

LoadItemL2（p）;

LoadItemL3（p）;

LoadItemL4（p）;

printf（"产生关联规则:

\n"）;

printf（"非空子集:

置信度:

\n"）;

for（i=0;i<10;i++）

{

if（curL3[i]!

=0&&countL3[i]>=2）

Support（curL3[i],i）;

}

return0;

}

（四）程序输出结果：

实验二分类模型1Id3算法

一、实验目的

通过实验，加深数据挖掘中分类（决策树）的认识，其经典算法为Id3算法，了解影响Id3算法性能的因素，掌握基于Id3算法理论的分类分析的原理和方法。

二、实验内容

对一数据集用Id3算法做数据分类分析（预测），用java语言实现。

三、方法手段

众所周知，数据库技术从20世纪80年代开始，已经得到广泛的普及和应用。

随着数据库容量的膨胀，特别是数据仓库以及web等新型数据源的日益普及，人们面临的主要问题不再是缺乏足够的信息可以使用，而是面对浩瀚的数据海洋如何有效地利用这些数据。

从数据中生成分类器的一个特别有效的方法是生成一个决策树（DecisionTree）。

决策树表示方法是应用最广泛的逻辑方法之一，它从一组无次序、无规则的事例中推理出决策树表示形式的分类规则。

决策树分类方法采用自顶向下的递归方式，在决策树的内部结点进行属性值的比较并根据不同的属性值判断从该结点向下的分支，在决策树的叶结点得到结论。

所以从决策树的根到叶结点的一条路径就对应着一条合取规则，整棵决策树就对应着一组析取表达式规则。

决策树是应用非常广泛的分类方法，目前有多种决策树方法，如ID3、CN2、SLIQ、SPRINT等。

四、Id3算法

1.1相关信息

决策树是一个类似于流程图的树结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输入，而每个树叶结点代表类或类分布。

数的最顶层结点是根结点。

一棵典型的决策树如图1所示。

它表示概念buys_computer，它预测顾客是否可能购买计算机。

内部结点用矩形表示，而树叶结点用椭圆表示。

为了对未知的样本分类，样本的属性值在决策树上测试。

决策树从根到叶结点的一条路径就对应着一条合取规则，因此决策树容易转化成分类规则。

图1

ID3算法特点：

1）决策树中每一个非叶结点对应着一个非类别属性，树枝代表这个属性的值。

一个叶

结点代表从树根到叶结点之间的路径对应的记录所属的类别属性值。

2）每一个非叶结点都将与属性中具有最大信息量的非类别属性相关联。

3）采用信息增益来选择能够最好地将样本分类的属性。

信息增益基于信息论中熵的概念。

ID3总是选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。

该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。

1.2问题重述

1、目标概念为“寿险促销”

2、计算每个属性的信息增益

3、确定根节点的测试属性

1.3模型求解

构造决策树的方法是采用自上而下的递归构造，其思路是：

1）以代表训练样本的单个结点开始建树（步骤1）。

2）如果样本都在同一类，则该结点成为树叶，并用该类标记（步骤2和3）。

3）否则，算法使用称为信息增益的机遇熵的度量为启发信息，选择能最好地将样本分类的属性（步骤6）。

该属性成为该结点的“测试”或“判定”属性（步骤7）。

值得注意的是，在这类算法中，所有的属性都是分类的，即取离散值的。

连续值的属性必须离散化。

4）对测试属性的每个已知的值，创建一个分支，并据此划分样本（步骤8~10）。

5）算法使用同样的过程，递归地形成每个划分上的样本决策树。

一旦一个属性出现在一个结点上，就不必考虑该结点的任何后代（步骤13）。

6）递归划分步骤，当下列条件之一成立时停止：

（a）给定结点的所有样本属于同一类（步骤2和3）。

（b）没有剩余属性可以用来进一步划分样本（步骤4）。

在此情况下，采用多数表决（步骤5）。

这涉及将给定的结点转换成树叶，并用samples中的多数所在类别标记它。

换一种方式，可以存放结点样本的类分布。

（c）分支test_attribute=ai没有样本。

在这种情况下，以samples中的多数类创建一个树叶（步骤12）。

1.4算法步骤

Decision_Tree（samples,attribute_list）

输入由离散值属性描述的训练样本集samples;

候选属性集合attribute_list。

输出一棵决策树。

（1）创建节点N；

（2）ifsamples都在同一类C中then

（3）返回N作为叶节点，以类C标记；

（4）ifattribute_list为空then

（5）返回N作为叶节点，以samples中最普遍的类标记；//多数表决

（6）选择attribute_list中具有最高