張雪峰,林曉飛

(東北大學 理學院,遼寧 沈陽 110819)

隨著大數(shù)據(jù)時代的到來,各種各樣的數(shù)據(jù)層出不窮,每組數(shù)據(jù)又有著繁多的特征,這使得數(shù)據(jù)處理成為當下的熱點問題。粗糙集理論是一種處理模糊和不確定性數(shù)據(jù)的數(shù)學工具,其主要思想就是在保持分類能力不變的前提下,通過知識約簡導出問題的決策或分類規(guī)則。目前,粗糙集理論已經(jīng)被成功地應用于機器學習、決策分析、過程控制、模式識別與數(shù)據(jù)挖掘等領域[1]。文獻[2]對信用卡欺詐檢測系統(tǒng)中持卡人行為進行了分析,使用粗糙集理論進行特征選擇、模糊邏輯決策和規(guī)則生成,使得到的結果更具有說服力。

粗糙集在屬性約簡上雖然有不錯的效果,但是弊端還是存在的,針對粗糙集的改進理論模糊粗糙集已成功地應用于屬性約簡、規(guī)則提取、分類樹歸納[3]等領域。文獻[4]首先基于加權鄰域關系構建加權鄰域粗糙集(WNRS);然后定義基于WNRS的依賴關系評估屬性子集,并通過貪心搜索算法選出相應子集,使用等距搜索找到最佳鄰域閾值;最后使用數(shù)據(jù)庫中的數(shù)據(jù)對比此模型與其他模型的性能。實驗表明,WNRS是可行且有效的,并且具有很高的分類精度和壓縮率。

粗糙集理論雖然成果顯著,但是還不足以作為一個分析數(shù)據(jù)建立模型的工具,而粗糙集和機器學習的有效結合在數(shù)據(jù)科學領域取得了更好的成績。文獻[5]提出了基于粗糙集理論、神經(jīng)網(wǎng)絡和遺傳算法的乳腺癌診斷系統(tǒng)。該系統(tǒng)首先通過訓練SOM神經(jīng)網(wǎng)絡對乳腺癌醫(yī)療數(shù)據(jù)進行離散化,然后通過遺傳算法對條件屬性進行約簡,最后從決策表中歸納出診斷規(guī)則。利用這些規(guī)則作為分類器來評價診斷系統(tǒng)的性能。實驗表明,與傳統(tǒng)的診斷方法相比,診斷準確率大幅度提高。文獻[6]考慮傳統(tǒng)的粗糙集理論不能處理連續(xù)屬性,而且得到的分類規(guī)則大多比較復雜;又考慮支持向量機理論能夠得到簡潔的分類規(guī)則,也能處理連續(xù)屬性,但僅適用于小樣本,對大樣本數(shù)據(jù)集有一定的局限性?；谏鲜隼碚撘约爸С窒蛄繖C分類方法僅與支持向量有關的特性,提出了一種先由粗糙集進行預處理的支持向量機分類方法。實驗表明,該方法在縮短訓練時間的基礎上保留了支持向量機方法所需分類信息,提高了分類精度,克服了其應用瓶頸。

機器學習的模型建立、參數(shù)調(diào)整等需要大量的人力和物力,所以可以實現(xiàn)從模型構建到應用的全程自動化的自動機器學習應運而生。文獻[7]提出了基于自動機器學習的水族文字識別,在縮短選擇模型時間的同時獲得了很高的識別精確率。文獻[8]提出了基于自動機器學習的遷移學習方法,它使用來自先前任務的知識來加速網(wǎng)絡設計,通過擴展基于遷移學習的架構搜索方法以支持多個任務的并行訓練,然后將搜索策略轉移到新任務。在語言和圖像分類數(shù)據(jù)上,基于自動機器學習的遷移學習將單任務訓練的收斂時間縮短了1個數(shù)量級以上。同時粗糙集也成功應用于圖像分割領域并取得了顯著的成果[9-10]。

本文將粗糙集和自動機器學習2種數(shù)據(jù)處理方法結合,該方法的優(yōu)勢在于既可以展示出粗糙集在數(shù)據(jù)降維上的作用,又充分展示了自動機器學習在參數(shù)調(diào)整方面的高效性。將粗糙集中的屬性約簡用于數(shù)據(jù)的預處理之上,通過數(shù)據(jù)降維剔除冗余指標,盡可能多地保留有用信息的同時也盡可能多地剔除冗余信息。而后續(xù)自動機器學習的準確調(diào)參也使得模型的分類準確率更高,模型的運行時間更短,同時自動機器學習根據(jù)當前模型會集成一個更優(yōu)的模型,將精確率再次提高。

1 相關算法

1.1 K均值聚類

由于粗糙集約簡只適用于離散數(shù)據(jù),本文選擇實驗數(shù)據(jù)為連續(xù)數(shù)據(jù),所以需要對連續(xù)數(shù)據(jù)進行離散化處理,而K均值聚類便是常用的離散化數(shù)據(jù)的聚類方法。

K均值聚類是基于樣本集合劃分的聚類算法。K均值聚類將樣本集合劃分為k個子集,構成k個類,將n個樣本分到k個類中,使得每個樣本到其所屬類的中心距離最小,其中每個樣本僅屬于1個類,這就是K均值聚類,同時根據(jù)1個樣本僅屬于1個類,也表示了K均值聚類是一種硬聚類算法。

K均值聚類可歸結為樣本集合X的劃分,或者從樣本到類的函數(shù)的選擇問題。K均值聚類的策略是通過損失函數(shù)的最小化選取最優(yōu)的劃分或函數(shù)C*。

首先,采用歐氏距離平方作為樣本之間的距離,

然后,定義每個樣本與其所屬類的中心的距離和為損失函數(shù),即

(1)

K均值聚類就是如何求解此優(yōu)化問題,

相似的樣本被聚到同類時,損失函數(shù)值最小,這個目標函數(shù)的最優(yōu)化能達到聚類的目的。但是,這是一個組合優(yōu)化問題,n個樣本分到k類的所有可能分法的數(shù)目是

(2)

這個數(shù)字是指數(shù)級的。事實上,K均值聚類的最優(yōu)解問題是NP(non deterministic ploynomial)困難問題,現(xiàn)實中采用迭代的方法求解。

K均值聚類算法[11]:

輸入:n個樣本的集合X和正整數(shù)k。

① 初始化。隨機選擇k個樣本點作為初始聚類中心。

② 對樣本進行聚類。針對初始化時選擇的聚類中心計算所有樣本到每個中心的距離,默認歐氏距離,將每個樣本聚集到與其最近的中心的類中,構成聚類結果。

③ 計算聚類后的類中心,計算每個類的質(zhì)心,即每個類中樣本的均值作為新的類中心。

④ 如果迭代收斂或符合停止條件,輸出C*=C(t)。重復執(zhí)行②,③直到聚類結果不再改變。

輸出:樣本集合的聚類C。

均值聚類算法的復雜度是O(mnk),其中m是樣本維數(shù),n是樣本個數(shù),k是類別個數(shù)。

1.2 粗糙集約簡算法

由于粗糙集方法在處理不確定信息時,具有不需要提供任何先驗信息的特點,因而在針對不確定性問題的描述和處理時較常規(guī)方法更具客觀性[12]。粗糙集約簡理論可以把圖1(a)的不規(guī)則圖形用圖1(b)規(guī)則的小矩形表示。

圖1 粗糙集約簡前后對比Fig.1 Comparison before and after rough set

定義1[1]知識和知識庫。設U≠?是感興趣的對象組成的有限集合,稱為論域。任何子集X∈U,稱為U中的一個概念或范疇。為了規(guī)范化起見,認為空集也是一個概念。U中的任何概念族稱為關于U的抽象知識,簡稱知識。對于那些在U上能形成劃分的知識再進行一次劃分,定義為:g=(X1,X2,…,Xn)。則U上的一族劃分稱為關于U的一個知識庫。

定義2[1]知識約簡是粗糙集理論的核心內(nèi)容之一,眾所周知,知識庫中的知識(屬性)并不是同等重要的,甚至其中某些知識是冗余的。所謂知識約簡,就是在保持知識庫分類能力不變的條件下,刪除其中不相關或不重要的知識。

結合粗糙集理論及K均值聚類算法便可以實現(xiàn)粗糙集的屬性約簡。

粗糙集約簡算法:

輸入:原始離散決策表,決策表條件屬性個數(shù)為K,令n=1且n∈。

① 固定條件屬性,保持其中K-1個條件屬性值不變。

② 改變條件屬性,改變剩余一個條件屬性值。

③ 判斷決策屬性值是否變化。

④ 若決策屬性值發(fā)生變化,保留此條件屬性;若決策屬性值未發(fā)生變化,剔除此條件屬性。

⑤ 令n=n+1。

⑥ 改變固定條件屬性組合并重復執(zhí)行②,③,④直到所有組合均作出判斷。

輸出:相對約簡屬性集。

在算法第③步中,判斷決策屬性值是否變化的依據(jù)進一步說明如下。

由于固定不同條件屬性篩選到的數(shù)據(jù)表個數(shù)不同,所以此處用n來表示根據(jù)篩選條件篩選到的數(shù)據(jù)個數(shù)。如果固定條件屬性X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14,X15,X16時,無論X1的值取0還是2,決策屬性的值始終是1,說明變量X1的改變不會影響分類結果,也就說明變量X1是冗余變量。如果固定條件屬性X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14,X15時,無論X16的值取0還是1,決策屬性的值始終在變化,說明變量X16的改變會影響分類結果,也就說明變量X16是有效變量。

1.3 自動機器學習方法

機器學習總的目標就是考慮如何學習模型和學習什么樣的模型,以使模型能對數(shù)據(jù)進行準確的預測和分析,同時也要考慮盡可能地提高效率。數(shù)據(jù)準備、算法選擇和超參數(shù)調(diào)整這些任務是機器學習任務最耗時的階段,調(diào)參和搜索網(wǎng)絡結構被認為是一項極其煩瑣并且耗費人力的工作,但是這項工作又極其重要,因為參數(shù)的好壞會直接影響到網(wǎng)絡的性能。

經(jīng)驗而言,只要有足夠多的時間并且嘗試足夠多的算法和參數(shù)組合之后,都會達到一個預期的效果,但是缺點就是費時費力。這也是之前的機器學習所做的任務。思考人類發(fā)明計算機的初衷,就是讓計算機來完成那些重復且煩瑣的任務,所以這項工作理論上來說也可以交給計算機來完成,在解放了人的同時,在模型的準確率上甚至會有更大的提升,因而,自動機器學習技術便應運而生。自動機器學習技術包含自動調(diào)節(jié)超參數(shù)、自動調(diào)整網(wǎng)絡結構等,在深度學習領域已取得了不錯的成績。

圖2 使用2個疊加層和基礎學習器的多層疊加策略Fig.2 Multi-layer overlay strategy using two overlay layers and basic learner

由于自動機器學習有著巨大的潛力,在這個領域已經(jīng)開發(fā)了很多的框架,本文所采用的框架是由亞馬遜公司開發(fā)的AutoGluon框架[13]。該框架的優(yōu)點在于能夠自動管理端到端的機器學習流程,融合了機器學習的眾多模型,而且它是一個處理異構數(shù)據(jù)集、神經(jīng)網(wǎng)絡以及基于多層疊加和重復K折疊組合的強大模型集成。AutoGluon相較于其他框架而言,優(yōu)勢在于尋找超參數(shù)的策略是自動設置固定的默認值,能夠使它在尋找超參數(shù)的過程中加快速度,同時也不會錯過最優(yōu)的超參數(shù)。

AutoGluon框架相比于其他框架的最大優(yōu)勢在于模型集成。將多個模型的預測結合起來的整體效果比單個模型的效果要好很多,這通常會大大降低最終預測的方差,不僅可以改進單個基礎預測的缺點,而且可以利用基礎模型之間的相互作用提供增強的預測能力。

1.4 決策樹模型

決策樹是一種基本的分類與回歸的樹形結構,表示基于特征對實例進行分類的過程,如圖3所示。決策樹通常是基于不同特征的信息增益生成的,設X是一個取有限個值的離散隨機變量,其概率分布為P(X=xi)=pi,i=1,2,…,n,則隨機變量X的熵定義為

(3)

這時熵的單位分別稱為比特或者納特。隨機變量X給定的條件下隨機變量Y的條件熵定義為

特征A對訓練數(shù)據(jù)集D的信息增益定義為

g(D,A)=H(D)-H(D|A),

則信息增益大的特征具有更強的分類能力。

圖3 決策樹模型Fig.3 Decision tree model

圖3中圓和方框分別表示內(nèi)部結點和葉結點。用決策樹分類,從根節(jié)點開始對實例的某一特征進行測試,根據(jù)測試結果,將實例分配到其子結點,這時,每個子結點對應著該特征的一個取值。如此遞歸地對實例進行測試并分配,直到達到葉結點,最后將實例分到葉結點的類中。

本文采用的決策樹模型是LightGBM[14],這是一種梯度增強決策樹(gradient boosting decision tree,GBDT)。LightGBM包含2種新技術:基于梯度的單邊采樣(gradient-based one-side sampling,GOSS)和互斥特征捆綁(exclusive feature bundling,EFB)。

使用GOSS可以排除很大一部分具有小梯度的數(shù)據(jù),而只使用其余的數(shù)據(jù)來估計信息增益。試驗證明具有較大梯度的數(shù)據(jù)實例在信息增益計算中起著更重要的作用,GOSS可以在較小的數(shù)據(jù)量下獲得相當精確的信息增益估計。

通常實際應用的中高緯度數(shù)據(jù)是稀疏數(shù)據(jù),使用EFB可以設計一種幾乎無損的方法來減少有效特征的數(shù)量,尤其是在稀疏特征空間中許多特征互斥的情況下。這可以安全的將互斥特征綁定在一起形成一個特征,從而減少特征維度。由于需要將特征劃分為更小的互斥捆綁數(shù)量,但是在多項式時間內(nèi)不可能去找到準確的解決辦法,所以EFB使用了一種近似的解決辦法,即特征之間允許存在少數(shù)的樣本點并不是互斥的,允許小部分的沖突可以得到更小的特征捆綁數(shù)量,更進一步提高計算的有效性。

1.5 BP神經(jīng)網(wǎng)絡模型

圖4 神經(jīng)元Fig.4 Neuron

神經(jīng)網(wǎng)絡一般可以看作一個非線性模型,其基本組成單元是具有非線性激活函數(shù)的神經(jīng)元,通過大量神經(jīng)元之間的連接,使得神經(jīng)網(wǎng)絡成為一種高度非線性的模型,如圖4所示。

假設一個神經(jīng)元,接收D個輸入x1,x2,…,xD,令x=(x1,x2,…,xD)T表示這組輸入,并用凈輸入z∈表示一個神經(jīng)元所獲得的輸入信號x的加權和,

式中,ω=(ω1,ω2,…,ωD)T∈D是D維的權重向量,b∈是偏置。

凈輸入z經(jīng)過一個非線性函數(shù)f后,得到神經(jīng)元的活性值a,

a=f(z)。

其中,非線性函數(shù)f稱為激活函數(shù),一般選擇如下函數(shù)作為激活函數(shù),

圖5 BP神經(jīng)網(wǎng)絡Fig.5 BP neural network

反向傳播神經(jīng)網(wǎng)絡(BP神經(jīng)網(wǎng)絡)是目前在分類問題上應用最多的一種神經(jīng)網(wǎng)絡,它是一種單向傳播的多層前向網(wǎng)絡。其學習算法遵循“誤差反向傳播原理”,學習的本質(zhì)是對各連接權重的動態(tài)調(diào)整,當一組學習樣本提供給網(wǎng)絡后,神經(jīng)元的激活值從輸入層經(jīng)各中間層向輸出層傳播,在輸出層的各神經(jīng)元獲得網(wǎng)絡的輸入響應,進而按照減少目標輸出與實際誤差的方向,從輸出層經(jīng)過各中間層逐層修正各連接權值,最后回到輸入層,這樣完成一次權值修正。最終使誤差函數(shù)減小到極小值,得到最優(yōu)擬合結果[15]。圖5便是一個含有輸入層、隱含層和輸出層的BP網(wǎng)絡。

訓練一個BP神經(jīng)網(wǎng)絡,實際上就是調(diào)整網(wǎng)絡的權重和偏置這2個參數(shù),分為前向傳輸和逆向反饋。前向傳播時,輸入樣本從輸入層傳入,經(jīng)各隱層逐層處理后傳向輸出層。若輸出層的實際輸出與期望的輸出不符,則轉入誤差的反向傳播階段。反向傳播時,將輸出以某種形式通過隱層向輸入層逐層反傳,并將誤差分攤給各層的所有單元,從而獲得各層單元的誤差信號,此誤差信號即作為修正各單元權值的依據(jù)。

FastAi[16]和MXNet[17]都是目前非常流行的神經(jīng)網(wǎng)絡訓練框架,本文采用這2種框架實現(xiàn)數(shù)據(jù)的分類,并比較2種框架下的運行時間和分類準確率,從而作出更加客觀的判斷。

2 算法設計

考慮到數(shù)據(jù)維度大,直接使用數(shù)據(jù)進行分類會大大影響效率,所以先進行粗糙集屬性約簡。由于粗糙集屬性約簡需要使用離散化數(shù)據(jù),所以使用K均值聚類算法對數(shù)據(jù)先進行離散化,得到離散化決策表,然后使用粗糙集屬性約簡得到約簡屬性集。利用引導聚集算法(Bagging)對樣本進行隨機采樣,得到多個樣本集,分別訓練多個樣本集得到多個弱分類器,針對弱分類器的分類結果投票得到強分類器作為預測模型之一,進行多次引導聚集算法得到多個預測模型。最后進行模型集成,將多個優(yōu)秀模型集成為一個模型,根據(jù)不同模型的不同分類準確率分別賦予不同的權重,得到最終的集成模型。

基于粗糙集和自動機器學習的分類算法:

輸入:原始數(shù)據(jù)(X,Y),分類模型個數(shù)M,分類聚集算法選取子集個數(shù)k。

① 對數(shù)據(jù)集的特征進行K均值聚類,得到離散的條件屬性。

② 對得到的條件屬性進行粗糙集數(shù)據(jù)約簡,篩選出重要特征。

③ 將篩選后的數(shù)據(jù)集隨機分成k個子集。

④ 用k個子集分別對M個分類模型進行訓練,得到多個模型參數(shù)φm,i。

⑤ 使用自動機器學習進行模型的參數(shù)調(diào)整得到最優(yōu)模型。

⑥ 對模型參數(shù)加權,得到集成模型f(x)=∑ωm,iφm,ix。

輸出:模型準確率,運行時間,M個分類模型權重,集成模型。

算法流程如圖6所示。

3 實驗結果與分析

3.1 數(shù)據(jù)選擇

原始數(shù)據(jù)如表1所示,數(shù)據(jù)量大導致無法展示全部數(shù)據(jù),所以省略其中的一部分。通過K均值進行離散化后的數(shù)據(jù)如表2所示。選擇干豆種類分別是:BARBUNYA、CALI、BOMBAY、SEKER,如圖7所示。

圖6 算法流程Fig.6 Schematic diagram of algorithm flow

表1 原始數(shù)據(jù)Table 1 Raw data

表2 離散化原始數(shù)據(jù)Table 2 Discrete raw data

圖7 不同干豆Fig.7 Different dried beans

3.2 數(shù)據(jù)處理

選擇樣本的原則是在7類干豆中隨機選擇4個種類,依據(jù)后續(xù)的K均值聚類分成4類。把這4類干豆中數(shù)量最少的干豆作為每組干豆的樣本量,除最少的一組干豆需要全部選擇之外,其他組干豆選擇遵循隨機原則。即4種干豆之中數(shù)量最少的為BOMBAY,數(shù)量是522,其他干豆也隨機抽取522個樣本,得到的數(shù)據(jù)維度是2 088×16,其中2 088是樣本數(shù),16是樣本的特征。使用K均值聚類的方法對數(shù)據(jù)做離散化處理,之后使用粗糙集的知識約簡算法對數(shù)據(jù)進行冗余屬性的剔除,利用分類聚集算法進行模型選擇,得到2種框架下的神經(jīng)網(wǎng)絡模型,分別用FastAi模型和MXNet模型表示,同時選擇LightGBM模型。接下來使用自動機器學習進行參數(shù)調(diào)整和模型集成,得到模型運行時間、分類準確率和模型損失率。

3.3 實驗結果

決策屬性D對應于4類干豆,分為0,1,2,3,屬性約簡之后的條件屬性由原來的16個變成了8個,見表3。為了驗證粗糙集屬性約簡的有效性和自動機器學習調(diào)參的準確性,分別在3種條件下進行測試:①不進行粗糙集屬性約簡,同時也不使用自動機器學習進行參數(shù)調(diào)整(no_tune);②使用自動機器學習進行參數(shù)調(diào)整,但不使用粗糙集進行屬性約簡(AutoML);③既使用粗糙集屬性約簡,又使用自動機器學習進行參數(shù)調(diào)整(AutoML+RS)。結果如圖8所示。自動機器學習給出的集成模型WeightedEnsemble根據(jù)3個模型的分類準確率分別賦予FastAi、MXNet、LightGBM 3個模型0.3、0.3、0.4的權重。不同條件下模型準確率見表4,運行時間見表5。從圖8(a)及表4、表5中可以看到FastAi模型的準確率從高到低的條件分別是AutoML+RS、AutoML、no_tune,運行時間從低到高的條件分別是AutoML+RS、AutoML、no_tune。隨著迭代次數(shù)的增加,AutoML+RS的準確率可以達到98.91%,運行時間可以縮短到9.50 s。從圖8(b)及表4、表5中可以看到MXNet模型的損失率從小到大的條件分別是AutoML+RS、AutoML、no_tune,運行時間從低到高的條件分別AutoML+RS、AutoML、no_tune。隨著迭代次數(shù)的增加,AutoML+RS條件下的MXNet模型損失率可以下降到1.4%,運行時間可以縮短到17.32 s。從圖8(c)及表4、表5中可以看到LightGBM模型的準確率從高到低的條件分別是AutoML+RS、AutoML、no_tune,運行時間從低到高的條件分別AutoML+RS、AutoML、no_tune。隨著迭代次數(shù)的增加,AutoML+RS的準確率可以達到98.55%,運行時間可以縮短到1.52 s。

表3 離散化并約簡后數(shù)據(jù)Table 3 Discrete and reduced data

圖8 不同模型結果Fig.8 Results of different models

表4 不同條件下模型準確率Table 4 Accuracy rate of models under different conditions 單位:%

表5 不同條件下模型運行時間Table 5 Running time of models under different conditions 單位:s

4 結 論

分別將不使用粗糙集約簡的數(shù)據(jù)和使用粗糙集約簡的數(shù)據(jù)應用3種模型在不同條件下進行了實驗。得出結論:使用自動機器學習進行調(diào)參之后,幾乎所有模型的準確率都有大幅度的提升,同時使用粗糙集約簡和自動機器學習進行調(diào)參之后,模型的準確率有了更大幅度的提升,模型損失率也大幅下降;從運行時間上,幾乎所有模型的運行時間都顯著縮短,也證明了粗糙集的屬性約簡確實有助于縮短建模時間;自動機器學習不僅對模型進行了參數(shù)調(diào)整,而且還對模型進行了集成,自動機器學習分別給出了3個模型不同的權重得到的集成模型,集成模型的準確率比其他模型更高,運行時間比其他模型更短。