叶志伟数据挖掘实验指导书算法编程部分Word文档下载推荐.docx
《叶志伟数据挖掘实验指导书算法编程部分Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《叶志伟数据挖掘实验指导书算法编程部分Word文档下载推荐.docx（55页珍藏版）》请在冰点文库上搜索。
q.itemk-1
then
beginc=p∞q
ifhas_infrequent_subset（c,Lk-1）
thendeletec
elseaddctoCk
ReturnCk
3、has_infrequent_subset（c,Lk-1）
功能：
判断候选集的元素
一个k-频繁项目集Lk-1，（k-1）-频繁项目集Lk-1
c是否从候选集中删除的布尔判断
Forall（k-1）-subsetsofcdo
IfNot（S∈Lk-1）THENreturnTRUE;
ReturnFALSE;
4、Rule-generate（L,minconf）
频繁项目集；
最小信任度
强关联规则
算法：
FOReachfrequentitemsetlkinL
generules（lk,lk）;
5、Genrules递归算法：
Genrules（lk:
frequentk-itemset,xm:
frequentm-itemset）
X={（m-1）-itemsetsxm-1|xm-1inxm};
Foreachxm-1inX
BEGINconf=support（lk）/support（xm-1）;
IF（conf≧minconf）THEN
BEGIN
输出规则:
xm-1->
（lk-xm-1）,support,confidence;
IF（m-1）>
1）THENgenrules（lk,xm-1）;
END;
END;
结合相关样例数据对算法进行调试，并根据相关实验结果对数据进行分析，
四、实验报告要求
1、用C语言或者其他语言实现上述相关算法。
2、实验操作步骤和实验结果，实验中出现的问题和解决方法。
五、注意事项
1、集合的表示及相关操作的实现；
2、项目集的数据结构描述；
参考核心代码如下：
（相关的测试main函数可以自己书写。
根据频繁k项集生成关联规则相对简单，只需要计算最小置信度即可从频繁K项集中找到所有的满足条件的关联规则。
）
//对事物进行第一次扫描，生成频繁一项集，并返回一项集中个数
intinit_pass（char*item,chartran[len_t][len],intlen,charres_item[len_t][len],floatmin_sup）
{
floatt_sup;
intnumber=0;
for（inti=0;
i<
len;
i++）
{
intcount=0;
for（intj=0;
j<
len_t;
j++）
{
for（intk=0;
k<
k++）
if（item[i]==tran[j][k]）
{
count++;
break;
}
break;
}
t_sup=count*1.0/len;
if（t_sup>
=min_sup）
res_item[number++][0]=item[i];
}
returnnumber-1;
}
//生成候选K项集，返回k项集中事物的个数
intcandidate_gen（charktran[len][k],charkktran[len][k+1]）
chartemp[k],temp1[k],ktemp[k+1];
strcpy（temp,ktran[i]）;
boolflag;
for（j=i+1;
strcpy（temp1,ktran[i]）;
for（intm=0;
m<
k;
m++）
{
if（（m<
k-1&
&
temp[m]==temp1[m]）||m==k-1）{
continue;
flag=true;
else{
flag=false;
}
if（flag）
if（temp[k-1]>
temp1[k-1]）
strcpy（ktemp,temp1）;
ktemp[k]=temp[k-1];
else
strcpy（ktemp,temp）;
ktemp[k]=temp1[k-1]
break;
flag=judge（kemp,ktran[len][k]）;
if（flag==true）
strcpy（kktran[number++],ktemp）;
//判断子集是否在k项集中
booljudge（char*srcstr,chardesstr[len][k]）
chartemp[k];
intcount=0;
k-1;
i;
temp[j]=srcstr[j];
for（intj=i+1;
k+1;
for（intp=0;
p<
p++）
if（strcmp（temp,desstr[i]）==0）
count++;
if（count==k-1）
returntrue;
returnfalse;
//apriori算法
intapriori（charitem[len],chartran[length][len],charres_tran[length][len],floatmin_sup）
charttran[length][len];
intnumber,count,t_num;
length;
ttran[i][j]='
0'
;
number=init_pass（item,tran[length][len],len,ttran[length][len],min_sup）;
for（inti=0i<
res_tran[i][0]=ttran[i][0];
for（intk=2;
number!
=0;
t_num=number;
number=candidate_gen（res_item[number][k-1],ttran[number][k]）;
if（k==2）
continue;
else
count=0;
for（inti=0;
number;
chartemp[k];
strcpy（temp,ttran[i]）;
boolt_flag=false;
for（intj=0;
{//求出候选K项集中每个事物的支持计数
intt_k=0;
for（intn=0;
n<
n++）{
boolm_flag=false
for（intg=t_k;
g<
g++）
{
if（temp[k]==tran[j][g]）
{
m_flag=true;
t_k=g;
break;
}
}
if（m_flag==true&
n==k-1）
t_flag=true;
}
if（t_flag==true）
count++;
flag=false;
if（count/length>
min_sup）
strcpy（res_item[i],temp）;
count=0;
returnt_num;
实验2-1ID3算法实现
通过编程实现决策树算法，信息增益的计算、数据子集划分、决策树的构建过程。
加深对相关算法的理解过程。
4学时
1、分析决策树算法的实现流程；
2、分析信息增益的计算、数据子集划分、决策树的构建过程；
3、根据算法描述编程实现算法，调试运行；
三、实验方法
算法描述：
以代表训练样本的单个结点开始建树；
若样本都在同一个类，则该结点成为树叶，并用该类标记；
否则，算法使用信息增益作为启发信息，选择能够最好地将样本分类的属性；
对测试属性的每个已知值，创建一个分支，并据此划分样本；
算法使用同样的过程，递归形成每个划分上的样本决策树
递归划分步骤，当下列条件之一成立时停止：
给定结点的所有样本属于同一类；
没有剩余属性可以进一步划分样本，在此情况下，采用多数表决进行
四、实验步骤
1、算法实现过程中需要使用的数据结构描述：
Struct
{intAttrib_Col;
//当前节点对应属性
intValue;
//对应边值
Tree_Node*Left_Node;
//子树
Tree_Node*Right_Node//同层其他节点
BooleanIsLeaf;
//是否叶子节点
intClassNo;
//对应分类标号
}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）
IntClass_Distribute[C];
If（Record_No==0）{returnNull}
N=newtree_node（）;
计算Data中各类的分布情况存入Class_Distribute
Temp_Num_Attrib=0;
For（i=0;
Num_Attrib;
i++）
If（Data[0][i]>
=0）Temp_Num_Attrib++;
IfTemp_Num_Attrib==0
N->
ClassNo=最多的类；
N->
IsLeaf=TRUE;
Left_Node=NULL;
N->
Right_Node=NULL;
ReturnN;
IfClass_Distribute中仅一类的分布大于0
ClassNo=该类；
ReturnN;
InforGain=0;
CurrentCol=-1;
Fori=0;
Num_Attrib-1;
TempGain=Compute_InforGain（Data,Record_No,I,Num_Attrib）;
If（InforGain<
TempGain）
{InforGain=TempGain;
CurrentCol=I;
Attrib_Col=CurrentCol;
//记录CurrentCol所对应的不同值放入DiferentValue[]；
I=0;
Value_No=-1;
Whilei<
Record_No{
Flag=false;
For（k=0;
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;
k=-1;
for（j=0;
Record_No-1;
if（Data[j][CurrentCol]==DiferentValu[i]）
{k=k++;
For（inti1=0;
i1<
i1++）
If（i1<
>
CurrentCol）SubData[k][i1]=Data[j][i1];
ElseSubData[k][i1]=-1;
Value=DiferentValu[i];
Isleaf=false;
ClassNo=0;
Left_Node=Build_ID3（SubData,k+1,Num_Attrib）;
Right_Node=newTree_Node;
N=N->
Right_Node;
3.3、计算信息增益
Compute_InforGain（Data,Record_No,Col_No,Num_Attrib）
IntDifferentValue[MaxDifferentValue];
IntTotal_DifferentValue;
Ints[ClassNo][MaxDifferentValue];
s=0;
//数组清0;
Total_DifferentValue=-1;
Record_No;
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;
ClassNo;
Sum=0;
For（j=0;
j++）ifData[j][Num_Attrib-1]==isum++;
Total_I=Compute_PI（Sum/Record_No）;
EA=0;
Total_DifferentValue;
i++）;
{temp=0;
sj=0;
//sj是数据子集中属于类j的样本个数；
For（j=0;
ClassNO;
sj+=s[j][i];
EA+=sj/Record_No*Compute_PI（s[j][i]/sj）;
Returntotal_I-EA;
3.4、得到某数字在数组中的位置
GetPosition（Data,DataSize,Value）
DataSize;
i++）if（Data[i]=value）returnI;
Return-1;
3.5、计算Pi*LogPi
FloatCompute_PI（floatpi）
Ifpi<
=0thenreturn0;
Ifpi>
=1thenreturn0;
Return0-pi*log2（pi）;
五、实验报告要求
六、注意事项
1、信息增益的计算；
2、选择相关字段后根据相关字段的取值对数据集合进行划分。
3、决策树构建的终止条件
实验2-2贝叶斯算法实现
通过对贝叶斯算法的编程实现，加深对贝叶斯算法的理解，同时利用贝叶斯算法对简单应用实现预测分类
1、分析贝叶斯算法；
2、计算条件概率；
3、预测精度的计算与评估；
4、编程实现贝叶斯分类算法，并对简单应用样本数据实现预测分类
5.参考实验数据http:
//archive.ics.uci.edu/ml/machine-learning-databases/wine/
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
2
Excellent
3
31~40
Yes
4
40
med
5
Low
6
7
8
Med
9
10
11
12
13
14
B、对数据中的枚举类型数据进行转换以便于数据处理：
ClassNo
4.3计算训练数据集数据中各属性在各类中的概率分布情况如图3-1所示
4.4利用测试数据计算贝叶斯算法的分类精度如图3-2所示
申请AttSetSize*MaxAttSize*ClassSize大小的空间→AttributeDistribute
i=0
AttSetSize
TrainSetSize
AttributeDistribute[i][DataBase[j][i]][DataBase[j][AttSetSize-1]]++
AttributeDistribute←0
AttSize;
MaxAttSize;
For（k=0;
ClassSize;
AttributeDistribute[i][j][k]=0;
j=0
i++
i==AttSetSize-1
AttributeDistribute[i][0][DataBase[j][AttSetSize-1]]++
j++
图3-1训练数据集各属性的概率分布计算
申请ClassSize*ClassSize个空间→Precise
SetSize
升级会员 