数据挖掘实验指导书.doc

《数据挖掘》实验指导书

2011年3月1日

长沙学院信息与计算科学系
前言
随着数据库技术的发展，特别是数据仓库以及Web等新型数据源的日益普及，形成了数据丰富，知识缺乏的严重局面。针对如何有效地利用这些海量的数据信息的挑战，数据挖掘技术应运而生，并显示出强大的生命力。数据挖掘技术使数据处理技术进入了一个更高级的阶段，是对未来人类产生重大影响的十大新兴技术之一。因此加强数据挖掘领域的理论与实践学习也已成为专业学生的必修内容。
本实验指导书通过大量的实例，循序渐进地引导学生做好各章的实验。根据实验教学大纲，我们编排了五个实验，每个实验又分了五部分内容：实验目的、实验内容、实验步骤、实验报告要求、注意事项。在实验之前，由教师对实验作一定的讲解后，让学生明确实验目的，并对实验作好预习工作。在实验中，学生根据实验指导中的内容进行验证与总结，然后再去完成实验步骤中安排的任务。实验完成后，学生按要求完成实验报告。整个教学和实验中，我们强调学生切实培养动手实践能力，掌握数据挖掘的基本方法。
长沙学院信息与计算科学系 数据挖掘实验指导书
实验一 K-Means聚类算法实现
一、实验目的
通过分析K-Means聚类算法的聚类原理，利用Vc编程工具编程实现K-Means聚类算法，并通过对样本数据的聚类过程，加深对该聚类算法的理解与应用过程。
实验类型：验证
计划课间：4学时

二、实验内容
1、分析K-Means聚类算法；
2、分析距离计算方法；
3、分析聚类的评价准则；
4、编程完成K-Means聚类算法，并基于相关实验数据实现聚类过程；

三、实验方法
1、K-means聚类算法原理
K-means聚类算法以k为参数，把n个对象分为k个簇，以使簇内的具有较高的相似度。相似度的计算根据一个簇中对象的平均值来进行。
算法描述：
输入：簇的数目k和包含n个对象的数据库
输出：使平方误差准则最小的k个簇
过程：
任选k个对象作为初始的簇中心；
Repeat
for j=1 to n DO
根据簇中对象的平均值，将每个对象赋给最类似的簇
for i=1 to k DO
更新簇的平均值
计算E
Unitl E不再发生变化
按簇输出相应的对象

2、聚类评价准则：
E的计算为：

四、实验步骤
4.1 实验数据
P192：15

4.2初始簇中心的选择
选择k个样本作为簇中心
For (i=0;i<k;i++)
For (j=0;j<AttSetSize;j++)
ClusterCenter[i][j]=DataBase[i][j]

4.3 数据对象的重新分配
Sim=某一较大数；ClusterNo=-1;
For (i=0;i<k;i++)
If (Distance(DataBase[j],ClusterCenter[i])<Sim)
{Sim=Distance(DataBase[j],ClusterCenter[i]);
ClusterNo=i;}
ObjectCluster[j]=ClusterNo;

4.4 簇的更新
For (i=0;i<k;i++)
{Temp=0;Num=0;
For (j=0;j<n;j++)
If (ObjectCluster[j]==i){Num++; Temp+=DataBase[j];}
If (ClusterCenter[i]!=Temp) HasChanged=TRUE;
ClusterCenter[i]=Temp;
}

4.5 结果的输出
For (i=0;i<k;i++)
{
Printf(“输出第%d个簇的对象:”，i);
For (j=0;j<n;j++)
If (ObjectCluster[j]==i) printf(“%d ”,j);
Printf(“\n”);
Printf(“\t\t\t 簇平均值为(%d,%d)\n”, ClusterCenter[i][0], ClusterCenter[i][1]);
}

五、注意事项
1、距离函数的选择
2、评价函数的计算

实验二 DBSCAN算法实现
一、实验目的
要求掌握DBSCAN算法的聚类原理、了解DBSCAN算法的执行过程。在此基础上，利用DBSCAN算法对给定样本数据实现聚类过程。
实验类型：综合
计划课间：4学时

二、实验内容
1、了解DBSCAN算法的聚类原理；
2、了解DBSCAN算法的执行过程；
3、编程实现DBSCAN算法；
4、对给定样本数据实现聚类过程

三、实验方法
3.1、DBSCAN算法的基本概念
l 对象的ε-邻域：给定对象在半径ε内的区域；
l 核心对象：若一个对象ε-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象；
l 直接密度可达：给定一个对象集合D，若p是在q的ε-邻域内，而q是一个核心对象，则称对象p从对象q出发是直接密度可达的；
l 密度可达：若存在一个对象链p1,p2,…,pn,p1=q,pn=p,对pi∈D,pi+1是从pi关于ε和MinPts直接密度可达的，则称对象p是从对象q关于ε和MinPts是密度可达的；
l 密度相连：若对象集合D中存在一个对象o，使得对象p和q是从o关于ε和MinPts是密度可达的，则对象p和q是关于ε和MinPts密度相连的；
l 噪声：一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合，不包含在任何簇中的对象被认为是噪声
3.2、实现的基本思想
通过检查数据集中每个对象的ε-邻域来寻找聚类。如一个点p的ε-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇。然后，DBSCAN寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并，当没有新的点可以被添加到任何簇时，聚类过程结束。

3.3 算法描述
输入：包含n个对象的数据库，半径，最小数目MinPts;
输出：所有生成的簇，达到密度要求
过程：
Repeat
从数据库中抽取一个未处理的点；
IF 抽出的点是核心点 THEN 找出所有从该店密度可达的对象，形成一个簇；
ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点；
Until 所有点都被处理

四、实验步骤
4.1 数据结构的分析
Struct List
{Int data[TOTALPOINT];
Int head=0;
Int tail=-1;}
List ClusterList;
Struct Node
{ int Attribute1;
int Attribute2}
Node DataBase[TOTALPOINT];
Boolean Neighbor[TOTALPOINT][TOTALPOINT];
Int ClusterNo[TOTALPOINT];

4.2 实验数据
P186 表5-8

4.3 计算临近
For (i=0;i<TOTALPOINT;i++)
For (j=0;j<TOTALPOINT;j++)
If (dist(DataBase[i],DataBase[i])<ε then
Neighbor[i][j]=true;Neighbor[j][i]=true;

4.4 聚类划分
CurrentClusterNO=0;
For (i=0;i<TOTALPOINT;i++)
{
NeighborPointsNum=0;
for (j=0;j<TOTALPOINT;j++)
if (Neighbor[i][j]==true)NeighborPointsNum++;
if (NeighborPointsNum)>=MinPts
{
// 记录邻居中已被划分的簇号
ClusterList.tail=-1;
ClusterList.head=0;
For (j=0;j<TOTALPOINT;j++)
If (Neighbor[i][j]==true) &&(ClusterNo[j]>0)
Then {ClusterList.tail++;
ClusterList.data[tail]=ClusterNo[j]}
// 当前核心对象的邻居对象划分为一簇
For (j=0;j<TOTALPOINT;j++)
If (Neighbor[i][j]==true) then
ClusterNo[j]=CurrentClusterNO;
// 将多个簇合并
While ClusterList.head<=ClusterList.tail
{ for (j=0;j<TOTALPOINT;j++)
If (ClusterNo[j]==ClusterList.data[head])
ClusterNo[j]=CurrentClusterNO;
ClusterList.head++;
}
}
}
4.5 聚类结果输出
For (i=-1;i<CurrentClusterNO;i++);
{
Printf(“\n输出第%d簇的对象：”,i);
For (j=0;j<TOTALPOINT;j++)
If (ClusterNo[j]=i) printf(“%d\t”,j);
}
五、注意事项
5.1. 噪声数据的处理
5.2 已划分的类存在直接密度可达时的相关类数据的合并
第21页
实验三 ID3算法实现

一、实验目的
通过编程实现决策树算法，信息增益的计算、数据子集划分、决策树的构建过程。加深对相关算法的理解过程。
实验类型：验证
计划课间：4学时

二、实验内容
1、分析决策树算法的实现流程；
2、分析信息增益的计算、数据子集划分、决策树的构建过程；
3、根据算法描述编程实现算法，调试运行；
4、对课后P161的第10题进行验算，得到分析结果。

三、实验方法
算法描述：
以代表训练样本的单个结点开始建树；
若样本都在同一个类，则该结点成为树叶，并用该类标记；
否则，算法使用信息增益作为启发信息，选择能够最好地将样本分类的属性；
对测试属性的每个已知值，创建一个分支，并据此划分样本；
算法使用同样的过程，递归形成每个划分上的样本决策树
递归划分步骤，当下列条件之一成立时停止：
给定结点的所有样本属于同一类；
没有剩余属性可以进一步划分样本，在此情况下，采用多数表决进行

四、实验步骤
1、算法实现过程中需要使用的数据结构描述：
Struct
{int Attrib_Col; // 当前节点对应属性
int Value; // 对应边值
Tree_Node* Left_Node; // 子树
Tree_Node* Right_Node // 同层其他节点
Boolean IsLeaf; // 是否叶子节点
int ClassNo; // 对应分类标号
}Tree_Node;

2、整体算法流程
主程序：
InputData();
T=Build_ID3(Data,Record_No, Num_Attrib);
OutputRule(T);
释放内存;
3、相关子函数：
3.1、 InputData()
{
输入属性集大小Num_Attrib;
输入样本数Num_Record;
分配内存Data[Num_Record][Num_Attrib];
输入样本数据Data[Num_Record][Num_Attrib]；
获取类别数C(从最后一列中得到);
}

3.2、Build_ID3(Data,Record_No, Num_Attrib)
{
Int Class_Distribute[C];
If (Record_No==0) { return Null }
N=new tree_node();
计算Data中各类的分布情况存入Class_Distribute
Temp_Num_Attrib=0;
For (i=0;i<Num_Attrib;i++)
If (Data[0][i]>=0) Temp_Num_Attrib++;
If Temp_Num_Attrib==0
{
N->ClassNo=最多的类；
N->IsLeaf=TRUE;
N->Left_Node=NULL;N->Right_Node=NULL;
Return N;
}
If Class_Distribute中仅一类的分布大于0
{
N->ClassNo=该类；
N->IsLeaf=TRUE;
N->Left_Node=NULL;N->Right_Node=NULL;
Return N;
}
InforGain=0;CurrentCol=-1;

For i=0;i<Num_Attrib-1;i++)
{
TempGain=Compute_InforGain(Data,Record_No,I,Num_Attrib);
If (InforGain<TempGain)
{ InforGain=TempGain; CurrentCol=I;}
}
N->Attrib_Col=CurrentCol;
//记录CurrentCol所对应的不同值放入DiferentValue[]；
I=0;Value_No=-1;
While i<Record_No {
Flag=false;
For (k=0;k<Value_No;k++)
if (DiferentValu[k]=Data[i][CurrentCol]) flag=true;
if (flag==false)
{Value_No++;DiferentValue[Value_No]=Data[i][CurrentCol] }
I++;
}
SubData=以Data大小申请内存空间；
For (i=0;i<Value_No;i++)
{
k=-1;
for (j=0;j<Record_No-1;j++)
if (Data[j][CurrentCol]==DiferentValu[i])
{k=k++;
For(int i1=0;i1<Num_Attrib;i1++)
If (i1<>CurrentCol)SubData[k][i1]=Data[j][i1];
Else SubData[k][i1]=-1;
}
N->Attrib_Col=CurrentCol;
N->Value=DiferentValu[i];
N->Isleaf=false;
N->ClassNo=0;
N->Left_Node=Build_ID3(SubData,k+1, Num_Attrib);
N->Right_Node=new Tree_Node;
N=N->Right_Node;
}
}

3.3、计算信息增益
Compute_InforGain(Data,Record_No, Col_No, Num_Attrib)
{
Int DifferentValue[MaxDifferentValue];
Int Total_DifferentValue;
Int s[ClassNo][MaxDifferentValue];

s=0;// 数组清0;
Total_DifferentValue=-1;
For (i=0;i<Record_No;i++)
{
J=GetPosition(DifferentValue,
Total_DifferentValue,Data[i][Col_no]);
If (j<0) {Total_DifferentValue++;
DifferentValue[Total_DifferentValue]=Data[i][Col_no];
J=Total_DifferentValue;}
S[Data[i][Num_Attrib-1]][j]++;
}
Total_I=0;
For (i=0;i<ClassNo;i++)
{
Sum=0;
For(j=0;j<Record_No;j++) if Data[j][Num_Attrib-1]==i sum++;
Total_I=Compute_PI(Sum/Record_No);
}
EA=0;
For (i=0;i<Total_DifferentValue;i++);
{ temp=0;sj=0; //sj是数据子集中属于类j的样本个数；
For (j=0;j<ClassNO;j++)
sj+=s[j][i];
For (j=0;j<ClassNO;j++)
EA+=sj/Record_No*Compute_PI(s[j][i]/sj);
}

Return total_I-EA;
}

3.4、得到某数字在数组中的位置
GetPosition(Data, DataSize,Value)
{
For (i=0;i<DataSize;i++) if (Data[i]=value) return I;
Return -1;
}

3.5、计算Pi*LogPi
Float Compute_PI(float pi)
{
If pi<=0 then return 0;
If pi>=1 then return 0;
Return 0-pi*log2(pi);
}

五、实验报告要求
1、用C语言实现上述相关算法。
2、实验操作步骤和实验结果，实验中出现的问题和解决方法。
六、注意事项
1、信息增益的计算；
2、选择相关字段后根据相关字段的取值对数据集合进行划分。
3、决策树构建的终止条件

实验四 贝叶斯算法实现
一、实验目的
通过对贝叶斯算法的编程实现，加深对贝叶斯算法的理解，同时利用贝叶斯算法对简单应用实现预测分类
实验类型：验证
计划课间：4学时

二、实验内容
1、分析贝叶斯算法；
2、计算条件概率；
3、预测精度的计算与评估；
4、编程实现贝叶斯分类算法，并对简单应用样本数据实现预测分类

三、实验方法
1、 实现贝叶斯算法
2、 利用实验数据对贝叶斯算法进行检测
3、 求解精确度计算
4、 调试程序
5、 完成整个分类与评估的过程

四、实验步骤
4.1 算法过程描述：
1）输入训练数据，将数据保存在DataBase二维数组中(数组的最后一个属性对应类别标号)
2）设定训练数据集与测试数据集大小(指定从数组下标0开始到TrainSetSize-1所对应的数据为训练数据，其余为测试数据)；
3）计算训练数据集数据中各属性在各类中的概率分布情况；
4）利用测试数据计算贝叶斯算法的分类精度；
5）输出分类结果；
4.2 数据处理
A、实验数据
RID
age
income
student
Credit_rating
BuyComputer
1
≦30
High
No
Fair
No
2
≦30
High
No
Excellent
No
3
31~40
High
No
Fair
Yes
4
>40
med
No
Fair
Yes
5
>40
Low
Yes
Fair
Yes
6
>40
Low
Yes
Excellent
No
7
31~40
Low
Yes
Excellent
Yes
8
≦30
Med
No
Fair
No
9
≦30
Low
Yes
Fair
Yes
10
>40
Med
Yes
Fair
Yes
11
≦30
Med
Yes
Excellent
Yes
12
31~40
Med
No
Excellent
Yes
13
31~40
High
Yes
Fair
Yes
14
>40
med
No
Excellent
No
B、对数据中的枚举类型数据进行转换以便于数据处理：

0
1
2
3
ClassNo
1
0
0
0
0
0
2
0
0
0
1
0
3
1
0
0
0
1
4
2
1
0
0
1
5
2
2
1
0
1
6
2
2
1
1
0
7
1
2
1
1
1
8
0
1
0
0
0
9
0
2
1
0
1
10
2
1
1
0
1
11
0
1
1
1
1
12
1
1
0
1
1
13
1
0
1
0
1
14
2
1
0
1
0
4.3 计算训练数据集数据中各属性在各类中的概率分布情况如图3-1所示
4.4 利用测试数据计算贝叶斯算法的分类精度如图3-2所示

No
No
Yes
Yes
申请AttSetSize*MaxAttSize*ClassSize大小的空间àAttributeDistribute
i=0
i<AttSetSize
j<TrainSetSize
AttributeDistribute[i][DataBase[j][i]][DataBase[j][AttSetSize-1]]++
AttributeDistributeß0
For (i=0;i<AttSize;i++)
For (j=0;j<MaxAttSize;j++)
For(k=0;k<ClassSize;k++)
AttributeDistribute[i][j][k]=0;
j=0
i++
No
i==AttSetSize-1
Yes
AttributeDistribute[i][0][DataBase[j][AttSetSize-1]]++
j++

图3-1 训练数据集各属性的概率分布计算

申请ClassSize*ClassSize个空间àPrecise
i<SetSize
Presizeß0 ; AttrClassDisß0
For (i=0;i<ClassSize;i++)
For (j=0;j<ClassSize;j++)
Presize[i][j]=0;
i=TrainSetSize;
i++
j=0
MaxP=0;ClassNo=0;
Tempß计算属于类j的概率
For (k=0;k<AttSetSize-1)
Temp*=AttributeDistribute[k][DataBase[i][k]][j]/AttributeDistribute[AttSetSize-1][0][j]
Temp*=AttributeDistribute[AttSetSize-1][0][j]/TrainSet
j<ClassSize
Temp>MaxP
MaxP=Temp;ClassNo=j
j++
Precise[DataBase[i][AttrSetSize-1]][ClassNo]++

图3-2 贝叶斯算法的分类精度计算
4.5 输出分类结果
For (i=0;i<ClassSize;i++)
{printf(“\n”);
For (j=0;j<ClassSize;j++) printf(“\t%d”, Precise[i][j]);
TotalCorrect+=Precise[i][i];
}
printf(“\n\nTotal Correct is%d”,TotalCorrect);

五、注意事项
注意单个样例数据的概率计算与各字段的概率计算的关系
实验五 Apriori算法实现

一、实验目的
1、掌握Apriori算法对于关联规则挖掘中频繁集的产生以及关联规则集合的产生过程；
2、根据算法描述编程实现算法，调试运行。并结合相关实验数据进行应用，得到分析结果。
数据和删除数据的操作。
实验类型：验证
计划课间：2学时

二、实验内容
1、频繁项集的生成与Apriori算法实现；
2、关联规则的生成过程与Rule-generate算法实现；
3、结合样例对算法进行分析；

三、实验步骤
编写程序完成下列算法：
1、Apriori算法
输入： 数据集D；最小支持数minsup_count；
输出： 频繁项目集L
L1={large 1-itemsets}
For (k=2; Lk-1≠Φ; k++)
Ck=apriori-gen (Lk-1); // Ck是k个元素的候选集
For all transactions t∈D do
begin Ct=subset(Ck,t); //Ct是所有t包含的候选集元素
for all candidates c ∈Ct do c.count++;
end
Lk={c ∈Ck| c.count ≧ minsup_count }
End
L=∪Lk;

2、apriori-gen (Lk-1) 候选集产生算法
输入： (k-1)-频繁项目集Lk-1
输出： k-频繁项目集Ck
For all itemset p∈Lk-1 do
For all itemset q∈Lk-1 do
If p.item1=q.item1, p.item2=q.item2, …,p.itemk-2=q.itemk-2, p.itemk-1<q.itemk-1
then
begin c=p∞q
if has_infrequent_subset(c, Lk-1)
then delete c
else add c to Ck
End
Return Ck

3、has_infrequent_subset(c, Lk-1)
功能：判断候选集的元素
输入： 一个k-频繁项目集Lk-1 ，(k-1)-频繁项目集Lk-1
输出：c是否从候选集中删除的布尔判断
For all (k-1)-subsets of c do
If Not(S∈Lk-1) THEN return TRUE;
Return FALSE;

4、Rule-generate(L,minconf)
输入：频繁项目集；最小信任度
输出：强关联规则
算法：
FOR each frequent itemset lk in L
generules(lk,lk);

5、Genrules递归算法：
Genrules(lk:frequent k-itemset, xm:frequent m-itemset)
X={(m-1)-itemsets xm-1 | xm-1 in xm};
For each xm-1 in X
BEGIN conf=support(lk)/support(xm-1);
IF (conf≧minconf) THEN
BEGIN
输出规则:xm-1->(lk-xm-1),support,confidence;
IF (m-1)>1) THEN genrules(lk,xm-1);
END;
END;
结合相关样例数据对算法进行调试，并根据相关实验结果对数据进行分析，
四、实验报告要求
1、用C语言实现上述相关算法。
2、实验操作步骤和实验结果，实验中出现的问题和解决方法。
五、注意事项
1、集合的表示及相关操作的实现；
2、项目集的数据结构描述；