655
文本挖掘之特征選擇（Python版）
機器學習算法的空間、時間複雜度依賴於輸入數據的規模，維度規約(Dimensionality reduction)則是一種被用於降低輸入數據維數的方法。維度規約可以分為兩類：
- 特征選擇(feature selection)，從原始的d維空間中，選擇為我們提供信息最多的k個維(這k個維屬於原始空間的子集)
- 特征提取(feature extraction)，將原始的d維空間映射到k維空間中(新的k維空間不輸入原始空間的子集)
在文本挖掘與文本分類的有關問題中，常采用特征選擇方法。原因是文本的特征一般都是單詞(term)，具有語義信息，使用特征選擇找出的k維子集，仍然是單詞作為特征，保留了語義信息，而特征提取則找k維新空間，將會喪失了語義信息。
對於一個語料而言，我們可以統計的信息包括文檔頻率和文檔類比例，所有的特征選擇方法均依賴於這兩個統計量，目前，文本的特征選擇方法主要有：DF, MI, IG, CHI，WLLR,WFO六種。
為了方便描述，我們首先一些概率上的定義：
p(t):一篇文檔x包含特征詞t的概率。
:文檔x不屬於Ci的概率。
p(Ci|t):已知文檔x的包括某個特征詞t條件下，該文檔屬於Ci的概率
: 已知文檔屬於Ci 條件下，該文檔不包括特征詞t的概率
類似的其他的一些概率如p(Ci), 
，
等，有著類似的定義。
為了估計這些概率，我們需要通過統計訓練樣本的相關頻率信息，如下表：
其中：
Aij: 包含特征詞ti，並且類別屬於Cj的文檔數量 Bij: 包含特征詞ti，並且類別屬於不Cj的文檔數量
Cij：不包含特征詞ti，並且類別屬於Cj的文檔數量 Dij：不包含特征詞ti，並且類別屬於不Cj的文檔數量
Aij + Bij: 包含特征詞ti的文檔數量 Cij + Dij：不包含特征詞ti的文檔數量
Aij + Cij：Cj類的文檔數量數據 Bij + Dij：非Cj類的文檔數量數據
Aij + Bij + Cij + Dij = N :語料中所有文檔數量。
有了這些統計量，有關概率的估算就變得容易，如：
p(ti) = (Aij + Bij) / N; p(Cj) = (Aij + Cij) / N;
p(Cj|tj) = Aij / (Aij + Bij)
......類似的一些概率計算可以依照上表計算。
介紹了事情發展的前因，現在進入正題：常見的四種特征選擇方法如何計算。
1）DF(Document Frequency)
DF:統計特征詞出現的文檔數量，用來衡量某個特征詞的重要性，DF的定義如下：
DF的動機是，如果某些特征詞在文檔中經常出現，那麼這個詞就可能很重要。而對於在文檔中出現很少(如僅在語料中出現1次)特征詞，攜帶了很少的信息量，甚至是"噪聲"，這些特征詞，對分類器學習影響也是很小。
DF特征選擇方法屬於無監督的學習算法(也有將其改成有監督的算法，但是大部分情況都作為無監督算法使用)，僅考慮了頻率因素而沒有考慮類別因素，因此，DF算法的將會引入一些沒有意義的詞。如中文的"的"、"是"， "個"等，常常具有很高的DF得分，但是，對分類並沒有多大的意義。
2）MI(Mutual Information)
互信息法用於衡量特征詞與文檔類別直接的信息量，互信息法的定義如下：
繼續推導MI的定義公式：
從上麵的公式上看出：如果某個特征詞的頻率很低，那麼互信息得分就會很大，因此互信息法傾向"低頻"的特征詞。相對的詞頻很高的詞，得分就會變低，如果這詞攜帶了很高的信息量，互信息法就會變得低效。
3）IG(Information Gain)
信息增益法，通過某個特征詞的缺失與存在的兩種情況下，語料中前後信息的增加，衡量某個特征詞的重要性。
信息增益的定義如下：
依據IG的定義，每個特征詞ti的IG得分前麵一部分：
計算值是一樣，可以省略。因此，IG的計算公式如下：
IG與MI存在關係：
因此，IG方式實際上就是互信息
與互信息
加權。
4）CHI(Chi-square)
CHI特征選擇算法利用了統計學中的"假設檢驗"的基本思想：首先假設特征詞與類別直接是不相關的，如果利用CHI分布計算出的檢驗值偏離閾值越大，那麼更有信心否定原假設，接受原假設的備則假設：特征詞與類別有著很高的關聯度。CHI的定義如下：
對於一個給定的語料而言，文檔的總數N以及Cj類文檔的數量，非Cj類文檔的數量，他們都是一個定值，因此CHI的計算公式可以簡化為：
CHI特征選擇方法，綜合考慮文檔頻率與類別比例兩個因素
5）WLLR(Weighted Log Likelihood Ration)
WLLR特征選擇方法的定義如下：
計算公式如下：
6)WFO（Weighted Frequency and Odds）
最後一個介紹的算法，是由蘇大李壽山老師提出的算法。通過以上的五種算法的分析，李壽山老師認為，"好"的特征應該有以下特點：
- 好的特征應該有較高的文檔頻率
- 好的特征應該有較高的文檔類別比例
WFO的算法定義如下：
如果
：
否則：
不同的語料，一般來說文檔詞頻與文檔的類別比例起的作用應該是不一樣的，WFO方法可以通過調整參數
，找出一個較好的特征選擇依據。
-----------------------------------------分割線---------------------------------------------
介紹完理論部分，就要給出代碼了（隻給出公式，不給出代碼的都是調戲良家的行為~）。文本挖掘之文本表示一文，利用了sklearn開源工具，自然先首先sklearn工具，可惜的是sklearn文本的特征選擇方法僅提供了CHI一種。為此在sklearn框架下，嚐試自己編寫這些特征選擇方法的代碼，自己動手，豐衣足食。
筆者實現了三種特征選擇方法：IG,MI和WLLR，看官如果對其他特征選擇方法感興趣，可以嚐試實現一下~ 好了，啥也不說了，上代碼，特征選擇模塊代碼：
#!/usr/bin/env python # coding=gbk import os import sys import numpy as np def get_term_dict(doc_terms_list): term_set_dict = {} for doc_terms in doc_terms_list: for term in doc_terms: term_set_dict[term] = 1 term_set_list = sorted(term_set_dict.keys()) #term set 排序後，按照索引做出字典 term_set_dict = dict(zip(term_set_list, range(len(term_set_list)))) return term_set_dict def get_class_dict(doc_class_list): class_set = sorted(list(set(doc_class_list))) class_dict = dict(zip(class_set, range(len(class_set)))) return class_dict def stats_term_df(doc_terms_list, term_dict): term_df_dict = {}.fromkeys(term_dict.keys(), 0) for term in term_set: for doc_terms in doc_terms_list: if term in doc_terms_list: term_df_dict[term] +=1 return term_df_dict def stats_class_df(doc_class_list, class_dict): class_df_list = [0] * len(class_dict) for doc_class in doc_class_list: class_df_list[class_dict[doc_class]] += 1 return class_df_list def stats_term_class_df(doc_terms_list, doc_class_list, term_dict, class_dict): term_class_df_mat = np.zeros((len(term_dict), len(class_dict)), np.float32) for k in range(len(doc_class_list)): class_index = class_dict[doc_class_list[k]] doc_terms = doc_terms_list[k] for term in set(doc_terms): term_index = term_dict[term] term_class_df_mat[term_index][class_index] +=1 return term_class_df_mat def feature_selection_mi(class_df_list, term_set, term_class_df_mat): A = term_class_df_mat B = np.array([(sum(x) - x).tolist() for x in A]) C = np.tile(class_df_list, (A.shape[0], 1)) - A N = sum(class_df_list) class_set_size = len(class_df_list) term_score_mat = np.log(((A+1.0)*N) / ((A+C) * (A+B+class_set_size))) term_score_max_list = [max(x) for x in term_score_mat] term_score_array = np.array(term_score_max_list) sorted_term_score_index = term_score_array.argsort()[: : -1] term_set_fs = [term_set[index] for index in sorted_term_score_index] return term_set_fs def feature_selection_ig(class_df_list, term_set, term_class_df_mat): A = term_class_df_mat B = np.array([(sum(x) - x).tolist() for x in A]) C = np.tile(class_df_list, (A.shape[0], 1)) - A N = sum(class_df_list) D = N - A - B - C term_df_array = np.sum(A, axis = 1) class_set_size = len(class_df_list) p_t = term_df_array / N p_not_t = 1 - p_t p_c_t_mat = (A + 1) / (A + B + class_set_size) p_c_not_t_mat = (C+1) / (C + D + class_set_size) p_c_t = np.sum(p_c_t_mat * np.log(p_c_t_mat), axis =1) p_c_not_t = np.sum(p_c_not_t_mat * np.log(p_c_not_t_mat), axis =1) term_score_array = p_t * p_c_t + p_not_t * p_c_not_t sorted_term_score_index = term_score_array.argsort()[: : -1] term_set_fs = [term_set[index] for index in sorted_term_score_index] return term_set_fs def feature_selection_wllr(class_df_list, term_set, term_class_df_mat): A = term_class_df_mat B = np.array([(sum(x) - x).tolist() for x in A]) C_Total = np.tile(class_df_list, (A.shape[0], 1)) N = sum(class_df_list) C_Total_Not = N - C_Total term_set_size = len(term_set) p_t_c = (A + 1E-6) / (C_Total + 1E-6 * term_set_size) p_t_not_c = (B + 1E-6) / (C_Total_Not + 1E-6 * term_set_size) term_score_mat = p_t_c * np.log(p_t_c / p_t_not_c) term_score_max_list = [max(x) for x in term_score_mat] term_score_array = np.array(term_score_max_list) sorted_term_score_index = term_score_array.argsort()[: : -1] term_set_fs = [term_set[index] for index in sorted_term_score_index] print term_set_fs[:10] return term_set_fs def feature_selection(doc_terms_list, doc_class_list, fs_method): class_dict = get_class_dict(doc_class_list) term_dict = get_term_dict(doc_terms_list) class_df_list = stats_class_df(doc_class_list, class_dict) term_class_df_mat = stats_term_class_df(doc_terms_list, doc_class_list, term_dict, class_dict) term_set = [term[0] for term in sorted(term_dict.items(), key = lambda x : x[1])] term_set_fs = [] if fs_method == 'MI': term_set_fs = feature_selection_mi(class_df_list, term_set, term_class_df_mat) elif fs_method == 'IG': term_set_fs = feature_selection_ig(class_df_list, term_set, term_class_df_mat) elif fs_method == 'WLLR': term_set_fs = feature_selection_wllr(class_df_list, term_set, term_class_df_mat) return term_set_fs
在movie語料裏麵比較著三種特征選擇方法，調用方法如下：
#!/usr/bin/env python # coding=gbk import os import sys import numpy as np import matplotlib.pyplot as plt from sklearn.datasets import load_files from sklearn.cross_validation import train_test_split from sklearn.feature_extraction.text import CountVectorizer from sklearn.naive_bayes import MultinomialNB import feature_selection def text_classifly_twang(dataset_dir_name, fs_method, fs_num): print 'Loading dataset, 80% for training, 20% for testing...' movie_reviews = load_files(dataset_dir_name) doc_str_list_train, doc_str_list_test, doc_class_list_train, doc_class_list_test = train_test_split(movie_reviews.data, movie_reviews.target, test_size = 0.2, random_state = 0) print 'Feature selection...' print 'fs method:' + fs_method, 'fs num:' + str(fs_num) vectorizer = CountVectorizer(binary = True) word_tokenizer = vectorizer.build_tokenizer() doc_terms_list_train = [word_tokenizer(doc_str) for doc_str in doc_str_list_train] term_set_fs = feature_selection.feature_selection(doc_terms_list_train, doc_class_list_train, fs_method)[:fs_num] print 'Building VSM model...' term_dict = dict(zip(term_set_fs, range(len(term_set_fs)))) vectorizer.fixed_vocabulary = True vectorizer.vocabulary_ = term_dict doc_train_vec = vectorizer.fit_transform(doc_str_list_train) doc_test_vec= vectorizer.transform(doc_str_list_test) clf = MultinomialNB().fit(doc_train_vec, doc_class_list_train) #調用MultinomialNB分類器 doc_test_predicted = clf.predict(doc_test_vec) acc = np.mean(doc_test_predicted == doc_class_list_test) print 'Accuracy: ', acc return acc if __name__ == '__main__': dataset_dir_name = sys.argv[1] fs_method_list = ['IG', 'MI', 'WLLR'] fs_num_list = range(25000, 35000, 1000) acc_dict = {} for fs_method in fs_method_list: acc_list = [] for fs_num in fs_num_list: acc = text_classifly_twang(dataset_dir_name, fs_method, fs_num) acc_list.append(acc) acc_dict[fs_method] = acc_list print 'fs method:', acc_dict[fs_method] for fs_method in fs_method_list: plt.plot(fs_num_list, acc_dict[fs_method], '--^', label = fs_method) plt.title('feature selection') plt.xlabel('fs num') plt.ylabel('accuracy') plt.ylim((0.82, 0.86)) plt.legend( loc='upper left', numpoints = 1) plt.show()
輸出的結果：
從上麵的圖看出：分類的性能隨著特征選擇的數量的增加，呈現“凸”形趨勢：1）在特征數量較少的情況下，不斷增加特征的數量，有利於提高分類器的性能，呈現“上升”趨勢；2）隨著特征數量的不斷增加，將會引入一些不重要的特征，甚至是噪聲，因此，分類器的性能將會呈現“下降”的趨勢。這張“凸”形趨勢體現出了特征選擇的重要性：選擇出重要的特征，並降低噪聲，提高算法的泛化能力。
參數文獻：
1.Y. Yang and J. Pedersen. 1997. A comparative study on feature selection in text categorization.
2.Shoushan Li, Rui Xia, Chengqing Zong and Chu-Ren Huang.2009.A Framework of Feature Selection Methods for Text Categorization
3.老板的課件
最後更新：2017-04-26 17:31:25