亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

ChiMerge算法 (java)

系統 2497 0

韓家煒 數據挖掘概念與技術 第三版 習題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的總個數 )
?
? expectedmatrix[i][j]是由上面 observedmatrix所得, expectedmatrix[i][j]= (obser矩陣的i行1的總個數* j列1的總個數)/(observ矩陣里1的總個數)?
?expectedmatrix:
區間: 類別 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行3列矩陣,所以一共卡方迭加了2*3=6次; ( observedmatrix[i][j]- expectedmatrix[i][j])/? expectedmatrix[i][j]
所以 ?chisquare = (1-0.25)^2 /0.25 + (0-0.25)^2/0.25 +(0-0.5)^2/0.5 + (0-0.75)^2/0.75 + (1-0.25)^2/0.25 + (2-1.5)^2/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 )
    

?

?

?

ChiMerge算法 (java)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

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

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: www天天干| 亚洲国产日产韩国欧美综合 | 亚洲国产精品综合久久久 | 欧美极品福利视频在线播放 | 国产精品美女久久久久网 | 青春草禁区视频在线观看 | 欧美黄色免费在线观看 | 精品成人久久 | 九九热免费观看 | 羞羞视频网站 | 国产精品国语自产拍在线观看 | 国产xxxx做受性欧美88 | 亚洲va久久久噜噜噜久久男同 | 国产原创精品 | 色综合久久天天综合绕观看 | 欧美视频在线看 | 久久福利青草精品免费 | 在线播放福利 | 亚洲国产男人本色在线观看的a站 | 久久99热久久精品23 | 国产原创精品 | 免费在线激情视频 | 国产成人精品综合 | 日本精品一区二区三区在线 | 国产热热| 热99久久| 在线综合视频 | 日本在线精品 | 九九伦理影院手机观看 | 97在线看| 久久黄色精品视频 | 天天色天天干天天 | 天天操天天干天天摸 | 久久久精品久久久久久久久久久 | 久草看片| 色色在线视频 | 日韩三级 | 婷婷色在线观看 | 国产欧美综合一区二区 | 精品国产一区二区 | 99精品国产兔费观看66 |