基于群的朴素贝叶斯分类

摘要：本文对群的朴素贝叶斯分类进行了简要论述。

关键词：对称性 朴素贝叶斯分类

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格式阅读原文

推荐访问:朴素 分类 贝叶斯