ChiMerge演算法：卡方檢驗+ChiMerge+Python

• 2021 年 1 月 6 日
• AI
• Python, 演算法

卡方分布與卡方檢驗

卡方分布

• 定義
  • 若n個相互獨立的隨機變數\xi_{1},\xi_{2},\dots,\xi_{n}均服從標準正態分布，則這n個服從標準正態分布的隨機變數的平方和Q=\sum_{i=1}^{n}\xi_{i}^{2} 構成一個新的隨機變數，其分布規律稱為\chi_{2}分布（chi-square distribution），記為Q滿足自由度為v的\chi_{2}分布Q \sim \chi^{2}(v)Q \sim \chi^{2}_{v}（其中v=n-k，k為限制條件數）；
  • 卡方分布是由正態分布構造而成的一個新的分布，當自由度v很大時，卡方分布近似為正態分布。
• 概率密度函數
  • 
  • f(x ; k)=\left\{\begin{array}{ll} \frac{x^{(k / 2)-1} e^{-x / 2}}{2^{k / 2} \Gamma\left(\frac{k}{2}\right)}, & x \geq 0 \\ 0, & \text { otherwise } \end{array}\right.
  • 其中，\Gamma (\frac {k}{2})是伽瑪函數；
  • 均值為自由度v，記為 E(\chi^{2})=v；
  • 方差為2倍的自由度:2v，記為D(\chi^{2}=2v。
• 性質
  • \chi_{2}分布在第一象限內，卡方值都是正值，隨著參數v的增大，\chi_{2}分布趨近於正態分布；
  • 卡方分布密度曲線下的面積都是1；
  • 隨著自由度v的增大，\chi_{2}分布向正無窮方向延伸（因為均值v越來越大），分布曲線也越來越低闊（因為方差2v越來越大）。
  • 不同的自由度決定不同的卡方分布，自由度越小，分布越偏斜；自由度越大，該函數影像越對稱；
  • 若\chi_{2}(v_2)，\chi_{2}(v_2)互相獨立，則\chi_{2}(v_2)+\chi_{2}(v_2)服從\chi_{2}分布，自由度為v_1+v_2。
• OneMoreThing（有待商榷）："為什麼這裡\xi需要正態分布，我的理解是，如果零假設為真，那麼觀測值和期望值之間的波動程度，應該是正態分布的，或者說「雜訊」應該是正態分布的。"源自卡方檢驗詳解

卡方\chi^{2}檢驗

• 基本原理：卡方檢驗就是統計樣本的實際觀測值與理論推斷值之間的偏離程度，實際觀測值與理論推斷值之間的偏離程度就決定卡方值的大小，如果卡方值越大，二者偏差程度越大；反之，二者偏差越小；若兩個值完全相等時，卡方值就為0，表明理論值完全符合。
• 首先假設H_0（觀察頻數與期望頻數沒有差別）成立，基於此前提計算出\chi^{2}值。如果\chi^{2}值「小」，傾向於接受H_0；如果\chi^{2}值大，就傾向於拒絕H_0。至於\chi^{2}在每個具體研究中究竟要大到什麼程度(置信度)才能拒絕\chi^{2}，則要藉助於卡方分布與自由度確定所對應的P值。
• \chi^{2}值計算
  • 設A代表某個類別的觀察頻數，E代表基於H_0計算出的期望頻數，A與E之差稱為殘差；
  • 殘差可以表示某一個類別觀察值和理論值的偏離程度，由於殘差有正有負，相加後會彼此抵消，為此可以將殘差平方後求和；
  • 殘差大小是一個相對概念，相對於期望頻數為10時，期望頻數為20的殘差非常大，但相對於期望頻數為1000時20的殘差就很小了，為此，將殘差平方除以期望頻數再求和，以估計觀察頻數與期望頻數的差別。
  • \chi^{2}=\sum \frac{(A-E)^{2}}{E}=\sum_{i=1}^{k} \frac{\left(A_{i}-E_{i}\right)^{2}}{E_{i}} \quad(i=1,2,3, \ldots, k)
• 檢驗的應用
  • 擬合優度檢驗（chi-squared test goodness of fit）
    • 實際執行多次試驗得到的觀察次數，與期望次數相比較，稱為卡方適度檢驗，即在於檢驗二者接近的程度，利用樣本數據以檢驗總體分布是否為某一特定分布的統計方法；
    • 零假設：觀察分布等於期望分布；
    • \chi^{2}=\sum_{i=1}^{k} \frac{\left(A_{i}-n p_{i}\right)^{2}}{n p_{i}} \quad(i=1,2,3, \ldots, k)
    • 其中，n為總頻數，p_i為i水平的期望頻率,i水平的期望頻數E_i等於總頻數n×i水平的期望概率p_i;
    • 確定自由度；選擇顯著性水平；
    • 比較臨界值和統計量（\chi^{2}值），若臨界值大於統計量，差異不顯著，接受零假設；否則拒絕。
  • 獨立性檢驗（chi-squared test of independence)
    • 卡方獨立性檢驗是用來檢驗兩個屬性間是否獨立，以一個變數為行，另一個變數為列，組成相依表；
    • 零假設：兩者相互獨立，這樣相依表的分布應該滿足乘法公式，即兩個獨立事件一起發生的概率等於分別發生的概率之積；
    • \chi^{2}=\sum_{i=1}^{c} \sum_{j=1}^{r} \frac{\left(o_{i j}-e_{i j}\right)^{2}}{e_{i j}}，其中o_{i j}是聯合事件(A_i,B_j)的觀測頻度（即實際計數），e_{i j}是(A_i,B_j)的期望頻度，e_{i j}=\frac{\operatorname{count}\left(A=a_{i}\right) \times \operatorname{count}\left(B=b_{j}\right)}{n}，其中n是總計數，\operatorname{count}\left(A=a_{i}\right)是A中具有值a_i的個數，\operatorname{count}\left(B=b_{j}\right)是B中具有值b_j的個數；
    • 根據\chi ^2分布的百分點表，查找自由度(r-1)\times(c-1)下的顯著水平，計算\chi^{2}值大於該值，拒絕假設，兩屬性相關，反之獨立。
  • 卡方檢驗的樣本量要求：一般認為對於卡方檢驗中的每一個單元格，要求其最小期望頻數均大於1，且至少有4／5的單元格期望頻數大於5，此時使用卡方分布計算出的概率值才是準確的。如果數據不符合要求，可以採用確切概率法進行概率的計算。

Python實現

見卡方分布、卡方獨立性檢驗和擬合性檢驗理論及其python實現

ChiMerge演算法

演算法原理

• ChiMerge 是監督的、自底向上的(即基於合併的)數據離散化方法。它依賴於卡方\chi^{2}檢驗：具有最小卡方值的相鄰區間合併在一起，直到滿足確定的停止準則。
• 高品質的離散化應該是：區間內一致，區間之間區分明顯。
• ChiMerge演算法流程
  • 初始化：根據要離散的屬性對實例進行排序：將數值屬性的每個值看作一個區間(左閉右開)；
  • 自底向上區間合併，當滿足停止條件的時候（高於預定卡方閾值），停止合併。
    • 計算每一對相鄰區間的卡方值；
    • 
    • 將卡方值最小的一對區間合併。
• 卡方閾值的選擇：先選擇顯著性水平，再由公式得到對應的卡方值。得到卡方值需要指定自由度，自由度比類別數量小1。例如，有3類，自由度為2，則90%置信度（10%顯著性水平)下，卡方的值為4.6。閾值的意義在於，類別和屬性獨立時，有90%的可能性，計算得到的卡方值會小於4.6，這樣，大於閾值的卡方值就說明屬性和類不是相互獨立的，不能合併。如果閾值選的大，區間合併就會進行很多次，離散後的區間數量少、區間大。
• ChiMerge演算法推薦使用0.90、0.95、0.99置信度，最大區間數取10到15之間。
• 下圖以部分iris數據集的sepal-length屬性為例，計算不同區間的\chi_{2}值，將其與預定義閾值比較，合併低於預定義閾值的區間。
• 

Python實現

• 數據集：iris數據集，見下圖。
• 

from collections import Counter
from time import ctime
 
def read(file):
    list_data=[]
    with open(file, 'r', encoding='utf-8') as fp:
        for line in fp:
            line=line.strip()
            if line!='':
                list_data.append(line.split(','))
    return list_data

def stas_count(list_data,i):
    ''' 統計將每個屬性具體對應的類別，
     返回形如[['4.3', 'Iris-setosa', 1], ['4.4', 'Iris-setosa', 3],...]的列表'''
    list_vc=[] # list_value+class
    for r in list_data:
        list_vc.append(str(r[i]+','+r[4]))

    list_vcc=[] # list_value-class-count
    for k,v in dict(Counter(list_vc)).items():
        list_tmp = k.split(',')
        list_tmp.append(v)
        list_vcc.append(list_tmp)
 
    return list_vcc
 
def collect(list_data,i):
    '''根據第i個屬性特徵構造一個數據結構，以便使用ChiMerge演算法。
    這個數據結構是形如 [('4.3', [1, 0, 0]), ('4.4', [3, 0, 0]),...]的列表，
    每一個元素是一個元組，
    元組的第一項是字元串，表示區間左端點，元組的第二項是一個列表，表示在此區間各個類別的實例數目'''
    list_cvv=stas_count(list_data,i)
    log_dic={}
    for record in list_cvv:
        if record[0] not in log_dic.keys():
            log_dic[record[0]]=[0,0,0]
        if record[1]=='Iris-setosa':
            log_dic[record[0]][0]=record[2]
        elif record[1]=='Iris-versicolor':
            log_dic[record[0]][1]=record[2]
        elif record[1]=='Iris-virginica':
            log_dic[record[0]][2]=record[2]
        else:
            raise TypeError("Data Exception")
    list_tuple=sorted(log_dic.items())
    
    return list_tuple
 
 
def combine(a,b):
    '''  a=('4.4', [3, 1, 0]), b=('4.5', [1, 0, 2])
         combine(a,b)=('4.4', [4, 1, 2])  '''
    c=a[:] # c[0]=a[0]
    for i in range(len(a[1])):
        c[1][i]+=b[1][i]
    return c

def chi2(A):
    m=len(A)
    k=len(A[0])
    R=[]
    for i in range(m):
        sum=0
        for j in range(k):
            sum+=A[i][j]
        R.append(sum)
    C=[]
    for j in range(k):
        sum=0
        for i in range(m):
            sum+=A[i][j]
        C.append(sum)
    N=0
    for ele in C:
        N+=ele
    M=0
    for ele in R:
        M+=ele
    assert  M==N
    res=0
    for i in range(m):
        for j in range(k):
            Eij=R[i]*C[j]/N
            if Eij!=0:
                res=res+(A[i][j]-Eij)**2/Eij
    return res

def ChiMerge(list_tuple,max_interval):
    num_interval=len(list_tuple)
    while num_interval>max_interval:               
        num_pair=num_interval-1 # 需兩兩配對，故減1
        chi_values=[]
        for i in range(num_pair):
            arr=[list_tuple[i][1],list_tuple[i+1][1]]
            chi_values.append(chi2(arr))
        min_chi=min(chi_values) # 最小卡方值
        for i in range(num_pair-1,-1,-1): # 合併最小值相鄰區間
            if chi_values[i]==min_chi:
                list_tuple[i]=combine(list_tuple[i],list_tuple[i+1])
                list_tuple[i+1]='Merged'
        while 'Merged' in list_tuple:
            list_tuple.remove('Merged')
        num_interval=len(list_tuple)
    split_points=[record[0] for record in list_tuple]
    
    return split_points


def run(path):
    list_iris =read(path)
    max_interval=6 # 離散化區間個數
    num_attr=4 # 屬性類別
    for i in range(num_attr):
        list_tuple=collect(list_iris,i)
        split_points=ChiMerge(list_tuple,max_interval) # discretize data using ChiMerge algorithm 
        print(split_points)
 

if __name__=='__main__':
    print('Start: ' + ctime())
    run('iris.data')
    print('End: ' + ctime())

參考

1. 卡方檢驗詳解 //www.jianshu.com/p/fcfac399de13
2. 卡方檢驗 //blog.csdn.net/qunxingvip/article/details/50447864
3. 卡方分布、卡方獨立性檢驗和擬合性檢驗理論及其python實現 //www.cnblogs.com/Yuanjing-Liu/p/9252844.html
4. ChiMerge演算法 //markdown.blog.csdn.net/article/details/50449376?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.control&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromBaidu-1.control
5. ChiMerge: Discretization of Numeric Attribute //www.aaai.org/Papers/AAAI/1992/AAAI92-019.pdf