数据挖掘课程分析

数据仓库与数据挖掘期末作业作业题目 学院：_ 专 业: 姓 名:凝聚的层次聚类算法的实现（java数学与系统科学学院信息与计算科学班级：12-1张娜号： 12010513332015年12月12日山东科技大学基于数据挖掘的课程相关性分析-、数据挖掘技术简介1.1数据挖掘的概念数据挖掘从广义上讲是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有 趣知识的过程。1.2数据挖掘的分析方法对于不同的问题类型以及数据的规模和类型，从功能上可以将数据挖掘分析方法分为 以下4种：(1) 关联分析:顾名思义，它的目的就是为了挖掘出隐藏在数据间的相互关系。(2) 序列模式分析:序列模式分析和关联分析法相似，其目的也是为了挖掘出数据之间 的联系，但序列模式分析的侧重点在于分析数据间的前后(因果)关系。(3) 分类分析:分析时首先为每一个记录赋予一个标记(即一组具有不同特征的类别)， 即按标记分类记录，然后检查这些标定的记录，描述出这些记录的特征。(4) 聚类分析:与分类分析法不同，聚类分析法的输入集是一组未标定的记录，其目的 是根据一定的规则，合理地划分记录集合，并用显式或隐式的方法描述不同的类别。针对本年级的学生成绩的数据结构，分析课程相关性，采用关联规则的挖掘方法是最 为直接有效的。二、联规则挖掘方法2.1关联规则的形式定义设I = T i2, i3-in是项的集合。设任务相关的数据集D是事务数据库的集合， 其中每个事务T是项目的集合，使得T属于I。每一个事务有一个表示符，称作TID。设 A是一个项目集，事务T包含A当且仅当A属于T。关联规则就是一个形如A=B的逻 辑蕴涵式，其中A属于I,B属于I且A HB为非空集。关联规则A=B在事务集D中 成立，其一需具有支持度S，其中S是D中事务包含A UB (即A和B二者)的数量， 即概率P(AUB)。表述为：suppor t(A = B) = P(AU B) = S支持度定义了项目在整个数据库中所占的比例，置信度定义了发现关联规则的强度。根 据上面的论述，关联规则的发现任务或问题可以定义为:给定一个事务数据库D，求出所有 满足最小支持度Smin的关联规则。2.2原始数据处理由于学生成绩的评分标准并不统一，有5级制有百分制，所以我们先将成绩数据处理一 下，用5级制来表示学生的成绩。同时我们给定一个最低成绩等级的阀值level,因为课程 的相关性分析，我们是根据同一学生几门课程同时优秀来得出课程之间的关系的，所以我们 应该把成绩优秀的课程挑出来，即在阀值level之上的认为是优秀的。这样我们就将原始的成绩表，转化为了一个二维矩阵，行数就是学生数，而每一行就是 每一个学生成绩在阀值level之上的课程编号，这里课程的编号可以简单用0, 1, 2, 3. 表示。通过这样处理过的成绩表，数据量就减少了，有利于提高效率。2.3 Apriori算法分析与设计Apriori算法是发现关联规则领域的经典算法，它使用一种称作逐层搜索的迭代方法。 首先，找出频繁1项集的集合，记作LI。L1用于找频繁2项集的集合L2 ,而L2用于找 L3，如此下去，直到不能找到频繁k项集。可以看出找每个Lk需要一次数据库扫描。这 也体现出Apriori的在效率上的一些问题，当数据库或k太大时，算法的时耗太大，效 率太低几乎无法完成，特别是频繁集很长或最小支持度非常小时，例如，当有10个频繁 1项集时，Apriori算法就会产生多于10个的候选2项集。因此算法的可扩展性不强;另 外，算法有时会推出一些虚假规则，认为很难对这些规则作出区分。为了提高算法的效率， 我们采用临时表的方法改进算法，这种方法可以利用以下两个事实：(1) 对于已知规模的事务数据库D，任意一个项集I的出现支持度与规模小于I的事 务无关。所以在第i次扫描数据库D时，可以删除规模小于I的事务记录。(2) k候选项集中不包含任何(k - 1)项集的项集一定不是频繁项集，因此k次扫描 时可以将这样的事务记录立即删除，从而减少了下次需要扫描的记录数。用临时表来完成频繁项集的选择，首先把(k - 1)项集中的第一个项集添加进临时表 中;然后把最后一项不同的其它项集添加进临时表，生成k项集，计算其支持度，若支持 度大于最小支持度，则生成该频繁项并保存，否则删除。依此循环，直至生成所有的频繁 项。实现如下： 算法:Apriori使用根据候选生成的逐层迭代找出频繁项集。第一步：先得到一项频繁项集L1。1、遍历成绩等级数据，统计所有课程的标号数目，存入数组a中。2、将未达到level的项去掉，更新数组a。第二步：根据已有的k-1项频繁项集a,得到k项频繁项集b。1、分别用数组a的第i(i=1,，na-1)行与a的第j( j=i,.,na)行进行比较，如 果两行不相同的元素个数为k,就将他作为候选项并返回，否则返回错误。2、统计1中返回的候选项的支持度，如果满足最小支持度计数阀值sup返回他的支持 度计数，否则返回错误。3、用满足1、2的候选项对比之前已经得到的k项候选集c,如果没有重复的便将其添 加到k项候选集c中，否则不添加。4、如果j没到na, j+1-j ；否则将临时候选集c添加到频繁项集b中，i+1-i;返回 第二步的第一小步，继续循环。通过上述算法，最后得到了在成绩等级阀值level条件下满足支持度计数sup的课程号 的频繁项集，以及相应的支持度计数。由于课程数量较多，为了更好地分析结果，我们将课程号转化为课程名，并将其写入记 事本文件中，方便读取和分析。存储格式为，每一行就是一个频繁项，最后是该项的频繁项 计数。三、主要算法的代码实现3.1初始数据处理int *GetData(int level=3)/返回值data数组，每一行表示一个学生，第一列记录此学生达到level的课程 数量，后几列表示达到level的课程号。int*score;score二File2Scoer();int *data=(int*)malloc(sizeof(int*)*StudentNumber); for(int i=0;iStudentNumber;i+)datai = (int*)malloc(sizeof(int)*(ClassNumber+l);for(int i=0;iStudentNumber;i+)da tai0=0;int seat=l;for(int j=O;jClassNumber;j+)if(scoreij=level)dat aisea t+二j;da tai0+;FreeSet(score,StudentNumber);return data;3.2 Apriori算法实现int * GetFrequentSet_l(int*data,int & class_N ,int level=3,int sup=3) int*set,aClassNumber,bClassNumber2;class_N=0;for(int i=O;iClassNumber;i+)ai=O;for(int i=0;iStudentNumber;i+)for(int j=0;jdatai0;j+)ada taij+l+;for(int i=O;iClassNumber;i+)if(ai=level)bclass_N0=i;bclass_N1=ai;class_N+;set=(int*)malloc(sizeof(int*)*class_N);int numb=0;for(int i=O;iclass_N;i+)if(bi1=sup)setnumb二(int*)malloc(sizeof (int)*2);setn umb0=bi0;setn umb+l=bil;class_N=numb; return set;void Candida te(i nt *a,i nt na,i nt*&b,i nt&n b,i nt nK,i nt sup,i nt *da ta)函数功能:根据k项的频繁项集，得到k+1项的频繁项集，用b带回新得到的满足支持 度sup的频繁项集。输入：a是k项频繁项集，是一个二维数组。Na是a的行数。Nk是上面的k,表示得到了 nk项的频繁项集，求nk+1项的频繁项集。Sup：最低支持度水平。Data：处理过的数据，已经由int *GetData(int)函数处理。输出：b：用于带回k+1项频繁项集的二维数组；Nb：带回b的行数int i,j,k;int*c=(int*)malloc(sizeof(int*)*na),nc=0;nb=0;for(i=0;inaT;i+)nc=0;for(j=i+1;jna;j+)int tempClassNumber+1;if(compare(ai,aj,nk, temp)/比较这两项是否可以构成一条新的 频繁项if(Support(data, temp,nk+1,sup)/判断新组成的频繁项是否满 足支持度的要求if(!lsln(c, temp,nc,nk+1)/判断temp是不是已经写进频繁 项集了cnc = (int*)malloc(sizeof(int)*(nk+2);/前 k+1 是频 繁向，最后一项是支持度for(k=0;k0)b=( int*)malloc(sizeof(int*)*(nc+nb); else break;else if(nc0)b=( int *)realloc(b,sizeof (int *)*(nc+nb);for(j=0;jnc;j+) if(!lsln(b,cj,nb,nk+1)bnb+=cj;else free(cj);free(c);bool compare(i nt *a,i nt *b,i nt n,int*t emp)/比较a和b是否相同，若不同元素只有n+1个，则将这n+1个元素用temp带回, 否则返回值为假int i,j,nt emp,d ,t ag;for(i=0;in;i+)tempi=ai;ntemp=0;for(i=0;in;i+)tag=0;for(j=0;jn;j+)if(bi!= tempj)if(ntemp=1)return false;else tag=1;break;if(ntemp=0&tag=0)d=bi;ntemp+;else if(ntemp=l&tag=0) return false;for(i=0;in;i+)if(di-1;j+)tempj+1=tempj;tempi=d;return true;bool Suppo rt(int *da ta,i nt *a,i nt na,i nt sup)/根据data求这个na项的频繁项的支持度，并判断是否达到要求。int i,j,k ,tag,t agsup;ana=0;for(i=0;iStudentNumber;i+)tagsup=0;for(k=0;kna;k+)tag=0;for(j=1;j=sup)return true;return false;bool IsIn (int *a,i nt *b,i nt na,i nt nb)/检查数组b是不是在二维数组a的某一行中 int i,j;for(i=0;ina;i+)for(j=0;jnb;j+) if(aij!=bj)break;else if(j=nb-1)return true;return false;3.3保存实验结果void Fpri ntfF ile(i nt *a,i nt na,i nt nk,char*fileName)/将n频繁项集写入文件中FILE *out;if (out 二 fopen(fileName, wt) = NULL)fprintf(stderr, Cannot open output file.n); return;int i,j;,nk,fileName);,nk);printf (正在将%d项频繁项集写入文件%s中，请稍后.n fprintf(out,%d 项频繁项集n,nk);if(na=0)fprintf(out,没有满足支持度的%d项频繁项集n for(i=0;ina;i+)for(j=0;j m .llllli-,/-,/-,-,/-, 1 1 1 1 1 1 1111111 1 1111111 1 111 矽间一mwfwl空WiWi数数数数数数数数数数数数数数数数数数数数数数数数数第一项：空间解析几何3,数学分析（1） 5,思修2,体育（1） 2,数值分析实验1, 选修（1） 3,选修（2） 3,支持度计数为：12。第二项：空间解析几何3，数学分析（1） 5,思修2,数学分析（3）4,数值分析实验 1,选修（1） 3,选修（2） 3,支持度计数为：12可以看出上面两条记录中的这几门课程之间的相关性支持度计数都为12,总人数共33 人，所以支持度为0.36。另一项：数学分析（1） 5,思修2,体育（1） 2,数值分析实验1,体育（4） 2,选修 （1） 3，选修（2） 3,支持度计数为：14。可以看出这几门课程之间的相关性支持度计数为14,所以支持度为0.42。22222222222222 囈寸康曝曝康康曝曝康康曝曝康康曝L i咼马马马马马马马马马马马马马马-三 11修修修修修修修修修修修修修修修皿222222222222222验实斤-m m協協協協協協協人41111111分ml实实实实实实实宀 值育育育育育育育理理理理理理理阿11 11 11 11 11 11 Qi2 2 2 2 2 2 2/k/k/k/k/k/k/k /课程-设二课程设:支支支支支支支计支支支支支计支亠5 5用.5VLk vll VLk V 度度度度度度度2应11 曹2)验用2应1度度度度度1)2)验2(实2 3软理实2 3软理实一 4)验薯4)黑原薯4)黑原析八 实实八G实八餐实分实八观 育理理值意于计据理值意于计曙宀5 5 5 5 5 5 5 L度宀支持度为：252727272627支持度为：2627上面是支持度计数不低于25的部分结果截图，4项的频繁项集。第一项：高等代数（1）4,思修2,数值分析实验1,体育（4） 2,支持度为：25。说明以上这几门课程的相关性支持度为：0.75。但是我们并不能认为高等代数和体育之 间就一定有很强的相关性，并不能说高等代数学好了，体育就一定可以学的不错，我们知道 他们之间并没有什么必然的联系，所以这样一条频繁项，对我们是没有用的。然而这样的结果，却是大量的，让我们很难发现有用的规则。通过上面的结果可以看出，选修课对于结果的影响是巨大的，有好多频繁项中都包含好 几门选修课，所以频繁项集特别多，而且频繁项中课程数目也比较多。4.2去掉选修课程为了得到更好的实验结论，我们要去掉一部分选修课程，有思修、毛概、以及几门学校 的公选课程，然后重新运行程序。1、运行参数设置最小支持度计数为15,，运行结果如下：Candidate2.txt -记事本几几几de实实3 3 3 集1)1)2)2)3)验验5 5 4 4 41 TI度度度度度度度度度一 1411244 - 、1X 支支支支支支支支支计 二二二二一设 - -a 二二二二一课 用5 1 1 4 11 应 1)弭救3)救救与 实3实I实实3理 八务柔分柔八aaz头库 学團于愿辛据度度度度度度度度度1度111111112持刘牛旧耦E梧式查巷帮助H0.4848480.4848480.4545450. 5151510. 5151510. 454545|0.4545450.4545450.636364支持度：0. 454545满足支持度计数阀值15的频繁项对多有两门课程的频繁项，并且一共只有10条频繁项 记录。通过这几项可以得出这几门数学课程之间有一定的相关性，例如：第九条中数值分析 实验和数学实验的支持度为0.636，已经到了比较高的水平。我们在学习中也知道，这两门课程的学习，都需要上机操作，都需要用数学软件编程序, 同时他们也都属于数学课程，而且都为实验课程，通过以上分析，这两门课程之间有很多的 相同性，然而通过数据挖掘的方法分析出的相关性也说明了，这两门课程之间有着很强的相 关性。2、运行参数设置最小支持度计数为13,运行结果如下:J Candidate3.txt -记事本3939393939394242424242423939394242423939393939390. 3939390. 3939390. 3939390. 4545450. 424242八93度93度93八93持93持935.3支.3支 3牛|7 : 3 : 3 : 一度度度度矗度1度1度 支支支支支支支支支支, 0* , J-|-i, J-|i 九 ,4434333335413隹3隹311111111111 1 寺 1寺 1计4 殳 宜救3)救宜 蠢 实3实CO 1实3实3 3实课3理 分实分实八务实分实实分笛头库实库实、厂厂厂厂厂厂厂厂厂厂靳计-计一计J-_一恃 _L 痔 、” 1+T- 支支支支支支支支支支计交计交-鼾_-调-m 二3理CO554 44444 444411 11 1I 一| 一| 1 )1 )3)验2)2)2)3)3)验3)3)3)3)验验验 实ml实H实实实 数数 数数数数咼亠咼亠咼数数数数数数数数数数5 5 5 5 5 5 4 4 4 4 4 4 43 3 3 3J-jzp l-jzp, .I? .I? .I? .I? = = k- dn 1I TI TI 1I TI TIllJll9.llJ.Jll9._-:_. nu nu nu nu数数数数数析 輝解解解解八费SSS分 3J空空空空数数数数数数咼亠咼亠咼亠咼亠咼亠咼F这是所有的三项频繁项集，其中支持度最高的一条为：数学分析（）5,数值分析实验 1,数学实验3,支持度计数：15,支持度：0.454545。这里同样包含了刚刚分析得到的结论, 另外加入了一门数学分析，支持度还是比较高的。j Candidate4.txt 记事本文件旧编辑E）梧式Q） MWCV）帮助（H）数学分析（1）5数值分析实验1数学实验3支持度计数：13,支持度：0. 393939这是支持度计数阀值为13时，四项的频繁项集，只剩下了一条记录。该记录中除了刚 才分析的三门课程，有添加了一门空间解析几何，也是一门数学课程。说明学好数学的基础课程，对于学好数学的实验课程是非常重要的，只有具备了一定的 理论基础才能更好地进行数学试验，取得优异的成绩。面对以上的实验结果，我们可将其看成一条条的规则。即：前面的几门课程= 最后一 门课程。例如：支持度计数：14,支持度：0.42424支持度计数：14,支持度：0.42424支持度计数：13,支持度：0.39393（空间解析几何3,数学分析（1）5）=数值分析实验1（空间解析几何3,数学分析（1）5）=数学实验3（数学分析（3）4,数值分析实验1）=数学实验3（空间解析几何3,数学分析（1） 5,数值分析实验1）=数学实验3支持度计数：13,支持度：0.39393