20131910084-陳國(guó)靜-實(shí)驗(yàn)4--Chimerge技術(shù)

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

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

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

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

5、和類不是相互獨(dú)立的，不能合并。如果閾值選的大，區(qū)間合并就會(huì)進(jìn)行很多次，離散后的區(qū)間數(shù)量少、區(qū)間大。用戶可以不考慮卡方閾值，此時(shí)，用戶可以考慮這兩個(gè)參數(shù)：最小區(qū)間數(shù)，最大區(qū)間數(shù)。用戶指定區(qū)間數(shù)量的上限和下限，最多幾個(gè)區(qū)間，最少幾個(gè)區(qū)間。11、 ChiMerge算法推薦使用.90、.95、.99置信度，最大區(qū)間數(shù)取10到15之間.三、實(shí)驗(yàn)環(huán)境個(gè)人計(jì)算機(jī)，MATLAB平臺(tái)四、實(shí)驗(yàn)記錄與實(shí)驗(yàn)結(jié)果分析（注意記錄實(shí)驗(yàn)中遇到的問題。實(shí)驗(yàn)報(bào)告的評(píng)分依據(jù)之一是實(shí)驗(yàn)記錄的細(xì)致程度、實(shí)驗(yàn)過程的真實(shí)性、實(shí)驗(yàn)結(jié)果的解釋和分析。如果涉及實(shí)驗(yàn)結(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%具體運(yùn)行 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ù)用于卡方值的計(jì)算及數(shù)據(jù)離散化操作 function m=chime(h)%進(jìn)行chimerge核心操作，建立區(qū)間矩陣，然后通過卡方檢驗(yàn)離散化數(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);%此（卡方表）矩陣用于保存計(jì)算卡方值的相關(guān)數(shù)據(jù) %后面4個(gè)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 %計(jì)算出這兩個(gè)相鄰區(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、運(yùn)行結(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