数据挖掘算法以及其实现--免费.doc

数据挖掘 实验报告实验一 分类技术及其应用实习要求： 基于线性回归模型拟合一个班学生的学习成绩，建立预测模型。数据可由自己建立100个学生的学习成绩。1） 算法思想：最小二乘法设经验方程是y=F(x)，方程中含有一些待定系数an，给出真实值(xi,yi)|i=1,2,.n,将这些x,y值 代入方程然后作差，可以描述误差：yi-F(xi)，为了考虑整体的误差，可以取平方和，之所以要平方是考虑到误差可正可负直接相加可以相互抵消，所以记 误差为：e=(yi-F(xi)2它是一个多元函数，有an共n个未知量，现在要求的是最小值。所以必然满足对各变量的偏导等于0，于是得到n个方程：de/da1=0de/da2=0.de/dan=0n个方程确定n个未知量为常量是理论上可以解出来的。用这种误差分析的方法进行回归方程的方法就是最小二乘法。线性回归如果经验方程是线性的，形如y=ax+b，就是线性回归。按上面的分析，误差函数为：e=(yi-axi-b)2各偏导为：de/da=2(yi-axi-b)xi=0de/db=-2(yi-axi-b)=0于是得到关于a,b的线性方程组：(xi2)a+(xi)b=yixi(xi)a+nb=yi设A=xi2,B=xi,C=yixi,D=yi，则方程化为：Aa+Bb=CBa+nb=D解出a,b得：a=(Cn-BD)/(An-BB)b=(AD-CB)/(An-BB)2） 编程实现算法C+程序：#include#includeusing namespace std;void main() double x,y,A=0.0,B=0.0,C=0.0,D=0.0,delta,a,b; int n,sno,avgstudy; cout请拟合输入样本数目n; for(int i=0;in;+i) cout请输入第i+1个学生学号sno; cout请输入学生上自习时间，按照每天小时计算x;cout请输入学生请输入平均成绩y; A+=x*x; B+=x; C+=x*y; D+=y; delta=A*n-B*B; a=(C*n-B*D)/delta); b=(A*D-C*B)/delta); couta=ab=bendl; if(fabs(delta)1e-10) cerrError!Divide by zeroendl; else couta=(C*n-B*D)/delta)endl b=(A*D-C*B)/delta)endl; cout输入您想预测的成绩，先输入平均日自习时间（小时）avgstudy; couta*avgstudy+b;3） 输出运算结果输入是将各个同学的上自习的时间 按照小时计算比如（4，85）（5，94），将成绩和上自习时间进行相应的线性回归，推导出相应的线型方程，以便今后对其他学生上自习以及成绩的估测。实习二 聚类技术及其应用实习题1 编程验证单连接凝聚聚类算法，实验数据可使用第五章表5.2 的数据进行。要求输出层次聚类过程中每一步的聚类结果。 实习题2 利用K-均值聚类算法对如下数据进行聚类，其中输入K=3，数据集为 2，4，10，12，3，20，30，11，25，23，34，22 。要求输出每个类及其中的元素。 1)算法基本思想的描述Given k, the k-means algorithm is implemented in four steps: Partition objects into k nonempty subsets Compute seed points as the centroids of the clusters of the current partition (the centroid is the center, i.e., mean point, of the cluster) Assign each object to the cluster with the nearest seed point Go back to Step 2, stop when no more new assignment2)编程实现算法/*引入库函数#include iostream.h#include math.h#include stdlib.h#include iomanip.h#include time.h#include fstream.h/*定义常量const int TRUE=1;const int FALSE=0;const int MarkovLengh=10000;const int MaxInnerLoop=10000;const int MaxOuterLoop=60;const double CO=0.1;const double DeclineRate=0.95;const long MAX=100000;const int AcceptRate=1;const double ForceDecline=0.9;/*定义全局变量int DataNum; /聚类样本数目int Dimension; /样本维数int K; /分类数double *DataSet; /指向浮点型的指针int HALT=0;int Row=3;/*/ 类GETDATA：设定全局变量，维数，样本数，和类别数等 * / 随机生成样本或手工输入样本的类 */*class GETDATApublic:GETDATA();void Display();void Initial();void Input();double FRand(double,double); double rand1,rand2; /随机数的高低值;GETDATA:GETDATA()int i,j;Dimension=2;DataNum=50;K=4;DataSet=new doubleDimension*DataNum;for(i=0;iDataNum;i+)for(j=0;jDimension;j+)DataSeti*Dimension+j=(double)rand()/(double)RAND_MAX)*100); /*显示当前待聚类的样本(维数，个数，类别数等)void GETDATA:Display()int i,j;cout 当前样本集如下:endl endl;for(i=0;iDataNum;i+)cout ;for(j=0;jDimension;j+) cout setw(8)DataSeti*Dimension+j;cout ;if(i+1)%Row=0)coutendl; coutendl endl;coutendl 以上实数样本集由计算机在-100之间随机产，其中：endl;coutendl 样本维数Dimension= Dimensionendl;cout 样本数 DataNum= DataNumendl;cout 类别数 K= Kendl;/*输入待聚类样本，包括维数，个数，类别数等void GETDATA:Input()char flag;int i,j;double s=0;coutendl 请依次输入: 维数 样本数目 类别数endl;coutendlDimension;coutendlDataNum;coutendlK;coutendl 随机生成数据输入R 人工输入按B: flag;if(flag=R|flag=r)cout 输入随机数生成范围(最小值和最大值):endlrand1;coutendlrand2;for(i=0;iDataNum;i+)for(j=0;jDimension;j+)DataSeti*Dimension+j=FRand(rand1,rand2);elseif(flag=H|flag=h)for(i=0;iDataNum;i+)coutendl 请输入第i+1 个样本的Dimension 个分量;for(j=0;jDataSeti*Dimension+j;else coutendl 非法数据！;/*初始化聚类样本void GETDATA:Initial()char ch;GETDATA:Display();coutendlch;while(!(ch=A|ch=a)&!(ch=B|ch=b)coutendlch;if(ch=A|ch=a) GETDATA:Input();double GETDATA:FRand(double rand1,double rand2)return rand1+(double)(double)rand()/(double)RAND_MAX)*(rand2-rand1);/*/ 类SSA: K-均值算法的实现 * / 功能：根据设定的K,DataNum,Dimension等聚类 */*class SAApublic:struct DataTypedouble *data;int father;double *uncle;struct ClusterTypedouble *center;int sonnum;SAA();void Initialize();void KMeans();void SA( );void DisPlay();void GetDataset(DataType *p1,double *p2,int datanum,int dim);void GetValue(double *str1,double *str2,int dim);int FindFather(double *p,int k);double SquareDistance(double *str1,double *str2,int dim);intCompare(double *p1,double *p2,int dim);void NewCenterPlus(ClusterType *p1,int t,double *p2,int dim);void NewCenterReduce(ClusterType *p1,int t,double *p2,int dim);double MaxFunc();void Generate(DataType *p1,ClusterType *c1);double Compare(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);void CopyStatus(DataType *p1,ClusterType *c1,DataType *p2,ClusterType *c2);int SecondFather(DataType *p,int t,int k);double AimFunction(DataType *q,ClusterType *c);double FRand(double ,double);void KMeans1();protected:double Temp;/double CO;/double DeclineRate;/int MarkovLengh;/int MaxInnerLoop;/int MaxOuterLoop;double AimFunc;DataType *DataMember, *KResult,*CurrentStatus,*NewStatus;ClusterType * ClusterMember,*NewCluster,*CurrentCluster; ; /end of class SAA/*建立构造函数，初始化保护成员SAA:SAA()int i;/DeclineRate=(double)0.9;/MarkovLengh=1000;/MaxInnerLoop=200;/MaxOuterLoop=10;/CO=1;DataMember=new DataTypeDataNum;ClusterMember=new ClusterTypeK;for(i=0;iDataNum;i+)DataMemberi.data=new doubleDimension;DataMemberi.uncle=new doubleK;for(i=0;iK;i+)ClusterMemberi.center=new doubleDimension;GetDataset(DataMember,DataSet,DataNum,Dimension);/endSAA/*初始化参数，及开始搜索状态void SAA:Initialize( )/K-均值聚类法建立退火聚类的初始状态/KMeans(); /*k-均值法进行聚类/*接口：数据，数量，维数，类别/逐点聚类方式void SAA:KMeans()int i,j,M=1;int pa,pb,fa;ClusterType *OldCluster;/初始化聚类中心OldCluster=new ClusterTypeK;for(i=0;iK;i+)/coutendli+1中心：;GetValue(ClusterMemberi.center,DataMemberi.data,Dimension);ClusterMemberi.sonnum=1;OldClusteri.center=new doubleDimension;GetValue(OldClusteri.center,ClusterMemberi.center,Dimension);for(i=0;iDataNum;i+) /coutendli+1: ClusterMember0.center0 ClusterMember1.center0 son: ClusterMember0.sonnum;for(j=0;jK;j+)DataMemberi.unclej=SquareDistance(DataMemberi.data,ClusterMemberj.center,Dimension);/cout i+1j+1: DataMemberi.unclej; /类中心ClusterMemberj.center0: DataMemberi.unclej=K)/coutendlpa 类样本数：ClusterMemberpa.sonnum;ClusterMemberpa.sonnum+=1;/coutendlpa 类样本数：ClusterMemberpa.sonnum;NewCenterPlus(ClusterMember,pa,DataMemberi.data,Dimension);/coutendli+1pa+1类 :ClusterMemberpa.center0;GetValue(OldClusterpa.center,ClusterMemberpa.center,Dimension); /开始聚类，直到聚类中心不再发生变化。逐个修改法while(!HALT)/一次聚类循环：.重新归类；.修改类中心for(i=0;iDataNum;i+) /coutendl;for(j=0;jK;j+)/cout D DataMemberi.data0 ClusterMemberj.center0 ;DataMemberi.unclej=SquareDistance(DataMemberi.data,ClusterMemberj.center,Dimension);/ coutDataMemberi.data0ClusterMember0l.center0 : DataMemberi.uncle0endl;/couti+1j+1 1)pa=DataMemberi.father;ClusterMemberpa.sonnum-=1;pb=DataMemberi.father=FindFather(DataMemberi.uncle,K);ClusterMemberpb.sonnum+=1;NewCenterReduce(ClusterMember,pa,DataMemberi.data,Dimension);NewCenterPlus(ClusterMember,pb,DataMemberi.data,Dimension);/*coutendl*M 次聚类：*; /聚一次类输出一次结果coutendlDataMemberi.data0 in pa+1 pb+1类: ;for(t=0;tK;t+)coutendl 第t+1 类中心: ClusterMembert.center0 样本个数：ClusterMembert.sonnum;DisPlay();M=M+1;*/endfor /判断聚类是否完成，HALT=1,停止聚类HALT=0;for(j=0;jK;j+)if(Compare(OldClusterj.center,ClusterMemberj.center,Dimension)break;if(j=K)HALT=1;for(j=0;jK;j+)GetValue(OldClusterj.center,ClusterMemberj.center,Dimension);/endwhile/end of KMeans/批聚类方式void SAA:KMeans1()int i,j,M=1;int pa,pb,fa;ClusterType *OldCluster;/初始化聚类中心OldCluster=new ClusterTypeK;for(i=0;iK;i+)OldClusteri.center=new doubleDimension;for(j=0;jK;j+)GetValue(OldClusterj.center,ClusterMemberj.center,Dimension);/开始聚类，直到聚类中心不再发生变化。逐个修改法while(!HALT)/一次聚类循环：.重新归类；.修改类中心for(i=0;iDataNum;i+) for(j=0;j1)pa=DataMemberi.father;ClusterMemberpa.sonnum-=1;pb=DataMemberi.father=FindFather(DataMemberi.uncle,K);ClusterMemberpb.sonnum+=1;NewCenterReduce(ClusterMember,pa,DataMemberi.data,Dimension);NewCenterPlus(ClusterMember,pb,DataMemberi.data,Dimension);/endfor /判断聚类是否完成，HALT=1,停止聚类HALT=0;for(j=0;jK;j+)if(Compare(OldClusterj.center,ClusterMemberj.center,Dimension)break;if(j=K)HALT=1;for(j=0;jK;j+)GetValue(OldClusterj.center,ClusterMemberj.center,Dimension);/endwhile/几个经常需要调用的小函数void SAA:NewCenterPlus(ClusterType *p1,int t,double *p2,int dim)int i;for(i=0;idim;i+)p1t.centeri=p1t.centeri+(p2i-p1t.centeri)/(p1t.sonnum);void SAA:NewCenterReduce(ClusterType *p1,int t,double *p2,int dim)int i;for(i=0;idim;i+)p1t.centeri=p1t.centeri+(p1t.centeri-p2i)/(p1t.sonnum);void SAA:GetDataset(DataType *p1,double *p2,int datanum,int dim)int i,j;for(i=0;idatanum;i+)for(j=0;jdim;j+)p1i.dataj=p2i*dim+j;void SAA:GetValue(double *str1,double *str2,int dim)int i;for(i=0;idim;i+)str1i=str2i;int SAA:FindFather(double *p,int k)int i,N=0;double min=30000;for(i=0;ik;i+)if(pimin)min=pi;N=i;return N;double SAA:SquareDistance(double *str1,double *str2,int dim)double dis=0;int i;for(i=0;idim;i+)dis=dis+(double)(str1i-str2i)*(str1i-str2i);return dis;intSAA:Compare(double *p1,double *p2,int dim)int i;for(i=0;idim;i+)if(p1i!=p2i)return 1;return 0;double SAA:FRand(double a,double b)return a+(double)(double)rand()/(double)RAND_MAX)*(b-a);void SAA:DisPlay()int i,N,j,t;ofstream result(聚类过程结果显示.txt,ios:ate);for(i=0;iK;i+)N=0;coutendlendl* 第i+1 类样本:*endl;resultendlendl* 第i+1 类样本:*endl;for(j=0;jDataNum;j+)if(DataMemberj.father=i)cout ;for(t=0;tDimension;t+)cout setw(5)DataMemberj.datat;cout ;if(N+1)%Row=0)coutendl;result ;for(t=0;tDimension;t+)result setw(5)DataMemberj.datat;result ;if(N+1)%Row=0)resultendl;N=N+1;/end forcoutendlendl 聚类结果，总体误差准则函数：AimFunction(DataMember,ClusterMember)endl;resultendl 聚类结果，总体误差准则函数：AimFunction(DataMember,ClusterMember)endl; result.close();/end of Displaydouble SAA:AimFunction(DataType *q,ClusterType *c)int i,j;double *p;p=new doubleK;for(i=0;iK;i+)pi=0;for(i=0;iK;i+)for(j=0;jDataNum;j+)if(qj.father=i)pi=pi+SquareDistance(ci.center,qj.data,Dimension);AimFunc=0;for(i=0;iK;i+)AimFunc=AimFunc+pi;return AimFunc;/*/ 主函数入口 * /*void main()/用户输入数据srand(unsigned)time(NULL);GETDATA getdata;getdata.Initial();ofstream file(聚类过程结果显示.txt,ios:trunc); /聚类结果存入“聚类结果显示.txt”文件中/k-均值聚类方法聚类SAA saa; /*此行不可与上行互换。saa.KMeans(); /逐个样本聚类/saa.KMeans1(); /批处理方式聚类，可以比较saa.KMeans()的区别coutendl*K-均值聚类结果：*;fileendl*K-均值聚类结果：*endl;file.close();saa.DisPlay(); coutendl 程序运行结束！endl;3)输出运算结果实习三 关联规则挖掘及其应用实习题：Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。它将关联规则挖掘算法的设计分解为两个子问题：（1） 找到所有支持度大于最小支持度的项集，这些项集称被为频繁项集（Frequent Itemset）。（2） 使用第一步产生的频繁集产生期望的规则。在图书馆管理系统中积累了大量的读者借还书的历史记录，基于Apriori算法挖掘最大频繁项目集，由此产生关联规则。数据格式可参阅文献参考文献：彭仪普,熊拥军: 关联挖掘在文献借阅历史数据分析中的应用.情报杂志. 2005年第8期1） 算法基本思想的描述首先产生频繁1-项集L1，然后是频繁2-项集L2，直到有某个r值使得Lr为空，这时算法停止。这里在第k次循环中，过程先产生候选k-项集的集合Ck，Ck中的每一个项集是对两个只有一个项不同的属于Lk-1的频集做一个(k-2)-连接来 产生的。Ck中的项集是用来产生频集的候选集，最后的频集Lk必须是Ck的一个子集。Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这 里的验证过程是算法性能的一个瓶颈。为了生成所有频集，使用了递推的方法。其核心思想简要描述如下：(1)L1 = large 1-itemsets;(2)for (k=2; Lk-1¹F; k+) do begin(3)Ck=apriori-gen(Lk-1);/新的候选集(4)for all transactions tÎD do begin(5)Ct=subset(Ck,t);/事务t中包含的候选集(6)for all candidates cÎ Ctdo(7)c.count+;(8)end(9)Lk=cÎ Ck |c.count³minsup(10)end(11)Answer=kLk;1.Find all frequent itemsets: By definition, each of these itemsets will occur at least as frequently as a predetermined minimum support count, min sup2. Generate strong association rules from the frequent itemsets: By definition, these rules must satisfy minimum support and minimum confidence3. Apriori pruning principle: If there is any itemset which is infrequent, its superset should not be generated/tested!Method: generate length (k+1) candidate itemsets from two length k frequent itemsets which have K-1 kinds same itemsets, and test the candidates against DB2） 编程实现算法1 Item.h 源文件/*- File : Item.h Contents : itemset management Author : Bart Goethals Update : 4/4/2003 -*/#include using namespace std;class Itempublic:Item(int i) : id(i), support(0), children(0) Item(const Item &i) : id(i.id), support(i.support), children(i.children) Item()int getId() const return id;int Increment(int inc = 1) const return support+=inc;set *makeChildren() const;int deleteChildren() const;int getSupport() const return support;set *getChildren() const return children;bool operator(const Item &i) constreturn id i.id;private:const int id;mutable int support;mutable set *children;2. AprioriRules.h 源文件class Itemset public: Itemset(int l) : length(l) t = new intl; Itemset(const Itemset &is) : length(is.length), support(is.support) t = new intlength; for(int i=0;ilength;i+) ti = is.ti; Itemset()delete t; int length; int *t; int support;class AprioriRules public: AprioriRules(); Apr