（电路与系统专业论文）延迟25ms+8kbps语音编码算法研究.pdf

太原理工大学博士研究生学位论文 基于计算智能的谱聚类方法研究 摘要 i i r f l l ijii i m rl l j i i f r f ll l l l l l lh l y 2 15 5 8 5 7 随着信息技术的快速发展，各行各业积累了大量的数据，如何帮助用 户从这些数据中提取人们感兴趣的、隐含的、对决策有潜在价值的知识， 已经成为信息技术领域的热点问题。作为一类新型的聚类分析方法，谱聚 类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意 形状的样本空间上聚类的优点，且仅与数据对象的数目有关，而与数据的 维数无关，因而可以避免高维特征向量所造成的奇异性问题。 谱聚类算法受到传统k - m e a n s 算法的影响，不同的初始聚类中心将会得 到不同的聚类结果，且易陷入局部最优解，收敛速度缓慢，同时聚类分组 数七的确定直接影响了聚类的质量，如何自动确定聚类分组数后是谱聚类算法 中一个关键问题。计算智能作为智能信息处理技术发展最有生命活力的研 究方向，它模拟自然界生物体系和人类智能，用计算机来模拟和再现某些 智能行为，主要包含遗传算法、人工免疫算法和蚁群算法等。 引入计算智能，本文主要针对谱聚类算法中初始化敏感问题，易陷入 局部最优问题和如何自动确定聚类分组数k 问题进行了较为深入的研究，主 要内容如下： 针对聚类算法对初始聚类中心敏感的问题，提出一种启发式初始化独 立的k - m e a n s 算法，并在此基础上提出了启发式初始化独立的谱聚类算法。 依据p r i m 算法选取庀个初始聚类中心，同时考虑距离和密度因素，且通过 设置闽值参数目避免同一类中的多个数据对象同时作为初始聚类中心。实 太原理工大学博士研究生学位论文 验结果表明，该算法通过谱映射达到了数据降维的目的，优化了原始谱聚 类算法的初始中心选取策略，有效地避免了初始聚类中心选取的盲目性， 快速地找到合适的初始聚类中心，而且降低了离群点数据对聚类性能产生 的影响，有效减少了聚类的迭代次数，提高了运行效率。 引入遗传算法，提出了一种遗传优化的谱聚类算法，较好地解决了原 始谱聚类算法容易陷入局部最优解的问题。实验结果表明该算法有效降低 了随机初始输入数据对算法的影响，提高了算法的稳定性和聚类性能。 针对谱聚类算法中如何确定聚类分组数的问题，提出了用于自动确定 聚类分组数k 的免疫聚类两阶段模型，据此提出了一种自适应谱聚类算法。 该算法通过模拟初次免疫应答和二次免疫应答过程，实现了聚类分组数k 的自动确定，并得到了相应的聚类中心，然后利用传统的聚类算法进行聚 类。人工数据集和u c i 数据集的实验结果表明，该算法不仅可以自动确定 聚类分组数，得到合适的聚类中心，而且有效地消除了数据输入顺序对算 法的影响，具有较好的扩展性，并可应用于增量样本数据的识别中。 分析社保审计中存在的问题和社保数据的特点，提出了一种基于聚类 分析的社保联网审计分析模型，将白适应谱聚类算法应用到基本养老保险 数据的审计中。实验结果表明，该算法可以自动确定合适的社保数据聚类 分组数，且得到了较高的聚类准确率。通过对聚类分组进行分析，归纳总 结了相关的社保规则，用于辅助社保人员做出审计判断，降低审计风险。、 关键词：聚类分析，谱聚类算法，最小生成树，遗传算法，人工免疫系统， 免疫应答 太原理工大学博士研究生学位论文 r e s e a r c ho ns p e c t r a l c l u s t e r i n gb a s e d o nc o m p u t a t i o n a li n t e l l i g e n c e a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，ah u g em a s so fd a t aa r e g e n e r a t e di nv a r i o l l sw a l k so f l i f e h o wt oh e l pp e o p l ee x t r a c tf r o mt h ed a t at h e h i d d e na n du s e f u li n f o r m a t i o nt h a tt h e ya r ei n t e r e s t e di nh a sb e c o m eah o tt o p i c i nt h ed o m a i no fi n f o r m a t i o nt e c h n o l o g y a san e w t y p eo fc l u s t e r i n ga n a l y s i s b a s e do ns p e c t r a lt h e o r y ，s p e c t r a lc l u s t e r i n ga l g o r i t h m sh a v et h ea d v a n t a g eo f c l u s t e r i n gd a t ai na n ys a m p l es p a c ec o m p a r e dw i t ht h et r a d i t i o n a lc l u s t e r i n g a l g o r i t h m b e s i d e s ，t h e ya r eo n l yr e l a t e dt ot h en u m b e ro f d a t ao b je c t s ，b u th a v e n o t h i n gt od ow i t hd a t ad i m e n s i o n s ，w h i c hc a na v o i dt h es i n g u l a r i t yp r o b l e m c a u s e db yh i g h d i m e n s i o n a le i g e n v e c t o r s a s s p e c t r a lc l u s t e r i n ga l g o r i t h m i si n f l u e n c e db yt r a d i t i o n a lk - m e a n s a l g o r i t h m ，d i f f e r e n ti n i t i a lc l u s t e r i n gc e n t e r sw i l lr e s u l t i ng e t t i n gd i f f e r e n t c l u s t e r i n g r e s u l t si n s p e c t r a lc l u s t e r i n ga l g o r i t h m ，a n ds p e c t r a l c l u s t e r i n g a l g o r i t h m i s a p tt of a l l i n g i n t ol o c a l o p t i m a ls o l u t i o n b e s i d e s ，h o w t o a u t o m a t i c a l l yd e t e r m i n i n gt h ec l u s t e rn u m b e rki sak e yi s s u e ，w h i c hd i r e c t l y a f f e c tt h ec l u s t e r i n gq u a l i t y a st h em o s tv i t a lr e s e a r c hd i r e c t i o ni ni n t e l l i g e n t i n f o r m a t i o np r o c e s s i n gt e c h n o l o g y ，c o m p u t a t i o n a li n t e l l i g e n c ei si n s p i r e df r o m t h en a t u r a l b i o l o g i c a ls y s t e ma n dh u m a ni n t e l l i g e n c e ，u s i n gc o m p u t e rt o s i m u l a t ea n dr e p r e s e n ts o m ei n t e l l i g e n ta c t i o n s ，w h i c hm a i n l yi n c l u d eg e n e t i c a l g o r i t h m ，a r t i f i c i a li m m u n ea l g o r i t h ma n da n tc o l o n ya l g o r i t h m e t c i i i i n t r o d u c i n gc o m p u t a t i o n a li n t e l l i g e n c et os p e c t r a lc l u s t e r i n ga l g o r i t h m ，t h e p a p e rm a i n l y f o c u s e so np r o b l e m ss u c ha si n i t i a l i z a t i o ns e n s i t i v i t y ，l o c a l o p t i m a ls o l u t i o na n dd e t e r m i n i n ga u t o m a t i c a l l yt h en u m b e ro fc l u s t e r i n g i n s p e c t r a lc l u s t e r i n ga l g o r i t h m t h em a i n c o n t e n t sa r ea sf o l l o w s ： t os o l v et h es e n s i t i v ei s s u eo fi n i t i a lc l u s t e r i n gc e n t e r si nc l u s t e r i n g a l g o r i t h m s ，ah e u r i s t i ci n i t i a l i z a t i o n i n d e p e n d e n tk - m e a n sa l g o r i t h mi sp r o p o s e d b a s e do ni m p r o v e dk - m e a n sa l g o r i t h m ，ah e u r i s t i ci n i t i a l i z a t i o n i n d e p e n d e n t s p e c t r a lc l u s t e r i n ga l g o r i t h mi sp u t f o r w a r d ki n i t i a lc l u s t e r i n gc e n t e r sa r e s e l e c t e db ym e a n so fp r i ma l g o r i t h m ；f a c t o r so fd i s t a n c ea n dd e n s i t ya r et a k e n i n t oa c c o u n t ；a n dt h et h r e s h o l dp a r a m e t e r0i ss e tt oa v o i ds e l e c t i n gt w oo r m o r ed a t ao b i e c t sf r o mt h es a m ec l a s s a si n i t i a l c l u s t e r i n g c e n t e r s 1h e 一 rtll e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mc a na c h i e v et h e a i mo fr e d u c i n gd a t a d i m e n s i o nb ys p e c t r a lm a p p i n g ，o p t i m i z et h es e l e c t i o ns t r a t e g yo f i n i t i a lc e n t e r s i n s p e c t r a la l g o r i t h m ，l e s s e n t h e i m p a c t o fo u t l i e rd a t ao nc l u s t e r i n g p e r f o r m a n c e ，a n de f f e c t i v e l yr e d u c et h ei t e r a t i o nt i m e sa n dt h u si m p r o v et h e r u n n i n ge f f i c i e n c y c o m b i n e dw i t ht h eg l o b a ls e a r c ha b i l i t yo fg e n e t i ca l g o r i t h m ，as p e c t r a l c l u s t e r i n gb a s e do ng e n e t i ca l g o r i t h mi sp u tf o r w a r d ，w h i c hc a nw e l ls o l v e t h e p r o b l e mo ft h eo r i g i n a la l g o r i t h m sa p t n e s sf a l l i n gi n t ol o c a lo p t i m a ls o l u t i o n e x p e r i m e n t a lr e s u l t si n d i c a t et h a t ，t h ea l g o r i t h m c a ne f f e c t i v e l yr e d u c et h e i m p a c to f r a n d o mi n i t i a li n p u td a t a ，a n dw i t hab e t t e rs t a b i l i t yi tc a ni m p r o v et h e c l u s t e r i n gp e r f o r m a n c e a t w o s t a g em o d e lo fi m m u n ec l u s t e r i n gi sp r o p o s e dt os o l v et h ep r o b l e m o fh o wt oa u t o m a t i c a l l yd e t e r m i n et h en u m b e ro fc l u s t e r s b a s e do nt h em o d e l ， a na d a p t i v es p e c t r a lc l u s t e r i n ga l g o r i t h mi st h e np u tf o r w a r d t h ea l g o r i t h m s u c c e e d si nd e t e r m i n i n ga u t o m a t i c a l l yt h en u m b e rko fc l u s t e r sb ys i m u l m i n g t h ep r o c e s so fp r i m a r yi m m u n er e s p o n s ea n dt h es e c o n di m m u n er e s p o n s e i t i v 太原理工大学博士研究生学位论文 a l s os u c c e e d si ng e t t i n gt h ec o r r e s p o n d i n gc l u s t e r i n gc e n t e r s a n dt h e nt h e t r a d i t i o n a lc l u s t e r i n ga l g o r i t h mi se m p l o y e dt oc l u s t e rt h ed a t a b o t ht h e e x p e r i m e n t si na r t i f i c i a ld a t a s e t sa n du c i d a t a s e t ss h o wt h a tt h ea l g o r i t h m ，w i t h ab e t t e rs c a l a b i l i t y ，c a nn o to n l yc o m p u t et h ev a l u eo f 岛g e tt h ea p p r o p r i a t e c e n t e r s ，e l i m i n a t e st h ei m p a c to fd a t ai n p u to r d e re f f e c t i v e l y ，b u ta l s o c a n a p p l i e d t oi d e n t i f yt h ei n c r e m e n t a ld a t a b ya n a l y z i n gt h ep r o b l e m si ns o c i a ls e c u r i t ya u d i t i n ga n dt h ef e a t u r e so f s o c i a ls e c u r i t yd a t a ，as o c i a ls e c u r i t ya u d i tm o d e lb a s e do nc l u s t e r i n ga n a l y s i si s p r o p o s e d 。a na d a p t i v es p e c t r a lc l u s t e r i n gi sa p p l i e d t ot h ea u d i to fb a s i cp e n s i o n i n s u r a n c ed a t a t h ee x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mc a na u t o m a t i c a l l y d e t e r m i n et h ea p p r o p r i a t ec l a s sn u m b e ro fs o c i a ls e c u r i t yd a t a ，a n do b t a i na h i g h e rc l u s t e r i n ga c c u r a c y b a s e do nt h ec l u s t e r i n ga n a l y s i s ，t h er e l e v a n ts o c i a l s e c u r i t yr u l e sa r es u m m a r i z e dt oh e l pt h es o c i a ls e c u r i t ys t a f fm a k er e a s o n a b l e a u d i tj u d g m e n ta n da v o i da u d i tr i s k s k e y w o r d s ：c l u s t e r i n ga n a l y s i s ，s p e c t r a lc l u s t e r i n g ，m i n i m u ms p a n n i n gt r e e ， g e n e t i ca l g o r i t h m ，a r t i f i c i a li m m u n es y s t e m ，i m m u n er e s p o n s e v 太原理工大学博士研究生学位论文 图索引 图1 1 典型的聚类过程2 f i g 1 1t h ec l u s t e r i n gp r o c e s s 2 图1 2 数据集d 1 的聚类结果1 0 f i g 1 2t h ec l u s t e r i n gr e s u l t so f d l 1 0 图1 3 数据集d 2 的聚类结果1 1 f i g 1 3t h ec l u s t e r i n gr e s u l t so f d 2 1 l 图2 1 个体结构1 8 f i g 2 - 1i n d i v i d u a ls t r u c t u r e 18 图2 2 免疫应答过程2 1 f i g 2 - 2t h ei m m u n er e s p o n s ep r o c e s s 2 1 图2 3 克隆选择学说示意图2 1 f i g 2 一：；s c h e m a t i cd i a g r a mo f c l o n i n gs e l e c t i o nt h e o r y 2 1 图3 一lh i i k m 算法的流程图2 8 f i g 3 1f l o wd i a g r a mo f h i i k ma l g o r i t h m 2 8 图3 2k - m e a n s 算法的聚类迭代过程( a ) 任意选取三点作为初始聚类中心( b ) g 一次迭代后更新 聚类中心( c ) 第二次迭代后更新聚类中心( d ) 第三次迭代更新聚类中心( 最优解) 2 9 f i g 3 2t h ei t e r a t i o no fk - m e a n sa l g o r i t h m ( a ) c h o o s et h r e ep o i n t sa st h ec e n t e r so fi n i t i a lc l u s t e r ( b ) u p d a t et h ec l u s t e r i n gc e n t e r sa f t e rf i r s ti t e r a t i o n ( c ) u p d a t et h ec l u s t e r i n gc e n t e r sa f t e rs e c o n d i t e r a t i o n ( d ) u p d a t et h ec l u s t e r i n gc e n t e r sa f t e rt h i r di t e r a t i o n ( t h eo p t i m a ls o l u t i o n ) 2 9 图3 3h i i k m 算法的聚类迭代过程( a 讨艮据h i i k m 算法选取三点作为初始聚类中心( b ) 第一次 迭代后更新聚类中心( 最优解) 3 0 f i g 3 - 3t h ei t e r a t i o no fk - m e a n sa l g o r i t h m ( a ) c h o o s et h r e ep o i n t sa st h ec e n t e r so fi n i t i a lc l u s t e r a c c o r d i n gt oh i i k m ( b ) u p d a t et h ec l u s t e r i n gc e n t e r sa f t e rf i r s ti t e r a t i o n ( t h eo p t i m a ls o l u t i o n ) 3 0 图3 4k - m e a n s 算法的聚类迭代过程( a ) 任意选取三点作为初始聚类中心3 1 f i g 3 4t h ei t e r a t i o no f k - m e a n sa l g o r i t h m ( a ) c h o o s et h r e ep o i n t sa st h ec e n t e r so f i n i t i a lc l u s t e r 。31 图3 5h i i k m 算法的聚类迭代过程( 槲艮据h i i k m 算法选取三点作为初始聚类中心3 1 f i g 3 - 5t h ei t e r a t i o no fh i i k ma l g o r i t h m ( a ) c h o o s et h r e ep o i n t sa st h ec e n t e r so fi n i t i a lc l u s t e r a c c o r d i n gt oh i i k m ( b ) u p d a t et h ec l u s t e r i n gc e n t e r sa f t e rf i r s ti t e r a t i o n ( t h eo p t i m a ls o l u t i o n ) 31 图3 - 6k - m e a n s 算法选取的初始聚类中心3 3 f i g ：；- 6t h ei n i t i a lc e n t e r so f c - m e a n sa l g o r i t h m 3 3 图3 7h i i k m 算法选取的初始聚类中心3 3 f i g 3 - 7t h e i n i t i a lc e n t e r so fh i i k ma l g o r i t h m 3 3 图3 8 教据集在二维空间的投影图3 5 f i g 3 8t w o d i m e n s i o np r o j e c t i o no f 3d a t a s e t s 3 5 图3 - 9h i i k m 算法选取的初始聚类中心3 6 f i g 3 - 9t h ei n i t i a lc e n t e r so f h i i k ma l g o r i t h m 3 6 图3 1 0 原始数据集3 9 f i g 3 - 1 0o r i g i n a ld a t a s e t 3 9 图3 1 1k - m e a n s 算法选取的初始聚类中心3 9 f i g 3 - - 1 1i n i t i a lc e n t e r so f k - m e a n sa l g o r i t h m 3 9 图3 1 2s c 算法选取的初始聚类中心3 9 x i 太原理工大学博士研究生学位论文 f i g 3 - 1 2i n i t i a lc e n t e r so f s p e c t r a lc l u s t e r i n ga l g o r i t h m 3 9 图3 1 3h i i s c 算法选取的初始聚类中心一4 0 f i g 3 一l31 1 1 i t i a lc e n t e r so f h i i s ca l g o r i t h m 4 0 图3 1 4k - m e a n s 算法的聚类结果4 0 f i g 3 - 1 4c l u s t e r i n gr e s u l t so f k - m e a n sa l g o r i t h m 4 0 图3 1 5s c 算法的聚类结果4 1 f i g 3 1 5c l u s t e r i n gr e s u l t so f s p e c t r a lc l u s t e r i n ga l g o r i t h m 4 1 图3 1 6h i i s c 算法的聚类结果4 1 f i g 3 - 1 6c l u s t e r i n gr e s u l t so f h i i s ca l g o r i t h m 4 1 图3 1 7 原始数据集的谱映射4 1 f i g 3 - 1 7s p e c t r a lm a p p i n go f o r i g i n a ld a t a s e t z 1 1 图3 1 83 种算法的聚类性能对比4 3 f i g 3 - 1 8t h ep e r f o r m a n c ec o m p a r i s o no f 3a l g o r i t h m s 4 3 图4 1 遗传算法的工作原理一4 6 f i g 4 1t h ep r i n c i p l eo f g e n e t i ca l g o r i t h m 4 6 图4 2d 3 数据分布5 2 f i g 4 2t h ed a t ad i s t r i b u t i o no f d 3 5 2 图4 3d 1 数据集上的r a n d 指标5 4 f i g 4 3t h er a n di n d e xo f d l 5 4 图4 4d 2 数据集的r a n d 指标5 4 f i g 4 4t h er a n di n d e xo f d 2 ：1 5 z i 图4 5d 3 数据集的r a n d 指标5 5 f i g 4 - 5t h er a n di n d e xo f d 3 5 5 图4 - 6u c i 数据集上的r a n d 指标5 7 f i g 4 - 6t h er a n di n d e xo f u c id a t a s e t s 5 7 图5 1 人工免疫算法的工作原理5 9 f i g 5 - 1t h ep r i n c i p l eo f a r t i f i c i a li m m u n ea l g o r i t h m 5 9 图5 2 免疫聚类两阶段模型6 2 f i g 5 - 2t h et w o s t a g em o d e lo fi m m u n ec l u s t e r i n g 。6 2 图5 3l o g i s t i c 映射6 5 f i g 5 3l o g i s t i cm a p p i n g 6 5 图5 - 4 原始数据6 9 f i g ：；4o r i g i n a ld a t a 6 9 图5 5 非凸原始数据7 0 f i g 5 5n o n c o n v e xo r i g i n a ld a t a 7 0 图5 - 6d 1 数据集的第一阶段实验结果7 1 f i g 5 6t h ef i r s t s t a g er e s u l t so f d l 7 1 图5 7d 1 数据集的第二阶段实验结果一7 1 f i g 5 - 7t h es e c o n d s t a g er e s u l t so f d l 7 1 图5 - 8d 2 数据集的实验结果7 2 f i g 5 8t h ec l u s t e r i n gr e s u l t so f d 2 7 2 图5 9d 3 数据集的实验结果7 2 f i g 5 - 9t h ec l u s t e r i n gr e s u l t so f d 3 7 ：! 图5 1 0d 4 数据集的实验结果7 3 x i i 太原理工大学博士研究生学位论文 f i g 5 - 1 0t h ec l u s t e r i n gr e s u l t so f d 4 7 3 图5 1 ld 5 数据集的实验结果7 3 f i g 5 1 1t h ec l u s t e r i n gr e s u l t so f d 5 7 3 图5 1 2s o n a r 数据集的实验结果7 5 f i g 5 1 2t h et w o s t a g er e s u l t so f s o n a r 7 5 图5 1 3i r i s 数据集的实验结果7 5 f i g 5 - 1 3t h et w o s t a g er e s u l t so f i r i s 7 5 图5 1 4w i n e 数据集的实验结果7 5 f i g 5 1 4t h et w o - s t a g er e s u l t so f w m e 7 5 图5 1 5v e h i c l e 数据集的实验结果7 5 f i g 5 1 5t h et w o - s t a g er e s u l t so f v e h i c l e 7 5 图5 16s1 的实验结果7 8 f i g 5 - 1 6t h ec l u s t e r i n gr e s u l t so f s l 7 8 图5 1 7s 2 的实验结果7 8 f i g 5 - 1 7t h ec l u s t e r i n gr e s u l t so f $ 2 。7 8 图5 1 8s 3 的实验结果7 8 f i g 5 - 1 8t h ec l u s t e r i n gr e s u l t so f s 3 一7 8 图5 。1 9s 4 的实验结果一