李福祥，王建敏，梁建創(chuàng)，2，王 雪

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

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

1 引 言

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

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

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

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

2 樸素貝葉斯分類器簡介

樸素貝葉斯分類器[11]是基于貝葉斯定理和屬性條件獨立性的一種分類算法.設(shè)樣本數(shù)據(jù)集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)是證據(jù)因子.

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

(2)

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

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

(3)

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

3 相關(guān)定理

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

通常以上定理稱為特征函數(shù)的連續(xù)性定理，因為它表明分布函數(shù)與特征函數(shù)的一一對應(yīng)關(guān)系有連續(xù)性.

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

則對任意實數(shù)y，有：

(4)

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

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

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

從而有：

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

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

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

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

4 數(shù)據(jù)預(yù)處理

4.1 缺失數(shù)據(jù)的處理

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

4.2 離散屬性連續(xù)化處理

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

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

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

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

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

5.1 訓練過程

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

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

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

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

(5)

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

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

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

5.2 實驗結(jié)果及分析

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

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

5.2.1 數(shù)據(jù)描述

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

表1 數(shù)據(jù)集描述

5.2.2 實驗設(shè)計

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

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

2)軟件環(huán)境：Windows 10 Professional 操作系統(tǒng)，用Python3.8編程實現(xiàn).

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

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

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

則分類正確率為：

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

5.2.3 實驗結(jié)果

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

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

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

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

6 結(jié) 論

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