一种基于非参数贝叶斯模型的聚类算法
第26卷第4期, 2013年10月宁波大学学报（理工版）首届中国高校优秀科技期刊奖V ol.26 No.4, Oct. 2013 JOURNAL OF NINGBO UNIVERSITY ( NSEE ) 浙江省优秀科技期刊一等奖
一种基于非参数贝叶斯模型的聚类算法
张媛媛
（宁波大学信息科学与工程学院, 浙江宁波 315211）
摘要: 鉴于聚类分析是机器学习和数据挖掘领域的一项重要技术, 并且与监督学习不同的是聚类分析中没有类别或标签的指导信息, 所以如何选择合适的聚类个数(即模型选择)一直是聚类分析中的难点. 由此提出了一种基于Dirichlet过程混合模型的聚类算法, 并用collapsed Gibbs采样算法对混合模型的参数进行估计. 新算法基于非参数贝叶斯模型的框架, 能够在不断的采样过程中优化模型参数并形成合适的聚类个数. 在人工合成数据集和真实数据集上的聚类实验结果表明: 基于Dirichlet过程混合模型的聚类算法不但能够自动确定聚类个数, 而且具有较强灵活性和鲁棒性.
关键词: 非参数贝叶斯模型; Dirichlet过程混合模型; 聚类分析; Gibbs采样
中图分类号: TP391 文献标志码: A 文章编号: 1001-5132（2013）04-0024-05
聚类分析是指在没有类别或标签信息的情况下, 将一组数据(或模式)进行分类的统计分析方法. 经过聚类分析后, 属于同类的数据比在不同类中的数据更具相似性. 经典的聚类算法有K均值聚类算法(K-means Algorithm)、基于EM(Expectation Maximization)优化的有限混合模型(Finite Mixture Models)算法以及基于密度的方法(Density-based Methods)等[1-2]. 但是这些算法都需要预先设定聚类或混合部件的个数, 若个数选择不当会直接导致模型的过拟合或欠拟合情况的发生. 因此, 如何选择合适的聚类个数是聚类分析的关键, 也是模式分类中的模型选择问题. 针对此问题, 一种直接的解决方式是尝试所有可能聚类个数的模型结构, 然后根据一定准则折中选取一个最优的、不易发生过拟合或欠拟合的模型. 常见评价方法有基于编码理论和最小信息长度的准则(Minimum Message Length, MML)、Akaike信息准则(Akaike’s Informa- tion Criterion, AIC)、贝叶斯信息准则(Bayesian Information Criterion、BIC)和最小描述长度准则(Minimum Description Length, MDL)[3]. 但是现有的这些模型选择方法不仅计算量较大, 而且泛化能力较弱, 尽管对训练样本数据拟合得较好, 但对未知数据可能拟合不好.
针对以上问题, 笔者设计实现了一种基于Dirichlet过程混合模型(Dirichlet Process Mixture Model, DPMM)的非参数聚类方法. 它为模型选择问题提供了一个比较灵活的解决之道, 是一种非参数贝叶斯模型(Nonparametric Bayesian Models), 也是近年来统计学习理论的研究热点[4-6]. 与传统的参数模型相比, DPMM采用单一复杂的混合模型, 并根据观测数据自动优化模型的结构, 使模型的分布参数随着观测数据进行调整[7-8]. 实验结果表明, 当DPMM用于聚类分析时, 无需预先指定类别数, 而是根据观测数据自动计算目前所需的类别数, 并以概率方式允许将来的新数据出现时产生新的类别. 在计算DPMM后验概率时, 由于后验概率不能被直接计算, 所以我们采用Gibbs采样法反复从条件分布中采样并更新模型参数. Gibbs采样法属马尔可夫链蒙特卡罗方法(Markov Chain Monte Carlo, MCMC), 是替代精确推理的近似推理方法. 和其它MCMC算法一样, Gibbs采样法产生一条马尔可夫链, 经过足够次数的采样后,
收稿日期:2013?06?09. 宁波大学学报（理工版）网址: https://www.wendangku.net/doc/401783673.html,/
基金项目:国家自然科学基金（61175026）; 浙江省新一代移动互联网用户端软件科技创新团队项目（2010R50009）; 宁波市自然科学基金（2011A610193）; 宁波大学学科项目（XKL09154）.
作者简介:张媛媛（1981－）, 女, 浙江宁海人, 博士研究生/实验师, 主要研究方向: 机器学习和计算机视觉. E-mail: zhangyuanyuan@https://www.wendangku.net/doc/401783673.html,
第4期 张媛媛: 一种基于非参数贝叶斯模型的聚类算法 25
该马尔可夫链可以达到稳态. 1
Dirichlet 过程混合模型
1.1 Dirichlet 过程
Dirichlet 过程是Ferguson 在1973年提出的一种随机过程, 它是一种描述概率分布的分布
[9-11]
.
假设0H 是侧度空间Ω上的一个概率分布, 0α是1个正实数, 那么对空间Ω任意一种有限剖分1(,T
2,,)k T T ", 如果随机概率侧度G 都满足下式:
100100(),,()~((),,()),k k G T G T Dir H T H T αα"" (1) 则称G 服从Dirichlet 过程, 记作00~(,)G DP H α.
由于按照以上的数学定义无法对Dirichlet 过程实现采样和对未知数据的预测, 所以在实际应用中往往采用Dirichlet 过程的其它构造形式, 比如
stick-breaking 构造过程就适合用于采样算法, 在计算新观测数据的预测分布时, 采用的是Polya 罐子构造模型(Polya Urn Model, PUM)和中国餐馆过程
(Chinese Restaurant Process, CRP).
假设混合系数1{}k k π∞==π是从以下的stick-
breaking 过程中得到的1个无穷序列[6]:
011
(1~Beta(1,),
,1,.
),k k k l k l v v v k πα?==∞?=∑" (2)
0H 是测度空间上Ω的一个基分布, 若概率测度G 满足下列条件:
10(),
~,
k k k k G H θθπδθ=∞
=∑ (3) 则该测度G 服从Dirichlet 过程分布, 混合系数序列π的产生过程记作0~)(GEM απ, 而GEM 为3个人名Griffiths, Engen 和McCloskey 的缩写.
假设G 服从Dirichlet 过程: 00~(,)G DP H α,
1,,n ηη"是服从分布G 的独立同分布的随机观测
变量, ,,*
*1K ηη"是其观测到的K 个不同取值, 那么
新的随机观测变量1n η+的预测条件分布具有以下形式:
*1100(,,,)n n H p ηηηηα+= | ="
00
1
*
**1(,)()K
k
k
k N n n H αδηαη
ηα=+++
∑, (4) 其中, k N 是指序列1,,n ηη"中其值等于*
k η的个数.
从(4)式可见, Dirichlet 过程具有很好的聚类性
质, 它可以将具有相同值的观测变量聚为一类. 假设1,,n c c "表示1,,n ηη"所属的类标签变量, 那么下个观测变量的类标签1n c +服从以下分布:
11(|,)n n p c j c c +=="
1
1(,)(,)K
k
k N j k j c n n αδδαα
=+++∑, (5)
其中, c 表示产生新的一个类别.
(5)式表示的概率分布可以用中国餐馆过程来形容: 假设有1个中国餐馆可以容纳无限张餐桌, 每张餐桌可以容纳无限数量的顾客. 在这里, 桌子对应某个类别i c , 而顾客对应观测变量i η. 根据(5)式, 第1n η+个顾客将以正比于已经就坐于第k 张桌子的顾客数k N 的概率坐于第k 张餐桌, 而且以正比于0α的概率就坐于1张新的餐桌. 由此可知, 某个餐桌上就座的顾客越多, 就越有可能加入新的顾客, 这也是一种“rich-gets-richer ”的性质.
1.2 Dirichlet 过程混合模型
Dirichlet 过程最重要的应用是作为概率模型中参数的先验分布. 假设有观测变量12,,y y "是服
从下列分布的独立同分布的变量: 00~(,)G DP H α, ~i G G η, (6) ~()i i i y F ηη. 观测变量i y 服从参数为i η的分布()i F η, G 是参数i η的先验分布, 假如G 服从基分布0H 和集中
参数0α的Dirichlet 过程, 则称此模型为Dirichlet
过程混合模型(DPMM), 其图模型结构如图1所示.
为计算方便, ()i F η往往是属于指数族分布的, 而0H 是相应的共轭先验分布. Dirichlet 过程只能把相同值的数据聚为一类, 但是DPMM 可以将服从相同参数分布的数据聚为一类, 所以特别适用于基于模型的聚类分析.
2 基于DPMM 的聚类算法
基于DPMM 聚类算法的基本思想是用混合部
件(Components)的概率分布来拟合观测数据, 这里的每个观测数据来自其中某个部件, 并用一个隐变量指示数据的来源. 理论上DPMM 有无限多个部件, 但是只用其中的一部分部件来解释现有的观测数据.
在计算图1模型的后验分布时, 用Gibbs 采样
26 宁波大学学报（理工版） 2013
法从后验分布(|,)i i i p y η?η采样得到i η, 下标i ?表示除i 以外的所有数据的集合. 由于这种直接的
Gibbs 采样法每次给定1个观测值后才更新1次, 所以收敛速度非常慢, 而且不适用于大规模的聚类分析. 因此笔者考虑在DPMM 的另一个等价模型[12-14]的基础上用collapsed Gibbs 采样法对参数进行采样, 即不直接采样i η, 而是采样观测变量的类标签i c , 然后更新部件i c 的参数
i c φ[6,15](图2).
图1 DPMM 的图
图2 DPMM 的无限
模型结构
混合模型结构
在这种构造方式中, 混合系数的先验分布服从参数为0α的stick-breaking 过程, k φ表示部件k 的分布参数, 0H 是k φ的先验分布, 其构造形式是:
00|~GEM()ααπ,
|~i c ππ, 00|~k H H φ, |~()i
i i c y c F φ.
给定独立同分布的观测数据1,,n y y "和其它观测数据的类标签的条件下, 数据i y 的类标签i c 的后验分布服从以下条件分布形式:
10(,,,|,)i n i p c y y α?∝"c
0(,)(,,)||i i i i i i p c p y c α???c y c . (8) (8)式右边第1项可以由中国餐馆过程构造, c 表示产生的新类别: 0(|,)i i p c j α?==c
1
1(,)(,).11K
k k N j k j c n n αδδαα=+
?+?+∑(9)
(8)式右边的第2项是i y 的预测分布, 若i c 是已存在的类标签, 则可以由下列式子计算:
(|,,)i i i i p c y j ??==y c
(|{|}),i k k y y c j k p i =≠. (10) 若i c 是新产生的类标签, 则i y 的预测分布是:
0(|,,)(|)d ()i i i i i j j y y p c j F H φφ??==y c . (11)
Gibbs 采样的基本思想是在隐变量上定义1个马尔可夫链, 每个隐变量都是在给定其它隐变量和数据的条件分布中采样得到, 它的平稳分布是隐变量的后验分布. 若从图2所示的DPMM 产生了n 个观测序列1,,n y y ", 则Gibbs 采样为每个观测值分配类标签1,,n c c ", 然后更新各部件的分布参数k φ和类别数目K .
综上所述, 当给定集中参数0α及第t 次采样后
观测数据的分类结果1:{}t
i n c 和聚类个数K 的情况下,
collapsed Gibbs 采样法按照以下过程对类标签进行
第1t +次采样:
(1) 将n 个观测数据随机排序, 得到(1),,σ"
()n σ.
(2) 对每个数据(1),,()n σσ"分别对其类标签
11:{}i t n c +采样: ①对现有的K 个聚类按照(10)式计算
i y 对每一个类的预测估计. 然后增加一个新类c , 并计算i y 属于该新类的概率估计. ②根据(8)式计算该i y 所属类别1i t c +的后验概率分布11(|,,t i p c y +" 0,,)n i y c α?, 并从该后验分布中采样得到1i t c +.
(3) 检查上述1K +个类内的观测数据量, 如果某类为空, 则将该类移除, 并且将聚类总数减1.
3
聚类分析试验
3.1 合成数据集
图3是DPMM 用于人工合成数据集的实验. 该数据是由多个不同形状的高斯分布生成的二维观测值, 每个观测值是由其中某个高斯分布产生. 这
2个数据集分别包括400n =和600n =个数据点,
真实的混合个数分别为15k =和27k =. 初始参数
0α的取值为:01α=, 每个聚类用不同深浅的椭圆
表示各类的密度轮廓. 图中每排图像显示在同个数据集上分别经过若干次Gibbs 采样后得到的结果. 例如在对第1个数据集聚类时, 当Gibbs 初始采样
7次的时候, 算法只产生几个聚类; 经过26次采样后, 算法产生了很多冗余的聚类; Gibbs 采样经过
36次循环后迅速找到了比较合适的聚类个数, 而且已经与真实模型非常地接近. 在此实验中, 聚类
相当于高斯核, 因此DPMM 也可以用于混合模型
的核密度估计.
3.2 真实数据集
实验中, 笔者采用2个从现实世界中收集的数 (7)
?k π
∞
第4期 张媛媛: 一种基于非参数贝叶斯模型的聚类算法 27
(a) k 1=5, n =400, 从左至右而下分别表示7次、26次、36次采样结果
(b) k 2=7, n =600, 从左至右而下分别表示10次、42次、80次采样结果
图3 聚类实验结果
据集来测试DPMM 聚类算法性能. 第1个测试集来自UCI 机器学习数据库(https://www.wendangku.net/doc/401783673.html,/
ml/datasets/Iris)的鸢尾科植物数据集(Iris dataset),这是模式识别中经常用来测试聚类性能的数据集. 该数据集包含3种类别的鸢尾科植物, 每个类别有
50个实例数据. 第一类和其它两类线性分离, 剩下的两类彼此非线性分离. 另1个测试集是来自ML
comp(https://www.wendangku.net/doc/401783673.html,/datasets/167)的真实图像数据集, 由7个室外图像数据组成, 包括天空、路径、草地、天空、树叶等图像, 每个实例有19个连续属性.
从(8)式可见, 后验分布与集中参数0α的选择相关, 所以为减少0α对聚类结果的影响, 笔者选择一个弱信息的概率分布作为0α的先验分布[6]
. 在实验中, 设置0α服从伽玛分布: 01~(,Gamma ακ
2)κ, 其中, 12,κκ是超参数. 由此, 0α也是DPMM
的1个隐变量, 因此在每次Gibbs 采样中, 也要对
0α进行采样, 实验中超参数取值为120.2,0.1κκ==.
由于V-Measure 是基于同质性和完整性的一个聚类评价标准, 因此笔者选用V-Measure 值来评估
聚类的性能. 表1显示了该实验得到的结果, 并由此可见, 图像数据集的V-Measure 值低于植物数据集, 这是因为图像特征本身比较复杂, 尤其在无监督学习下更难以区分.
表1 真实数据集的聚类结果
Name n d k V-Measure
Iris 150 4 3
73% Image
2310 19 7
65%
注: 每个数据集由k 个类, n 个实例组成, 每个实例具有d 维属性.
4
总结
提出了一种基于DPMM 和collapsed Gibbs 采
样法的聚类算法, 实验结果表明该算法可以自动确定聚类个数和估计混合模型参数, 可用于聚类、模式识别、核密度估计等应用. 但是这种模型仍然有很多值得探讨和发展的地方[16-18]. 首先, DPMM 适用于对一组数据的聚类分析, 但是不能用于成
组数据的建模分析. 我们可以把DPMM 扩展成分层Dirichlet 混合模型, 这样就可以在组和组之间实现聚类的共享. 其次, 目前基于Dirichlet 过程的模型主要采用Gibbs 采样计算, 但是这种方法不仅计算量大而且往往收敛缓慢, 尤其需要处理的大规模数据量时, 需要用更加快速有效的近似方法来替代, 比如并行采样算法或者变分推断算法. 再次,
DPMM 假设生成数据是跟次序无关(即可交换的), 但是在处理有时间或空间依赖数据时, 这种假设显然是不合适的, 所以研究有依赖关系的Dirichlet 模型(Dependent Dirichlet Models)是很有必要的工作. 最后, 基于DPMM 的聚类算法是一种无监督的学习, 但是在某些应用中监督信息是非常有用的, 所以如何把这两种学习方式有效地结合在一起也是今后的一个研究内容.
参考文献:
[1] Jain K A. Data clustering: 50 years beyond K-means[J].
Pattern Recognition Letters, 2010, 31:651-666.
28 宁波大学学报（理工版） 2013
[2]Bishop M C. Pattern recognition and machine learning
[M]. New York: Springer Press, 2007.
[3]Claeskens G, Hjort N L. Model selection and model
averaging[M]. New York: Cambridge University Press, 2008.
[4]Shahbaba B, Neal R. Nonlinear models using Dirichlet
process mixtures[J]. The Journal of Machine Learning Research, 2009, 10:1829-1850.
[5]Fox E, Sudderth E, Jordan M, et al. Nonparametric
Bayesian learning of switching linear dynamical systems
[C]. In Advances in Neural Information Processing
Systems 21, Vancouver and Whistler, BC, Canada: The MIT Press, 2008.
[6]Sudderth E. Graphical models for visual object
recognition and tracking[D]. MA, Cambridge: Massa- chusetts Institute of Technology, 2006.
[7]Gershman S, Blei D. A tutorial on Bayesian nonpara-
metric models[J]. Journal of Mathematical Psychology, 2012, 56:1-12.
[8]Hjort L N, Holmes M P, Walker G S. Bayesian
nonparametric[M]. New York: Cambridge University Press, 2010.
[9]Ferguson S T. A Bayesian analysis of some nonparametric
problems[J]. The Annals of Statistics, 1973, 12:209-230. [10]周建英, 王飞跃, 曾大军. 分层Dirichlet过程及其应用
综述[J]. 自动化学报, 2011, 37(4):390-407.
[11]Teh W Y. Dirichlet processes[C]. Machine Learning
Summer School Tutorial and Practical Course, 2007. [12]Teh W Y, Jordan I M, Beal J M, et al. Hierarchical
Dirichlet processes[J]. Journal of the American Statistical Association, 2006, 101:1566-1581.
[13]Rasmussen E C. The infinite Gaussian mixture model[C].
In Advances in Neural Information Processing Systems 12, MIT Press, 2000:554-560.
[14]Teh W Y. Bayesian nonparametric: DP mixtures[EB/OL].
[2009-10-11]. https://www.wendangku.net/doc/401783673.html,/~ywteh/teaching/ npbayes.html.
[15]Neal R. Markov chain sampling methods for Dirichlet
process mixture models[J]. Journal of Computational and Graphical Statistics, 2000, 9:249-265.
[16]Blei M D, Jordan I M. Variational inference for Dirichlet
process mixtures[J]. Bayesian Analysis, 2006(1):121-144.
[17]Blei M D, Frazier P. Distance dependent Chinese
restaurant processes[J]. The Journal of Machine Learning Research, 2011, 12:2461-2488.
[18]Rasmussen, C, Williams C M. Gaussian processes for
machine learning[M]. New York: Springer Press, 2006.
Data Clustering via Nonparametric Bayesian Models
ZHANG Yuan-yuan
(Faculty of Information Science and Engineering, Ningbo University, Ningbo 315211, China )
Abstract: Clustering is one of the most useful techniques in machine learning and data mining. In cluster analysis, model selection concerning how to determine the number of clusters is an important issue. Unlike supervised learning, there are no class labels and criteria to guide the search, so the model for clustering is always difficult to select. To tackle this problem, we present the concept of nonparametric clustering approach based on Dirichlet process mixture model (DPMM), and apply a collapsed Gibbs sampling technique to sample the posterior distribution. The proposed clustering algorithm follows the Bayesian nonparametric framework and can optimize the number of components and the parameters of the model. The experimental result of clustering shows that this Bayes model has promising properties and robust performance.
Key words: nonparametric Bayesian models; Dirichlet process mixture model; clustering analysis; Gibbs sampling
（责任编辑 章践立）
贝叶斯定理在定位与跟踪上应用参考
2.1贝叶斯定理 贝叶斯定理是关于随机事件A和B的条件概率的一则定理。 贝叶斯定理公式：P(A|B)=P(B|A)*P(A)/P(B) （2.1.1） 上面的公式也可变形为：P(B|A)=P(A|B)*P(B)/P(A) （2.1.2） 这里，P(A|B)是在B发生的情况下A发生的可能性。 在贝叶斯定理中，每个名词定义如下： P(A)是A的先验概率。之所以称为"先验"是因为它不考虑任何B方面的因素。 P(A|B)是已知B发生后A的条件概率，也由于得自B的取值而被称作A的后验概率。 P(B|A)是已知A发生后B的条件概率，也由于得自A的取值而被称作B的后验概率。 P(B)是B的先验概率。 2.2贝叶斯估计 2.2.1 贝叶斯估计的基本原理。 A．贝叶斯估计的4个步骤 ?假设 ?将待估计的参数看作符合某种先验概率分布的随机变量 ?估计方式 ?通过观察样本，将先验概率密度通过贝叶斯规则转化为后验概率密度。 B．概率密度估计的两种基本方法 方法1：参数估计(parametric methods) 根据对问题的一般性的认识，假设随机变量服从 某种分布，分布函数的参数通过训练数据来估计。 如：ML 估计，Bayesian估计。 方法2：非参数估计(nonparametric methods)： 不用模型，而只利用训练数据本身对概率密度做 估计。 C．贝叶斯估计应用及其框图 贝叶斯估计应用在很多领域，在概率、数理统计学中以贝叶斯姓氏命名的有贝叶斯公式、贝叶斯风险、贝叶斯决策函数、贝叶斯决策规则、贝叶斯估计量、贝叶斯方法、贝叶斯统计等等. 贝叶斯统计学派把任意一个未知参数都看成随机变量，应用一个概率分布去描述它的未知状况，该分布称为先验分布。 图 2.1 贝叶斯估计应用框图
非参数估计的论文
贝叶斯非参数统计的探讨与研究 14数6 14010648 应陆峰 参考文献：百度百科，中国知网杨磊博士论文 贝叶斯非参数统计是一个新兴的但发展迅速的统计研究领域,不但其理论成果非常丰富,其实际应用范围也十分广泛。然而,贝叶斯非参数统计的传统研究着眼于一种纯贝叶斯的多层先验结构,其中需要事先确定先验分布。一旦不能事先容易地确定先验,特别是因为贝叶斯非参数统计通常要求一个复杂的过程先验,那么这一多层先验结构将会受到挑战和质疑。 传统的贝叶斯非参数统计分析的这一缺陷促使我们采用一种更加灵活,更加稳健的统计框架—经验贝叶斯分析—来实施统计推断和统计建模。这是因为在进行经验贝叶斯分析时,人们通常基于观测数据来估计先验参数,而不是事先主观地给定。另外,众所周知,如果可识别性不成立,那么基于观测值来估计参数将会变得毫无意义,而且,可识别性也是证明参数估计或者后验分布的渐近收敛性质的前提条件之一。许多统计学家试图找出可识别性成立的条件,但据我们所知,确实存在许多关于有限混合可识别性的理论成果；但可数无穷混合的可识别性仍然很少被研究到,因此也是一个开放的问题。例如,Ferguson(1983)指出Dirichlet过程先验的混合模型,作为一个可数无穷混合的特例,其可识别性尚未解决。为了解决贝叶斯非参数统计中这些问题和挑战,基于经验贝叶斯的框架和几种不同的数据结构：一元数据,多元数据和单调缺失数据,我们尝试分别对几类过程先验中的参数进行估计。 根据华东师范大学杨磊博士的论文，本博士论文的主要内容如下所述。首先,在第一章中,我们对贝叶斯非参数统计进行一个全面的回顾,包括：人们为什么使用贝叶斯非参数统计,其简要的历史发展,其丰富的理论成果和实际应用。我们以回顾一系列文献的方式,阐述了贝叶斯非参数统计中的计算问题、未来的研究方向和可能面临的挑战。在此之后,我们引入了人们所熟知的经验贝叶斯假定和几种数据结构。这些数据结构非常普遍且颇具代表性,因而能够表达对多种实际数据进行统计建模的设想。在第二章,通过引入分布集上的良序和序列的一致收敛,我们提出了一个可数无穷混合可识别性成立的充分条件,并且相信此充分条件比Tallis(1969)所提出的无穷维矩阵条件更加容易验证。然后我们运用此充分条件去重新验证了已知可识别性成立的几个例子,进而考查了几个新分布族的可数无穷混合的可识别性,其中包括：正态分布,伽玛分布,柯西分布,非中心卡方分布和广义逻辑斯蒂分布。第三章涉及单调缺失数据机制下Dirichlet过程先验中的先验参数估计问题。我们试图基于经验贝叶斯框架下的部分观测数据,来估计DP(α,α)中的未知精度参数α和未知概率测度a。 我们发现,在Dirichlet过程先验的假定下,数据的缺失不影响精度参数α的估计,因其可以通过极大化某个似然函数来有效地估计。然而,对假定密度函数存在的概率测度a而言,我们必须借助于处理缺失数据的非参数密度估计方法来对其进行估计。精度参数α的估计的强相合性和渐近正态性在非常一般的条件下得到了证明,同时我们也证明了a的密度估计的L1收敛性。另外基于二维单调缺失数据,通过最小化渐近积分均方误差,我们提出了此密度估计的最优窗宽选取方法,并且发现此密度估计优于单调缺失数据下其他已有的方法。第四章涉及一元数据
第三章 非参数判别分类方法
第三章非参数判别分类方法 学习指南： 前一章重点学习的贝叶斯决策具有理论指导的意义，同时也指明了根据统计参数分类决策的方法。沿这条路走就要设法获取样本统计分布的资料,要知道先验概率，类分布概率密度函数等。 然而在样本数不足条件下要获取准确的统计分析也是困难的。这样一来人们考虑走另一条道路，即根据训练样本集提供的信息，直接进行分类器设计。这种方法绕过统计分布状况的分析，绕过参数估计这一环，而企图对特征空间实行划分，称为非参数判别分类法，即不依赖统计参数的分类法。这是当前模式识别中主要使用的方法，并且涉及到人工神经元网络与统计学习理论等多方面，是本门课最核心的章节之一。 非参数判别分类方法的核心是由训练样本集提供的信息直接确定决策域的划分方法。 这里最重要的概念是分类器设计用一种训练与学习的过程来实现。机器自动识别事物的能力通过训练学习过程来实现，其性能通过学习过程来提高，这是模式识别、人工神经元网络中最核心的内容。 学习这一章要进一步体会模式识别中以确定准则函数并实现优化的计算框架。 由于决策域的分界面是用数学式子来描述的，如线性函数，或各种非线性函数等。因此确定分界面方程，包括选择函数类型与确定最佳参数两个部分。 一般说来选择函数类型是由设计者确定的，但其参数的确定则是通过一个学习过程来实现的，是一个叠代实现优化的过程。 因此本章从最简单的函数类型讲起，再扩展到非线性函数。学习的重点要放在线性判别函数的基本内容上，然后再注意如何扩展到非线性函数的应用上去。 该章的学习最好通过概念的反复推敲与思考，以加深对重要概念的理解，另一方面通过实验，亲自体验设计模式识别系统的完整过程，对学习才会更加真切。 学习目的 (1) 通过本章学习掌握模式识别中最重要的非参数判别分类法的原理 (2) 掌握机器自学习的原理，自学习功能已不仅在模式识别中应用，目前经常用机器学习这个词以涉及更为广泛的内容。 (3) 学习线性分类器的三种典型算法，这三种算法各自形成体系，分别形成了传统模式识别、人工神经元网络以及统计学习理论 (4) 用近邻法进行分类 (5) 通过相应数学工具的运用进一步提高运用数学的本领 本章重点 (1) 非参数判别分类器的基本原理，与参数判别分类方法的比较 (2) 线性分类器的三种典型方法——以Fisher准则为代表的传统模式识别方法，以感知准则函数为代表的机器自学习方法，以及支持向量机代表的统计学习理论。
贝叶斯非参数性模型的matlab代码(Matlab codes for Bayesian nonparametric model)
贝叶斯非参数性模型的matlab代码(Matlab codes for Bayesian nonparametric model) 数据介绍： Matlab codes for implementing the Bayesian nonparametric model are given and also can be found on our Web site at (https://www.wendangku.net/doc/401783673.html,/st1sak). Here is a description of the programs and how they are to be used. Note that these codes are not general and so the user needs to modify them for his or her own purposes. 关键词： 算法,统计,matlab代码,贝叶斯模型,非参数性, algorithm,statistic,matlab code,Bayesian model,nonparametric, 数据格式： TEXT 数据详细介绍： Matlab codes for Bayesian nonparametric mode Matlab codes for implementing the Bayesian nonparametric model are given and also can be found on our Web site at (https://www.wendangku.net/doc/401783673.html,/st1sak). Here is a description of the programs and how they are to be used. Note that these
CMU高级机器学习非参数贝叶斯模型
Advanced Machine Learning Nonparametric Bayesian Models -- Learning/Reasoning in Open Possible Worlds --Learning/Reasoning Eric Xing Lecture 17, August 14, 2009 Reading: Eric Xing ? Eric Xing @ CMU, 2006-2009 1 Clustering Eric Xing ? Eric Xing @ CMU, 2006-2009 2 1 Image Segmentation How to segment images? Manual segmentation (very expensive Algorithm segmentation K-means Statistical mixture models Spectral clustering Problems with most existing algorithms Ignore the spatial information Perform the segmentation one image at a time Need to specify the number of segments a priori Eric Xing ? Eric Xing @ CMU, 2006-2009 3 Object Recognition and Tracking (1.9, 9.0, 2.1 (1.8, 7.4, 2.3 (1.9, 6.1, 2.2 (0.7, 5.1, 3.2 (0.9, 5.8, 3.1 (0.6, 5.9, 3.2 t=1 Eric Xing t=2 ? Eric Xing @ CMU, 2006-2009 t=3 4 2 Modeling The Mind … Latent brain processes: View picture Read sentence Decide whether consistent fMRI scan: ∑ … … Eric Xing … t=1 ? Eric Xing @ CMU, 2006-2009 t=T 5 The Evolution of Science Research circles Phy Research topics Bio CS PNAS papers 1900 Eric Xing ? Eric Xing @ CMU, 2006-2009 2000 6 ? 3 A Classical Approach Clustering as Mixture Modeling Then "model selection" Eric Xing ? Eric Xing @ CMU, 2006-2009 7 Partially Observed, Open and Evolving Possible Worlds Unbounded # of objects/trajectories Changing attributes Birth/death, merge/split Relational ambiguity The parametric paradigm: p φk0 ({ } or p({φ } 1:T k Event model p φkt +1 motion model t k ({ } {φ } Ξ*+1|t+1 t Finite Entity space Structurally unambiguous Ξ*|t t Sensor model p(x | {φk } observation space How to open it up? ? Eric Xing @ CMU, 2006-2009 8 Eric Xing 4 Model Selection vs. Posterior Inference Model selection "intelligent" guess: ??? cross validation: data-hungry information theoretic: AIC TIC MDL : ? arg min KL f (? | g (? | θ ML , K Parsimony, Ockam's Razor need to compute data likelihood ( Bayes factor: Posterior inference: we want to handle uncertainty of model complexity explicitly
贝叶斯粗糙集
山西大学研究生学位课程论文 （2010----2011学年第一学期） 学院（中心、所）：计算机信息与技术学院 专业名称：计算机应用技术 课程名称：高等数理统计 论文题目：基于贝叶斯方法的分类预测 授课教师（职称）：张小琴（讲师） 研究生姓名：翁小奎 年级： 2010级 学号： 201022403005 成绩： 评阅日期： 山西大学研究生学院 2011年1月12日
基于贝叶斯方法的分类预测 摘要：本文通过对概率论与数理统计中的贝叶斯方法的学习与了解，并联系与自己研究的相关内容，介绍一下基本的贝叶斯分类模型和贝叶斯信念网络模型，并对网络模型的学习进行了讨论，从实际出发，介绍了几种可以简化模型结构、降低学习复杂性的可行方法，简要说明了这些方法在网络模型中的应用，对贝叶斯分类模型的准确性及其主要特点进行了分析。 关键词：数据挖掘分类预测贝叶斯方法信念网络 l 引言 随着数据库技术的日益成熟和广泛应用，人们收集的数据成指数地增长。尤其是伴随着因特网的诞生和普及，数据量更是急剧增加，人们而对的早已不只是本部门或本企业的庞大数据库，而是来自全球的数据汪洋。如此浩瀚的数据海洋“隐藏了什么”、“预示了什么”、“表明了什么”?人们感到“数据过剩” 和“知识贫乏”的矛盾。由此，从庞大数据集中开采有用知识的技术——数据挖掘(Data Mining)便应运而生。 分类预测是数据挖掘中的一大任务。分类就是找出一组能够描述数据集合典型特征的模型，以便住给定其他变量值的条件下能对人们感兴趣的未知变量值做出预测。分类预测的变最是范畴型的，即将未知数据映射到某种离散类别之一。分类预测模型可以通过分类挖掘算法从一组类别已知的训练样本数据中学习获得。 分类挖掘获得的分类模型可以采用多种形式描述输出，常见的有：分类规则(IF_rrHEN)、决策树、数学公式、神经网络等形式。而基于贝叶斯方法的分类模型则是一种概率模型，常可以借助有向无环图来描述这种概率模型，因此也是一种图形模型。这种图表示强调了模型结构的独立性，在计算机科学中也被称为信念网络(belief network)。在数据挖掘中，通常事先对数据的模型结构了解甚少，因此选择比较简单、灵活的模型结构或函数形式是有益的，而且较简单的模型具有更加稳定和更易于解释的优势，还经常可以为更复杂的模型提供函数分量。基于贝叶斯方法的分类预测模型就具有形式简单、易于解释，且可以很容易从不同的角度进行推广等特点。
第十二章 非参数判别分析与非参数聚类(非参数统计,西南财大)
第十二章 非参数判别分析与非参数聚类 第一节 非参数判别分析 一、引言 关于判别分析的一般概念我们在多元统计分析中已经详细的讨论，在那里我们采用了距离判别、贝叶斯判别和典型判别法。这些判别法都需要估计总体的参数，而贝叶斯判别时，我们还指定了总体服从正态分布。在非参数统计中，不对变量的分布做任何假设，这里主要有两种方法，BAYES 方法和近邻方法进行非参数判别分析。 设有M 个类，用Y 记一具体的对象所属的类，Y 可能的取值为M ,,2,1 。设有了n 个经过明确判定的样本，第i 个样本的指标为i X ,所属的类为),,2,1(n i Y i =，,n 个样本记()()(){},,,,,,,221n n n Y Y Y Z X X X 1 =，常称为“训练样本” 。这一名称的来由使因为日后进行的判别工作依赖，因此可以说它们“训练了”人们如何取进行判别。 非参数方法是基于组概率密度函数的非参数估计。每组的非参数密度估计核产生的分类准则采用核方法或k 最近邻方法。 马氏距离或欧氏距离用来确定样品的接近程度。 二、核方法 1、Bayes 方法概念 设有M 个总体M G G ,,1 分别具有概率分布密度)(),(1x f x f M ，出现M 个总体的先验概率分别为M p p ,,1 ，0>=i p ，11=++M p p 。 贝叶斯判别的规则将样品判给) () ()|(000x f P x f p x G P j j k k k ∑= 最大的类，即 如果)(max )(1x f p x f p j j M j l l ≤≤=，判l G Y ∈ 2、Bayes 方法和密度函数估计的联系
3.4经验Bayes估计
188 3.4 经验贝叶斯估计 经验贝叶斯方法（Empirical Bayes Method ）是H.Robbins 在1955年提出的，这种方法的思想受到统计学者的高度重视.统计界元老J. Neyman 甚至称它为统计判决的“两大突破”之一.几十年来，许多学者将Robbins 的思想用于种种统计问题，得到了一些重要结果. 前面曾经指出，贝叶斯方法的困难之一，就在于要求参数具有一定的先验分布.即使在某项具体问题中可认为这个要求是合理的，参数的先验分布一般也无法预知，因而往往对它做一种人为性规定.因为当先验分布的指定与实际情况不符时，所得的解会受到较大影响，这样以来在对先验分布无法基本确定时，贝叶斯方法的适用性和优越性就受到限制.经验贝叶斯方法就是针对这个问题提出的. 经验贝叶斯方法分为两类，一是非参数经验贝叶斯方法，二是参数经验贝叶斯方法. 3.1 非参数经验贝叶斯方法简介 非参数经验贝叶斯方法完全不指明先验分布，在获得数据后，利用数据来估计有关分布. 假定参数θ∈Θ（Θ为参数空间），θ的先验分布函数为()G θ，分布密度为()πθ. ()d d X D =∈（D 为决策类），损失函数为(,)L d θ，样本空间为*X ，而随机变量*X X ∈.于是对给定的θ，X 的概率密度为(|)f x θ.决策函数d 的风险函数为 []*(,)(,())(,())()X R d E L d X L d x q x dx θθθθθ==∫ )(d R 称为决策函数d 在给定先验分布()G θ下的贝叶斯风 险()[(,)](,)(),R d E R d R d d θθπθθΘ==∫
贝叶斯分类器及概率密度函数估计方法实验
《模式识别》课程实验 贝叶斯分类器及概率密度函数估计方法实验
一、实验目的： 1、掌握密度函数监督参数估计和非参数估计方法； 2、掌握贝叶斯最小错误概率分类器设计方法； 二、实验内容： 对于一个两类分类问题，设两类的先验概率相同（12()()P P ωω=），两类的类条件概 率密度函数服从二维正态分布，即 111(|)~(,)P N ωx μΣ 222(|)~(,)P N ωx μΣ 其中，1[3,6]T =μ，10.5002??=????Σ，1[3,2]T =-μ，12002?? =? ??? Σ。 1）随机产生两类样本； 2）设计最大似然估计算法对两类类条件概率密度函数进行估计； 3）设计非参数估计算法对两类的类条件概率密度进行估计（任选Parzen 窗法或kn-近邻法之一），并分析样本数量、窗宽、k 等因素对概率密度函数估计的影响； 4）分别用2）、3）中估计的类条件概率密度函数设计最小错误概率贝叶斯分类器，实现对两类样本的分类。 三、设计思路： （1）用m vnr nd()函数随机产生两类样本 （2）由已知可知道 1 1N M L i i x N μ== ∑ 将第一问产生的样本代入上面两个式子，得到样本的均值向量和协方差矩阵。 将均值向量和协方差矩阵画出来。 （3）本实验应用Par zen 窗法 选择方窗函数： 1 1 ()() N T i i M L M L i x x N μμ∧∧ ∧ ==--∑∑
当|u |≤0.5时，1)(=u φ 当|u |＞0.5时， 0)(=u φ 构造出X ，Y 坐标，制作网格，用坐标与样本点做差，比上超立方体边长，再将结果与0.5作比较，根据结果确定窗的值。 将窗值代入公式∑== N i N N u V N 1 )(1 1p φ，再用 X 、Y 、P 作图。 （4）在上题基础上给定几个新样本值，用设计的最小错误概率贝叶斯分类器判别，输出结果。 四、实验结果： （1）两类样本： A ．样本一： B ．样本二： （2）最大似然估计