（应用数学专业论文）数据质量和隐私保护中聚类分类算法的应用研究.pdf

数据质量和隐私保护中聚类分类算法的应用研究 作者姓名：吕威 导师姓名：李磊、姚正安教授 摘要 数据质量和隐私保护问题已经引起了学术界广泛的关注，并已成为当前学术界的热点 研究领域数据质量并不仅仅是指数据错误，通常定义为数据的一致性( c o n s i s t e n c y ) 、正 确性( c o r r e c t n e s s ) 、完整性( c o m p l e t e n e s s ) 和最小性( m i n i m a l i t y ) 这四个指标在信息系统中 得到的满足程度，也有文献把“适合使用”作为衡量数据质量的初步标准基于隐私保护的 数据挖掘是指在尽量不影响挖掘结果的情况下，让一些敏感信息得到尽可能多的保密 当前数据质量的研究大多集中在相似重复记录清理、不完整数据清理和错误数据清理 等方面为了更适合不同数据挖掘任务的完成，本文拓宽了数据质量的定义内涵，将对数 据集基于不同目标进行变换都称为提高数据质量的操作本文主要使用了多种聚类策略来 提高不同挖掘目标的数据质量 本文拓展了传统的数据一致性( c o n s i s t e n c y ) 定义，借鉴连续函数的思想，提出了一个 分类样本空间的一致性度量概念来衡量数据集的分类一致性，进一步将其推广到数值型 连续数据上作为具体验证，将提出的连续分类一致性定义用到了s o m 方法中，得到基 于s o m 连续分类一致性定义的分类方法最后从v c 维的角度分析了提出算法的优点 为了使核方法适用于大规模数据集的求解，本文提出了基于聚类加权的快速核方 法快速聚类核方法使用聚类方法让原始数据集规模缩小，从而解决了核计算中大规模 矩阵的计算效率( 甚至不可运行) 的问题，使矩阵特征值求解问题的规模从o ( n 3 ) 下降 到0 f f 3 ) ，2 n 且本文给出了详细的理论证明，在极大地提高算法效率的情况下，分 类精度的差别可以严格控制在微小范围内最后我们还将此方法具体应用于k e r n e lf o l e y s a m m o nt r a n s f o r m ( k f s t ) 算法和k e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i s ( k p c a ) 算 法中 本文提出了一种基于偏离g a u s s ( 高斯) 分布的变量聚类i c a 方法，先对变量进行聚 类，再在每一类变量上进行i c a 分析，即通过变量聚类的方法来提高数据集的针对i c a 的 数据质量针对i c a 方法的特点，将每个变量与用极大似然估计得到的g a u s s 分布进行比 较，得到一个差值序列，根据这个差值序列进行变量之间的聚类实验结果表明我们的方 法能提高数据集的分类一致性，从而提高了预测精度 第i 页，共1 1 5 页 箱量巨 通过对大型稀疏数据库的分析，本文提出了一种基于反向变量聚类的分层加速算法 这种方法可以提高大型稀疏数据库中对大数据集操作的速度，同时节约了存储空间其主 要思想是利用反向变量聚类的方法，对属性进行聚类，生成一个投影聚类数据库投影数 据库中，多个属性被统一聚集在一个聚类变量下，从而属性的数量被极大地减少了分层 加速算法压缩了稀疏数据集，节约了存储空间，提高了运算的效率 本文对一类含有敏感属性的数据集进行了分析，提出了基于等距加密( i s o m e t r i c e n c r y p t i o n ，i e ) 的数据集变换方法，以提高数据集对保密性数据质量要求第一个等 距加密方法是旋转变换，首先对旅游者的敏感属性进行随机等距旋转变换，再对变化 后的数据隼停用基于案例的推理方法进行旅游线路的聚类分析这罩的旋转变换方法 可以保持数据集中任意两点间的距离不变，从而对变换前后的数据集进行基于案例推 理寻书最近邻点得到的结果是一致的而且旋转变换是随机的，可以经受攻击而不容 易砖攻 i ! j 使旅游者的敏感信息得到严格的保护进一步，将旋转变换的方法推广 至u a o n n s o n l l n o e n s t r a u s s 随机映射的力法和流形学习l m a n i f o l dl e a r n i n g ) 的方法上，侍 到了基于j o h n s o n l i n d e n s t r a u s s 随机映射$ 1 k 一最近邻法的旅游线路分类算法、基于流形学 习和k 一最近邻法的旅游线路分类算法 通过对一类水量预测调度数据集进行分析后，本文提出了结合先验知识和分形理论 的水量预测算法，先对各水厂的历史数据进行分析，用改进嵌入维数和时间延迟计算 的g p 预测算法拟合预测此水厂数据，再根据各水厂当天其它信息结合先验知识自动调整 权重，最后得出总规划水量算法较好地把先验知识嵌入了预测调度算法中，同时解决了 水量预测和水量调度的问题 关键词：数据质量，一致性，s o m ，聚类，核方法，f c k f s t ，f c k p c a ，i c a ，隐 私保护，i e ，j o h n s o n l i n d e n s t r a u s s 随机映射，流形学习，分形理论 第i i 页，共1 1 5 页 芡，、毒 t h er e s e a r c ha n d a p p l i c a t i o n0 1 1c l u s t e r i n ga n d c l a s s i f i c a t i o na n a l y s i si nd a t aq u a l i t ya n d p r i v a c y p r e s e r v i n g ： n a m e ：l uw e i m a j o r ：a p p l i e dm a t h e m a t i c s s u p e r v i s o r ：l il e ia n d 托坳z h e n g ：a n a b s t r a c t d a t aq u a l i t ya n dp r i v a c y p r e s e r v i n gh a v ea l r e a d ya r o u s e dt h eb r o a di n t e r e s t ，a n dt h e y a r et h ec u r r e n th o tr e s e a r c ha r e a t h ed a t aq u a l i t yi s u s u a l l yd e f i n e da sc o n s i s t e n c y , c o r r e c t n e s s ，c o m p l e t e n e s sa n dm i n i m a l i t y ，a n ds o m el i t e r a t u r e sr e g a r d ”s u i t st h eu s e ”a st h e p r e l i m i n a r ys t a n d a r do fd a t aq u a l i t y p r i v a c y - p r e s e r v i n gd a t am i n i n gr e f e r sw h i l ek e e p i n g s o m es e n s i t i v ei n f o r m a t i o n ss e c r e t i td o e sn o ta f f e c tt h em i n i n gr e s u l t t h ed a t aq u a l i t yr e s e a r c hm o s t l yc o n c e n t r a t e si nt h ep r o c e s so fs i m i l a rr e c o r d ，i n c o m p l e t ed a t aa n dw r o n gd a t a t h i sp a p e rw i d e n st h ed e f i n i t i o na n dc o n n o t a t i o no fd a t aq u a l i t y a l lt h e s ec o r r e s p o n d i n gs u i t a b l et r a n s f o r m a t i o n sa c c o r d i n gt ot h ed i f f e r e n td a t am i n i n gr e - q u e s ta r ec a l l e de n h a n c i n go fd a t aq u a l i t y t h i sp a p e ru s ed i f f e r e n tc l u s t e r i n gs t r a t e g yt o i m p r o v ei t sd a t aq u a l i t yf o rd i f f e r e n tg o a ld u t y p r o f i t i n gf r o mt h et h o u g h to fc o n t i n u o u sf u n c t i o n ，t h ep a p e rd e v e l o p e sd e f i n i t i o na n d c o n n o t a t i o no fd a t ac o n s i s t e n c ya n dp r o p o s e sa c o n s i s t e n c ym e a s u r ei nc l a s s i f i e ds a m p l e s p a c e f u r t h e rw eh a v eg i v e na nc l a s s i f i e dc o n s i s t e n c yd e f i n i t i o no fn u m e r i c a lc o n t i n u o u s d a t a ，e s p e c i a l l yc l a s s i f i e dc o n s i s t e n c yd e f i n i t i o na b o u ts o mm e t h o d t h ep a p e ra l s od i s c u s s e st h ei n f l u e n c eo ft h ec l a s s i f i e dd e f i n i t i o no nc l a s s i f i e dp r e c i s i o n f i n a l l yw e a n a l y z et h e m e r i to fp r o p o s e da l g o r i t h mf r o mv cd i m e n s i o na n g l e t h ep a p e ra n a l y z e st h et h o u g h ta n dt h es o l u t i o no fk e r n e lm e t h o d f i n d i n gt h a tk e r n e l m e t h o dc a ns o l v en o n l i n e a rd i s c r i m i n a n t sw e l l h o w e v e r ，k e r n e lm e t h o da l s of a c e sw i t h l a r g eo ( n 3 ) m a t r i xc a l c u l a t i o np r o b l e m sw i t ht h es a m p l es i z en k e r n e lm a t r i xw i l lb e c o s t l ya n de v e ni n t r a c t a b l et oc o m p u t ew h e nni sl a r g e w 色p r o p o s eaf a s tc l u s t e r i n g b a s e d k e r n e la p p r o a c ht ot a c k l et h i sp r o b l e m f a s tc l u s t e r i n g - b a s e dk e r n e lm e t h o dn e e d ss o l v i n ga d e d u c t i v efxzm a t r i xr e p r e s e n t i n gc l u s t e r i n gd a t ai n s t e a do fa n x nm a t r i xo fo r i g i n a ld a t a w h e r efi se n o r m o u s l ys m a l l e rt h a n 几t h i sp a p e ra l s op r o v e st h a tt h o u g hi m p r o v i n gt h e 第i i i 页，共1 1 5 页 英文摘要 c a l c u l a t e de f f i c i e n c yg r e a t l y ，t h ec l a s s i f i e dp r e c i s i o ni sa l m o s tu n c h a n g e a b l e f i n a l l yw ea p p l y t h i sm e t h o dt ok e r n e lf o l e y s a m m o nt r a n s f o r m ( k f s t ) a n dk e r n e lp r i n c i p a lc o m p o n e n t a n a l y s i s ( k p c a ) ，a sw e l la sf a m o u sk e r n e lf i s h e rd i s c r i m i n a n t ( k f d ) m e t h o d w ea p p l y o u rm e t h o dt od i g i t sa n di m a g e sr e c o g n i t i o np r o b l e m s ，a n do b t a i ng o o de x p e r i m e n t a lr e s u l t s t h ep a p e rp r o p o s e so n ev a r i a b l ec l u s t e r i n gi c ab a s e do i ld e v i a t i n gg a u s sd i s t r i b u t e s f i r s tw ec l u s t e rt h ev a r i a b l e ，t h e nu s ei c aa n a l y s i si ne a c hc l u s t e r i n go fv a r i a b l e w e e n h a n c et h ed a t aq u a l i t yf o ri c ao ft h ed a t a s e tt h r o u g hv a r i a b l ec l u s t e r i n gm e t h o d i n v i e wo ft h ec h a r a c t e r i s t i co fi c a w eo b t a i nd i f f e r e n c e sb e t w e e ne a c hv a r i a b l ea n dg a u s s d i s t r i h u t i n nw h i e bi sp 岛t i m a t e d b yt h pm a x i m u ml i k e l i h o o d a n dw ec l u s t e rt h ev a r i a b l e b a s e dt h e s ed i f f e r e n c e s t h ee x p e r i m e n t a lr e s u l ti n d i c a t eo u rm e t h o dc a ne n h a n c et h ed a t a c e n s i s t e n c 5 7a n df o r e c a s tp r e c i s i o n t h ep a p e ra n a l y z e st h el a r g e s c a l es p a r s ed a t a b a s e ，a n dp r o p o s e so n ea c c e l e r a t i o na l g o r i t h mb a s e do nt h er e v e r s ev a r i a b l ec l u s t e r t h ea l g o r i t h me n h a n c e so p e r a t i o ns p e e da n d s a v e ss t o r a g es p a c eo ft h el a r g e - s c a l es p a r s ed a t a b a s e t h em a i ni d e ai su s i n gr e v e r s ev a r i a b l ec l u s t e rm e t h o dt oc a r r yc l u s t e rt ot h ea t t r i b u t e s i tp r o d u c e sap r o j e c t i o nc l u s t e r i n g d a t a b a s e ，a n di te n a b l e sm a n ya t t r i b u t e st oc o m b i n eu n d e ro n ec l u s t e rv a r i a b l e t h ea l g o - r i t h mr e d u c e st h ea t t r i b u t eq u a n t i t ye n o r m o u s l y ，t h u sr e d u c e st h es p a r s ed a t a s e t i ts a v e s t h es t o r a g es p a c e ，e n h a n c i n gt h eo p e r a t i o ne f f i c i e n c y t h ep a p e ra n a l y z e so n ek i n dd a t a s e ti n c l u d i n gs e n s i t i v ea t t r i b u t e v c ep r o p o s ed a t a s e t t r a n s f o r m a t i o nm e t h o db a s e do ni s o m e t r i ce n c r y p t i o n ( i e ) i no r d e rt oe n h a n c et h es e c r e t d a t aq u a l i t yr e q u i r e m e n to fd a t a s e t t h ef i r s ti em e t h o di sr o t a t i o nt r a n s f o r m w ef i r s t p r o c e s st h et o u r i s t s s e n s i t i v ea t t r i b u t i o nu s i n gr a n d o mi s o m e t r i cr o t a t i o nt r a n s f o r m ，t h e n u s ec a s eb a s e dr e a s o n i n gt oa n a l y z et h et o u rc i r c u i to nt r a n s f o r m e dd a t a s e t i tc a ns t r i c t l y b ep r o v e dt h a tp r e s e n t e dr o t a t i o nt r a n s f o r mc a l lk e e pt h ed i s t a n c eb e t w e e nt w op o i n t si n v a r i a b l e s ot h en e a r e s tp o i n t st h a tw e r ef o u n du s i n gc a s eb a s e dr e a s o n i n go nt w od i f f e r e n t d a t a s e ta r es a m e a n dt h er o t a t i o nt r a n s f o r mi sr a n d o m ，w h i c hi sn o te a s i l yb eb r e a c h e d f u r t h e r ，w eg e n e r a l i z et h i sm e t h o dt oj o h n s o n l i n d e n s t r a u s sr a n d o mp r o j e c t i o na n dm a n i f o l dl e a r n i n gm e t h o d t h r o u g ha n a l y s i so fo n ek i n dw a t e rd i s p a t c hf o r e c a s td a t a s e t ，t h ep a p e rp r o p o s e st h e w a t e rv o l u m ef o r e c a s ta l g o r i t h mt h a tu n i t ea p r i o r ik n o w l e d g ea n dt h ef r a c t a lt h e o r y f i r s t w ea n a l y z et h eh i s t o r i c a ld a t ao fv a r i o u sw a t e rw o r k s ，t h e nw eu s eg pp r e d i c a t ea l g o r i t h m b a s e do nt h ei m p r o v e dc o m p u t i n go fe m b e d d i n gd i m e n s i o na n dt i m ed e l a yt op r e d i c a t et h e w a t e rv o l u m e t h ea l g o r i t h mh a si n s e r t e dt h ea p r i o r ik n o w l e d g ei nt h ef o r e c a s td i s p a t c h m e t h o dw e l l ，s i m u l t a n e o u s l ys o l v i n gt h ef o r e c a s ta n dt h ed i s p a t c ho fw a t e rv o l u m e k e y w o r d s ：d a t aq u a l i t y , c o n s i s t e n c y ，s o m ，c l u s t e r i n g ，k e r n e lm e t h o d ，f c k f s t ，f c k p c a ，i c a ，p r i v a c yp r e s e r v i n g ，i e ，j o h n s o n l i n d e n s t r a u s sr a n d o mp r o j e c t i o n ，m a i n f o l d l e a r n i n g f r a c t a lt h e o r y 第i v 页，共11 5 页 插图目录 插图目录 2 1 神经元示意图( 定) 一维神经元示意图； ( 中、右) ：维神经元示：盘图1 8 2 2 神经元示意图1 9 2 - 3s 0 、i 结构示意图1 9 2 4b p 例络示意图2 1 2 - 52 9 类问题预测精度随分类一致性变化趋势i 划2 5 263 炎问题颅测精度随分类一致性变化趋势图2 g 2 7v c 维示意图2 8 2 - 8s i m 巧i 意图_ 2 9 31 孩方法的，黔1 、：思想3 2 3 2 二维映射到i 维分类例3 2 3 - 3 数据集卜的线性s v 、1 分类和二 e 线性r b f 核s v 、1 分类3 4 3 4 聚类示意劁3 5 3 - 5 k f s t 和f c k l 7 s t 存数据凭n 一卜的比较( 圮) t 3 卜经过k f s t 变换后特征空问 分布( f i ) 1 3 j ：经过f c k f s t 变换后特征伞| 、h j 分布4 6 3 - 6k f s i 和f c k f s t 在数据集1 1 3 卜的比较( 尤) 1 1 3 卜经过k f s i 变换后特征空 间分稚( 彳i ) 1 1 3 上经过f c k f s t 变换后特征夺间分布4 6 3 7 左图：在人造数据集一h 的p c a ，t 7 y 7 代表第、二个特征方向右罔：用 i 个点代表原盘厶数据集然后在新数据上执行p c a 比较夕。i 彳i 两个图后发 现，右图的特扯方向与左图的很接近，但右图 j 作计算p c a 的数掂远少于 左图的数据集数量4 8 3 - 8 邻域示意图( 左) 网邻域示意图；( 右) 方邻域示意图5 3 3 - 9 有限覆盖示意图5 3 4 1 i c a 例子( 左) 独屯源信号；( i l j ) 左图的混合( 脱测) 信号；( 右) 两 个独立高斯型变量的多维分布5 6 4 2 线性混合信号系统摸犁示意图5 6 4 3两矢量i c a 五意图( 龙) 独立源信号；( f i ) 混合( 观测) 信号5 7 5 1 属性数随对象数变化图7 0 5 2 运算时问随刖。象数变化图7 0 6 - 1 流形例子7 9 6 2l l e 算法示意图8 1 6 3l l e 算法的例子8 l 6 4m d s 示意图8 2 6 5 测地距离示意图8 3 7 1 平h 话务量预测结果图9 3 第v i i i 页，共1 1 5 页 2 1 2 2 2 3 3 一l 3 2 3 3 ，3 4 - j a j u 3 7 3 8 3 9 3 1 0 3 1 1 3 1 2 表格目录 分柿式数捌库中数据一致性方法比较 2 9 类i u j 题预测结果 3 类问题预测结果 常用的核函数 o p t d i g i t s 数据库q | ，各个类存训练集核测试集喀- 所占样本数目一 p e n d i g i t s 数扒库中各个类往训练集核测试集中所占样本数目： 存数摒傣i 卜k f s t 和f c k f s t 投影向跫比较( r b f 03 ) 二。 在数据集i i h f s t 和f ( 1 i f s t 投影向餐比较( r b f 2 ) 舀：数捌集i 上k f s t 和f c i f s t 的运行速度和分类精度( r b f o 3 ) j j ：w = 在数据集i ik k f s t 和f c k s t 的运行速度和分类精度( r b f 2 ) 人工实验数据集 i ：聚合法刚好相反， 是把每一个个体都看成一个单独的类，尔后从个体相似度入手，通过粘连操作聚集相似 度足够大的个体，逐步聚成更大的类等级聚合聚类法是目前使用最多、研究最为充分的 算法，其基本思想，是通过建立并逐步更新距离系数矩阵( 或相似系数矩阵) ，找出合 并最接近的两类，直到全部聚类对象被合并为一类为止 基本的分层聚类方法是由k a u f m a n 和r o u s s e e u w 提出的凝聚方 法a g n e s ( a g g l o m e r a t i v en e s t i n g ) 和分裂方法d i a n a ( d i v i s i v ea n a l y s i s ) 【k r 9 0 分层聚类方法虽然简单，但经常会遇到合并点或者分裂点选择的困难这样的决定非 常关键，因为一旦一组对象被合并或者分裂，下一步的处理将在新生成的类上进行已做 的处理不能被撤销，类之间也不能交换对象如果在某一步没有很好地做出合并或分裂的 决定，可能会导致低质量的聚类结果而且，这种聚类方法不具有很好的可伸缩性因此 人们提出众多改进的分层聚类算法以改进分层聚类方法的性能 b i r c h z r l 9 6 是一种较为有效的分层聚类算法，把层次聚集的形成过程到结果看 作一棵树，然后结合其他的聚集方法进行修剪b i r c h 算法可以分为两步，第一步扫描 数据库建立一棵簇特征树，可以看作是保持数据内在簇结构的多级压缩；第二步选择 一个聚类算法( 如划分法) 对簇特征树的叶子结点进行聚类b i r c h 算法的时间复杂度 为o ( n ) ，其中为进行聚类的对象的个数 g u h a 等提出一种分层凝聚聚类算法c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a - t i v e s ) g r s 9 8 1 ，c u r e 算法选择基于质心和基于代表对象方法之间的中间策略，可 以有效的处理大数据集和以任意形状分布的数据，可以识别任意形状的簇而且不降低 聚集的质量；能更好地过滤异常点，并提高了效率，减少了时间复杂度但c u r e 只适 合数值型数据，为了适合分类数据，作者又提出了一种算法r o c k ( r o b u s tc l u s t e r i n g a l g o r i t h mc a t e g o r i c a ld a t a ) g r s 9 9 1 k a r y p i s ，h a n 和k u m a r 基于对c u r e 和r o c k 缺点的观察，提出了采用动态模型 的c h a m e l e o n 方法 k h k 9 9 它先建立对象的k 最近邻图，接着用图的分割算法将数据 第5 页，共1 1 5 页 1 3 聚类算法相关研究现状 对象划分成非常小的子聚类，然后通过分层聚类算法不断地合并这些小的聚类，从而得 到最后的聚类结果 1 3 2 划分法( p a r t i t i o n i n gm e t h o d ) 划分聚类法，又称动态聚类法、逐步聚类法，其基本思想是，在一个平面层次上对所 有的样本点先作出某种较为粗略的划分，然后按照某种最优的准则进行修正，通过算法 的迭代执行得到一个较为合理的有k 个类的聚类结果近年来研究一直较受关注，其中 最为典型的为k m e a n s 算法和k 中心点( k m e d o i d ) 方法 , x k q u e e n 提出的k m e a n s 方法 m a c 6 7 1 中，每个类用该类中对象的平均值表示k 孺。肌s 方法是解决聚类问题的一种经典方法，其基本算法如下：先随机选择k 个对象作 为簇的中心，将剩余的对象划分给离它最近的中心，然后再计算出新的簇中心重复以 上过程，直到k 个簇的中心点都不再发生变化k m e a n s 算法的计算复杂性是o ( n k t ) ，其 中，n 为原始数据数量，七为类的数量，为迭代次数较之系统聚类法，划分聚类法明显 的优势是运算量小，能用于处理庞大的样本数据，也为实时处理提供了一定的可能性 k m e a n s 方法的主要优点是简单、快速，其缺点主要是： 1 ) k m e a n s 法要求用户必须事先给出要生成的簇的数目，选择初始划分的最佳方 向、更新分区和停止准则且其结果与数据输入顺序有关，不同的初始值可能会导致不同 的结果 2 ) 对于噪声和孤立点敏感，很容易受例外情况的影响适用于发现球状类，但不适 合发现非凸面状的簇，也不适合大小差别较大的簇 3 ) 这一方式通常首先根据距离来调整确定类，然后再确定类名，因此也存在着类名 表达问题 4 ) 一个对象只能属于一个类中，不能揭示其多重属性 k m e d o i d s 算法采用最接近于聚类中心的数据点作为簇的中心点以改进k m e a n s 方 法的不足p a m ( p a r t i t i o n sf o ra r o u n dm e d o i d s ) k r 9 0 是最早提出的k m o d o i d 之一， 它选用簇中位置最靠近中心的对象作为代表对象( 中心点) ，然后反复用非代表对 象( 非中心点) 代替中心点，直到找到最合适的中心点p a m 法有效地消除了对孤 立点数据的敏感性，比k m e a n s 方法更健壮，不易受极端数据的影响但p a m 只对小 数据集非常有效( 如1 0 0 个对象聚成5 类) ，对大数据集效率并不高n g 和h a n 提出 的c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o nr a n d o m i z e ds e a r c h ) 【n h 9 4 将采 样技术与p a m 结合起来，就是用实际数据的抽样来代替整个数据，然后再在这些抽 样的数据上利用k m e d o i d s 算法得到最佳的m e d o i d s ，能处理较大的数据集合复杂度 是o ( k s 2 + k ( n 一七) ) ，其中s 是样本大小 第6 页，共1 1 5 页 筝一章j 毛 1 3 3 基于密度的方法( d e n s i t y - b a s e dm e t h o d ) 基于样本之间的距离的聚类方法只能发现球状的簇，基于密度的方法可用来过滤“噪 声 孤立点数据，以发现任意形状的簇其主要思想是只要临近区域的密度( 样本的数 目) 超过某个阈值则继续聚类即对于给定簇中的每个样本，在一个给定范围的区域中至 少包含某个数目的样本这样的方法可以过滤“噪声 数据，发现任意形状的类但对密 度分布不均的数据集，往往得不到满意的聚类结果其缺点是： 1 ) 也要求用户对初值的设定，而不同的初值会影响聚类的质量 2 1 不能处理高维度的数据 e s t e r 等提出的d b s c a n - ( o e n s i t y - b a a e d s p a t i a l - c h m t e r i n g - 叼f , ，a p p t i e a c i o n s ，w i t h n o i s e ) f e k s 9 6 是基于密度聚类的代表方法该算法将具有足够高密度的区域划分成 类，并可以在带有“噪声”的空间数据中发现任意形状的类算法0 p t i c s f a b k 9 9 1 是一 种基于类排序的方法，为自动和交互式的聚类分析提供了一个扩充的簇序d e n c l u e f h k 9 8 算法基于一系列密度分布函数，这种算法可以看作d b s c a n 和k m e a n s 聚类方法 的推广 1 3 4 基于网格的方法( g r i d b a s e dm e t h o d ) 基于网格的聚类方法将数据空间划分从有限数目的单元( c e l l ) 从而形成一种网格结 构，然后在这种网格结构上进行聚类这种方法所有的处理都是以单个的单元为对象的， 主要优点是处理速度很快，通常与目标数据库中记录的个数无关，而只与数据空间的单 元有关 s t i n g ( s t a t i s t i c a li n f o r m a t i o ng r i d ) f 、y m 9 7 是基于网格的多分辨率方法，将数 据的汇总信息放在层状的树中，树的结点就是网格，从最底层的网格开始逐级向上计算 网格内数据的统计信息树中的不同层次，代表着不同的分辨率，越接近叶子结点的层 次，其分辨率也越高w a v e c l u s t e r s c z 9 8 算法基于信号处理技术，它用小波变换对数据 进行过滤该方法首先通过在数据空间上增加一个多维网格结构来汇总数据，然后采用一 种小波变换来变换原特征空间，在变换后的空间中找到密集区域，能很好的处理高维数 据和大数据集a g r a w a l 等提出的c l i q u e ( c l u s t e r i n gi nq u e s t ) 是综合了基于密度和网格 方法的聚类方法，对于大型数据库中的高维数据的聚类非常有效 1 3 5 基于模型的方法( m o d e l b a s e dm e t h o d ) 基于模型的方法首先是基于这样一个假定：目标数据集是由一系列的概率分 布所决定的那么，可以在空间中寻找诸如密度分布函数这样的模型来实现聚类 基于统计学的方法和基于神经网络的方法是近些年两种不同的尝试方向f i s h e r 提一 出的c o b w e b 算法 f i s 8 7 ，g e n n a r i 等提出的c l a s s i t g l f 算法，c h e e s e m a n 等提出 的a u t o c l a s s 算法【c s l 等都属于统计学方法 第7 页，共1 1 5 页 1 4 分类预测相关研究现状 竞争学习f c o m p e t i t i v el e a r n i n g ) r z 8 5 采用若干个单元的层次结构，它们以一种 “胜者为王 ( w i n n e r - t a k e - a 1 1 ) 的方式对系统当前处理的对象进行竞争学习矢量量 化( l e a r n i n gv e c t o rq u a n t i z a t i o n ，l v q ) k o h 8 4 是由k o h o n e n 提出的，是一种自适应数据 聚类方法，它基于对具有期望类别信息数据的训练尽管是一种有监督训练方法，然 而l v q 采用了无监督数据聚类技术，对数据集进行预处理，可获得聚类中心 自组织特征映射( s e l f - o r g a n i z i n gm a p ，s o m ) k o h 9 8 ，k o h 9 5 也是由k o h o n e n 在1 9 8 1 年 提出的一种基于神经网络模型的聚类方法，它模拟大脑神经系统自组织特征映射的功 能，在训练中能无监督地进行自组织学习s o m 以其具有的拓扑结构保持、概率分布保 持、尤导师学习及可视化等特征，广泛应用于聚类分析中s o m 的优点为：可以实时学 纠其有稳定件无须外界给出评价函麴，能够识别向茸：窄间中最又意义的特征，抗噪 音能力强不足之处为：当网络的连接过多，节点数目庞大时，其计算量大，需要较长的 学习时间；网络连接权向量初值的选取对网络收敛性影响很大 c h a m e l e o n ( 变色龙) 方法是一个在层次聚类中采用动态模型的层次聚类算法它将 互连性和近似性大的簇合并，可以高质量地发现任意形状的簇但k 一最近邻图中k 值和最 d , - 等分、用户指定方式中阈值的选取仍是个难题在最坏情况下，高维数据的处理代价 可能需要o ( n 2 ) 的时间，效率仍然不够 1 4 分类预测相关研究现状 分类问题一直是人工智能领域的重点研究对象 v a p 9 5 ，也是目前机器学习和模式识 别的研究热点所谓分类问题就是用计算机来模拟人的学习分类能力，数据集分成训练集 和测试集，每个样