數(shù)據(jù)挖掘?qū)嶒?yàn)報(bào)告

1、數(shù)據(jù)挖掘?qū)嶒?yàn)報(bào)告K-最臨近分類算法學(xué)號(hào)： 姓名：汪文娟一、 數(shù)據(jù)源說明1.數(shù)據(jù)理解選擇第二包數(shù)據(jù)Iris Data Set，共有150組數(shù)據(jù),考慮到訓(xùn)練數(shù)據(jù)集的隨機(jī)性和多樣性，選擇rowNo模3不等于0的100組作為訓(xùn)練數(shù)據(jù)集，剩下的50組做測試數(shù)據(jù)集。（1) 每組數(shù)據(jù)有5個(gè)屬性，分別是：1. sepal length in cm 2. sepal wrowNoth in cm 3. petal length in cm 4. petal wrowNoth in cm 5. class: - Iris Setosa - Iris Versicolour - Iris Virginica（2)

2、為了操作方便，對各組數(shù)據(jù)添加rowNo屬性,且第一組rowNo=1。2.數(shù)據(jù)清理現(xiàn)實(shí)世界的數(shù)據(jù)一般是不完整的、有噪聲的和不一致的。數(shù)據(jù)清理例程試圖填充缺失的值，光滑噪聲并識(shí)別離群點(diǎn)，并糾正數(shù)據(jù)中的不一致。a) 缺失值：當(dāng)數(shù)據(jù)中存在缺失值是，忽略該元組（注意：本文選用的第二組數(shù)據(jù)Iris Data Set的Missing Attribute Values: None）。b) 噪聲數(shù)據(jù)：本文暫沒考慮。二、 K-最臨近分類算法KNN(k Nearest Neighbors)算法又叫k最臨近方法，假設(shè)每一個(gè)類包含多個(gè)樣本數(shù)據(jù)，而且每個(gè)數(shù)據(jù)都有一個(gè)唯一的類標(biāo)記表示這些樣本是屬于哪一個(gè)分類， KNN就是計(jì)

3、算每個(gè)樣本數(shù)據(jù)到待分類數(shù)據(jù)的距離，如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。因此，采用這種方法可以較好地避免樣本的不平衡問題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。 該方法的不足之處是計(jì)算量較大，因?yàn)閷γ恳粋€(gè)待分類的文本都要計(jì)算它到全體已

4、知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對已知樣本點(diǎn)進(jìn)行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。（1）算法思路：K-最臨近分類方法存放所有的訓(xùn)練樣本，在接受待分類的新樣本之前不需構(gòu)造模型，并且直到新的（未標(biāo)記的）樣本需要分類時(shí)才建立分類。K-最臨近分類基于類比學(xué)習(xí)，其訓(xùn)練樣本由N維數(shù)值屬性描述，每個(gè)樣本代表N維空間的一個(gè)點(diǎn)。這樣，所有訓(xùn)練樣本都存放在N維模式空間中。給定一個(gè)未知樣本，k-最臨近分類法搜索模式空間，找出最接近未知樣本的K個(gè)訓(xùn)練樣本。這K個(gè)訓(xùn)練樣本是未知樣本的K

5、個(gè)“近鄰”。“臨近性”又稱為相異度（Dissimilarity），由歐幾里德距離定義，其中兩個(gè)點(diǎn) X（x1,x2,xn）和Y（y1,y2,yn）的歐幾里德距離是：未知樣本被分配到K個(gè)最臨近者中最公共的類。在最簡單的情況下，也就是當(dāng)K=1時(shí)，未知樣本被指定到模式空間中與之最臨近的訓(xùn)練樣本的類。（2）算法步驟：step.1-初始化距離為最大值step.2-計(jì)算未知樣本和每個(gè)訓(xùn)練樣本的距離diststep.3-得到目前K個(gè)最臨近樣本中的最大距離maxdiststep.4-如果dist小于maxdist，則將該訓(xùn)練樣本作為K-最近鄰樣本step.5-重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的距離

6、都算完step.6-統(tǒng)計(jì)K-最近鄰樣本中每個(gè)類標(biāo)號(hào)出現(xiàn)的次數(shù)step.7-選擇出現(xiàn)頻率最大的類標(biāo)號(hào)作為未知樣本的類標(biāo)號(hào)三、 算法源代碼/ KNN.cpp K-最近鄰分類算法/#include #include #include #include #include #include #include / 宏定義/#define ATTR_NUM 4 /屬性數(shù)目#define MAX_SIZE_OF_TRAINING_SET 1000 /訓(xùn)練數(shù)據(jù)集的最大大小#define MAX_SIZE_OF_TEST_SET 100 /測試數(shù)據(jù)集的最大大小#define MAX_VALUE 10000.0 /

7、屬性最大值#define K 7/結(jié)構(gòu)體struct dataVector int ID; /ID號(hào)char classLabel15; /分類標(biāo)號(hào)double attributesATTR_NUM; /屬性;struct distanceStruct int ID; /ID號(hào)double distance; /距離char classLabel15; /分類標(biāo)號(hào);/ 全局變量/struct dataVector gTrainingSetMAX_SIZE_OF_TRAINING_SET; /訓(xùn)練數(shù)據(jù)集struct dataVector gTestSetMAX_SIZE_OF_TEST_SET;

8、 /測試數(shù)據(jù)集struct distanceStruct gNearestDistanceK; /K個(gè)最近鄰距離int curTrainingSetSize=0; /訓(xùn)練數(shù)據(jù)集的大小int curTestSetSize=0; /測試數(shù)據(jù)集的大小/ 求 vector1=(x1,x2,.,xn)和vector2=(y1,y2,.,yn)的歐幾里德距離/double Distance(struct dataVector vector1,struct dataVector vector2)double dist,sum=0.0;for(int i=0;iATTR_NUM;i+)sum+=(vector

9、1.attributesi-vector2.attributesi)*(vector1.attributesi-vector2.attributesi);dist=sqrt(sum);return dist;/ 得到gNearestDistance中的最大距離，返回下標(biāo)/int GetMaxDistance()int maxNo=0;for(int i=1;igNearestDistancemaxNo.distance)maxNo = i; return maxNo;/ 對未知樣本Sample分類/char* Classify(struct dataVector Sample)double d

10、ist=0;int maxid=0,freqK,i,tmpfreq=1;char *curClassLable=gNearestDistance0.classLabel;memset(freq,1,sizeof(freq);/step.1-初始化距離為最大值for(i=0;iK;i+)gNearestDistancei.distance=MAX_VALUE;/step.2-計(jì)算K-最近鄰距離for(i=0;icurTrainingSetSize;i+)/step.2.1-計(jì)算未知樣本和每個(gè)訓(xùn)練樣本的距離dist=Distance(gTrainingSeti,Sample);/step.2.2-

11、得到gNearestDistance中的最大距離maxid=GetMaxDistance();/step.2.3-如果距離小于gNearestDistance中的最大距離，則將該樣本作為K-最近鄰樣本if(distgNearestDistancemaxid.distance) gNearestDistancemaxid.ID=gTrainingSeti.ID;gNearestDistancemaxid.distance=dist;strcpy(gNearestDistancemaxid.classLabel,gTrainingSeti.classLabel);/step.3-統(tǒng)計(jì)每個(gè)類出現(xiàn)的次

12、數(shù)for(i=0;iK;i+) for(int j=0;jK;j+)if(i!=j)&(strcmp(gNearestDistancei.classLabel,gNearestDistancej.classLabel)=0)freqi+=1;/step.4-選擇出現(xiàn)頻率最大的類標(biāo)號(hào)for(i=0;itmpfreq) tmpfreq=freqi; curClassLable=gNearestDistancei.classLabel;return curClassLable;/ 主函數(shù)/void main() char c; char *classLabel=;int i,j, rowNo=0,T

13、ruePositive=0,FalsePositive=0;ifstream filein(iris.data);FILE *fp;if(filein.fail()coutCant open data.txt=MAX_SIZE_OF_TRAINING_SET) coutThe training set has MAX_SIZE_OF_TRAINING_SET examples!endlendl; break ;/rowNo%3!=0的100組數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)集if(rowNo%3!=0)gTrainingSetcurTrainingSetSize.ID=rowNo;for(int i = 0;

14、i gTrainingSetcurTrainingSetSize.attributesi;fileinc;fileingTrainingSetcurTrainingSetSize.classLabel;curTrainingSetSize+;/剩下rowNo%3=0的50組做測試數(shù)據(jù)集else if(rowNo%3=0)gTestSetcurTestSetSize.ID=rowNo;for(int i = 0;i gTestSetcurTestSetSize.attributesi;fileinc;fileingTestSetcurTestSetSize.classLabel;curTestS

15、etSize+;filein.close();/step.2-KNN算法進(jìn)行分類，并將結(jié)果寫到文件iris_OutPut.txtfp=fopen(iris_OutPut.txt,w+t);/用KNN算法進(jìn)行分類fprintf(fp,*程序說明*n);fprintf(fp,* 采用KNN算法對iris.data分類。為了操作方便，對各組數(shù)據(jù)添加rowNo屬性,第一組rowNo=1!n);fprintf(fp,* 共有150組數(shù)據(jù),選擇rowNo模3不等于0的100組作為訓(xùn)練數(shù)據(jù)集，剩下的50組做測試數(shù)據(jù)集n);fprintf(fp,*nn);fprintf(fp,*實(shí)驗(yàn)結(jié)果*nn);for(i=

16、0;icurTestSetSize;i+) fprintf(fp,*第%d組數(shù)據(jù)*n,i+1);classLabel =Classify(gTestSeti); if(strcmp(classLabel,gTestSeti.classLabel)=0)/相等時(shí)，分類正確TruePositive+;coutrowNo:;coutgTestSeti.ID t;coutKNN分類結(jié)果: ; coutclassLabel(正確類標(biāo)號(hào): ;coutgTestSeti.classLabel)n;fprintf(fp,rowNo: %3d t KNN分類結(jié)果: %s ( 正確類標(biāo)號(hào): %s )n,gTest

17、Seti.ID,classLabel,gTestSeti.classLabel);if(strcmp(classLabel,gTestSeti.classLabel)!=0)/不等時(shí)，分類錯(cuò)誤/cout *分類錯(cuò)誤*n;fprintf(fp, *分類錯(cuò)誤*n);fprintf(fp,%d-最臨近數(shù)據(jù):n,K);for(j=0;jK;j+)/coutgNearestDistancej.IDtgNearestDistancej.distancetgNearestDistancej.classLabel15endl;fprintf(fp,rowNo: %3d t Distance: %f tClas

18、sLable: %sn,gNearestDistancej.ID,gNearestDistancej.distance,gNearestDistancej.classLabel);fprintf(fp,n); FalsePositive=curTestSetSize-TruePositive;fprintf(fp,*結(jié)果分析*n,i);fprintf(fp,TP(True positive): %dnFP(False positive): %dnaccuracy: %fn,TruePositive,FalsePositive,double(TruePositive)/(curTestSetSi

19、ze-1);fclose(fp); return;四、 詳細(xì)描述該算法獲得的模型采用第二包數(shù)據(jù)Iris Data Set，共有150組數(shù)據(jù),考慮到訓(xùn)練數(shù)據(jù)集的隨機(jī)性和多樣性，選擇rowNo模3不等于0的100組作為訓(xùn)練數(shù)據(jù)集，剩下的50組做測試數(shù)據(jù)集。對未知樣本進(jìn)行分類（括號(hào)里的正確類標(biāo)號(hào)是讀取的iris.data文件里的類標(biāo)號(hào)，括號(hào)外的是計(jì)算所得），本文取k=7個(gè)最鄰近數(shù)據(jù)。以第19組為例進(jìn)行說明，未知樣本ROWNO為57，經(jīng)過KNN算法分類，與之最臨近的7組數(shù)據(jù)rowNo號(hào)分別為：52、86、128、139、92、64、71，其中類標(biāo)號(hào)為Iris-versicolor的有5個(gè)，類標(biāo)號(hào)為Ir

20、is-virginica的有2個(gè)，Iris-versicolor為最多，因此據(jù)此估計(jì)該組樣本的類標(biāo)號(hào)為Iris-versicolor。50組測試樣本運(yùn)行結(jié)果如下：*程序說明* 采用KNN算法對iris.data分類。為了操作方便，對各組數(shù)據(jù)添加rowNo屬性,第一組rowNo=1!* 共有150組數(shù)據(jù),選擇rowNo模3不等于0的100組作為訓(xùn)練數(shù)據(jù)集，剩下的50組做測試數(shù)據(jù)集*實(shí)驗(yàn)結(jié)果*第1組數(shù)據(jù)*rowNo: 3 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 43 Distance: 0. ClassLable: Iri

21、s-setosarowNo: 2 Distance: 0. ClassLable: Iris-setosarowNo: 4 Distance: 0. ClassLable: Iris-setosarowNo: 13 Distance: 0. ClassLable: Iris-setosarowNo: 7 Distance: 0. ClassLable: Iris-setosarowNo: 46 Distance: 0. ClassLable: Iris-setosarowNo: 10 Distance: 0. ClassLable: Iris-setosa*第2組數(shù)據(jù)*rowNo: 6 KNN

22、分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 22 Distance: 0. ClassLable: Iris-setosarowNo: 47 Distance: 0. ClassLable: Iris-setosarowNo: 11 Distance: 0. ClassLable: Iris-setosarowNo: 49 Distance: 0. ClassLable: Iris-setosarowNo: 19 Distance: 0. ClassLable: Iris-setosarowNo: 20 Distance: 0.

23、 ClassLable: Iris-setosarowNo: 17 Distance: 0. ClassLable: Iris-setosa*第3組數(shù)據(jù)*rowNo: 9 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 14 Distance: 0. ClassLable: Iris-setosarowNo: 2 Distance: 0. ClassLable: Iris-setosarowNo: 4 Distance: 0. ClassLable: Iris-setosarowNo: 13 Distance: 0. Clas

24、sLable: Iris-setosarowNo: 46 Distance: 0. ClassLable: Iris-setosarowNo: 31 Distance: 0. ClassLable: Iris-setosarowNo: 43 Distance: 0. ClassLable: Iris-setosa*第4組數(shù)據(jù)*rowNo: 12 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 31 Distance: 0. ClassLable: Iris-setosarowNo: 25 Distance: 0. ClassL

25、able: Iris-setosarowNo: 40 Distance: 0. ClassLable: Iris-setosarowNo: 50 Distance: 0. ClassLable: Iris-setosarowNo: 7 Distance: 0. ClassLable: Iris-setosarowNo: 8 Distance: 0. ClassLable: Iris-setosarowNo: 10 Distance: 0. ClassLable: Iris-setosa*第5組數(shù)據(jù)*rowNo: 15 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-set

26、osa )7-最臨近數(shù)據(jù):rowNo: 34 Distance: 0. ClassLable: Iris-setosarowNo: 17 Distance: 0. ClassLable: Iris-setosarowNo: 11 Distance: 0. ClassLable: Iris-setosarowNo: 37 Distance: 0. ClassLable: Iris-setosarowNo: 16 Distance: 0. ClassLable: Iris-setosarowNo: 49 Distance: 0. ClassLable: Iris-setosarowNo: 19 D

27、istance: 0. ClassLable: Iris-setosa*第6組數(shù)據(jù)*rowNo: 18 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 1 Distance: 0. ClassLable: Iris-setosarowNo: 40 Distance: 0. ClassLable: Iris-setosarowNo: 29 Distance: 0. ClassLable: Iris-setosarowNo: 5 Distance: 0. ClassLable: Iris-setosarowNo: 41 Dista

28、nce: 0. ClassLable: Iris-setosarowNo: 8 Distance: 0. ClassLable: Iris-setosarowNo: 28 Distance: 0. ClassLable: Iris-setosa*第7組數(shù)據(jù)*rowNo: 21 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 49 Distance: 0. ClassLable: Iris-setosarowNo: 37 Distance: 0. ClassLable: Iris-setosarowNo: 11 Distance

29、: 0. ClassLable: Iris-setosarowNo: 29 Distance: 0. ClassLable: Iris-setosarowNo: 28 Distance: 0. ClassLable: Iris-setosarowNo: 40 Distance: 0. ClassLable: Iris-setosarowNo: 32 Distance: 0. ClassLable: Iris-setosa*第8組數(shù)據(jù)*rowNo: 24 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 40 Distance:

30、0. ClassLable: Iris-setosarowNo: 26 Distance: 0. ClassLable: Iris-setosarowNo: 44 Distance: 0. ClassLable: Iris-setosarowNo: 28 Distance: 0. ClassLable: Iris-setosarowNo: 32 Distance: 0. ClassLable: Iris-setosarowNo: 8 Distance: 0. ClassLable: Iris-setosarowNo: 50 Distance: 0. ClassLable: Iris-setos

31、a*第9組數(shù)據(jù)*rowNo: 27 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 1 Distance: 0. ClassLable: Iris-setosarowNo: 50 Distance: 0. ClassLable: Iris-setosarowNo: 41 Distance: 0. ClassLable: Iris-setosarowNo: 44 Distance: 0. ClassLable: Iris-setosarowNo: 40 Distance: 0. ClassLable: Iris-setosaro

32、wNo: 8 Distance: 0. ClassLable: Iris-setosarowNo: 28 Distance: 0. ClassLable: Iris-setosa*第10組數(shù)據(jù)*rowNo: 30 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 31 Distance: 0. ClassLable: Iris-setosarowNo: 38 Distance: 0. ClassLable: Iris-setosarowNo: 4 Distance: 0. ClassLable: Iris-setosarowNo

33、: 13 Distance: 0. ClassLable: Iris-setosarowNo: 7 Distance: 0. ClassLable: Iris-setosarowNo: 35 Distance: 0. ClassLable: Iris-setosarowNo: 10 Distance: 0. ClassLable: Iris-setosa*第11組數(shù)據(jù)*rowNo: 33 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 34 Distance: 0. ClassLable: Iris-setosarowNo:

34、22 Distance: 0. ClassLable: Iris-setosarowNo: 11 Distance: 0. ClassLable: Iris-setosarowNo: 49 Distance: 0. ClassLable: Iris-setosarowNo: 47 Distance: 0. ClassLable: Iris-setosarowNo: 20 Distance: 0. ClassLable: Iris-setosarowNo: 17 Distance: 0. ClassLable: Iris-setosa*第12組數(shù)據(jù)*rowNo: 36 KNN分類結(jié)果: Iris

35、-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 38 Distance: 0. ClassLable: Iris-setosarowNo: 2 Distance: 0. ClassLable: Iris-setosarowNo: 41 Distance: 0. ClassLable: Iris-setosarowNo: 35 Distance: 0. ClassLable: Iris-setosarowNo: 29 Distance: 0. ClassLable: Iris-setosarowNo: 50 Distance: 0. ClassLable

36、: Iris-setosarowNo: 10 Distance: 0. ClassLable: Iris-setosa*第13組數(shù)據(jù)*rowNo: 39 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 13 Distance: 0. ClassLable: Iris-setosarowNo: 46 Distance: 0. ClassLable: Iris-setosarowNo: 4 Distance: 0. ClassLable: Iris-setosarowNo: 14 Distance: 0. ClassLable:

37、Iris-setosarowNo: 7 Distance: 0. ClassLable: Iris-setosarowNo: 31 Distance: 0. ClassLable: Iris-setosarowNo: 43 Distance: 0. ClassLable: Iris-setosa*第14組數(shù)據(jù)*rowNo: 42 KNN分類結(jié)果: Iris-setosa ( 正確類標(biāo)號(hào): Iris-setosa )7-最臨近數(shù)據(jù):rowNo: 14 Distance: 0. ClassLable: Iris-setosarowNo: 2 Distance: 0. ClassLable: Iris-setosarowNo: 4 Distance: 0. ClassLable: Iris-setosarowNo: 13 Distance: 0. ClassLable: Iris-setosarowNo: 31 Distance: 0. ClassL