利用 ChiMerge 分析鸢尾花資料集

ChiMerge 是監督的、自底向上的(即基于合并的)資料離散化方法。

它依賴于卡方分析：具有最小卡方值的相鄰區間合并在一起，直到滿足确定的停止準則。

基本思想

對于精确的離散化，相對類頻率在一個區間内應當完全一緻。

是以，如果兩個相鄰的區間具有非常類似的類分布，則這兩個區間可以合并；否則，它們應當保持分開。

而低卡方值表明它們具有相似的類分布。

要點

• 最簡單的離散算法： 等寬區間

  從最小值到最大值之間,均分為N等份

  如此， 若 A, B為min/max， 則每個區間的長度為w=(B-A) / N, 區間邊界值為 A+W, A+2W, …. A+(N-1)W

• 類似的一種算法: 等頻區間

  間隔邊界被選擇為使得每個間隔包含大約相同數量的訓練示例

  是以，如果N = 10，每個區間将包含大約10％的例子

以上兩種簡單算法有弊端

• 等寬區間劃分，劃分為5區間，最高工資50000，則所有工資低于10000的人都被劃分到同一區間
• 等頻區間可能正好相反，所有工資高于50000的人都會被劃分到50000這一區間中。

這兩種算法都忽略了執行個體所屬的類型，落在正确區間裡的偶然性很大

• C4、CART、PVM算法在離散屬性時會考慮類資訊，但随着算法的運作動态執行，而不是在預處理階段。

  例如，C4算法（ID3決策樹系列的一種），将數值屬性離散為兩個區間，而取這兩個區間時，該屬性的資訊增益是最大的。

• 評價一個離散算法是否有效很難，因為不知道什麼是最高效的分類

• 離散化的主要目的

  除了從訓練資料中消除數值之外，還要産生一個簡潔的數字屬性彙總

• 高品質的離散化

  區間内均勻性,區間間差異

• ChiMerge算法用卡方統計量來決定相鄰區間的頻率明顯不同,如果它們足夠相似以證明合并它們
• ChiMerge算法包括兩步,當滿足停止條件的時候，區間合并停止

  • 初始化

    根據要離散的屬性對執行個體進行排序：每個執行個體屬于一個區間

  • 合并區間，又包括兩步

    (1) 計算每一對相鄰區間的卡方值

    (2) 将卡方值最小的一對區間合并

預先設定一個卡方的門檻值，在門檻值之下的區間都合并，門檻值之上的區間保持分區間

卡方的計算公式

參數說明

• m=2（每次比較的區間數是2個）
• k=類的數量
• Aij=第i區間第j類的執行個體的數量
• Ri=第i區間的執行個體數量

  

• Cj=第j類的執行個體數量

  

• N=總的執行個體數量

  

• Eij= Aij的期望頻率

  

• 卡方門檻值的确定

  先選擇顯著性水準，再由公式得到對應的卡方值。

  得到卡方值需要指定自由度，自由度比類别數量小1。例如，有3類，自由度為2，則90%置信度（10%顯著性水準)下，卡方的值為4.6。

  門檻值的意義在于，類和屬性獨立時，有90%的可能性，計算得到的卡方值會小于4.6，這樣，大于門檻值的卡方值就說明屬性和類不是互相獨立的，不能合并。如果門檻值選的大，區間合并就會進行很多次，離散後的區間數量少、區間大。

  使用者可以不考慮卡方門檻值，此時，使用者可以考慮這兩個參數：最小區間數，最大區間數。使用者指定區間數量的上限和下限，最多幾個區間，最少幾個區間。

• ChiMerge算法推薦使用.90、.95、.99置信度，最大區間數取10到15之間以防止

  過多的間隔被建立

實戰

取鸢尾花資料集作為待離散化的資料集合，使用ChiMerge算法，對四個數值屬性分别進行離散化

令停機準則為

max_interval=6

下面Python程式

資料集

大緻分兩步：

整理資料

讀入鸢尾花資料集，構造可以在其上使用ChiMerge的資料結構，即, 形如

[

('4.3', [1, 0, 0]),

('4.4', [3, 0, 0]),

...]

的清單，每一個元素是一個元組，元組的第一項是字元串，表示區間左端點，元組的第二項是一個清單，表示在此區間各個類别的執行個體數目；

離散化

使用ChiMerge方法對具有最小卡方值的相鄰區間進行合并，直到滿足最大區間數(max_interval)為6

程式最終傳回區間的分裂點

# coding=utf-8
from time import ctime

''' 讀取資料'''


def read(irisdata):
    instances = []
    fp = open(irisdata, 'r')
    for line in fp:
        line = line.strip('\n')
        if line != '':
            instances.append(line.split(','))
    fp.close()
    return instances


''' 将第i個特征和類标簽組合起來
 如:
    [ 
      [0.2,'Iris-setosa'],
      [0.2,'Iris-setosa'],
                ...
                          ]'''


def split(instances, i):
    log = []
    for line in instances:
        log.append([line[i], line[4]])
    return log


''' 統計每個屬性值所具有的執行個體數量
 [['4.3', 'Iris-setosa', 1], ['4.4', 'Iris-setosa', 3],...]'''


def count(log):
    log_cnt = []
    # 以第0列進行排序的 升序排序
    log.sort(key=lambda attr: attr[0])
    i = 0
    while i < len(log):
        cnt = log.count(log[i])
        record = log[i][:]
        record.append(cnt)
        log_cnt.append(record)
        i += cnt
    return log_cnt


''' log_cnt  是形如： ['4.4', 'Iris-setosa', 3] 
    的統計對于某個屬性值，對于三個類所含有的數量
    傳回結果形如：{4.4:[0,1,3],...} 
    屬性值為4.4的對于三個類的執行個體數量分别是：0、1、3 '''


def build(log_cnt):
    log_dict = {}
    for record in log_cnt:
        if record[0] not in log_dict.keys():
            log_dict[record[0]] = [0, 0, 0]
        if record[1] == 'Iris-setosa':
            log_dict[record[0]][0] = record[2]
        elif record[1] == 'Iris-versicolor':
            log_dict[record[0]][1] = record[2]
        elif record[1] == 'Iris-virginica':
            log_dict[record[0]][2] = record[2]
        else:
            raise TypeError('Data Exception')
    log_truple = sorted(log_dict.items())
    return log_truple


def collect(instances, i):
    log = split(instances, i)
    log_cnt = count(log)
    log_tuple = build(log_cnt)
    return log_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[:]
    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 = []
    '''第i個區間的執行個體數'''
    for i in range(m):
        sum = 0
        for j in range(k):
            sum += a[i][j]
        r.append(sum)
    c = []
    '''第j個類的執行個體數'''
    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
    res = 0.0
    for i in range(m):
        for j in range(k):
            Eij = 1.0 * r[i] * c[j] / n
            if Eij != 0:
                res = 1.0 * res + 1.0 * (a[i][j] - Eij) ** 2 / Eij
    return res


'''ChiMerge 算法'''
'''下面的程式可以看出，合并一個區間之後相鄰區間的卡方值進行了重新計算，而原作者論文中是計算一次後根據大小直接進行合并的
下面在合并時候隻是根據相鄰最小的卡方值進行合并的，這個在實際操作中還是比較好的
'''


def chimerge(log_tuple, max_interval):
    num_interval = len(log_tuple)
    while num_interval > max_interval:
        num_pair = num_interval - 1
        chi_values = []
        ''' 計算相鄰區間的卡方值'''
        for i in range(num_pair):
            arr = [log_tuple[i][1], log_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:
                log_tuple[i] = combine(log_tuple[i], log_tuple[i + 1])
                log_tuple[i + 1] = 'Merged'
        while 'Merged' in log_tuple:
            log_tuple.remove('Merged')
        num_interval = len(log_tuple)
    split_points = [record[0] for record in log_tuple]
    return split_points


def discrete(path):
    instances = read(path)
    max_interval = 6
    num_log = 4
    for i in range(num_log):
        log_tuple = collect(instances, i)
        split_points = chimerge(log_tuple, max_interval)
        print split_points


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

           

函數說明

• collect(Instances,i)

  讀入鸢尾花資料集，取第i個特征構造一個資料結構，以便使用ChiMerge算法。這個資料結構 形如 [('4.3', [1, 0, 0]), ('4.4', [3, 0, 0]),...]的清單，每一個元素是一個元組，元組的第一項是字元串，表示區間左端點，元組的第二項是一個清單，表示在此區間各個類别的執行個體數目

• ChiMerge(log_tuple,max_interval)

  ChiMerge算法，傳回區間的分裂點

程式運作結果

參考文獻

http://www.aaai.org/Papers/AAAI/1992/AAAI92-019.pdf