機(jī)器學(xué)習(xí)算法實(shí)踐：樸素貝葉斯 (Naive Bayes)
前言
上一篇《機(jī)器學(xué)習(xí)算法實(shí)踐：決策樹 (Decision Tree)》總結(jié)了決策樹的實(shí)現(xiàn)，本文中我將一步步實(shí)現(xiàn)一個(gè)樸素貝葉斯分類器，并采用SMS垃圾短信語料庫中的數(shù)據(jù)進(jìn)行模型訓(xùn)練，對(duì)垃圾短信進(jìn)行過濾，在***對(duì)分類的錯(cuò)誤率進(jìn)行了計(jì)算。
正文
與決策樹分類和k近鄰分類算法不同，貝葉斯分類主要借助概率論的知識(shí)來通過比較提供的數(shù)據(jù)屬于每個(gè)類型的條件概率, 將他們分別計(jì)算出來然后預(yù)測(cè)具有***條件概率的那個(gè)類別是***的類別。當(dāng)然樣本越多我們統(tǒng)計(jì)的不同類型的特征值分布就越準(zhǔn)確，使用此分布進(jìn)行預(yù)測(cè)則會(huì)更加準(zhǔn)確。
貝葉斯準(zhǔn)則
樸素貝葉斯分類器中最核心的便是貝葉斯準(zhǔn)則，他用如下的公式表示:
此公式表示兩個(gè)互換的條件概率之間的關(guān)系，他們通過聯(lián)合概率關(guān)聯(lián)起來，這樣使得我們知道p(B|A) 的情況下去計(jì)算p(A|B) 成為了可能，而我們的貝葉斯模型便是通過貝葉斯準(zhǔn)則去計(jì)算某個(gè)樣本在不同類別條件下的條件概率并取具有***條件概率的那個(gè)類型作為分類的預(yù)測(cè)結(jié)果。
使用條件概率來進(jìn)行分類
這里我通俗的介紹下如何通過條件概率來進(jìn)行分類，假設(shè)我們看到了一個(gè)人的背影，想通過他背影的一些特征(數(shù)據(jù))來判斷這個(gè)人的性別(類別)，假設(shè)其中涉及到的特征有: 是否是長(zhǎng)發(fā), 身高是否在170以上，腿細(xì)，是否穿裙子。當(dāng)我們看到一個(gè)背影便會(huì)得到一個(gè)特征向量用來描述上述特征(1表示是，0表示否): ω=[0,1,1,0]
貝葉斯分類便是比較如下兩個(gè)條件概率:
- p(男生|ω) ，ω 等于 [0,1,1,0 的條件下此人是男生的概率
- p(女生|ω)) ，ω 等于 [0,1,1,0] 的條件下此人是女生的概率
若p(男生|ω)>p(女生|ω) , 則判定此人為男生, 否則為女生
那么p(男生|ω) 怎么求呢? 這就要上貝葉斯準(zhǔn)則了
根據(jù)貝葉斯準(zhǔn)則，
寫成好理解些的便是:
如果特征之間都是相互獨(dú)立的(條件獨(dú)立性假設(shè))，那么便可以將上述條件概率改寫成:
這樣我們就能計(jì)算當(dāng)前這個(gè)背影屬于男生和屬于女生的條件概率了。
實(shí)現(xiàn)自己的貝葉斯分類器
貝葉斯分類器實(shí)現(xiàn)起來非常的簡(jiǎn)單, 下面我以進(jìn)行文本分類為目的使用Python實(shí)現(xiàn)一個(gè)樸素貝葉斯文本分類器.
為了計(jì)算條件概率，我們需要計(jì)算各個(gè)特征的在不同類別下的條件概率以及類型的邊際概率，這就需要我們通過大量的訓(xùn)練數(shù)據(jù)進(jìn)行統(tǒng)計(jì)獲取近似值了，這也就是我們訓(xùn)練我們樸素貝葉斯模型的過程.
針對(duì)不同的文本，我們可以將所有出現(xiàn)的單詞作為數(shù)據(jù)特征向量，統(tǒng)計(jì)每個(gè)文本中出現(xiàn)詞條的數(shù)目(或者是否出現(xiàn)某個(gè)詞條)作為數(shù)據(jù)向量。這樣一個(gè)文本就可以處理成一個(gè)整數(shù)列表，并且長(zhǎng)度是所有詞條的數(shù)目，這個(gè)向量也許會(huì)很長(zhǎng)，用于本文的數(shù)據(jù)集中的短信詞條大概一共3000多個(gè)單詞。
- def get_doc_vector(words, vocabulary):
- ''' 根據(jù)詞匯表將文檔中的詞條轉(zhuǎn)換成文檔向量
- :param words: 文檔中的詞條列表
- :type words: list of str
- :param vocabulary: 總的詞匯列表
- :type vocabulary: list of str
- :return doc_vect: 用于貝葉斯分析的文檔向量
- :type doc_vect: list of int
- '''
- doc_vect = [0]*len(vocabulary)
- for word in words:
- if word in vocabulary:
- idx = vocabulary.index(word)
- doc_vect[idx] = 1
- return doc_vect
統(tǒng)計(jì)訓(xùn)練的過程的代碼實(shí)現(xiàn)如下:
- def train(self, dataset, classes):
- ''' 訓(xùn)練樸素貝葉斯模型
- :param dataset: 所有的文檔數(shù)據(jù)向量
- :type dataset: MxN matrix containing all doc vectors.
- :param classes: 所有文檔的類型
- :type classes: 1xN list
- :return cond_probs: 訓(xùn)練得到的條件概率矩陣
- :type cond_probs: dict
- :return cls_probs: 各種類型的概率
- :type cls_probs: dict
- '''
- # 按照不同類型記性分類
- sub_datasets = defaultdict(lambda: [])
- cls_cnt = defaultdict(lambda: 0)
- for doc_vect, cls in zip(dataset, classes):
- sub_datasets[cls].append(doc_vect)
- cls_cnt[cls] += 1
- # 計(jì)算類型概率
- cls_probs = {k: v/len(classes) for k, v in cls_cnt.items()}
- # 計(jì)算不同類型的條件概率
- cond_probs = {}
- dataset = np.array(dataset)
- for cls, sub_dataset in sub_datasets.items():
- sub_dataset = np.array(sub_dataset)
- # Improve the classifier.
- cond_prob_vect = np.log((np.sum(sub_dataset, axis=0) + 1)/(np.sum(dataset) + 2))
- cond_probs[cls] = cond_prob_vect
- return cond_probs, cls_probs
注意這里對(duì)于基本的條件概率直接相乘有兩處改進(jìn):
- 各個(gè)特征的概率初始值為1，分母上統(tǒng)計(jì)的某一類型的樣本總數(shù)的初始值是1，這是為了避免如果有一個(gè)特征統(tǒng)計(jì)的概率為0，則聯(lián)合概率也為零那自然沒有什么意義了, 如果訓(xùn)練樣本足夠大時(shí)，并不會(huì)對(duì)比較結(jié)果產(chǎn)生影響.
- 由于各個(gè)獨(dú)立特征的概率都是小于1的數(shù)，累積起來必然會(huì)是個(gè)更小的書，這會(huì)遇到浮點(diǎn)數(shù)下溢的問題，因此在這里我們對(duì)所有的概率都取了對(duì)數(shù)處理，這樣在保證不會(huì)有損失的情況下避免了下溢的問題。
獲取了統(tǒng)計(jì)概率信息后，我們便可以通過貝葉斯準(zhǔn)則預(yù)測(cè)我們數(shù)據(jù)的類型了，這里我并沒有直接計(jì)算每種情況的概率，而是通過統(tǒng)計(jì)得到的向量與數(shù)據(jù)向量進(jìn)行內(nèi)積獲取條件概率的相對(duì)值并進(jìn)行相對(duì)比較做出決策的。
- def classify(self, doc_vect, cond_probs, cls_probs):
- ''' 使用樸素貝葉斯將doc_vect進(jìn)行分類.
- '''
- pred_probs = {}
- for cls, cls_prob in cls_probs.items():
- cond_prob_vect = cond_probs[cls]
- pred_probs[cls] = np.sum(cond_prob_vect*doc_vect) + np.log(cls_prob)
- return max(pred_probs, key=pred_probs.get)
進(jìn)行短信分類
已經(jīng)構(gòu)建好了樸素貝葉斯模型，我們就可以使用此模型來統(tǒng)計(jì)數(shù)據(jù)并用來預(yù)測(cè)了。這里我使用了SMS垃圾短信語料庫中的垃圾短信數(shù)據(jù), 并隨機(jī)抽取90%的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，剩下10%的數(shù)據(jù)作為測(cè)試數(shù)據(jù)來測(cè)試我們的貝葉斯模型預(yù)測(cè)的準(zhǔn)確性。
當(dāng)然在建立模型前我們需要將數(shù)據(jù)處理成模型能夠處理的格式:
- ENCODING = 'ISO-8859-1'
- TRAIN_PERCENTAGE = 0.9
- def get_doc_vector(words, vocabulary):
- ''' 根據(jù)詞匯表將文檔中的詞條轉(zhuǎn)換成文檔向量
- :param words: 文檔中的詞條列表
- :type words: list of str
- :param vocabulary: 總的詞匯列表
- :type vocabulary: list of str
- :return doc_vect: 用于貝葉斯分析的文檔向量
- :type doc_vect: list of int
- '''
- doc_vect = [0]*len(vocabulary)
- for word in words:
- if word in vocabulary:
- idx = vocabulary.index(word)
- doc_vect[idx] = 1
- return doc_vect
- def parse_line(line):
- ''' 解析數(shù)據(jù)集中的每一行返回詞條向量和短信類型.
- '''
- cls = line.split(',')[-1].strip()
- content = ','.join(line.split(',')[: -1])
- word_vect = [word.lower() for word in re.split(r'\W+', content) if word]
- return word_vect, cls
- def parse_file(filename):
- ''' 解析文件中的數(shù)據(jù)
- '''
- vocabulary, word_vects, classes = [], [], []
- with open(filename, 'r', encoding=ENCODING) as f:
- for line in f:
- if line:
- word_vect, cls = parse_line(line)
- vocabulary.extend(word_vect)
- word_vects.append(word_vect)
- classes.append(cls)
- vocabulary = list(set(vocabulary))
- return vocabulary, word_vects, classes
有了上面三個(gè)函數(shù)我們就可以直接將我們的文本轉(zhuǎn)換成模型需要的數(shù)據(jù)向量，之后我們就可以劃分?jǐn)?shù)據(jù)集并將訓(xùn)練數(shù)據(jù)集給貝葉斯模型進(jìn)行統(tǒng)計(jì)。
- # 訓(xùn)練數(shù)據(jù) & 測(cè)試數(shù)據(jù)
- ntest = int(len(classes)*(1-TRAIN_PERCENTAGE))
- test_word_vects = []
- test_classes = []
- for i in range(ntest):
- idx = random.randint(0, len(word_vects)-1)
- test_word_vects.append(word_vects.pop(idx))
- test_classes.append(classes.pop(idx))
- train_word_vects = word_vects
- train_classes = classes
- train_dataset = [get_doc_vector(words, vocabulary) for words in train_word_vects]
訓(xùn)練模型:
- cond_probs, cls_probs = clf.train(train_dataset, train_classes)
剩下我們用測(cè)試數(shù)據(jù)來測(cè)試我們貝葉斯模型的預(yù)測(cè)準(zhǔn)確度:
- # 測(cè)試模型
- error = 0
- for test_word_vect, test_cls in zip(test_word_vects, test_classes):
- test_data = get_doc_vector(test_word_vect, vocabulary)
- pred_cls = clf.classify(test_data, cond_probs, cls_probs)
- if test_cls != pred_cls:
- print('Predict: {} -- Actual: {}'.format(pred_cls, test_cls))
- error += 1
- print('Error Rate: {}'.format(error/len(test_classes)))
隨機(jī)測(cè)了四組，錯(cuò)誤率分別為:0, 0.037, 0.015, 0. 平均錯(cuò)誤率為1.3%
測(cè)完了我們嘗試下看看不同類型短信各個(gè)詞條的概率分布是怎樣的吧:
- # 繪制不同類型的概率分布曲線
- fig = plt.figure()
- ax = fig.add_subplot(111)
- for cls, probs in cond_probs.items():
- ax.scatter(np.arange(0, len(probs)),
- probs*cls_probs[cls],
- label=cls,
- alpha=0.3)
- ax.legend()
- plt.show()
試試決策樹
上一篇我們基于ID3算法實(shí)現(xiàn)了決策樹，同樣是分類問題，我們同樣可以使用我們的文本數(shù)據(jù)來構(gòu)建用于分類短信的決策樹，當(dāng)然唯一比較麻煩的地方在于如果按照與貝葉斯相同的向量作為數(shù)據(jù)，則屬性可能會(huì)非常多，我們?cè)跇?gòu)建決策樹的時(shí)候每層樹結(jié)構(gòu)都是遞歸通過遍歷屬性根據(jù)信息增益來選取***屬性進(jìn)行樹分裂的，這樣很多的屬性可能會(huì)對(duì)構(gòu)建決策樹這一過程來說會(huì)比較耗時(shí).那我們就試試吧…
- # 生成決策樹
- if not os.path.exists('sms_tree.pkl'):
- clf.create_tree(train_dataset, train_classes, vocabulary)
- clf.dump_tree('sms_tree.pkl')
- else:
- clf.load_tree('sms_tree.pkl')
- # 測(cè)試模型
- error = 0
- for test_word_vect, test_cls in zip(test_word_vects, test_classes):
- test_data = get_doc_vector(test_word_vect, vocabulary)
- pred_cls = clf.classify(test_data, feat_names=vocabulary)
- if test_cls != pred_cls:
- print('Predict: {} -- Actual: {}'.format(pred_cls, test_cls))
- error += 1
- print('Error Rate: {}'.format(error/len(test_classes)))
隨機(jī)測(cè)了兩次，錯(cuò)誤率分別為:0.09, 0.0
效果還算不錯(cuò)
我們還是用Graphviz可視化看一下決策樹都選取了那些詞條作為判別標(biāo)準(zhǔn)(這時(shí)候決策樹的好處就體現(xiàn)出來了)。
可見決策樹的深度并不是很深，如果分類類型一多，估計(jì)深度增加上去決策樹可能會(huì)有些麻煩。
總結(jié)
本文我們使用Python一步步實(shí)現(xiàn)了樸素貝葉斯分類器，并對(duì)短信進(jìn)行了垃圾短信過濾，同樣的數(shù)據(jù)我們同決策樹的分類效果進(jìn)行了簡(jiǎn)單的比較。本文相關(guān)代碼實(shí)現(xiàn):https://github.com/PytLab/MLBox/tree/master/naive_bayes 。決策樹過濾垃圾短信的腳本在https://github.com/PytLab/MLBox/tree/master/decision_tree
參考
- 《Machine Learning in Action》
- 實(shí)例詳解貝葉斯推理的原理
- 大道至簡(jiǎn)：樸素貝葉斯分類器
相關(guān)閱讀
