927
對ChiMerge問題的解析與程序實現(matlab)
此問題與數據挖掘中的ChiMerge算法相關，用matlab程序實現。
問題描述：
ChiMerge是監督的、自底向上的數據離散化方法。它依賴於卡方分析：具有最小卡方值的相鄰區間合並在一起，直到滿足確定的停止標準。
（1）、簡述ChiMerge如何工作。
（2）、取鳶尾花數據集作為待離散化的數據集合，鳶尾花數據集可以從UCI機器學習數據庫得到。使用ChiMerge方法，對四個數值屬性分別進行離散化。（令停止條件為：max-interval=6）。你需要寫一個小程序，以避免麻煩的數值計算。提交你的簡要分析和檢驗結果：分裂點、最終的區間以及源程序文檔。
問題分析及回答：
（1）、ChiMerge的工作原理：
ChiMerge算法過程：
第一步：初始化：
根據要離散的屬性對實例進行排序；每個實例屬於一個區間。
第二步：合並區間，又包括兩步驟：
A、計算每一對相鄰區間的卡方值；
B、將卡方值最小的一對區間合並。
簡化為：
將離散屬性值進行升序排序；
將每個實例設置成單獨區間；
While（截止條件）
{
循環對每對相鄰區間進行卡方計算，找出最小卡方值的相鄰區間；
對相鄰區間進行合並；
}
（2）對鳶尾花數值的ChiMerge處理：
輸入為：鳶尾花數據集（https://archive.ics.uci.edu/ml/datasets/Iris）
ChiMerge.m
%ChiMerge.m:This Program 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-virginica')==1
c(i,1)=3;
end
end
%具體運行
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.m
%建立chime函數用於卡方值的計算及數據離散化操作
function m=chime(h)
%進行chimerge核心操作，建立區間矩陣，然後通過卡方檢驗離散化數據！
y=sortrows(h,1);%排序操作
ty=size(y);
leny=ty(1,1);
x=[y(:,1) y(:,1)];%初始化區間矩陣
tx=size(x);
lenx=tx(1,1);
while lenx>6
%外層循環，用於結束條件判定
min=9999;
for j=1:lenx-1
%內層循環，用於找出具有最小卡方值的相鄰區間
ans=0;
m=zeros(3,7);%此（卡方表）矩陣用於保存計算卡方值的相關數據
%後麵4個for循環用於卡方表數據的設置
for i=1:leny
if y(i,1)>=x(j,1)&&y(i,1)<=x(j,2)
m(1,y(i,2))=m(1,y(i,2))+1;
elseif y(i,1)>=x(j+1,1)&&y(i,1)<=x(j+1,2)
m(2,y(i,2))=m(2,y(i,2))+1;
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
%計算出這兩個相鄰區間的卡方值
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 ans<=min
min=ans;
key=j;
end
End
%相鄰區間合並步驟
x(key,2)=x(key+1,2);
x(key+1,:)=[];
lenx=lenx-1;
end
x
運行結果：
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!
結論：
最後區間： 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], [3.4 , 4.4]. p: [1.0 , 1.9], [3.0 , 4.4], [4.5 , 4.7], [4.8 , 4.9], [5.0 , 5.1], [5.2 , 6.9]. q: [0.1 , 0.6], [1.0 , 1.3], [1.4 , 1.6], [1.7 , 1.7], [1.8 , 1.8], [1.9 , 2.5]. 分裂點： a: 4.3, 4.9, 5.0, 5.5, 5.8, 7.1 b: 2.0, 2.3, 2.5, 2.9, 3.0, 3.4 p: 1.0, 3.0, 4.5, 4.8, 5.0, 5.2 q: 0.1, 1.0, 1.4, 1.7, 1.8, 1.9
最後更新：2017-04-03 05:39:52