基于SVM的概率密度估计及分布估计算法

总第236期

2009年第6期

计算机与数字工程

Computer&DigitalEngineeringVol.37No.6

　25

基于SVM的概率密度估计及分布估计算法

徐玉兵　谭　瑛　曾建潮　张建华

(太原科技大学系统仿真与计算机应用研究所　太原　030024)

3

摘　要　在最大熵分布估计算法中,根据Jaynes原理来建立分布估计算法中的概率密度。基于SVM的概率密度估计则是根据概率密度的定义,由核函数构造一个包含未知参数的概率密度函数。它根据样本点建立这个概率密度的数学规划模型,并用不敏感损失函数的支持向量机方法来求解这个模型。对得到的概率密度进行仿真测试,最后将得到的密度应用到分布估计算法中。

关键词　核函数　样本点　舍选法　分布估计算法中图分类号　TP301

DensityEstimationBasedonSupportVectorne

withitsApplicationinEstimationhms

XuYubing　TanYingianhua

(SystemsSimulationand,UniversityofScienceandTenchnology,Taiyuan　030024)

Abstract　In

theedistributionestimatealgorithmanditsapplication,itconstructsthedensityof

theestimationofdistalgorithmsaccordingtoJaynesprinciple.Onthebasisofprobabilitydensityandthroughthekernelfunction,densityestimationbasedonsupportvectormachineconstructsaprobabilitydensityfunctionwhichin2cludesunknownparameters.IttakesuseofinsensitivelossfunctionπsSVMtosolvethemathematicalmodelthatwascon2structedbysamplepoints.Havingasimulationtestonthedensity,thenitwillbeappliedintheestimateofdistributional2gorithm.

Keywords　kernelfunction,empiricaldistributionfunction,regressionestimate,acceptance-rejectionmethod,es2timationofdistributionalgorithms

ClassNumber　TP301

1　引言

概率密度具有广泛应用,可用于数据挖掘中的聚类分析[1]以及电子器件寿命估计和排队论[2]。在一些情况下我们可以知道密度服从的分布,如电子器件寿命服从指数分布以及排队理论服从的泊松分布,它们的密度可以通过样本矩估计或极大似然估计等参数估计方法得到概率密度。但在实际应用中很多时候我们并不知道概率密度服从的分布,这时可根据样本

点进行回归估计得到实际概率密度的一个近似估计。

然而参数估计具有很大的局限性。例如对高斯分布可以估计未知参数,但对混合高斯密度就得不到很好的结果。在60年代,人们提出了非参数估计方法并建立了一套完善的渐近理论。这种方法的目标是从较宽的函数集中估计密度,而不是局限于参数化的函数集。非参数估计是为解决密度估计和函数回归估计的问题发展起来的。为了使理论全面,人们找到构造和分析非参数算法的一般

3

收稿日期:2009年3月26日,修回日期:2009年4月13日

作者简介:徐玉兵,男,硕士研究生,研究方向:智能计算。谭瑛,女,教授,硕士生导师,研究方向:数据库,决策支持系统。曾建潮,男,教授,博士生导师,研究方向:复杂系统与群体智能,智能计算,群控制与决策。张建华,男,博士研究生,研究方向:分布估计算法。

　26徐玉兵等:基于SVM的概率密度估计及分布估计算法第37卷

性原则。后来又产生对非参数估计具有稀疏性的支持向量机方法[4]。

对于ε我们也可以去取它的值,逼近精度ε越低则需要的支持向量的个数越少[5]。对一维情况的概率模型我们采用的核函数[5]为:

K(x,z)=k(x,z)=

2　支持向量机方法估计概率密度

2.1　概率密度的性质及构造

1+e-

t(x-z)

(10)

t(x-z)

由概率密度的定义[2]可知概率密度具有非负性和规范性,即概率密度p(x)需满足:

p(x)≥0且

2+e

t(x-z)

+e-

(11)

∫

-∞

+∞

p(x)dx=1(1)(2)

t为一常数,函数K是k的积分,经检验k(x,z)≥0

假设　(x1,y1),(x2,y2),…,(xl,yl)

且

∫k(x,z)dx=1。对概率密度是二维的情况

-∞

+∞

是取自概率密度p(x)未知的分布的一系列样本点

(xi可以是数或向量0≤yi≤1,若yi未知则通过构

我们采用的核函数是:

K(X,Xi)=k(X,Xi)=

造经验分布函数来获得[3])。我们构造一个概率密度函数

l

1+e

)-t(X1-X1i

1+e-

22t(X-Xi)

(12)

2+e

11t(X-Xi)

+e-

11t(X-Xi)

×

(13)

)=p(x,β

i=1

βik(x,xi)∑

[4]

(3)

对未知的概率密度p(x)进行回归估计,其中

k(x,xi)是核函数

l

2+et

(X2-X2)

i

+e-

2t(X-X)

。由于式(3)是概率密度,因此

k(,ikXi)=

根据概率密度的性质需要满足下面的条件:

i=1

k(x,x)dx=1。

-∞

i

+β∑

i

=1　i=1,…,l

(=(5)

2+e

dd

-Xi)

11t(X-Xi)

+e-

11t(X-Xi)

×…×

(14)

k(x,t)≥0且

()-∞

+2+e

t(X

d

d

-Xi)

+e-

t(X

t是以未知参数变量。用基于支持向量机的方

d为密度的维数。

法求解线性算子方程[4]:

Ap(x)=F(x

)

(6)

A是运算算子,对函数p(x)运算之后,得到F(x)。

2.3　概率密度仿真结果

一维概率密度的仿真结果:核函数中的t的值取1.85,从概率密度函数:

p(x)=0.2就是通过核函数和样本点式(2)对p(x)在像空间进行回归估计得到关于核函数的概率密度式(3)中

的βi的值。2.2　求解概率密度的数学模型

-e

π2

2

-+0.8e

π2

72

(15)

中采41个样本点,然后再用采样点构造一概率密度函数,使构造的概率密度函数的分布尽可能逼近实际概率密度的分布。实验

图1　测试密度与实际密度

在本文中我们采用ε不敏感损失函数

l

l

ii

l

[3,6]

的线

性SVM方法。进行回归估计,该问题等价于:

3

ξ,ξ)=min　F(

l

i=1

δβ+∑ξ+∑ξ∑

i=1

i=1

j

3

(7)

结果如图1,虚线表示

s.t　yj-l

i=1

βK(x∑

ij

ε+ξ,xi)≤j=1,2,…,lj　

3

实际概率密度函数,实

线表示构造的概率密度函数。从图上可以看出构造的概率密度与实际的概率密度非常接近。虚线表示实际密度,实线表示回归估计的概率密度。

下边二维正态分布N(0,1,0,1,0)的密度图像,及用支持向量机密度估计法对N(0,1,0,1,0)进行估计得到的密度图像(t=1.85,采样点为121个):

对混合分布0.4×N(0,1,0,1,0)+0.6×N(6,1,6,1,0)进行测试(t=1.65,采样点为180

i=1l

βK(x∑

i

ε+ξ,xi)-yj≤j=1,2,…,lj　

i=1

β=1∑

i

3

ξ　　0,ξ0,β0　j=1,2,…,lj≥j≥j≥

δ　　i=

l

l

j=1

∑‖xi-xj‖2

yi(1-yi)　i=1,2,…,l

l

(8)(9)

ε=min　　

个):

第37卷(2009)第6期计算机与数字工程　27

分布估计算法可归纳为下面几个步骤[8]:

1)随机产生包含N个个体的种群。

2)构建描述解空间的概率模型,通过对种群的

评估,选择优秀的个体集合,然后采用统计学习等手段构建一个描述当前解的概率模型。

3)由概率模型随机采样产生包含M(N<M)个新个体的种群。

4)用测试函数对M个新个体进行测试选出适应度最好的N个个体。此时若满足要求停止,否则转到2)。

3.2　本文使用的分布估计算法

本文的分布估计算法步骤如下:

1)用随机函数产生包含N个个体的种群;2)根据一致的样本点,支持向量机的方法构建

描述解空间的概率模型;

3)2)中建立的概率个新个体的种群;

M个新个体进行测试选出适N个个体。此时若满足要求停止,否则转到2)。3.3　采样方法

在分布估计算法中的第三步我们采用扩展的舍选法采样[9]。设f(x)是密度函数sup{f(x):x∈R}=f0<∞,f(x)=0当x|[a,b]时。生成以

f(x)为密度的随机变量X的简单舍选算法如下:

1)生成[0,1]上的独立均匀随机数u和v,U=

a+(b-a)×u,V=f0×v;

2)若V≤f(U)则X=U,输出U;3)转1),直到有输出。

2.4　结论

假设测试函数的取值域为[ai,bi],若扩展到d维模型则需生成[0,1]上的d+1个独立随机数

rndi使得

xi=ai+(bi-ai)×rndi,i≤d,f=f0×rndd+1

(16)

从上面的仿真中我们可以看出,用支持向量机的方法求解出的概率密度函数可以很好的逼近实际的概率密度。

3　基于支持向量机的概率密度在分

布估计算法中的应用

3.1　分布估计算法的简单介绍与模型

3.4　将验证过的概率模型用于分布估计算法中并

进行测试测试函数:

d

分布估计算法

[8]

是在进化算法领域兴起的一

f1(x)=

类新型的优化算法。在分布估计算法舍弃了遗传算法的交叉和变异等遗传操作,采用概率模型来学习和采样。它通过一个概率模型描述候选解在空间中的分布,从宏观角度建立一个描述解分布的概率模型,然后对概率模型采样产生新的种群。如此反复进行,实现种群的进化直到终止条件。

i=1

2

(xi-x2+(xi-1)i)

-10≤x≤10

d

f2(x)=-110

-5

+

i=1

∑y

i

y1=x1,yi=xi+yi-1i=2　-0.16≤xi≤0.16

　28

d

徐玉兵等:基于SVM的概率密度估计及分布估计算法第37卷

f3(x)=1+

i=1

4000

2

d

-

i=1

∏

cos

等教育出版社,2003

[2]魏宗舒.概率论与数理统计教程[M].北京:高等教

-10≤xi≤10

育出版社,1983

[3]J.Weston,A.Gammerman,M.Stitson,V.Vapnick,V.Vovk,C.WatkinsDensityEstimationUsingSupportVec2torMachine[M].TechnicalReortCSD-TR-97-23,1998

[4]VapnikVN.张学工译.统计学习理论的本质[M].

进行50次实验,每次试验的进化代数为100代并将50次的最优值的平均值作为实验结果。

表1　所求密度应用于分布估计算法所得测试结果

测试f1f2f3

个体的种群的选择找到最优值求得的平均220000.1506.1859310-6220000.150-3.996310-3220000.1507.229310-6

北京:清华大学出版社,2000

[5]VladimirN.Vapnik.许建华,张学工译.统计学习

理论[M].北京:电子工业出版社,2004

[6]张炤,张素,章琛曦,等.基于支持向量机的概率密

4　结语

由二、三部分的实验可以看出,用支持向量机方法求得的概率密度可以很好地逼近实际概率密度,并在相应的分布估计算法中取得了较好的效果。该概率密度更接近于实际概率密度,而不同于现在的分布估计算法中使用的含参数的高斯概率密度方法,对于高维的情况我们需要进一步研究。

参考文献

[1]李雄飞,李军.[:度估计方法[J].系统仿真学报,2005,17(10):2355～2357

[7]VapnikV,MukherjeeS.SupportVectorMethodforMultivariateDensityEstimation[M].AdvancesinNeuralInformationProcessingSystems,MITPress,2000:659～665

[8]周树德,孙增圻.[J].自动化学

报,2007,33(2)124

],.[J].

(4):40～43

数学建模于数学实验[M].赵静译.北京:高等教

育出版社,2000

(上接第20页)[7]对模糊ISODATA方法进行改进,定义反映了样

则会引起计算溢出。实际应用中发现:m值的选取应注意:m值越小,迭代次数越少,分类速度越快,分类矩阵U的值越趋向于0,1两极,最优分类矩阵的模糊性越小[5];

()

4)参数m、分类数c、初始分类矩阵U0和ε的取值,都影响最终的软分类矩阵。已有一些关于从众多的软分类矩阵选出最优的分类矩阵的标准(关于聚类有效性的研究),例如:Bezdek的划分系数法、平均模糊熵法,比例指数法和文献[6]等等。

5)上述模糊ISODATA优化迭代方法以目标

c

n

本Xj与第i类中心Vi的差异程度的加权广义闵氏权距离,使之在理论上更加严谨,在应用上更适合需要考虑指标不同时权重对分类的影响与作用。

6)文献[8]探讨了动态模糊ISODATA的聚类方法,这种方法能自动增加或减小分类数,提供分类的隶属函数以供分析每一样本与各类的关系,从而获得有关类别边界的信息,准确的实现分类。

参考文献

[1]贺仲雄.模糊数学及其应用[M].天津科学技术出

版社,1983

[2]J.C.BezedekClustervaliditywithfuzzysets[J].JournalofCybernetics,1974,3(3):58～72

[3]J.C.BezdekPhysicalinterpretationoffuzzyISODATA[J].IEEETrans,SystemsMan,Cybern,1976,SME-6

[4]张俊福.应用模糊数学[M].地质出版社,1988[5]张冠军.变压器绝缘诊断中的模糊ISODATA法[J].高电压技术,1999,(1)

[6]于剑,程乾生.关于聚类有效性函数EP(u,c)的研

函数J(U,V)=

i=1j=1

∑∑

uij‖xj-vi‖为基础。由

2

于对上式表示的函数求关于uij的导数时,变量uij将会消失而无法解得uij,为此,引入任意参数m作

),这样目标函数就变为变量uij的指数(1≤m<∞

为式Jm(U,V)。显然,参数m的引入在数学理论上不够严密,实际上如何取定m就缺乏依据,从而引入一定的主观任意性。为此,Bezdek在文[3]中对参数m的确定进行了模拟试验研究,试验结果表明,参数m以采用2为优。

考虑到现实中各个样本的特征指标对分类的影响一般来说并不等同,必须赋以不同的权重,文献

究[J].电子学报,2001,(7)

[7]黄健元.模糊ISODATA聚类分析方法的改进[J].

南京航空航天大学学报,2000,32(2)

[8]毖为建.动态模糊ISODATA聚类方法及其在故障

诊断中的应用[J].同济大学学报,1997,25(1)

本文来源：https://www.bwwdw.com/article/bysm.html