1、實驗一 分類技術(shù)及其應(yīng)用實習(xí)要求： 基于線性回歸模型擬合一個班學(xué)生的學(xué)習(xí)成績，建立預(yù)測模型。數(shù)據(jù)可由自己建立100個學(xué)生的學(xué)習(xí)成績。1） 算法思想：最小二乘法設(shè)經(jīng)驗方程是y=F(x)，方程中含有一些待定系數(shù)an，給出真實值(xi,yi)|i=1,2,.n,將這些x,y值 代入方程然后作差，可以描述誤差：yi-F(xi)，為了考慮整體的誤差，可以取平方和，之所以要平方是考慮到誤差可正可負直接相加可以相互抵消，所以記 誤差為：e=(yi-F(xi)2它是一個多元函數(shù)，有an共n個未知量，現(xiàn)在要求的是最小值。所以必然滿足對各變量的偏導(dǎo)等于0，于是得到n個方程：de/da1=0de/da2=0.de/

2、dan=0n個方程確定n個未知量為常量是理論上可以解出來的。用這種誤差分析的方法進行回歸方程的方法就是最小二乘法。線性回歸如果經(jīng)驗方程是線性的，形如y=ax+b，就是線性回歸。按上面的分析，誤差函數(shù)為：e=(yi-axi-b)2各偏導(dǎo)為：de/da=2(yi-axi-b)xi=0de/db=-2(yi-axi-b)=0于是得到關(guān)于a,b的線性方程組：(xi2)a+(xi)b=yixi(xi)a+nb=yi設(shè)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） 編程實現(xiàn)算法C+

3、程序：#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請擬合輸入樣本數(shù)目n; for(int i=0;in;+i) cout請輸入第i+1個學(xué)生學(xué)號sno; cout請輸入學(xué)生上自習(xí)時間，按照每天小時計算x;cout請輸入學(xué)生請輸入平均成績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);

4、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輸入您想預(yù)測的成績，先輸入平均日自習(xí)時間（小時）avgstudy; couta*avgstudy+b;3） 輸出運算結(jié)果輸入是將各個同學(xué)的上自習(xí)的時間 按照小時計算比如（4，85）（5，94），將成績和上自習(xí)時間進行相應(yīng)的線性回歸，推導(dǎo)出相應(yīng)的線型方程，以便今后對其他學(xué)生上自習(xí)以及成績的估測。實習(xí)二 聚類技術(shù)及其應(yīng)用實習(xí)題1 編程驗證單連接凝聚

5、聚類算法，實驗數(shù)據(jù)可使用第五章表5.2 的數(shù)據(jù)進行。要求輸出層次聚類過程中每一步的聚類結(jié)果。 實習(xí)題2 利用K-均值聚類算法對如下數(shù)據(jù)進行聚類，其中輸入K=3，數(shù)據(jù)集為 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

6、 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)編程實現(xiàn)算法/*引入庫函數(shù)#include iostream.h#include math.h#include stdlib.h#include iomanip.h#include time.

7、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=;const int AcceptRate=1;const double ForceDecline=0.9;/*定義全局變量int DataNum; /聚類樣本數(shù)目int Dimens

8、ion; /樣本維數(shù)int K; /分類數(shù)double *DataSet; /指向浮點型的指針int HALT=0;int Row=3;/*/ 類GETDATA：設(shè)定全局變量，維數(shù)，樣本數(shù)，和類別數(shù)等 * / 隨機生成樣本或手工輸入樣本的類 */*class GETDATApublic:GETDATA();void Display();void Initial();void Input();double FRand(double,double); double rand1,rand2; /隨機數(shù)的高低值;GETDATA:GETDATA()int i,j;Dimension=2;DataNum=

9、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); /*顯示當(dāng)前待聚類的樣本(維數(shù)，個數(shù)，類別數(shù)等)void GETDATA:Display()int i,j;cout 當(dāng)前樣本集如下:endl endl;for(i=0;iDataNum;i+)cout ;for(j=0;jDimension;j+) cout setw(8)DataSeti*Dimensio

10、n+j;cout ;if(i+1)%Row=0)coutendl; coutendl endl;coutendl 以上實數(shù)樣本集由計算機在-100之間隨機產(chǎn)，其中：endl;coutendl 樣本維數(shù)Dimension= Dimensionendl;cout 樣本數(shù) DataNum= DataNumendl;cout 類別數(shù) K= Kendl;/*輸入待聚類樣本，包括維數(shù)，個數(shù)，類別數(shù)等void GETDATA:Input()char flag;int i,j;double s=0;coutendl 請依次輸入: 維數(shù) 樣本數(shù)目 類別數(shù)endl;coutendlDimension;couten

11、dlDataNum;coutendlK;coutendl 隨機生成數(shù)據(jù)輸入R 人工輸入按B: flag;if(flag=R|flag=r)cout 輸入隨機數(shù)生成范圍(最小值和最大值):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*Dimensi

12、on+j;else coutendl 非法數(shù)據(jù)！;/*初始化聚類樣本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-均值算法的實現(xiàn)

13、* / 功能：根據(jù)設(shè)定的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 *st

14、r1,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();voi

15、d 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 ,

16、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/*建立構(gòu)造函數(shù)，初始化保護成員SAA:SAA

17、()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;Get

18、Dataset(DataMember,DataSet,DataNum,Dimension);/endSAA/*初始化參數(shù)，及開始搜索狀態(tài)void SAA:Initialize( )/K-均值聚類法建立退火聚類的初始狀態(tài)/KMeans(); /*k-均值法進行聚類/*接口：數(shù)據(jù)，數(shù)量，維數(shù)，類別/逐點聚類方式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(Clust

19、erMemberi.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+)DataMembe

20、ri.unclej=SquareDistance(DataMemberi.data,ClusterMemberj.center,Dimension);/cout i+1j+1: DataMemberi.unclej; /類中心ClusterMemberj.center0: DataMemberi.unclej=K)/coutendlpa 類樣本數(shù)：ClusterMemberpa.sonnum;ClusterMemberpa.sonnum+=1;/coutendlpa 類樣本數(shù)：ClusterMemberpa.sonnum;NewCenterPlus(ClusterMember,pa,DataM

21、emberi.data,Dimension);/coutendli+1pa+1類 :ClusterMemberpa.center0;GetValue(OldClusterpa.center,ClusterMemberpa.center,Dimension); /開始聚類，直到聚類中心不再發(fā)生變化。逐個修改法while(!HALT)/一次聚類循環(huán)：.重新歸類；.修改類中心for(i=0;iDataNum;i+) /coutendl;for(j=0;jK;j+)/cout D DataMemberi.data0 ClusterMemberj.center0 ;DataMemberi.unclej=

22、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(Clust

23、erMember,pa,DataMemberi.data,Dimension);NewCenterPlus(ClusterMember,pb,DataMemberi.data,Dimension);/*coutendl*M 次聚類：*; /聚一次類輸出一次結(jié)果coutendlDataMemberi.data0 in pa+1 pb+1類: ;for(t=0;tK;t+)coutendl 第t+1 類中心: ClusterMembert.center0 樣本個數(shù)：ClusterMembert.sonnum;DisPlay();M=M+1;*/endfor /判斷聚類是否完成，HALT=1,停止聚

24、類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 Cl

25、usterTypeK;for(i=0;iK;i+)OldClusteri.center=new doubleDimension;for(j=0;jK;j+)GetValue(OldClusterj.center,ClusterMemberj.center,Dimension);/開始聚類，直到聚類中心不再發(fā)生變化。逐個修改法while(!HALT)/一次聚類循環(huán)：.重新歸類；.修改類中心for(i=0;iDataNum;i+) for(j=0;j1)pa=DataMemberi.father;ClusterMemberpa.sonnum-=1;pb=DataMemberi.father=Fin

26、dFather(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)

27、HALT=1;for(j=0;jK;j+)GetValue(OldClusterj.center,ClusterMemberj.center,Dimension);/endwhile/幾個經(jīng)常需要調(diào)用的小函數(shù)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 *

28、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=str2

29、i;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 di

30、m)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(聚類過程結(jié)果顯示.txt,ios:ate);for(i=0;iK;i+)N=0;coutendlendl* 第i+1 類樣本:*endl;resultendlendl* 第i+1 類樣本:*endl;for(j=0;j

31、DataNum;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 聚類結(jié)果，總體誤差準則函數(shù)：AimFunction(DataMember,ClusterMember)endl;

32、resultendl 聚類結(jié)果，總體誤差準則函數(shù)：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);Ai

33、mFunc=0;for(i=0;iK;i+)AimFunc=AimFunc+pi;return AimFunc;/*/ 主函數(shù)入口 * /*void main()/用戶輸入數(shù)據(jù)srand(unsigned)time(NULL);GETDATA getdata;getdata.Initial();ofstream file(聚類過程結(jié)果顯示.txt,ios:trunc); /聚類結(jié)果存入“聚類結(jié)果顯示.txt”文件中/k-均值聚類方法聚類SAA saa; /*此行不可與上行互換。saa.KMeans(); /逐個樣本聚類/saa.KMeans1(); /批處理方式聚類，可以比較saa.KMean

34、s()的區(qū)別coutendl*K-均值聚類結(jié)果：*;fileendl*K-均值聚類結(jié)果：*endl;file.close();saa.DisPlay(); coutendl 程序運行結(jié)束！endl;3)輸出運算結(jié)果實習(xí)三 關(guān)聯(lián)規(guī)則挖掘及其應(yīng)用實習(xí)題：Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。它將關(guān)聯(lián)規(guī)則挖掘算法的設(shè)計分解為兩個子問題：（1） 找到所有支持度大于最小支持度的項集，這些項集稱被為頻繁項集（Frequent Itemset）。（2） 使用第一步產(chǎn)生的頻繁集產(chǎn)生期望的規(guī)則。在圖書館管理系統(tǒng)中積累了大量的讀者借還書的歷史記錄，基于Apriori算法挖掘最大頻繁項目

35、集，由此產(chǎn)生關(guān)聯(lián)規(guī)則。數(shù)據(jù)格式可參閱文獻參考文獻：彭儀普,熊擁軍: 關(guān)聯(lián)挖掘在文獻借閱歷史數(shù)據(jù)分析中的應(yīng)用.情報雜志. 2005年第8期1） 算法基本思想的描述首先產(chǎn)生頻繁1-項集L1，然后是頻繁2-項集L2，直到有某個r值使得Lr為空，這時算法停止。這里在第k次循環(huán)中，過程先產(chǎn)生候選k-項集的集合Ck，Ck中的每一個項集是對兩個只有一個項不同的屬于Lk-1的頻集做一個(k-2)-連接來 產(chǎn)生的。Ck中的項集是用來產(chǎn)生頻集的候選集，最后的頻集Lk必須是Ck的一個子集。Ck中的每個元素需在交易數(shù)據(jù)庫中進行驗證來決定其是否加入Lk，這 里的驗證過程是算法性能的一個瓶頸。為了生成所有頻集，使用了遞推

36、的方法。其核心思想簡要描述如下：(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);/事務(wù)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

37、 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 p

38、runing 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） 編程實現(xiàn)算法1 Item.h 源文件/*- File : Item.h

39、 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)

40、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;