基于K-medoids聚類的貝葉斯集成算法

盛靜文　于艷麗　江開忠

摘要：樸素貝葉斯分類算法由于其計算高效在生活中應用廣泛。本文根據集成算法的差異性特征，聚類算法聚類點的選擇方式的可變性，提出了基于K-medoids聚類技術的貝葉斯集成算法，樸素貝葉斯的泛化性能得到了提升。首先，通過樣本集訓練出多個樸素貝葉斯基分類器模型;然后，為了增大基分類器之間的差異性，利用K-medoids算法對基分類器在驗證集上的預測結果進行聚類;最后，從每個聚類簇中選擇泛化性能最佳的基分類器進行集成學習，最終結果由簡單投票法得出。將該算法應用于UCI數據集，并與其他類似算法進行比較可得，本文提出的基于K-medoids聚類的貝葉斯集成算法（NBKME）提高了數據集的分類準確率。

關鍵詞：樸素貝葉斯;分類;K-medoids聚類;集成算法

【Abstract】TheNaiveBayesclassificationalgorithmiswidelyusedinlifeduetoitscomputationalefficiency.Basedonthedifferencecharacteristicsoftheensemblealgorithmandthevariabilityoftheclusteringpointselectionmethodoftheclusteringalgorithm，thispaperproposesaBayesianensemblealgorithmbasedonK-medoidsclusteringtechnology，andthegeneralizationperformanceofNaiveBayeshasbeenimproved.Firstly，multipleNaiveBayesianclassifiermodelsaretrainedthroughthesampleset;then，inordertoincreasethedifferencebetweenthebaseclassifiers，theK-medoidsalgorithmisusedtogatherthepredictionresultsofthebaseclassifiersonthevalidationset;Finally，thebaseclassifierwiththebestgeneralizationperformanceisselectedfromeachclusterforensemblelearning，andthefinalresultisobtainedbyasimplevotingmethod.ThealgorithmisappliedtoUCIdatasetandcomparedwithothersimilaralgorithms.TheBayesianensemblealgorithmbasedonK-medoidsclustering（NBKME）proposedinthispaperimprovestheclassificationaccuracyofthedataset.

【Keywords】NaiveBayes;classification;K-medoidsclustering;ensemblealgorithm

作者簡介：盛靜文（1995-），女，碩士研究生，主要研究方向：機器學習、大數據;于艷麗（1993-），女，碩士研究生，主要研究方向：不平衡數據;江開忠（1965-），男，博士，副教授，主要研究方向：大數據。

0引言

分類問題在機器學習理論中占據重要地位，在監督學習中也是一個核心問題。在日常生活中，可見到很多分類問題，比如在醫學方面，將病人的檢查結果分為陽性和陰性，這就是一個二分類問題;在電子郵箱中，郵件的種類有3種，可能被分為垃圾郵件、廣告郵件和正常郵件，這就是一個多分類問題;圖像中的圖像分割，最簡單的方法就是對每一個像素進行分類。因此，分類問題是機器學習的基礎，研究分類算法對于社會發展具有不可替代的作用。

在眾多分類算法中，樸素貝葉斯方法[1]是一種基于概率的簡單有效的機器學習分類方法，現已廣泛應用在數據挖掘、計算機視覺、自然語言處理、模式識別、生物特征識別等領域。在很多的場合中，貝葉斯分類算法的性能與神經網絡和決策樹等算法比較接近，甚至要更好。貝葉斯算法不僅簡單，而且當數據集的規模很大時，分類的正確率也很高。同時，還可以精確地用數學公式表示出來。集成學習[2]，是指結合多個學習器進行學習任務的一種機器學習方法，也稱為分類器的集成。該方法可以對線性回歸、決策樹、支持向量機等基學習器進行集成訓練，令性能較單一學習器有較大的提升。集成學習主要分為2類。其中一類是由Breiman[3]提出的一種叫Bagging的集成方法。該方法的主要思想是通過自助法（Bootstrap）從訓練集中抽取N個訓練子集，然后對這N個訓練子集進行訓練可以生成N個基學習器，最終結果由這N個基學習器投票或平均的方式得出，如此一來不僅提高了模型學習的精度，而且也降低了過擬合的風險。集成學習[4]通常適用于不穩定的學習算法，如決策樹算法、BP神經網絡算法等，而樸素貝葉斯是一種穩定的學習方法，因此本文主要研究如何破壞樸素貝葉斯算法的穩定性并提高基分類器之間的差異性來進行集成，從而提高泛化性能。

針對貝葉斯集成算法，已經有很多學者做了相關的研究。文獻[5]在房價評估模型中引入集成學習和貝葉斯優化，模型精度提升了3.15個百分點;文獻[6]提出了一種深度集成樸素貝葉斯模型，緩解了樸素貝葉斯特征獨立性假設的缺點;文獻[7]建立動態隨機樹貝葉斯回歸模型，并通過集成（平均）來提高回歸模型的泛化能力;文獻[8]提出一種基于貝葉斯集成的SAR目標識別方法，有效解決了同一類目標數據可能會因為不同的表現形式產生錯誤的識別的問題。

本文在鐘熙等人[9]研發的基于Kmeans++聚類的樸素貝葉斯分類器集成方法的基礎上提出了基于K-medoids的貝葉斯集成算法。首先，通過對初始訓練樣本集自助采樣形成樣本子集，對樣本子集隨機抽取屬性形成屬性子集來訓練基分類器，把每個基分類器在驗證集上的預測結果作為聚類數據;然后，使用K-medoids算法對結果數據進行聚類，從而得到若干個基分類器簇，統計每個簇中的所有基分類器在驗證樣本集上的泛化性能，并選擇每個簇中泛化性能最好的基分類器代表該簇;最后，對選擇出來的基分類器進行集成，通過簡單投票法得到最終的預測結果。對于本文提出的算法的有效性，在UCI數據集上得到了驗證。

1相關理論

1.1樸素貝葉斯分類模型

1.3K-medoids聚類算法

K-medoids聚類算法[12-13]是K-means聚類算法的一種改進，K-means算法是在一組給定的數據中隨機選取k個數據作為初始聚類中心，接著計算所有數據與初始聚類中心的相似度，將數據放入與其最相似的聚類中心所代表的類;接下來，根據每個類內的數據的均值更新聚類中心點并重新劃分數據集中的數據，不斷迭代上述過程直至數據集中的數據所屬的類不再發生變化或者直至算法收斂為止[14]。K-medoids聚類算法與K-means不同的是在算法迭代過程中，K-medoids聚類算法選擇與類簇內數據均值距離最近的數據對象作為新的聚類中心點。

K-medoids的具體流程如下：

（1）任意選取K個對象作為初始聚類中心點。

（2）將余下的對象分到各個類中去（根據與中心點最相近的原則）。

（3）在每個類中，順序選取一個，計算可用于代替的總代價。選擇最小的來代替。這樣K個medodis就改變了。

（4）重復（2）、（3），直到K個medoids固定下來。

2基于聚類的選擇性樸素貝葉斯集成

差異性是集成算法的基礎，一般源于基分類器的訓練樣本，這樣同一算法在不同訓練樣本下即可訓練出不同的基分類器。經典的集成方法Bagging和Adaboost都是同一算法在不同設置下的集成，其差異性源于訓練樣本的不同。將一個大的訓練樣本集根據相似度分成多個組，在每組進行分類訓練，這樣就在分類器訓練前顯性地增加了差異性，從而不用在訓練過程中考慮如何平衡差異性和分類正確率的問題，因為在訓練樣本劃分時分類器訓練前即對差異性做了保證，而分類正確率即成為在分類器訓練過程中唯一需要考慮的因素[15-17]。

基于K-medoids聚類的貝葉斯集成算法主要分為如下方面：

（1）使用Bagging集成算法，進行自主采樣獲得樣本子集，再對樣本子集隨機抽取一定比例的屬性獲得屬性子集，這就使得樸素貝葉斯變得不穩定，進而基分類器差異性較大。

（2）本文在K-means的基礎上改進采用K-medoids算法對測試集的結果進行聚類，以達到樸素貝葉斯分類模型聚類的目的，從而獲得差異性更大的基分類器。

（3）進行選擇性集成。選擇性集成不僅可以提高算法性能，還能加快預測速度。從聚類產生的每個簇中選出泛化性能最佳的基分類器進行集成，并利用簡單投票法得出最終的預測結果。

算法的主要步驟如下：

3實驗

3.1實驗數據

本文采用UCI數據庫中的部分數據集，算法過程通過Python實現。為了驗證本文提出的基于K-medoids聚類的貝葉斯集成算法（NBKME）的優勢，將其與樸素貝葉斯算法（NB）、NBFS（即用樸素貝葉斯做基分類器，訓練樣本集是從樣本子集中隨機抽取屬性形成的屬性子集的Bagging算法）、NBK（基于K-means聚類的貝葉斯集成算法）、NBKM（基于K-means++聚類的貝葉斯集成算法）進行比較。數據集見表1。

3.2實驗結果及分析

本文選用的基分類器為樸素貝葉斯分類器，基分類器的數目為100，聚類算法簇的個數為10，在每個數據集上進行10次實驗，實驗結果見表2。

由表2可以看出NBFS的分類準確度高于NB，這就說明在Bagging算法中隨機抽取屬性子集可以提高分類準確率，集成算法的泛化性能也提高了;而NBK算法和NBKM算法對所有基分類器的結果進行聚類，有效增強了基分類器間的差異性，分類準確率也有所提高。而本文提出的基于NBKME算法將NBK和NBKM算法中的聚類方式變換為K-medoids。根據表2中的結果可見，聚類中心選擇方式的改變也進一步提高了分類準確率。

4結束語

建立科學有效的信用評估模型，能夠為研究人員提供重要的決策支持，減少損失，意義十分重大。針對傳統的樸素貝葉斯分類算法的改進，本文提出的基于K-medoids聚類的貝葉斯集成算法，通過屬性子集的選取，樸素貝葉斯的聚類和聚類中心點選取方式的改變提高了分類器的泛化性能，分類準確率更高。下一步的工作可以圍繞分類器的運行效率和樣本子集的選取方式展開。

參考文獻

[1]杜選.基于加權補集的樸素貝葉斯文本分類算法研究[J].計算機應用與軟件，2014，31（9）：253-255.

[2]TANGJialin，SUQinglang，SUBinghua，etal.Parallelensemblelearningofconvolutionalneuralnetworksandlocalbinarypatternsforfacerecognition[J].ComputerMethodsandProgramsinBiomedicine，2020，197：105622.

[3]BREIMANL.Baggingpredicators[J].MachineLearning，1996，24（1）：123-140.

[4]劉振剛.集成學習在三維模型分類中的應用[J].計算機產品與流通，2020（4）：261.

[5]顧桐，許國良，李萬林，等.基于集成LightGBM和貝葉斯優化策略的房價智能評估模型[J].計算機應用，2020，40（9）：2762-2767.

[6]吳皋，李明，周稻祥，等.基于深度集成樸素貝葉斯模型的文本分類[J].濟南大學學報（自然科學版），2020，34（5）：436-442.

[7]王雙成，鄭飛，唐曉清.動態隨機樹貝葉斯集成回歸模型研究[J].小型微型計算機系統，2019，40（4）：715-720.

[8]陳博，王珺琳，劉長清，等.基于貝葉斯集成算法的仿真SAR目標識別方法[J].中國電子科學研究院學報，2017，12（1）：73-77.

[9]鐘熙，孫祥娥.基于Kmeans++聚類的樸素貝葉斯集成方法研究[J].計算機科學，2019，46（S1）：439-441，451.

[10]漆原，喬宇.針對樸素貝葉斯文本分類方法的改進[J].電子科學技術，2017，4（5）：114-116，129.

[11]孟小燕.基于屬性權重的Bagging回歸算法研究[J].現代電子技術，2017，40（1）：95-98，103.

[12]韓冰，姜合.基于相似度計算公式改進的K-中心點算法[J].計算機與現代化，2019（5）：113-117.

[13]YUDonghua，LIUGuojun，GUOMaozu，etal.AnimprovedK-medoidsalgorithmbasedonstepincreasingandoptimizingmedoids[J].ExpertSystemsWithApplications，2018，92：464-473.

[14]XUXingbang，CHINan.Thephaseestimationofgeometricshaping8-QAMmodulationsbasedonK-meansclusteringinunderwatervisiblelightcommunication[J].OpticsCommunications，2019，444：147-153.

[15]徐浩然，許波，徐可文.機器學習在股票預測中的應用綜述[J].計算機工程與應用，2020，56（12）：19-24.

[16]武建軍，李昌兵.基于互信息的加權樸素貝葉斯文本分類算法[J].計算機系統應用，2017，26（7）：178-182.

[17]MURALIDHARANV，SUGUMARANV.AcomparativestudyofNaveBayesclassifierandBayesnetclassifierforfaultdiagnosisofmonoblockcentrifugalpumpusingwaveletanalysis[J].AppliedSoftComputing，2012，12（8）：2023-2029.