第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)