数据挖掘实验报告
实验二:关联规则挖掘
班级:计算机XX班 姓名:XXX
学号:XXX
日期:
一、实验目的
用C语言实现数据中的关联规则挖掘。(使用Apriori算法)
二、实验内容
1.数据平滑
使用你熟悉的程序设计语言,如C,C++,JAVA,SQL Server等,实现Apriori算法。要求程序具有一定的通用性,使用下面的两组数据进行验证。
提示:
(1)Items集合中元素的数目不限于26个,故不可使用A-Z代表Item’s name;
(2)仅输出频繁1项集L1,频繁2项集L2,频繁3项集L3……即可,不比输出关联规则。
三、主要算法代码
char shop[10]; //用于存放每一种商品
int sn; //商品信息(商品种类数)
int tr[100][100],l[100],tn; //tr记录事务信息(数字化之后的事务信息),l记录每条事务包含的商品数,tn记录总共有多少条事务记录
int min_sup=2; //最小支持度计数
float min_conf=0.7f; //最小置信度阈值
typedef struct
{
int * *p; //记录i项集的所有内容(比如1项集的内容,2项集的内容,或者3项集的内容等等)
int * num; //各个项集的支持计数(比如1项集中的每一条记录的支持度计数为多少,或者2项集中的每一条记录的支持度计数为多少等等)
int i; //项集的项数(比如1项集,或者为2项集,或者为3项集) int n; //项集的数目(比如得到的1项集中有多少条记录,或者为2项集中有多少条记录,或者3项集中有多少条记录)
} Large;
bool subset(int t,int k)//判断名称为t的商品是否在事务k中
{
int mid,right,left; left=1; right=l[k]; for(int i=left;i<=right;i++) { if(tr[k][i]==t) { } return true;
}
while(left<=right) {
mid=(left+right)/2; if(tr[k][mid]==t) {
return true; }
if(tr[k][mid]>t) {
right=mid-1; }
else
{
left=mid+1; }
}
return false;
}
Large find_f1() {
Large C1,L1; //产生频繁1项集L1
int i,k; C1.i=1; C1.n=0; for(i=1;i<=sn;i++) //产生C1 { if(C1.n==0) //初始化C1 { } else { } *(*(C1.p+C1.n-1)+0)=i; *(C1.num+C1.n-1)=0; for(k=1;k<=tn;k++) C1.n++; C1.p=(int * *)realloc(C1.p,C1.n*sizeof(int *)); C1.num=(int *)realloc(C1.num,C1.n*sizeof(int)); *(C1.p+C1.n-1)=(int *)malloc(C1.i*sizeof(int)); C1.n=1; C1.p=(int * *)malloc(C1.n*sizeof(int *)); C1.num=(int *)malloc(C1.n*sizeof(int)); *( C1.p+C1.n-1)=(int *)malloc(C1.i*sizeof(int));
} { } if(subset(i,k)) { } *(C1.num+C1.n-1)=*(C1.num+C1.n-1)+1; L1.i=1; L1.n=0; for(i=0;i<C1.n;i++) { if(*(C1.num+i)>=min_sup) { if(L1.n==0) { } else { L1.n=1; L1.p=(int * *)malloc(L1.n*sizeof(int *)); L1.num=(int *)malloc(L1.n*sizeof(int)); *( L1.p+L1.n-1)=(int *)malloc(L1.i*sizeof(int));
}
} } } L1.n++; L1.p=(int * *)realloc(L1.p,L1.n*sizeof(int *)); L1.num=(int *)realloc(L1.num,L1.n*sizeof(int)); *(L1.p+L1.n-1)=(int *)malloc(L1.i*sizeof(int)); *(*( L1.p+L1.n-1)+0)=*(*( C1.p+i)+0); *(L1.num+L1.n-1)=*(C1.num+i); cout<<"L1:"<<endl; for(i=0;i<L1.n;i++) { } return L1; cout<<shop[*(*( L1.p+i)+0)]<<' '<<*(L1.num+i)<<endl;
bool In_subset(Large Lp,int *c) //剪枝步运算 {
int i,j,m,tag; int * temp=(int *)malloc(Lp.i*sizeof(int)); for(i=0;i<Lp.i+1;i++)
{ for(j=0;j<i;j++) //生成子集 { } for(j=i+1;j<Lp.i+1;j++) { } tag=1; for(m=0;m<Lp.n;m++) { for(j=0;j<Lp.i;j++) { } if(j==Lp.i) { tag=0; //匹配成功,进行下个子集匹配 if(*(temp+j)!=*(*(Lp.p+m)+j)) { } break; *(temp+j-1)=*(c+j); *(temp+j)=*(c+j);
break;
}
}
if(tag==1)
{
return false; }
}
return true; }
Large apriori_gen(Large Lp) {
int i,j,k;
int *c=(int *)malloc((Lp.i+1)*sizeof(int)); Large Cn;
Cn.i=Lp.i+1;
Cn.n=0;
for(i=0;i<Lp.n;i++)
{
for(j=i+1;j<Lp.n;j++) {
for(k=0;k<Lp.i-1;k++) //连接步运算
{ } if(k==Lp.i-1) { if(*(*(Lp.p+i)+k)>*(*(Lp.p+j)+k)) { } else { } *(c+k)=*(*(Lp.p+i)+k); *(c+k+1)=*(*(Lp.p+j)+k); *(c+k)=*(*(Lp.p+j)+k); *(c+k+1)=*(*(Lp.p+i)+k); if(*(*(Lp.p+i)+k)!=*(*(Lp.p+j)+k)) { } else { } *(c+k)=*(*(Lp.p+i)+k); break;
} if(In_subset(Lp,c)) //通过剪枝运算 { } if(Cn.n==0) { } else { } for(k=0;k<Cn.i;k++) { } *(*(Cn.p+Cn.n-1)+k)=*(c+k); Cn.n++; Cn.p=(int * *)realloc(Cn.p,Cn.n*sizeof(int *)); Cn.num=(int *)realloc(Cn.num,Cn.n*sizeof(int)); *(Cn.p+Cn.n-1)=(int *)malloc(Cn.i*sizeof(int)); Cn.n=1; Cn.p=(int * *)malloc(Cn.n*sizeof(int *)); Cn.num=(int *)malloc(Cn.n*sizeof(int)); *(Cn.p+Cn.n-1)=(int *)malloc(Cn.i*sizeof(int));
} } } return Cn;
void f() {
int i,j,k,m,lk=1; Large *L=(Large *)malloc((lk+1)*sizeof(Large)); Input(); *(L+1)=find_f1(); for(k=2;(*(L+k-1)).n!=0;k++) { Large Ck=apriori_gen(*(L+k-1)); for(i=0;i<Ck.n;i++) { *(Ck.num+i)=0; for(m=1;m<=tn;m++) { for(j=0;j<Ck.i;j++) { if(!subset(*(*(Ck.p+i)+j),m)) {
} } break; if(j==Ck.i) //如果相等,说明数据库中的事务包含k项集的当前项
间
(*(L+k)).n=0; //初始化k项频繁集包含 } L=(Large *)realloc(L,(k+1)*sizeof(Large));//为存放k项频繁集申请空 } { } *(Ck.num+i)=*(Ck.num+i)+1;//使k项集的第i项加1 的项数
(*(L+k)).i=k; //初始化k项频繁集的标志"k"
for(i=0;i<Ck.n;i++) { if(*(Ck.num+i)>=min_sup) //与限值(最小支持度计数)比较
{ if((*(L+k)).n==0)
{ (*(L+k)).n=1; (*(L+k)).p=(int * *)malloc((*(L+k)).n*sizeof(int *)); (*(L+k)).num=(int *)malloc((*(L+k)).n*sizeof(int)); *((*(L+k)).p+(*(L+k)).n-1)=(int
*)malloc((*(L+k)).i*sizeof(int));
*));
(*(L+k)).num=(int } else { (*(L+k)).n++; (*(L+k)).p=(int * *)realloc((*(L+k)).p,(*(L+k)).n*sizeof(int
*)realloc((*(L+k)).num,(*(L+k)).n*sizeof(int));
*((*(L+k)).p+(*(L+k)).n-1)=(int
*)malloc((*(L+k)).i*sizeof(int));
} for(j=0;j<Ck.i;j++) //将满足条件的候选集中的当前记录的内容赋给k项频繁集L
{ } *(*((*(L+k)).p+(*(L+k)).n-1)+j)=*(*(Ck.p+i)+j);
*((*(L+k)).num+(*(L+k)).n-1)=*(Ck.num+i);//将该记录对应的支持度计数记录在k项频繁集L的num数组的对应位置
} } } if((*(L+k)).n==0) { } lk++; cout<<"L"<<k<<":"<<endl; for(i=0;i<(*(L+k)).n;i++) { } for(j=0;j<(*(L+k)).i;j++) { } cout<<*((*(L+k)).num+i)<<endl; cout<<shop[*(*((*(L+k)).p+i)+j)]<<' '; break; }
四、实验结果
根据Apriori算法进行关联规则挖掘,最后输出频繁1项集L1,频繁2项集
L2,……
五、心得体会
数据挖掘中的Apriori算法关联规则挖掘原理看似简单,但利用计算机进行具体的挖掘过程时并不容易。所以对于算法的理解必须更为深入才能保证编程的顺利完成。
一、实验说明及目的
1、使用真实数据进行数据挖掘实验,实验前进行数据的预处理。
2、训练一些不同类型的模型(具体类型可以讨论),与此同时分析哪些参数将对支持向量机(SVM)模型的性能产生影响。
3、通过实验来分析预测,将其他一些属性作为森林覆盖类型(Cover_Type 属性)的模型输入所产生的效果。原始数据和数据的描述见网址http://kdd.ics.uci.edu/databases/covertype/covertype.html
4、该实验将使学生理解完成一次真实数据预处理以及在数据挖掘过程中对属性、数据覆盖类型等方面的分析工程。
二、实验具体任务及其说明
1、数据预处理工作
(1)数据样本的生成:根据原始数据集生成统一的随机样本,样本数据量大约是原始数据量的10%,要求使用不重复抽样。(任务1)
(2)森林覆盖值的映射:变换不同种类的属性,将森林覆盖值2映射到0,将其他值所有森林覆盖值(1,3,4,5,6,7)映射到1。(任务2)
(3)数据预处理技巧:自行决定是否需要其他的数据预处理,注意某些Weka软件的使用技巧,如一些输入输出格式问题。有时某些方法也做必要的调整,在某些情况下必须对数据有明确的预处理,做数据预处理时可以查看Weka软件针对该技巧或方法的描述。
(4)预处理说明:原始数据集非常大,具有7种类型的森林覆盖,检查整个数据集装载到Weka软件是发生的情况,如果机器内存耗尽,可以尽量增大堆的大小试试。Weka使用指南对此有描述如何操作。)2、模型训练工作
(1)使用Weka分类器的评价工具进行预测。使用Naïve Bayes分类器对抽样样本进行训练以预测变换的森林覆盖类型(即是映射到种类0还是1),使用10层交叉验证来评估变换的模型,Weka软件中自带有对其分类器的表现评价器,使用自带的评价器来确定变换模型的精确度和变动率指标(ROC)。(任务3)
(2)对SVM模型进行训练:使用Weka软件的SMO分类器对支持向量机(SVM)模型进行训练,训练2种形式的SVM模型,一种是带多项式核函数的SVM模型,另一种是带径向基核函数(RBF Kernel)的SVM模型。训练时所有的参数均使用默认值,分析并确定这些模型的精确度和变动率指标(ROC)。对SVM模型进行所有的抽样样本进行训练可能会很慢,所以对抽样样本进行分割,即使用1/20的抽样样本数据(或者1/200的原始数据集)进行训练,使用19/20的抽样样本进行测试。(任务4)
(3)对SVM模型训练后进行评估:使用至多1/20的抽样数据进行训练,以找出带RBF核函数的SVM最好的表现情况。改变参数复杂度参数C和参数gamma(在Weka中针对RBF核函数也有一个参数C,该参数将不改变),使用一个等比数列的值分析这2个参数同时变化时产生的影响,看看这2个参数同时比默认情况下大一些或小一些的情况,以找出最佳的参数设置。分析并确定所有SVM模型的精确度和变动率指标(ROC)。(注意:如果使用1/20的抽样样本数据量来训练各自的SVM模型超过30分钟,可以进一步减少样本数据量以避免计算资源的耗尽,在提交的实验报告中可以记录这些样本数据的具体训练时间)(任务5)
三、实验结果的提交说明
1、描述所有的数据预处理步骤。
(1)在使用Weka软件的知识流工具时,提交其中的工作流图示,并对工作流中所有参数设置进行阐述。
(2)提交产生抽样样本数据的代码并对代码进行适当的注释说明,还可以描述产生的样本有多少元组等。
2、描述怎样训练和评估Naïve Bayes模型。
(1)在使用Weka软件的知识流工具时,提交其中的工作流图示,并对工作流中所有参数设置进行阐述。
(2)给出模型的训练时间、精确度和变动率指标范围。
3、描述怎样训练和评估上述2个SVM模型。
(1)给出模型的训练时间、精确度和变动率指标范围。
4、给出所有(C,gamma)参数组合序列,针对每个组合给出模型训练时间、精确度和变动率指标范围。讨论那个参数组合是最佳的。
5、给出训练后Naïve Bayes模型的ROC曲线和SVM模型的最佳ROC曲线,可以使用Weka软件的“Model Performance Chart”工具去实现,提供软件中“Classifier Performance Evaluator”合适的输出作为该工具的输入。
四、实验步骤及相关结果
1、任务1的具体实验步骤
(1)使用C程序生成抽样样本数据:
#include<stdio.h>
#include<string.h>
int main()
{
int i;
FILE *fp1;
FILE *fp2;
char msg[200];
fp1=fopen(".\\covtype.data\\covtype.txt","r");
fp2=fopen(".\\covtype.data\\project.txt","w");
srand(1);
while(!feof(fp1))
{
fgets(msg,200,fp1);
i=rand()%10;
if (i==1)
{
fprintf(fp2,"%s",msg); //every line of data has 10% probability to be written
}
}
return 1;
}
//**样本有58105个实例数据。**
(2)使用下面的格式表示格式、属性名、数据生成arff文件
“
@relation forest
@attribute Elevation numeric
@attribute Aspect numeric
@attribute Slope numeric
@attribute Horizontal_Distance_To_Hydrology numeric
@attribute Vertical_Distance_To_Hydrology numeric
@attribute Horizontal_Distance_To_Roadways numeric
@attribute Hillshade_9am numeric
@attribute Hillshade_Noon numeric
@attribute Hillshade_3pm numeric
@attribute Horizontal_Distance_To_Fire_Points numeric
@attribute Wilderness_Area numeric
@attribute w_a_1 numeric
@attribute w_a_2 numeric
@attribute w_a_3 numeric
@attribute w_a_4 numeric
@attribute Soil_Type_1 numeric
@attribute Soil_Type_2 numeric
@attribute Soil_Type_3 numeric
@attribute Soil_Type_4 numeric
@attribute Soil_Type_5 numeric
@attribute Soil_Type_6 numeric
@attribute Soil_Type_7 numeric
@attribute Soil_Type_8 numeric
@attribute Soil_Type_9 numeric
@attribute Soil_Type_10 numeric
@attribute Soil_Type_11 numeric
@attribute Soil_Type_12 numeric
@attribute Soil_Type_13 numeric
@attribute Soil_Type_14 numeric
@attribute Soil_Type_15 numeric
@attribute Soil_Type_16 numeric
@attribute Soil_Type_17 numeric
@attribute Soil_Type_18 numeric
@attribute Soil_Type_20 numeric
@attribute Soil_Type_21 numeric
@attribute Soil_Type_22 numeric
@attribute Soil_Type_23 numeric
@attribute Soil_Type_24 numeric
@attribute Soil_Type_25 numeric
@attribute Soil_Type_26 numeric
@attribute Soil_Type_27 numeric
@attribute Soil_Type_28 numeric
@attribute Soil_Type_29 numeric
@attribute Soil_Type_30 numeric
@attribute Soil_Type_31 numeric
@attribute Soil_Type_32 numeric
@attribute Soil_Type_33 numeric
@attribute Soil_Type_34 numeric
@attribute Soil_Type_35 numeric
@attribute Soil_Type_36 numeric
@attribute Soil_Type_37 numeric
@attribute Soil_Type_38 numeric
@attribute Soil_Type_39 numeric
@attribute Soil_Type_40 numeric
@attribute Cover_Type numeric
//the last numeric will change to “{0,1}” later, this kind is faster to preprocess
@data”
2、任务2的具体实验步骤
(1)使用Weka软件的探测器打开sample.arff文件。
(2)在预处理时,点击“edit”按钮,选择“cover_type”属性行,选择替代值,用值“0”代替原来的值“2”,用“1”代替原来的值“3,4,5,6,7”(保持原来的值“1”不变)。
打开文件后探测器显示界面如下:
打开文件后指示器界面如下:
替代操作界面:
替换了所有的值之后,将arff文件中的命令” @attribute Cover_Type numeric” 变成 ” @attribute Cover_Type {0,1}”。
3、任务3的具体实验步骤
(1)使用Weka的知识流插件,具体工作流布局如下图所示:
按照要求,参数设置:默认设置,交叉验证层数F=10
精确度: 40733 70.1024%(正确分类情况下)
ROC范围:0.759
历时过程及时间如下:
建立模型用了20秒。(各自运行环境不同时间将不同!)
模型的评价结果如上图所示。
数据森林覆盖图如下所示:
4、任务4的具体实验步骤
(1)带多项式核函数的SVM模型情况下,使用Weka的知识流插件,具体工作流布局如下图所示:
SMO 参数设置如下:
训练测试数据分割生成如下:
精确度:40958 74.1993 %(正确分类情况下)
ROC范围:0.744
历时过程及时间如下:
建立模型用了7秒。(各自运行环境不同时间将不同!)
模型的评价结果如下图所示:
(2)带RBF核函数的SVM模型情况下,使用Weka的知识流插件,具体工作流布局如下图所示:
SMO 参数设置如下:
精确度:37745 68.3786 %(正确分类情况下)
ROC范围:0.687
历时过程及时间如下:
建立模型用了9分钟41秒。(各自运行环境不同时间将不同!)
模型的评价结果如下图所示:
5、任务5的具体实验步骤
不同复杂度C下,参数gamma、精确度、ROC范围、耗时的表现结果如下:
根据上表结果做图分析,下图显示了综合展示了该模型在不同的复杂度C下面各自的性能表现,反应了精确度、gamma、复杂度参数C之间的关系。
分析:
从上图可以看出,随着复杂度C和gamma的增大,共同作用下使模型的精确度有所增加,但持续使得C和gamma的增大,对精确度的改善不明显。通过分析,最好的组合是当C=30,gamma=0.15的情况下,精确度达到77.17%,其ROC范围为0.773。.
Naïve bayes模型的ROC曲线如下图所示:
最好的参数组合情况下, ROC曲线表现最好的结果如下:
实验报告编辑人:魏林锋
数据挖掘实验报告K最临近分类算法学号311062202姓名汪文娟一数据源说明1数据理解选择第二包数据IrisDataSet共有15…
甘肃政法学院本科生实验报告四姓名贾燚学院计算机科学学院专业信息管理与信息系统班级10级信管班实验课程名称数据仓库与数据挖掘实验日期…
数据挖掘实验报告药物研究专业学号姓名时间20xx1208数据挖掘实验报告药物分析一实验目的1学习数据挖掘的理论知识理解数据挖掘的目…
计算机科学与技术系数据挖掘实验报告姓名学号授课教师完成时间1数据挖掘实验报告评分2目录1数据挖掘综述411什么是数据挖掘412数据…
数据挖掘实验报告一实验名称有线电视服务销售CampR树二实验目的1学习和了解数据挖掘的基础知识学会使用SPSSClementine…
甘肃政法学院本科生实验报告四姓名贾燚学院计算机科学学院专业信息管理与信息系统班级10级信管班实验课程名称数据仓库与数据挖掘实验日期…
论文报告案例分析院系信息学院专业统计班级10级统计3班学生姓名李健学号20xx210453任课教师刘洪伟20xx年01月17日课程…
计算机科学与技术系数据挖掘实验报告姓名学号授课教师完成时间1数据挖掘实验报告评分2目录1数据挖掘综述411什么是数据挖掘412数据…
数据挖掘实验报告K最临近分类算法学号311062202姓名汪文娟一数据源说明1数据理解选择第二包数据IrisDataSet共有15…
正如柏拉图所说:需要是发明之母。随着信息时代的步伐不断迈进,大量数据日积月累。我们迫切需要一种工具来满足从数据中发现知识的需求!而…