離散屬性的樸素貝葉斯分類算法的優化

李福祥，王建敏，梁建創，2，王 雪

1(哈爾濱理工大學 理學院，哈爾濱 150080)

2(鉅泉光電科技(上海)股份有限公司 技術研發部，上海 200000)

1 引 言

當今社會高速發展，高新技術遍地開花，萬物之間的聯系使得信息量急劇增加，各領域對海量數據的分類處理的需求也增多，因此對分類技術的研究也一直是眾多學者關注的重點.貝葉斯分類器其核心就是貝葉斯定理，在其分類過程中運用了概率統計的知識而塑造的一類算法.其中，樸素貝葉斯分類器(Naive Bayes Classifier，NBC)對貝葉斯分類器進行了理想化和簡化，成為最經典的分類算法，與其他分類算法相比，具有很大的優勢，NBC之所以簡單是因為它引入了一個很強的限制條件：屬性條件獨立性假設，凡事有利就有弊，雖然降低了計算開銷，但卻損失了算法分類精度，現實生活中數據是復雜的，真正的獨立是很少的，所以這個條件在實際生活中是很難成立的.為了提高算法分類性能，人們自然會想到探索屬性之間的依賴關系，借助其他算法改進樸素貝葉斯分類器，降低不切實際的獨立性假設帶來的影響.FRIEDMAN選擇從結構上改進樸素貝葉斯分類器，構造了TAN算法[1]，以最大帶權生成樹算法[2]為基礎，將無序分類變為有序分類.金哲將遺傳算法引入到了NBC中，在此基礎之上提出了GBAN分類器[3].眭俊明等人利用高階頻繁項集的原理，充分考慮了數據屬性間的相關性，從而提出了新的貝葉斯分類算法：FISC算法[4].王中鋒等人通過對TAN分類器結構的分析，提出一種不考慮邊重定向的TAN分類器[5].ZHOU通過分析貝葉斯分類原理和改進方法，利用粗糙集對屬性進行約簡，提出了一種同時改進屬性約簡和權重的樸素貝葉斯算法[6].寧可等人為了對高維連續數據離散化，采用了高斯分割的方法，提出了基于屬性關聯的樸素貝葉斯分類算法[7]，屬性數量越多，算法分類效果提升越明顯.張坤等人提出了一種利用可分解的評分函數構建TAN分類器的算法[8].余良俊等人用MI衡量不同屬性對分類的貢獻度，利用ODE模型分類器進行判別，提出MI-ODE算法[9].

對于分類算法而言，數據的屬性一般劃分為兩種：連續型和離散型，連續屬性也稱為定量屬性，例如：人的身高體重、西瓜的含糖率和密度等.離散屬性也稱為定性屬性，例如：顏色、性別等.對于連續屬性的取值允許被排序，也能進行各種算術運算，幾乎都可以被學習器所用，如有必要，可以視具體問題而定，進行對應的預處理分析.離散屬性具有有序和無序之分，有序離散屬性是指各類別之間有程度的差別，例如：成績屬性的取值可以分為優、良、中、及格、不及格，無序離散屬性是指所分類別或屬性之間無程度和順序的差別，例如：性別屬性的取值可以是男、女，離散屬性雖然可以很好的描述屬性的性質，但是無法進行算術運算.

大部分的分類模型都是基于數學運算，所以字串資料是無法運算的.基于此，本文對樸素貝葉斯分類器的離散屬性進行數據預處理，采用數值標記[10]的方法將離散屬性轉換成連續的數值，即用指定的數來代表離散屬性的取值，比如：對于頭發顏色，我們規定1代表黑，2代表白，往后推.對離散屬性做數據預處理之后，這樣就可以對離散屬性進行數值計算.

樸素貝葉斯分類器的假設在現實中往往不能滿足，使得分類精度降低.針對這個問題，本文通過正交矩陣對連續屬性和數值標記的離散屬性做正交變換，變換之后的屬性特征消除了屬性之間線性關系的影響，增強了屬性的條件獨立性，貼近了NBC的假設條件，從而提高算法分類精度.將改進后的算法用典型數據測試、分析，與樸素貝葉斯(NBC)、貝葉斯網(BN)相比，改進的算法(INB)分類性能提高.

2 樸素貝葉斯分類器簡介

樸素貝葉斯分類器[11]是基于貝葉斯定理和屬性條件獨立性的一種分類算法.設樣本數據集D={x1，x2，…，xm}，每個樣本xi=(xi1，xi2，…，xin)是一個n維屬性向量，類別標記為y={c1，c2，…，cN},即D可以分為N個類別.

基于貝葉斯定理，后驗概率P(c|x)可表示為：

(1)

其中，P(c)是類“先驗”概率；P(x|c)是樣本x相對于標記c的類條件概率；P(x)是證據因子.

樸素貝葉斯基于屬性條件獨立性假設，對已知類別，上式可表示為：

(2)

其中n為屬性數目，xi為x在第i個屬性上的取值.

由于對所有類別來說P(x)相同，因此由貝葉斯判定準則有：

(3)

這就是樸素貝葉斯分類器的表達式.

3 相關定理

定理1.[12]分布函數序列{Fn(x)}弱收斂于分布函數F(x)的充要條件是{Fn(x)}的特征函數序列{φn(t)}收斂于F(x)的特征函數φ(t).

通常以上定理稱為特征函數的連續性定理，因為它表明分布函數與特征函數的一一對應關系有連續性.

定理2.[12]設{Xn}是獨立同分布的隨機變量序列，且E(Xi)=μ，Var(Xi)=σ2>0存在，若記

則對任意實數y，有：

(4)

又因為E(Xn-μ)=0，Var(Xn-μ)=σ2，所以有：

φ′(0)=0，φ″(0)=-σ2

于是特征函數φ(t)有展開式：

從而有：

而e-t2/2正是N(0，1)分布的特征函數，定理得證.

上述定理只假設n獨立同分布、方差存在，不管原來的分布是什么，只要n充分大，就可以用正態分布去逼近隨機變量和的分布.

定理3.[13]實對稱矩陣M的屬于不同特征值的特征向量是正交的.

定理4.[13]實對稱矩陣一定可以正交相似于對角矩陣.

4 數據預處理

4.1 缺失數據的處理

在現實生活中，由于多方面的原因，我們很難遇到完美的數據，要么無法直接獲取想要的數據，要么就是獲取到的數據不盡如人意，一旦擁有了高價值的數據，就能進行高效的數據挖掘，而在數據分析過程中，經常會遇到數據值缺失的問題，這也是難以避免的.對缺失值的處理方法有很多，主要是從刪除元組、數據補齊、不處理這3個角度來處理缺失值[14].由于本文所采用的數據集缺失值比較少，所以對缺失數據的處理就根據統計學中的眾數原理，用該屬性在其他所有對象的取值次數最多的值(即出現頻率最高的值)來補齊該缺失的屬性值[15].

4.2 離散屬性連續化處理

一般而言，數據的屬性一般分為兩種類型：一種是連續(定量)屬性，通過連續的數值來刻畫被研究對象的某些屬性，如人的身高、體重等；另一種是離散(定性)屬性，通過文字語言或少量離散數值來描述被研究對象的某些屬性，如顏色、性別等.現實世界中，絕大多數的數據庫中，既包含了連續屬性，又包含了離散屬性.

樸素貝葉斯分類器的思想基礎就是對于給出的未分類對象，也就是測試集，計算在該測試集出現的條件下每個類別出現的概率，比較這些概率大小，將測試集判給概率最大的一類.也就是說，在類先驗概率的基礎上將數據集歸為n個標簽中后驗概率最大的標簽(基于最小錯誤率貝葉斯決策原則)，NBC對于連續型樣本屬性的類條件概率計算公式使用概率密度函數估計，對于離散型樣本屬性的類條件概率計算公式根據頻率估計概率得到.本文將離散型樣本屬性通過數值標記的方法將其連續化[16]，處理之后的離散型樣本屬性的類條件概率計算公式也通過概率密度函數來估計.

設樣本數據集D={x1，x2，…，xm}，每個樣本xi=(xi1，xi2，…，xin)是一個n維屬性向量，屬性Ak有nk個取值，先對數據集的屬性值進行數值化預處理，把屬性Ak的nk個可能的取值按1到nk進行數值標記[17]，例如：將西瓜數據集中色澤：青綠、烏黑、淺白轉化為1，2，3.類別標記為y={c1，c2，…，cN}，即D可以分為N個類別.

通過數值標記就可以將離散型樣本屬性進行了數值化處理[18]，這樣就可以計算各類樣本在各個屬性上取值的均值和方差，就可以使用概率密度函數來估計離散型樣本屬性的類條件概率.

5 改進的樸素貝葉斯分類器(INB)

5.1 訓練過程

設樣本數據集D={x1，x2，…，xm}，每個樣本xi=(xi1，xi2，…，xin)是一個n維屬性向量，屬性Ak有nk個取值，類別標記為y={c1，c2，…，cN}，即D可以分為N個類別，訓練步驟如下：

步驟2.補齊缺失值，根據統計學中的眾數原理，用該屬性在其他所有對象的取值次數最多的值(即出現頻率最高的值)來補齊該缺失的屬性值.

步驟3.對離散屬性進行數值標記，把屬性Ak的nk個可能的取值按1到nk進行數值標記，例如：將西瓜數據集中色澤：青綠、烏黑、淺白轉化為1，2，3.

步驟5.計算正交矩陣P，使得PTMP=Λ，其中Λ為對角矩陣.計算M的全部特征值，并求出相應的特征向量，構造正交矩陣P.如果M的特征值有重根，可以通過施密特正交化過程，然后經過單位化，得到一個標準正交基，也就是正交矩陣P；如果M的全部特征值無重根，那么直接將特征向量單位化即可，同樣得到正交矩陣P.

(5)

矩陣P可以將矩陣M相似對角化，乘積矩陣P-1MP的主對角元素是矩陣M的特征值：

通過上述方法所求的P是正交矩陣，可知P-1=PT，所以正交矩陣P可以將實對稱矩陣M合同對角化，使得PTMP=Λ，其中Λ為對角矩陣.

步驟8.基于最小化分類錯誤率的貝葉斯判定準則對測試集進行分類.

5.2 實驗結果及分析

首先對實驗數據集進行描述，然后根據算法步驟設計實驗，在對比試驗中，從UCI數據庫中選取9個數據集，用十折交叉的方法，檢測本文提出的改進的樸素貝葉斯分類器(INB)、標準的樸素貝葉斯分類器(NBC)、貝葉斯網(BN)這3個分類器的分類性能.

將本文的改進的樸素貝葉斯分類器(INB)與樸素貝葉斯(NBC)、貝葉斯網(BN)進行比較.

5.2.1 數據描述

本文從UCI機器學習數據庫中選取了9個數據集分別為balance、breast-cancer、car evaluation、German credit、hayes-roth、hepatitis、liver-disease、mushroom、tic-tac-toe,如表1所示.

表1 數據集描述

5.2.2 實驗設計

為了驗證本章提出的改進的樸素貝葉斯分類算法的有效性，對算法進行測試.實驗環境如下：

1)硬件環境：1.5GHz CPU，內存為4GB，硬盤100GB以上的個人計算機.

2)軟件環境：Windows 10 Professional 操作系統，用Python3.8編程實現.

本文采用十折交叉驗證估計算法的準確性.十折交叉驗證的步驟：先將數據集劃分成10個大小相似的互斥子集，每個子集盡可能保持數據分布的一致性，輪流將其中9個子集的并集作為訓練集，剩余的1個子集作為測試集，進行試驗.每次試驗都會得到相應的正確率，10次結果的正確率的平均值作為對算法精度的估計.原理如圖1所示.

圖1 十折交叉驗證法原理圖

分類任務中最常用的性能度量就是錯誤率和正確率.把分類錯誤的樣本數占樣本總數的比例稱為錯誤率，即如果在m個樣本中有a個樣本分類錯誤，則錯誤率為：

則分類正確率為：

一般用百分比形式表示.本文采用正確率對分類算法進行性能評估.

5.2.3 實驗結果

對所有數據集，采用十折交叉驗證，分別記錄標準樸素貝葉斯(NBC)、貝葉斯網(BN)和改進的樸素貝葉斯(INB)的分類正確率，最后將得到的結果進行比較，如表2、圖2所示.

表2 各種算法的分類正確率

圖2 NBC、BN和INB分類正確率對比

從表2、圖2中可看出，改進的樸素貝葉斯分類器(INB)在本文中所使用的9個數據集分類準確率都優于樸素貝葉斯(NBC)、貝葉斯網(BN)，運行時間和樸素貝葉斯分類器差別不明顯，說明了改進的算法分類(INB)的有效性和準確性.

6 結 論

本文在樸素貝葉斯分類器的基礎上，提出一種改進算法，詳細介紹了改進算法的訓練過程，對離散屬性數值標記，之后用正交矩陣對連續屬性和處理之后的離散屬性做正交變換，增強了屬性之間相互獨立性，貼近了樸素貝葉斯分類器的屬性條件獨立性假設，從而提高了算法的分類準確率.最后通過UCI數據集對比改進的樸素貝葉斯分類(INB)、樸素貝葉斯(NBC)、貝葉斯網(BN)的分類正確率，實驗結果表明，改進的樸素貝葉斯分類器(INB)的分類性能有較大的提高.