基于群的樸素貝葉斯分類

摘要：本文對群的樸素貝葉斯分類進行了簡要論述。

關鍵詞：對稱性 樸素貝葉斯分類

1 概述

對稱性使人們在觀察自然和認識自然過程中產生的一種觀念，自然界千變萬化的運動，從一個側面來說，往往顯示出各式各樣的對稱樣，同時又通過這些對稱性的演化和殘缺來反映出運動演化的特點。對稱性的描述定義有很多種，從物理學出發，對稱性可以概括為：如果某一現象（或系統）在某一變換下不改變，則說該現象（或系統）具有該變換所對應的對稱性。

每一種對稱性都和某種特定的變換相聯系，對稱性的千差萬別也就集中在與之相聯系的各種變換上，因此可以根據變換所涉及的對象以及變換的性質對對稱性進行研究與分類。對于對稱性的描述與研究最有效的數學工具是群論與群表示論。物理學中對稱性研究相當多的部分運用群論來分析，概括和研究物理學的規律。例如，晶體中的對稱性，根據對稱性的結構對晶體進行分類，以及利用群論結果確定晶體中電子的波函數。另外一方面，根據群論的抽象機制對宇宙中粒子的運動行為作出預測。

統計學家運用對稱性對數據進行分析，并且專門開發了一個研究方向：數據分析的對稱性研究。對稱性研究主要運用統計與代數分析復雜的結構性數據，例如DNA分子結構，Sloan字體等具有對稱性的數據。這些數據(x)由一個有限集合V作為索引或者標注，有限集合V具有可以有群刻畫的對稱性，或者V可以構成一個群。簡而言之，對稱性研究利用具有對稱性的數據索引方便的對數據{x（s），s∈V}進行分類，解釋，統計性分析。目前對稱性研究主要用于短核苷酸序列索引的數據分析，由Sloan字體的對稱性索引的對比敏感度與熵的分析，地質成分熵的分解，初等平面圖像對稱索引的數據的分類與統計分析等。

既然物理學家與統計學家能夠運用群論認識自然界數據的規律，那么我們從數據分析的角度看，利用數據中的對稱性，結合機器學習方法，對數據進行分析，其目的就是揭示這些數據具有的規律，從而幫助用戶提供解釋的依據。對于具有復雜結構的某些數據，我們采用李群，李群結構是對學習問題很有用的一套理論工具，李群之所以受人們關注，一方面是李群有好的數學結構，另一方面受到物理學家和化學家廣泛使用李群方法來處理物理學中的晶體數據、有機物和無機物的數據、藥物分子結構數據等這些復雜數據的啟發。如何把李群運用到機器學習中，以下文獻提供了一個參考作用。

對于構成李群的數據，我們采用李群學習范式分析數據的維數，緊致性，連通性，子群，陪集。但仍有一個問題必須解決：如何確保計算復雜度問題。李群存在著復雜的代數結構，代數結構對于數據的分析有著至關重要的作用，但與統計對比，機器學習的代數方面的研究涉及的很少，只保留在理論層面上，原因之一是由于對象的巨大數量，很難計算。

2 基于群的樸素貝葉斯學習基本框架

設想學習問題定義如下，學習器L工作在實例空間X和假設空間H上，H上假設X上定義的某種實數值函數（即H中每一個h為一函數：h，X→R其中R代表實數集），L面臨的問題從H中抽取的目標函數h。如果實例空間X是一個可以用群G刻畫的對稱空間，或者實例X是一個群，則可以利用群作用于實例空間，產生實例空間X的商空間X/G，則假設空間H的h變換為h：X/G→R。本文學習算法的基本框架見圖2.1。

一般來說，給定的樣本數據具有隱藏的對稱性，無法直接作為實例空間X，如DNA分子序列，實例空間X的每個實例都相當于該樣本數據提取的一個特征，所以構造一個有序的實例空間（特征空間），能夠極大程度的反映不同DNA分子的差異。

2.1 構造實例空間X：

由于我們的算法主要針對分子序列分類，所以直接從樣本數據出發。

任何一個長度為 的分子序列可以有一個函數s：P→A表示，其中P={1，2，…， }是字母表A的每個字母所處的有序位置的集合。典型的字母表比如：DNA分子序列的字母：A={A，G，T，C}，RNA分子的字母表：A={A，G，T，U}，或者簡單的二元字母表A={U，Y}，嘌呤（U=A或者U=G）與嘧啶（Y=C或者Y=T）。Doi(1991)提出有效的局部序列長度為2，3，4，5，6。│A│表示字母表中字母的個數。X表示長度為L的所有│A│-序列構成的空間。實例空間X有│A│ 個實例。

2.2 構造X的商空間

已知實例空間X具有│A│個實例（特征），當 較大時，則會出維數災難問題，為了解決這個問題，可以根據實例空間X的規律，構造感興趣的群對X進行劃分，不同的群將會對實例空間X產生不同的劃分，要結合具體問題構造不同的群。例如對于DNA分子序列構造的實例空間，我們感興趣的是序列中符號的構成關系，所以一般選擇n階置換群Sn（n=2，3，4）。

定義：（群作用）群在一個集合V的作用是一個映射：φ：G×V→V，且φ滿足以下條件：對所有的s∈V，φ（1，s）=s，對于所有的τ，δ∈G，s∈V，φ（σ，φ（τ，s））=φ（δτ，s）。

根據φ，對于s∈X，群G作用在實例空間上產生的軌道為o={φτ（s）；τ∈G}，軌道空間中的任兩個實例都是等價的，在某一個群G作用下，X的所有軌道集合構成了一個X的另一個空間：商空間X/G，即X=o1∪o2∪…∪oλ，λ表示軌道的個數，oi（i=1，…，λ）表示第i個軌道空間，則每一個軌道空間的實例（特征）都是等價的。如何確定軌道的個數λ，我們引用Burnside引理：

Burnside引理：若一個有限群作用實例空間X上，則X中軌道的個數：

其中f ix（τ）={s∈X；φτ（s）=s}，表示具有對稱性τ的X中實例集合，│f ix（τ）│表示具有對稱性τ的X中實例的個數，│G│表示群G中元素的個數。

由于軌道oi的每個實例（特征）都是等價的，則每個軌道就可以作為DNA分子序列的一個特征（屬性），使用字母ai表示。X的商空間的維數為λ，DNA分子序列的屬性為（a1，a2，…，aλ）。

2.3 構造假設空間H

由于H中的假設為X上定義的某種實數值函數h，學習器L學習的空間X已經變成商空間X/G，則h變化為：h：X/G→R；X商空間的每個軌道oi作為一個函數h的一個變量xi（i=1，2，…，λ），H的變量數為λ。由于我們采用群的劃分方法，軌道之間相互獨立，則變量之間相互獨立。假設每個變量xi服從均值為μi，方差為δi的高斯分布，空間的H的個假設h的表達式為：

本文采用一般的統計學方法計算每個變量xi的均值μi與δi值，舉一個簡單的例子說明：對于每個核苷酸，統計每個實例空間中每個實例在DNA分子中出現的頻數，比如，已知DNA分子序列，

則每個實例的頻數為

構造的實例空間X為：X={s:Q→A}，其中Q={1，2，3}，A={a，g，c，t}，構造的實例空間共有64個實例，構造的群為S3={1，（12），（13），（23），（123），（132）}，則由Burnside引理計算出λ=35，軌道劃分如下：

。同一個軌道內的實例的頻數相加。則可以計算出變量xi（i=1，2，…，λ）的樣本值，然后使用統計的方法估計出每個變量的均值與方差。

2.4 樸素貝葉斯分類

樸素貝葉斯分類器應用到學習任務中，每個樣本數據由屬性值的合取描述，而目標函數h從商空間X/G中取值，學習器L被提供一系列關于目標函數的訓練樣例以及新實例（描述為屬性值的元組） ，然后對新實例分類。貝葉斯方法的分類目標在給定描述實例（DNA分子序列）的屬性值，得到做可能的目標值hMAP。

使用貝葉斯公式重寫為：

樸素貝葉斯分類器基于一個簡單的假設：在跟定目標值時屬性值之間相互條件獨立。換言之，該假定在給定實例的目標值情況下，觀察到聯合的a1，a2，…，aλ的概率等于每個單獨屬性的概率乘機：

（2.3）

將其代入式（2.2），可以得到樸素貝葉斯所使用的方法：

（2.4）

其中hNB表示樸素貝葉斯分類器輸出的目標值。

將2.1式代入式2.4得到：

基于群的樸素貝葉斯算法如下：

Examples是不同的DNA分子序列的集合以及類別名。H是所有可能假設的集合此函數作用提取DNA分子的屬性，構造假設空間H，計算屬性分布的高斯參數。變量n表示每種類別的DNA分子序列。

1.依據Examles構造實例空間X=（w1，w2，…，wn）；

2.構造群G

3.計算假設空間H的每個hj的每個變量xi的均值ui，方差δi

對于H中每個假設hj：

n=0；

對于類別為hj的每個example：

n←n+1

統計實例空間X每個實例wi的頻數；

根據群G與wi計算軌道數λ；

劃分實例空間X=o1∪o2∪…∪oλ；

計算每個軌道oi的頻數；

變量xi=oi（i=1，2，…，λ）；

計算假設hj的每個變量的均值ui，方差δi

CLASSIFY_NAIVE_BAYES_DNA(DNA)

對于DNA分子，返回其估計的類別。

計算變量xi的值；

返回hNB；

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文