20131910084-陳國靜-實驗4--Chimerge技術(shù)

1、云南大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院數(shù)學(xué)系信息與計算科學(xué)專業(yè)云南大學(xué)數(shù)學(xué)與與統(tǒng)計學(xué)院上機實踐報告課程名稱：數(shù)據(jù)挖掘年級：2013上機實踐成績：指導(dǎo)教師：彭程姓名：陳國靜上機實踐名稱：Chimege技術(shù)學(xué)號：20131910084上機實踐日期： 2016/4/18上機實踐編號：No.4上機實踐時間： 15:50一、實驗?zāi)康氖煜himege技術(shù)，對數(shù)據(jù)挖掘有一個了解。二、實驗內(nèi)容1、 最簡單的離散算法是： 等寬區(qū)間。 從最小值到最大值之間,，均分為N等份， 這樣， 如果A, B為最小最大值， 則每個區(qū)間的長度為w=(B-A) / N,則區(qū)間邊界值為A+W, A+2W,. A+(N-1)W.2、 還有一種簡單算

2、法，等頻區(qū)間。區(qū)間的邊界值要經(jīng)過選擇，使得每個區(qū)間包含大致相等的實例數(shù)量。比如說N=10，每個區(qū)間應(yīng)該包含大約10%的實例。3、 以上兩種算法有弊端：比如，等寬區(qū)間劃分，劃分為5區(qū)間，最高工資為50000，則所有工資低于10000的人都被劃分到同一區(qū)間。等頻區(qū)間可能正好相反，所有工資高于50000的人都會被劃分到50000這一區(qū)間中。這兩種算法都忽略了實例所屬的類型，落在正確區(qū)間里的偶然性很大。4、 C4、CART、PVM算法在離散屬性時會考慮類信息，但是是在算法實施的過程中間，而不是在預(yù)處理階段。例如，C4算法（ID3決策樹系列的一種），將數(shù)值屬性離散為兩個區(qū)間，而取這兩個區(qū)間時，該屬性的信

3、息增益是最大的。5、 評價一個離散算法是否有效很難，因為不知道什么是最高效的分類。6、 離散化的主要目的是：消除數(shù)值屬性以及為數(shù)值屬性定義準確的類別。7、 高質(zhì)量的離散化應(yīng)該是：區(qū)間內(nèi)一致，區(qū)間之間區(qū)分明顯。8、 ChiMerge算法用卡方統(tǒng)計量來決定相鄰區(qū)間是否一致或者是否區(qū)別明顯。如果經(jīng)過驗證，類別屬性獨立于其中一個區(qū)間，則這個區(qū)間就要被合并。9、 ChiMerge算法包括2部分：1、初始化，2、自底向上合并，當(dāng)滿足停止條件的時候，區(qū)間合并停止。第一步：初始化 根據(jù)要離散的屬性對實例進行排序：每個實例屬于一個區(qū)間 第二步：合并區(qū)間，又包括兩步驟 (1)計算每一對相鄰區(qū)間的卡方值(2)將卡方

4、值最小的一對區(qū)間合并預(yù)先設(shè)定一個卡方的閾值，在閾值之下的區(qū)間都合并，閾值之上的區(qū)間保持分區(qū)間。 卡方的計算公式：參數(shù)說明；m=2（每次比較的區(qū)間數(shù)是2個）k=類別數(shù)量 Aij=第i區(qū)間第j類的實例的數(shù)量Ri=第i區(qū)間的實例數(shù)量Cj=第j類的實例數(shù)量N=總的實例數(shù)量Eij= Aij的期望頻率10、卡方閾值的確定：先選擇顯著性水平，再由公式得到對應(yīng)的卡方值。得到卡方值需要指定自由度，自由度比類別數(shù)量小1。例如，有3類，自由度為2，則90%置信度（10%顯著性水平)下，卡方的值為4.6。閾值的意義在于，類別和屬性獨立時，有90%的可能性，計算得到的卡方值會小于4.6，這樣，大于閾值的卡方值就說明屬性

5、和類不是相互獨立的，不能合并。如果閾值選的大，區(qū)間合并就會進行很多次，離散后的區(qū)間數(shù)量少、區(qū)間大。用戶可以不考慮卡方閾值，此時，用戶可以考慮這兩個參數(shù)：最小區(qū)間數(shù)，最大區(qū)間數(shù)。用戶指定區(qū)間數(shù)量的上限和下限，最多幾個區(qū)間，最少幾個區(qū)間。11、 ChiMerge算法推薦使用.90、.95、.99置信度，最大區(qū)間數(shù)取10到15之間.三、實驗環(huán)境個人計算機，MATLAB平臺四、實驗記錄與實驗結(jié)果分析（注意記錄實驗中遇到的問題。實驗報告的評分依據(jù)之一是實驗記錄的細致程度、實驗過程的真實性、實驗結(jié)果的解釋和分析。如果涉及實驗結(jié)果截屏，應(yīng)選擇白底黑字。）程序如下：%ChiMerge.m:This Progr

6、am will achieve the ChiMeige function! %File Read Part:%格式化讀文件： a,b,p,q,class = textread( Iris.txt,%f,%f,%f,%f,%s );%Data Processing %處理字符串：t=size(class); for i=1:t(1,1) if strcmp(class(i,1),Iris-setosa)=1 c(i,1)=1; elseif strcmp(class(i,1),Iris-versicolor)=1 c(i,1)=2; elseif strcmp(class(i,1),Iris-

7、virginica)=1 c(i,1)=3; endend%具體運行 h1=a c; h2=b c; h3=p,c; h4=q,c; disp(Case 1:); chime(h1); disp(End!); disp(Case 2:); chime(h2); disp(End!); disp(Case 3:); chime(h3); disp(End!); disp(Case 4:); chime(h4); disp(End!);%建立chime函數(shù)用于卡方值的計算及數(shù)據(jù)離散化操作 function m=chime(h)%進行chimerge核心操作，建立區(qū)間矩陣，然后通過卡方檢驗離散化數(shù)據(jù)

8、！ y=sortrows(h,1);%排序操作 ty=size(y); leny=ty(1,1); x=y(:,1) y(:,1);%初始化區(qū)間矩陣 tx=size(x); lenx=tx(1,1); while lenx6 %外層循環(huán)，用于結(jié)束條件判定 min=9999; for j=1:lenx-1 %內(nèi)層循環(huán)，用于找出具有最小卡方值的相鄰區(qū)間 ans=0; m=zeros(3,7);%此（卡方表）矩陣用于保存計算卡方值的相關(guān)數(shù)據(jù) %后面4個for循環(huán)用于卡方表數(shù)據(jù)的設(shè)置 for i=1:leny if y(i,1)=x(j,1)&y(i,1)=x(j+1,1)&y(i,1)=x(j+1,

9、2) m(2,y(i,2)=m(2,y(i,2)+1; end end end for i=1:3 m(3,i)=m(1,i)+m(2,i); end for i=1:3 m(i,7)=m(i,1)+m(i,2)+m(i,3); end for i=1:2 for k=4:6 m(i,k)=m(i,7)*m(3,k-3)/m(3,7); if m(i,k)=0 m(i,k)=0.1; end end end %計算出這兩個相鄰區(qū)間的卡方值 for i=1:2 for k=1:3 ans=ans+(m(i,k)-m(i,k+3)2)/m(i,k+3); end end %找出最小卡方值 if a

10、ns=min min=ans; key=j; end end %相鄰區(qū)間合并步驟 x(key,2)=x(key+1,2); x(key+1,:)=; lenx=lenx-1; endxIris.txt5.1 3.5 1.4 0.2 Iris-setosa4.9 3.0 1.4 0.2 Iris-setosa4.7 3.2 1.3 0.2 Iris-setosa4.6 3.1 1.5 0.2 Iris-setosa5.0 3.6 1.4 0.2 Iris-setosa5.4 3.9 1.7 0.4 Iris-setosa4.6 3.4 1.4 0.3 Iris-setosa5.0 3.4 1.5

11、 0.2 Iris-setosa4.4 2.9 1.4 0.2 Iris-setosa4.9 3.1 1.5 0.1 Iris-setosa5.4 3.7 1.5 0.2 Iris-setosa4.8 3.4 1.6 0.2 Iris-setosa4.8 3.0 1.4 0.1 Iris-setosa4.3 3.0 1.1 0.1 Iris-setosa5.8 4.0 1.2 0.2 Iris-setosa5.7 4.4 1.5 0.4 Iris-setosa5.4 3.9 1.3 0.4 Iris-setosa5.1 3.5 1.4 0.3 Iris-setosa5.7 3.8 1.7 0.

12、3 Iris-setosa5.1 3.8 1.5 0.3 Iris-setosa5.4 3.4 1.7 0.2 Iris-setosa5.1 3.7 1.5 0.4 Iris-setosa4.6 3.6 1.0 0.2 Iris-setosa5.1 3.3 1.7 0.5 Iris-setosa4.8 3.4 1.9 0.2 Iris-setosa5.0 3.0 1.6 0.2 Iris-setosa5.0 3.4 1.6 0.4 Iris-setosa5.2 3.5 1.5 0.2 Iris-setosa5.2 3.4 1.4 0.2 Iris-setosa4.7 3.2 1.6 0.2 I

13、ris-setosa4.8 3.1 1.6 0.2 Iris-setosa5.4 3.4 1.5 0.4 Iris-setosa5.2 4.1 1.5 0.1 Iris-setosa5.5 4.2 1.4 0.2 Iris-setosa4.9 3.1 1.5 0.1 Iris-setosa5.0 3.2 1.2 0.2 Iris-setosa5.5 3.5 1.3 0.2 Iris-setosa4.9 3.1 1.5 0.1 Iris-setosa4.4 3.0 1.3 0.2 Iris-setosa5.1 3.4 1.5 0.2 Iris-setosa5.0 3.5 1.3 0.3 Iris

14、-setosa4.5 2.3 1.3 0.3 Iris-setosa4.4 3.2 1.3 0.2 Iris-setosa5.0 3.5 1.6 0.6 Iris-setosa5.1 3.8 1.9 0.4 Iris-setosa4.8 3.0 1.4 0.3 Iris-setosa5.1 3.8 1.6 0.2 Iris-setosa4.6 3.2 1.4 0.2 Iris-setosa5.3 3.7 1.5 0.2 Iris-setosa5.0 3.3 1.4 0.2 Iris-setosa7.0 3.2 4.7 1.4 Iris-versicolor6.4 3.2 4.5 1.5 Iri

15、s-versicolor6.9 3.1 4.9 1.5 Iris-versicolor5.5 2.3 4.0 1.3 Iris-versicolor6.5 2.8 4.6 1.5 Iris-versicolor5.7 2.8 4.5 1.3 Iris-versicolor6.3 3.3 4.7 1.6 Iris-versicolor4.9 2.4 3.3 1.0 Iris-versicolor6.6 2.9 4.6 1.3 Iris-versicolor5.2 2.7 3.9 1.4 Iris-versicolor5.0 2.0 3.5 1.0 Iris-versicolor5.9 3.0 4

16、.2 1.5 Iris-versicolor6.0 2.2 4.0 1.0 Iris-versicolor6.1 2.9 4.7 1.4 Iris-versicolor5.6 2.9 3.6 1.3 Iris-versicolor6.7 3.1 4.4 1.4 Iris-versicolor5.6 3.0 4.5 1.5 Iris-versicolor5.8 2.7 4.1 1.0 Iris-versicolor6.2 2.2 4.5 1.5 Iris-versicolor5.6 2.5 3.9 1.1 Iris-versicolor5.9 3.2 4.8 1.8 Iris-versicolo

17、r6.1 2.8 4.0 1.3 Iris-versicolor6.3 2.5 4.9 1.5 Iris-versicolor6.1 2.8 4.7 1.2 Iris-versicolor6.4 2.9 4.3 1.3 Iris-versicolor6.6 3.0 4.4 1.4 Iris-versicolor6.8 2.8 4.8 1.4 Iris-versicolor6.7 3.0 5.0 1.7 Iris-versicolor6.0 2.9 4.5 1.5 Iris-versicolor5.7 2.6 3.5 1.0 Iris-versicolor5.5 2.4 3.8 1.1 Iris

18、-versicolor5.5 2.4 3.7 1.0 Iris-versicolor5.8 2.7 3.9 1.2 Iris-versicolor6.0 2.7 5.1 1.6 Iris-versicolor5.4 3.0 4.5 1.5 Iris-versicolor6.0 3.4 4.5 1.6 Iris-versicolor6.7 3.1 4.7 1.5 Iris-versicolor6.3 2.3 4.4 1.3 Iris-versicolor5.6 3.0 4.1 1.3 Iris-versicolor5.5 2.5 4.0 1.3 Iris-versicolor5.5 2.6 4.

19、4 1.2 Iris-versicolor6.1 3.0 4.6 1.4 Iris-versicolor5.8 2.6 4.0 1.2 Iris-versicolor5.0 2.3 3.3 1.0 Iris-versicolor5.6 2.7 4.2 1.3 Iris-versicolor5.7 3.0 4.2 1.2 Iris-versicolor5.7 2.9 4.2 1.3 Iris-versicolor6.2 2.9 4.3 1.3 Iris-versicolor5.1 2.5 3.0 1.1 Iris-versicolor5.7 2.8 4.1 1.3 Iris-versicolor

20、6.3 3.3 6.0 2.5 Iris-virginica5.8 2.7 5.1 1.9 Iris-virginica7.1 3.0 5.9 2.1 Iris-virginica6.3 2.9 5.6 1.8 Iris-virginica6.5 3.0 5.8 2.2 Iris-virginica7.6 3.0 6.6 2.1 Iris-virginica4.9 2.5 4.5 1.7 Iris-virginica7.3 2.9 6.3 1.8 Iris-virginica6.7 2.5 5.8 1.8 Iris-virginica7.2 3.6 6.1 2.5 Iris-virginica

21、6.5 3.2 5.1 2.0 Iris-virginica6.4 2.7 5.3 1.9 Iris-virginica6.8 3.0 5.5 2.1 Iris-virginica5.7 2.5 5.0 2.0 Iris-virginica5.8 2.8 5.1 2.4 Iris-virginica6.4 3.2 5.3 2.3 Iris-virginica6.5 3.0 5.5 1.8 Iris-virginica7.7 3.8 6.7 2.2 Iris-virginica7.7 2.6 6.9 2.3 Iris-virginica6.0 2.2 5.0 1.5 Iris-virginica

22、6.9 3.2 5.7 2.3 Iris-virginica5.6 2.8 4.9 2.0 Iris-virginica7.7 2.8 6.7 2.0 Iris-virginica6.3 2.7 4.9 1.8 Iris-virginica6.7 3.3 5.7 2.1 Iris-virginica7.2 3.2 6.0 1.8 Iris-virginica6.2 2.8 4.8 1.8 Iris-virginica6.1 3.0 4.9 1.8 Iris-virginica6.4 2.8 5.6 2.1 Iris-virginica7.2 3.0 5.8 1.6 Iris-virginica

23、7.4 2.8 6.1 1.9 Iris-virginica7.9 3.8 6.4 2.0 Iris-virginica6.4 2.8 5.6 2.2 Iris_virginica6.3 2.8 5.1 1.5 Iris_virginica6.1 2.6 5.6 1.4 Iris-virginica7.7 3.0 6.1 2.3 Iris-virginica6.3 3.4 5.6 2.4 Iris-virginica6.4 3.1 5.5 1.8 Iris-virginica6.0 3.0 4.8 1.8 Iris-virginica6.9 3.1 5.4 2.1 Iris-virginica

24、6.7 3.1 5.6 2.4 Iris-virginica6.9 3.1 5.1 2.3 Iris-virginica5.8 2.7 5.1 1.9 Iris-virginica6.8 3.2 5.9 2.3 Iris-virginica6.7 3.3 5.7 2.5 Iris-virginica6.7 3.0 5.2 2.3 Iris-virginica6.3 2.5 5.0 1.9 Iris-virginica6.5 3.0 5.2 2.0 Iris-virginica6.2 3.4 5.4 2.3 Iris-virginica5.9 3.0 5.1 1.8 Iris-virginica

25、運行結(jié)果：Case 1: x = 4.3000 4.8000 4.9000 4.9000 5.0000 5.4000 5.5000 5.7000 5.8000 7.0000 7.1000 7.9000 End! Case 2: x = 2.0000 2.2000 2.3000 2.4000 2.5000 2.8000 2.9000 2.9000 3.0000 3.3000 3.4000 4.4000 End! Case 3: x = 1.0000 1.9000 3.0000 4.4000 4.5000 4.7000 4.8000 4.9000 5.0000 5.1000 5.2000 6.9000 End! Case 4: x = 0.1000 0.6000 1.0000 1.3000 1.4000 1.6000 1.7000 1.7000 1.8000 1.8000 1.9000 2.5000 End!結(jié)論：最后區(qū)間： a: 4.3 , 4.8,4.9 , 4.9, 5.0 , 5.4, 5.5 , 5.7, 5.8 , 7.0, 7.1 , 7.9. b: 2.0 , 2.2, 2.3 , 2.4, 2.5 , 2.8, 2.9 , 2.9, 3.0 , 3.3