韓家煒 數據挖掘概念與技術 第三版 習題3.12
取 鳶尾花數據集iris.data 作為待離散化的數據集合,使用ChiMerge算法,對四個數值屬性進 行離散化,對四個屬性進行區間合并,最終合并區間個數剩下為6個即停:即max_interval=6。
一、樣本數據
iris.data 數據形式為:前面4列是屬性,最后一列是數據類名,
5.1,3.5,1.4,0.2,Iris-setosa 4.9,3.0,1.4,0.2,Iris-setosa 4.7,3.2,1.3,0.2,Iris-setosa 6.6,2.9,4.6,1.3,Iris-versicolor 5.2,2.7,3.9,1.4,Iris-versicolor 6.0,3.0,4.8,1.8,Iris-virginica 6.9,3.1,5.4,2.1,Iris-virginica
........
?此數據集一共3個類名:String[] classifies = {"Iris-setosa","Iris-versicolor","Iris-virginica"};
?
二、算法理論:
算法理論步驟參考:?http://blog.csdn.net/zhaoyl03/article/details/8689440
第一步:初始化?
初始化時,一個數據認為是一個區間,每個屬性對該屬性下的各個區間進行升序排序
第二步:合并區間:(直到剩下區間數目為6)
(1)?計算每一對相鄰區間的卡方值
? 卡方公式是:?
其中observed是expected是一個二行n列矩陣,二行是兩個區間,n列是指數據一共有n個類。
? ? ? ?這里iris.data數據中一共有三個類,所以是2行3列矩陣:e.g
?observedmatrix:(下面表只有紅色數字部分才為observedmatrix[2][3]的值。)
區間: | 類別Iris-setosa | 類別 Iris-versicolor | 類別 Iris-virginica | i行計算1的總個數 |
{3.0} | 1 | 0 | 0 | 1 |
{3.1,3.2,3.3} | 0 | 1 | 2 | 3 |
j列計算1的總個數 | 1 | 1 | 2 | 4 ? ?(矩陣里 1的總個數 ) |
區間: | 類別 Iris-setosa | 類別 Iris-versicolor | 類別 Iris-virginica |
{3.0} | 1*1/4=0.25 | 1/4=0.25 | 2*1/4=0.5 |
{3.2,3.3} | 1*3/4=0.75 | 1/4=0.25 | 2*3/4 = 1.5 |

(2)?將上面卡方值最小的一對區間合并
? ? ??
第三步:輸出結果:6個區間的最大最小值
?
?
三、算法理論數據結構化
將上面算法理論數據結構化:
iris.data ?中
1.屬性:每個屬性都有多個區間,所以定義屬性是一個list,list的元素是什么類型呢? 是一個區間類型(所以寫一個區間類:包括 區間最大最小值,區間包含的元素)。
2.區間:每個區間會包含很多元素,所以也需要一個list來存,list元素什么類型好? ?再寫一個數據 Data類,包括(數據,數據對應的類別(在卡方運算里會用到類別))
?所有數據都具備了結構了,整體結構這是最重要的。
List<Interval>[] attributelists = new ArrayList[attributenum]; for ( int i=0;i<attributenum;i++ ) { attributelists[i] = new ArrayList<Interval> (); } class Interval { // 每個區間都是有最小值最大值,以及該區間所包含的所有數據 public double maxvalue = 0.0 ; public double minvalue = 0.0 ; public List<Data> intervallist = new ArrayList<Data>(); // 區間里的list每個元素都是Data類型 } class Data { // 每個數據都包含它的值和類別 public double value = 0.0 ; public String classify = "" ; }
?
?
四、Java 實現
public class ChiMergeTest {
public static int classificationnum = 3; // 類個數 public static int attributenum = 4 ; public static List<Interval>[] attributelists = new ArrayList[attributenum]; // 右邊不能Arraylist<interval>!! public static String[] classifies = {"Iris-setosa","Iris-versicolor","Iris-virginica" }; public static void main(String[] args) throws Exception { String inputpath = "iris.data" ; readFile(inputpath); // 將輸入數據的 結構化 chiMerge(); printresult(); }
?
對應上面算法步驟:
第一步:初始化?
初始化時,一個數據認為是一個區間,每個屬性對該屬性下的各個區間進行升序排序
public static void readFile(String inputpath) throws Exception { BufferedReader br = new BufferedReader( new FileReader(inputpath)); String line = br.readLine(); for ( int i=0;i<attributenum;i++ ) { attributelists[i] = new ArrayList<Interval> (); } while (line!= null && line.length()>0 ) { String[] temp = line.split(","); // 將數據分隔, for ( int i=0; i<attributelists.length; i++) { // 遍歷屬性名 Interval interval = new Interval(); Data onedata = new Data(); onedata.value = Double.parseDouble(temp[i]); onedata.classify = temp[4 ]; interval.minvalue = interval.maxvalue = onedata.value; interval.intervallist.add(onedata); // 區間加入了一個數據 attributelists[i].add(interval); // 第i個屬性加入了一個區間 } line = br.readLine(); } br.close(); sort(); } public static void sort() { // 初步建立屬性list時,對區間進行排序 for ( int i = 0; i<attributenum; i++ ){ List <Interval> attrlist = attributelists[i]; Collections.sort(attrlist, new IntervalComparator()); // 排序 combineRepeatedData(attrlist); // CombineRepeatedDatawithHash(attrlist); // 等同于上面方法,不同順序會再被打算。麻煩。 } // for } public static void combineRepeatedData(List<Interval> attrlist) { for ( int j=0; j<attrlist.size()-1 ;j++ ) { Interval inteFront = attrlist .get(j) ; Interval intevbehind = attrlist.get(j+1 ); List <Data> listFront = inteFront.intervallist; List <Data> listbehind = intevbehind.intervallist; Data dataFront = listFront.get(0 ); Data databehind = listbehind.get(0 ); while (databehind.value == dataFront.value &&(j<attrlist.size()-1) ) { // 屬性list已經排序,如果后面一個data值跟前面data相同,則合并到前面的。 attrlist.get(j).intervallist .addAll (listbehind); //用得不熟!! attrlist .remove (j +1 );
if ((j<attrlist.size()-1 )) { inteFront = attrlist.get(j); intevbehind = attrlist.get(j+1 ); listFront = inteFront.intervallist; listbehind = intevbehind.intervallist; dataFront = listFront.get(0 ); databehind = listbehind.get(0 ); } } } }
class IntervalComparator implements Comparator { // 升序了。 對list引用類型寫compartor排序方法很重要!! public int compare(Object arg0, Object arg1) { Interval i1 = (Interval)arg0; Interval i2 = (Interval)arg1; Data x1 = i1.intervallist.get(0); // 一開始所有區間就一個元素而已 Data x2 = i2.intervallist.get(0 ); int result = 0 ; if (x2.value< x1.value) {result = 1 ; } if (x2.value> x1.value) {result = -1 ; } return result; } }
?
第二步:合并區間:(直到剩下區間數目為6)
public static void chiMerge() { for ( int i=0; i<attributelists.length; i++ ){ List <Interval> attrlist = attributelists[i]; while (attrlist.size()>6){ // 最終的終止條件是形成6個區間 double minchisquare = 10000000; // 定義一個屬性里最小的卡方值 。。 變量放在的位置很重要,是放在循環里面還是外面很重要,就因為這個找錯誤還挑不出來,白花了兩個小時 int minchisquareindex =0; // 記住兩個區間最小卡方值的第一個區間在屬性list的下標 // 遍歷一個屬性的相鄰的兩個區間 for ( int j=0; j<attrlist.size()-1;j++){ // 遍歷一個屬性的每個兩個區間比較 Interval interval1 = attrlist.get(j); // 要比較兩個區間 Interval interval2 = attrlist.get(j+1 ); Matrixs matrixs = buildObseredandExpectedMatrixs (attrlist,interval1, interval2); // 返回了兩個observed,expected矩陣 double chisquarevalue = calchi (matrixs); // 計算兩個區間的卡方值 if (chisquarevalue < minchisquare ){ // 找最小的卡方值 minchisquare = chisquarevalue; minchisquareindex = j; // 表示當前最小的卡方值的兩個區間中第一個區間在該屬性list的下標位置 } } // for mergetwoIntervals( attrlist,minchisquareindex); // 合并第i個屬性list里的最小兩個區間。最終的合并! } // while } }
?
(1)?計算每一對相鄰區間的卡方值
public static double calchi(Matrixs matrixs) { double [][] observedMatrix = new double [2][3 ]; double [][] expectedMatrix = new double [2][3 ]; observedMatrix = matrixs.observedMatrix; expectedMatrix = matrixs.expectedMatrix; // 求卡方 int chisquarevalue =0 ; for ( int r=0; r<2; r++ ) { for ( int c=0;c<3;c++ ) { chisquarevalue += (observedMatrix[r][c]- expectedMatrix[r][c]) *(observedMatrix[r][c]- expectedMatrix[r][c]) / expectedMatrix[r][c] ; } } // System.out.println("卡方值:"+chisquarevalue); return chisquarevalue; } public static Matrixs buildObseredandExpectedMatrixs(List<Interval> attrlist,Interval interval1,Interval interval2) { // 返回兩個矩陣:obeserved和expected矩陣 // 建立observedMatrix double [][] observedMatrix = new double [2][3 ]; double [][] expectedMatrix = new double [2][3 ]; int [] linesum = new int [2] ; // 矩陣兩行的計算 int [] columnsum = new int [3]; // 矩陣三列都計算 linesum[ 0] = interval1.intervallist.size(); linesum[ 1] = interval2.intervallist.size(); int allsum = linesum[0] + linesum[1 ]; columnsum[ 0]= columnsum[1] = columnsum[2] = 0; // 初始化列 // 取第一個區間 for ( int k=0; k< interval1.intervallist.size() ; k++) { // 遍歷一個區間里所有元素 Data data = interval1.intervallist.get(k); if (data.classify.equals(classifies[0])) { // 是類別1:Iris-setosa columnsum[0]++ ; observedMatrix[ 0][0]++ ; } else if (data.classify.equals(classifies[1])) { // 是類別2:Iris-versicolor columnsum[1]++ ; observedMatrix[ 0][1]++ ; } else if (data.classify.equals(classifies[2])) { // 是類3 columnsum[2]++ ; observedMatrix[ 0][2]++ ; } } // for // 取第2個區間 for ( int k=0; k< interval2.intervallist.size() ; k++) { // 遍歷一個區間里所有元素 Data data = interval2.intervallist.get(k); if (data.classify.equals(classifies[0])) { // 是類別1:Iris-setosa columnsum[0]++ ; observedMatrix[ 1][0]++ ; } else if (data.classify.equals(classifies[1])) { // 是類別2:Iris-versicolor columnsum[1]++ ; observedMatrix[ 1][1]++ ; } else if (data.classify.equals(classifies[2])) { // 是類3 columnsum[2]++ ; observedMatrix[ 1][2]++ ; } } // for // 建立expectedMatrix for ( int r=0; r<2; r++ ) { for ( int c=0;c<3;c++ ) { expectedMatrix[r][c] = linesum[r] * columnsum[c] / allsum; if (expectedMatrix[r][c]==0.0 ) expectedMatrix[r][c] =0.0001; // 因為求卡方的時候,這個值會作分母,所以分母不能作0.分母變小,則卡方值就大,卡方值越大,越不相似,越不會被合并了 } } Matrixs matrixs = new Matrixs(); matrixs.expectedMatrix = expectedMatrix; matrixs.observedMatrix = observedMatrix; return matrixs; } } class Matrixs { public double [][] observedMatrix = new double [2][3 ]; public double [][] expectedMatrix = new double [2][3 ]; }
(2)?將上面卡方值最小的一對區間合并
public static void mergetwoIntervals(List<Interval> attrlist, int minchisquareindex) {
// List<Interval> attrlist =attributelists[0]; // 將當前最小的卡方值對應的兩個區間進行合并;刪去已被合并的區間 List<Data> mergedlist = attrlist.get(minchisquareindex+1).intervallist; // 被合并的區間里的數據list attrlist.get(minchisquareindex).intervallist.addAll(mergedlist); attrlist.get(minchisquareindex).maxvalue = attrlist.get(minchisquareindex+1).maxvalue; // 該區間的最大值是第二個區間的最大值,因為區間已經排過序了 attrlist.remove(minchisquareindex+1); // 該屬性刪去已被合并的區間 }
?
?
?第三步:輸出結果:6個區間的最大最小值
public static void printresult() { for ( int i=0; i<attributenum; i++ ){ System.out.println( "第"+(i+1)+"個屬性:" ); for ( int j=0; j<attributelists[i].size(); j++) { // 每個屬性是list,遍歷屬性list每一個元素 Interval in = attributelists[i].get(j); System.out.println( "( "+in.minvalue +" , " + in.maxvalue + " )" ); // 每個interval類里的list每個元素都是一個Data類型 } } }
?
?最終結果如下:
第1個屬性: ( 4.3 , 4.8 ) ( 4.9 , 5.2 ) ( 5.3 , 5.3 ) ( 5.4 , 6.9 ) ( 7.0 , 7.0 ) ( 7.1 , 7.9 ) 第2個屬性: ( 2.0 , 2.0 )( 2.2 , 2.2 ) ( 2.3 , 2.3 ) ( 2.4 , 3.5 ) ( 3.6 , 3.6 ) ( 3.7 , 4.4 ) 第3個屬性: ( 1.0 , 1.9 ) ( 3.0 , 4.4 ) ( 4.5 , 4.5 ) ( 4.6 , 4.7 ) ( 4.8 , 5.1 ) ( 5.2 , 6.9 ) 第4個屬性: ( 0.1 , 0.6 ) ( 1.0 , 1.5 ) ( 1.6 , 1.6 ) ( 1.7 , 1.7 ) ( 1.8 , 1.8 ) ( 1.9 , 2.5 )
?
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
