（计算机应用技术专业论文）基于图形处理器的聚类分析算法研究.pdf

在职人员同等学力硕士学位论文 摘要 聚类分析作为一种新兴的数据处理技术，近年来已成为数据挖掘中 一个非常活跃的研究方向。同时随着实际应用中数据流的广泛出现，不 仅需要考虑提高聚类质量，如何提升聚类处理速度也是一个亟需解决的 问题。由于目前各种聚类算法均是采用c p u 进行计算实现，聚类效率无 法完全满足实际需要。图形处理器( g r a p h i c sp r o c e s s i n gu n i t ：以下简称 g p u ) 具有很高的并行计算能力、超常的浮点运算速度。本文将目前几种 典型聚类算法在c p u 上执行的部分关键计算步骤转移到g p u 上，进行非 图形绘制的通用计算处理，以提高聚类速度。 与经典k m e a n s 算法相比，e n h a n c e dk m e a n s 算法只需处理部分点 集的距离计算和比较操作，因而可使聚类效率得到较大提裔。以此算法 为基础，提出了基于此算法的c p u + g p u 的协同处理模式，利用g p u 多 个子素处理器可以进行并行计算的特性，将算法中处理比较耗时的距离 计算与比较、每次参与循环计算的点集合判断步骤由g p u 实现，而初始 化、中心点计算、聚类结束判定步骤仍由c p u 实现，在这种协同计算模 式下，可使e n h a n c e dk m e a n s 算法的聚类效率提高约3 5 。 其次，对经典r o c k 和v b a c c 层次聚类算法及改进的基于动态近邻选 择模型的d n n s 算法进行分析比较。在此基础上，借鉴l a r s e n 提出的利用 g p u 进行矩阵快速相乘的思想，将此思想和g p u 多子素处理器并行处理特 点结合起来，应用在d n n s 算法中，即将算法中的主要运算步骤连接度矩 阵计算用g p u 实现，而建堆及合并操作由c p u 完成，这样可使d n n s 算法 的聚类时间减少2 5 左右。 在一台配有p e n t i u mi v3 4 gc p u 和n v i d i ag e f o r c e6 8 0 0g t 显卡的 计算机上实现了上述基于g p u 的算法和完全由c p u 完成的算法，实现过程 中注意到c p u 与g p u 之间较小总线带宽，将c p u 与g p u 之间的数据传输最 小化。实验结果表明：在具有相同聚类质量的前提下，基于g p u 的聚类 算法的运算速度明显快于传统的基于c p u 的聚类算法的处理速度。因此， 这种g p u 和c p u 的协同处理模式将对数据流的快速聚类实现具有一定的 借鉴意义。 关键词：图形处理器；通用计算；数据流；聚类分析；层次聚类 基于图形处理器的聚类分析算法研究 abstr a ct c l u s t e r i n ga n a l y s i si so n eo ft h en e wt e c h n i q u e so fd a t ap r o c e s s i n g ， w h i c hb e c a m ea na c t i v er e s e a r c hd i r e c t i o no fd a t am i n i n gi nr e c e n ty e a r s a t t h es a m et i m e ，w i t ht h el a r g ev o l u m e so fd a t aa r r i v i n gi nas t r e a mi nt h e a p p l i c a t i o n s ，n o to n l yc l u s t e r i n gq ua 1 i t ys h o u l db et a k e ni 丑t oa c c o u n t ，b u t h o wt oi m p r o v et h es p e e do fc i u s t e r i n gp r o c e s s i n gw a sa ni m p o r t a n tk e y p r o b l e mt h a t s h o u l db es o l v e d u r g e n t l y s i n c et h ec u r r e n tc l u s t e r i n g m e t h o d sw e r er e a l i z e db ym e a n so ft h ec o n v e n t i o n a lp r o c e s s i n gw i t hc p u c a l c u l a t i o n ，t h ec l u s t e r i n ge f f i c i e n c yc o u l dn o tm e e tt h er e q u i r e m e n t si nt h e p r a c t i c e f o rt h ee x c e l l e n tp e r f o r m a n c eo fg r a p h i c sp r o c e s s i n gu n i t ( g p u ) s u c ha st h eo u t s t a n d i n gc a p a b i i i t yo fp a r a l l e lc a l c u l a t i o n ，e x c e l l e n tn u m b e r o fn o a t i n g - p o i n to p e r a t i o n sp e rs e c o n d ，t h ep a r t i a lk e ys t e p st h a tw e r ed e a l t w i t hc p ui nt h e s et y p i c a la l g o r i t h m sa tp r e s e n tw e r et r a n s f e r r e dt og p u w h i c hc o u l dc a r r yo u tn o n - i m a g i n ep r o t r a c t i o nc o m p u t a t i o na n dw a sj u s t s o c a l l e d g e n e r a ip u r p o s ec o m p u t a t i o n o ng p u( g p g p u ) s ot h a tt h e c l u s t e r i n gs p e e dw a sg r e a t l yr a i s e d c o m p a r e dw i t ht h ec l a s s i ck m e a n sa l g o r i t h m ，f o ro n l yp a r t i a ld a t a p o i n t s w o u l db eu s e di nt h e o p e r a t i o n s o fd i s t a n c ec o m p u t i n ga n d c o m p a r i s o ni nt h ee n h a n c e d k m e a n sm e t h o d ， t h ec l u s t e r i n ge f n c i e n c y w o u l db ei m p r o v e di ns o m ee x t e n t b a s e do nt h em e t h o d ，t h ec o o r d i n a t i o n m o d eo fc p u + g p uw a sp r o p o s e d t h ed i s t a n c ec o m p u t i n ga n dc o m p a r i s o n ， t h es e l e c t i o no ft h ed a t a p o i n t sa g g r e g a t i o nc o n c e r n e dw i t ht h ei t e r a t i v e c o m p u t a t i o n ，b o t ho fw h i c hw o u l dh a v es p e n tm u c ht i m ei nt h ea l g o r i t h m s ， w e r e i m p l e m e n t e db yu s i n g g p u s p a r a l l e lc a p a b i l i t y o n f r a g m e n t p r o c e s s o r s ， w h i l et h e s t e p o ft h ei n i t i a l i z a t i o n ，t h ec a l c u l a t i o no ft h e c e n t r o i d sa n dt h ej u d g m e n to nt h et e r m i n a t i o no fc l u s t e r i n gw e r er e a l i z e db y c p u u n d e rt h ee n v i r o n m e n t st h a tt h ec a l c u l a t i o nw a sf i n i s h e db y c p u + g p u ，t h ec l u s t e r i n ge f f i c i e n c yo ft h ee n h a n c e d k m e a n sa l g o r i t h m w a si n c r e a s e da b o u t35 t h e n ，c l a s s i cr o b u s tc l u s t e r i n ga l g o r i t h mf b rc a t e g o r i c a la t t r i b u t e s ( r o c k ) ，h i e r a r c h i c a lm e t h o dv a l u eb a l a n c e da g g l o m e r a t i v ec o n n e c t i v i t y n 在职人员同等学力硕士学位论文 c l u s t e r i n g( v b a c c ) a n dt h e o p t i m i z e dd y n a m i c n e a r e s n e i g h b o r s s e l e c t i o n ( d n n s ) m e t h o d sw e r es t u d i e da n dc o m p a r e d b a s e do ni t ，r e f c r f e d t ot h ei d e at h a tf a s tm a t r i xm u l t i p l i e su s i n gg r a p h i c sh a r d w a r ep r o p o s e db y l a r s e n ，t h i si d e aw a sc o m b i n e dw i t ht h ep a r a l l e lc a p a b i l i t yo nf r a g m e n t p r o c e s s o r so fg p ua n dw a su s e di nt h ed n n s ，n a m e l yt h ek e ys t e pt h a tt h e c a l c u l a t i o no ft h ec o n n e c t i o nm a t r i xw a st r a n s f e r r e dt og p ua n dt h e b u i l d i n ga l lh e a p sa n dm e r g i n ga p p l i c a t i o nw e r ef i n i s h e db yc p u t h e c l u s t e r i n gt i m eo fd n n sw a sr e d u c e da p p r o x i m a t e l y2 5 a tl a s tt h ea l g o r i t h m sb a s e do ng p ua n dt h ea l g o r i t h m sf i n i s h e d o n l yb yc p uw e r ec o n d u c t e di n ap cw i t hp e n t i u mi v3 4 gc p ua n d n v i d i ag e f o r c e6 8 0 0g tg r a p h i cc a r d d u r i n gt h ec o u r s eo fr e a l i z a t i o n ， t h el i m i t e db a n d w i d t hb e t w e e nt h eg p ua n dc p uw a st a k e ni n t oa c c o u n t a n dt h ed a t at r a n s f e r r i n gb e t w e e nt h e mw a sm i n i m i z e d t h ee x p e r i m e n t a l r e s u l t ss h o wt h a tc l u s t e r i n ga n a l y s i sa l g o r i t h mb a s e do ng p uh a dam u c h h i g h e fs p e e d t h a nt h ec o n v e n t i o n a l c p u b a s e da l g o r i t h m s u n d e ft h e c o n d i t i o nt h a tt h ec l u s t e r i n gq u a l i t yi st h es a m e t h u st h ec o o r d i n a t i o n m o d eo fc p u + g p uh a dv e r yi m p o r t a n tr e f e r r i n gs i g n i f i c a n c ef o rt h ef a s t c l u s t e r i n go fd a t as t r e a m s k e yw o r d s ：g r a p h i c sp r o c e s s i n gu n i t ； s t r e a m ；c l u s t e f i n ga n a l y s i s ；h i e r a r c h i c a l n i g e n e r a lp u r p o s ec o m p u t a t i o n ；d a t a c l u s t e r i n g 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：雪印卜日期：跏3 年1 月上日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密毗 、 ( 请在以上相应方框内打“”) 作者签名：苍；球一 导师签名： 日期：。j i 嘲年月r 日 a日期：么时年，月，日 力 。 厶 在职人员同等学力硕士学位论文 1 1 研究目的 第1 章绪论 数据聚类是数据挖掘的一个重要工具，目前作为一种强有力的信息处理方法 而被广为研究。然而，随着现代传感器和计算机网络技术的发展，在越来越多的 实际应用中，一般当大量数据源源不断的出现时，如何对剧增的数据集进行数据 聚类，聚类算法除了需要考虑聚类质量外，聚类处理速度往往也一个亟需重视的 重要指标，所以如何提高聚类处理速度以满足现实环境中对聚类算法的需要是本 文研究的重点。自于图形处理器( g r a p h i c sp r o c e s s i n gu n i t ，简称g p u ) 专为图形渲染 设计，其超长流水线管道、并行计算能力、可编程性的优异特性，使其浮点运算 速度越来越快，并行处理能力也越来越优异，于是g p u 越来越多地被做为非图形 绘制方面的通用计算应用，这已经成为g p u 的一个发展趋势。因而，在研究各种 传统聚类方法的优缺点基础上，分析一些改进的聚类方法特点及适应环境，在其 聚类效率有一定提高的基础上，继而探讨如何将g p u 的通用计算功能应用到这些 改进的聚类算法中，即将算法中的一些影响时问复杂度的关键计算步骤转移到 g p u 上完成，其余操作步骤出c p u 完成，尝试通过g p u + c p u 的一种处理模式对 一些聚类算法进行效率优化，使聚类质量在不变甚至更优的前提下，极大的提高 数据聚类速度，以开发出满足实际环境对聚类速度要求的快速、高效的聚类算法。 1 2 选题的背景与依据 由于实际应用广泛存在，聚类问题在数据库、数据挖掘和统计领域都得到了 大量研究n 3 1 。近年来，大量研究开始考虑面对海量数据如何提高聚类效率的问题。 传统聚类方法可划分为基于划分的方法、基于层次的方法、基于密度的方法等h 3 ， 与传统的基于磁盘的聚类问题不同，数据流聚类问题除了需要考虑聚类质量以外， 聚类处理速度往往也是数据流挖掘算法的一个重要指标1 。在数据流聚类处理操作 中，由于存储空间是一定的，相对源源不断到达的海量数据，空间就显得不足， 尤其当数据流出现b u r s t 时( 即短时内大量数据到达有限的存储空间) ，若此时满足 对到达的数据要实时、在线处理，数据流挖掘处理速度问题就已成为一个尚待解 决的重要问题。 而图形处理器最初是用来绘制图形，由于游戏、仿真、电影制作等业界对图 形处理能力不断增长的需求，进入3 d 时代后g p u 的性能发生着日新月异的变化。 从1 9 9 3 年以来，图形处理器的性能便以每年2 8 倍的速度增长，目前主流图形处理 基于图形处理器的聚类分析算法研究 器规模已经大大超越了现今的主流c p u 哺1 ，n v i d i a 公司的g 7 0 系列和a t i 公司的 x 1 8 0 0 、x 1 9 0 0 系列g p u 晶体管规模轻松超过三亿，大大超过目前主流的双核c p u ， 而将在2 0 0 6 年年底上市的下一代g p u 规模就突破了6 亿大关n 3 。在运算能力方面， g 7 l 处理器p i xe ：ls h a d e r 的峰值运算能力更达到了惊人的2 5 0 g n o p s ( 1g i g a f l o p s = 1 秒钟进行1 0 亿次的浮点运算) ，大大超过目前主流双核处理器的2 倍。另外显存的 大小对g p u 处理能力也有很大影响，但是显存的位宽也很重要，或者说显存与g p u 交换数据的带宽。例如：显存位宽为2 5 6 b i t g d d r 的g 7 1 轻松达到了5 1 2 g b s 的显 存带宽，而主流双核处理器的双通道d d r 2 8 0 0 数据带宽才只有1 2 8 g b s 阳1 。因此， 在单精度浮点矢量运算中，g p u 的优势是非常明显的，属于面向高密集运算的处 理机，如能加以利用，将极大的提升效率，并且节省能源的消耗。 由于现代g p u ( g r a p h i c sp r o c e s s i n gu n i t ) 中的子素处理器部分是河编程的，即允 许用户编写简单的子素程序在子素处理器上并行运行，子素处理器不但可以直接 访问纹理内存，而且能够执行浮点向量操作，于是用其做非图形绘制方面的通用 计算一1 引，如几何运算、碰撞检测、运动规划、代数运算、优化计算、偏微分方程 p d e s ( p a r t i a ld i f e r e n t i a le q u a t i o n s ) 数值求解问题等。但是其在聚类分析中还未被应 用，所以探索研究如何将g p u 的通用计算能力应用到聚类分析算法中，研究是否 可以加速聚类算法的速度。 1 3 图形处理器用于通用计算的国内外研究现状 近年来图形处理器( g p u ) 高速发展，其发展速度大大超过摩尔定律速度阳1 。 n v i d i a 公司1 9 9 9 年首先由提出g p u 后，目前图形芯片的主要市场被n v i d i a 和a t i 这两家公司占领，其发展速度是c p u 速度的三倍多，平均约一年便有新一代的g p u 诞生，运算速度也越来越快。2 0 0 4 年推出的g p un v i d i ag e f o r c e6 8 0 0u l t r a 可达 到峰值4 0g i g a n o p s ( 1g i g a n o p s = 1 秒钟进行l o 亿次的浮点运算) ，2 0 0 5 年刚发布的 n v i d l a g e f o r c e7 8 0 0g t x 更是将峰值提高至令人惊讶的1 6 9g i g a n o p s n 纠，极高的 性能和前所未有的发展速度极大地提高了g p u 的速度与绘制图形的质量，促进了 与计算机图形相关应用领域的快速发展。与此同时，图形处理器绘制流水线的高 速并行性以及可编程功能为图形处理以外的通用计算提供了良好的运行平台阳一引， 利用图形卡来进行一般意义上的计算，而不是单纯的绘制，这使得g p u 用于通用。 计算( g e n e r a lp u r p o s eg p u ) 即g p g p u 成为近年来人们关注的一个研究热点。目前 用于通用计算的主要领域有n 2 1 g p u 在流体模拟和代数计算、数据库应用n 引、频谱 分析等方面应用。只要是有重复的大量数据运算和高频率的内存存取的算法操作， 使用g p u 处理就可以得到比c p u 强大得多的计算能力。与此同时，因为实际相关 应用领域的强大驱动，如大数据量的图形环境模型以及虚拟现实、计算机仿真、 计算机游戏等实时需求促使g p u 高速发展n 刳，使g p u 以及相关软硬件的发展产生 2 在职人员同等学力硕士学位论文 强大的动力，使g p u 在近几年内得到进一步的高速发展，这为g p u 用于通用计算 提供更丰富的功能和更强的能力。 1 4 研究内容与研究意义 数据聚类的研究随着传感器和计算机网络技术的发展，在越来越多的实际应 用中，当数据以流的形式出现时，对于一个好的聚类算法，不仅要考虑聚类质量， 其聚类处理速度也将显的尤为重要。本文首先在研究各种聚类算法并且比较各种 算法优缺点的基础上，分析一些典型聚类方法的改进，在改进算法效率提高的基 础上，将图形处理器优异的浮点运算速度和并行处理能力应用在算法的计算步骤 中，利用g p u 多个子素处理器的并行处理特性及可编程性，将算法中的某些影响 时间复杂度的关键步骤计算转移到g p u 的子素处理器上，通过编制子素处理程序 实现并行计算，而算法其余操作步骤由c p u 完成，从而提出一种g p u + c p u 的计算 处理模式处理聚类算法。同时，考虑到c p u 与g p u 之间的总线带宽较小，尽量将 c p u 与g p u 之间的数据传输实现最小化，使得传输开销代价最小。在聚类质量不 变的前提下，提高聚类处理速度，探索出基于g p u + c p u 模式的聚类算法，使数据 挖掘速度得到提高。 这种模式对于处理海量数据集合下对快速高效聚类操作的需求有一定满足， 使数据挖掘速度可以得到一定提高，对于适应现实环境下聚类速度的要求，具有 一定借鉴意义。 1 5 本文的主要工作及组织结构 本文的工作是在李肯立教授的指导下完成的。主要工作如下： 第一：综合分析比较目前采用的几种主要的数据聚类算法：基于划分的方法、 基于层次的方法、基于密度的等方法特点及适用环境。 第二：比较典型的层次聚类算法r o c k 和v b a c c 及改进的基于动态近邻选 择模型d n n s 算法的优缺点。研究e n h a n c e dk m e a n s 算法，和k m e a n s 算法相比 如何使聚类效率提高。 第三：研究g p u 的工作原理，尤其对其通用计算( g e n e r a lp u r p o s eg r a p h i c s p r o c e s s i n gu n i t ：以下简称g p g p u ) 应用深入了解，本文是利用g p u 做代数计算方面 的应用，因此重点要解决如何在g p u 中建立合适的数据转换模式，及应该在g p u 中实现何种计算步骤，以实现时间复杂度的快速减少。 第四：研究基于g p u 的e n h a n c e dk m e a n s 算法的实现方案。综合分析算法 各步骤，利用g p u 多个子素处理器可以进行并行计算的特性，将算法中处理比较 耗时的距离计算与比较、每次参与循环计算的点集合判断步骤交给g p u 完成，而 基于图形处理器的聚类分析算法研究 初始化、中心点计算、聚类结束判定步骤由c p u 实现，在g p u 和c p u 的共同计 算下，使e n h a n c e dk m e a n s 算法的聚类效率显著提高。 第五：研究基于g p u 的d n n s 算法的实现方案。借鉴l a r s e n 提出的利用g p u 进行矩阵快速相乘的思想，将此思想和g p u 多子素处理器并行处理特点结合起来， 应用在d n n s 算法中，综合分析算法各步骤，将对算法复杂度产生关键影响的连 接度矩阵计算步骤交由g p u 完成，而建堆及合并操作由c p u 完成，在c p u 和g p u 的协同处理下使d n n s 算法的聚类时间快速减少。 第六：通过对试验数据集合在设定的试验环境中实现上述算法。综合实验， 分析结论。 本文的组织结构如图1 1 所示： 1 6 小结 图1 1 论文结构图 这一章是整篇论文的绪论部分，着重介绍了本文的研究目的、选题的背景与 依据，简单概括了g p u 的国内外研究现状，对本文的研究目标与研究意义进行阐 述，最后是本文的主要工作以及整个学位论文的组织结构安排。 4 在职人员同等学力硕+ 学位论文 2 1 聚类分析综述 第2 章预备知识 近年来数据挖掘引起信息产业界极大关注，成为当前计算机领域的一个研究 热点，而引起广泛的关注。随着数据的丰富带来对强有力的数据分析工具需要， 大量数据被描述为“数据丰富，信息贫乏”。同时伴随近年来互联网的发展与快 速普及，使得人类第一次真j 下体会到了数据海洋的无边无际。面对如此海量的数 据资源，决策者迫切需要一种新技术和智能工具，从巨大数据资源中提取有价值 的知识与信息资源，从而可以科学地进行各种决策。于是，知识发现一一个新的 研究领域应运而生。数据挖掘n 4 。吲( d a t am i n i n g ) 就是从大量的、不完全的、有噪 声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、 但又是潜在有用的信息和知识的过程。由于蕴藏知识的数据信息大多存储于数据 库中，因此又称作数据库中的知识发现( k d d ：k n o w l e d g ed i s c o v e f yi nd a t a b a s e ) 。 将数据库中的数据分类( 即聚类操作) 是数据挖掘的基本操作n 引。将物理或 抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类分析。通 过聚类生成的簇是一组数据对象的集合，这些对象数据彼此之间相似，而不同簇之 间的对象尽可能不同。作为一个数据挖掘的功能，聚类分析可以作为独立的工具 来获取数据分布的情况，这样可以观察形成的每个簇的特点，从而可以对特定的 某些簇做进一步分析；也可以作为其它算法( 如特征和分类等) 的预处理步骤。聚 类分析作为数据挖掘技术的一个重要的研究方向，目前主要集中在如何提高聚类 算法的有效性和实用性及对聚类算法进行改进，实现算法的整合。 2 1 1 聚类分析概念 聚类分析h 1 正在蓬勃发展，有贡献的研究领域包括数据挖掘、电子商务、图像 处理、统计学、生物学、文本分类等户聚类与分类不同：分类问题中知道训练集 的分类属性，而聚类问题则需要们从数据集中找这个分类属性，聚类所说的类不 是事先给定的，而是根据数据的相似性和距离来划分，聚类的数目和结构都没有 事先假定。所谓聚类，就是将物理或抽象对象的集合组成由类似的对象组成的多 个簇的过程。由聚类所生成的簇是一组数据对象的集合，同一簇中的对象尽可能 相似，而不同簇中的对象尽可能相异。相似或不相似的度量通常就是利用( 各对象 间) 距离来进行描述的。作为统计学的一个分支，聚类分析己被广泛研究多年，主 要集中在基于距离的聚类分析研究方面。在机器学习领域，聚类分析属于一种无 指导学习方法。在数据挖掘领域，研究工作已经集中在为大型数据库的有效和实 基于图形处理器的聚类分析算法研究 际的聚类分析新招适当的方法，聚类分析已成为数据挖掘领域中一个非常活跃的 研究课题。 2 1 2 聚类算法概述 按照聚类的原理和方法，目前主要使用的聚类算法竹3 可以分为以下几类： 1 基于划分的方法 把数据集d 采用一个划分准则( 例如距离) ，划分为后个子集( 簇c l u s t e r ) ， 使同一个簇中的对象是相似的，不同的簇中的对象是不相似的，使相应准则最优。 典型的划分方法包括：k 平均算法，k 中心点算法等。 2 基于层次的方法 是将数据对象组成一棵聚类的树，根据层次分解是自底向上还是自顶向下， 它分为凝聚的和分裂的方法。典型的方法有b i r c h 、c u b e 、r o c k 等。 3 基于密度的方法 绝大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球状 的类，而对发现任意形状的聚类结果上提出了基于密度的聚类方法n t 旧1 ，其主要思 想是：只要临近区域的密度( 对象或数据点的数目) 超过某个值，就继续聚类。也就 是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数 目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的类。典 型的基于密度的聚类算法包括：d b s c a n ，o p t i c s ，d e n c l u e ，d b c l a s d ， g d b s c a n 等。 4 基于网格的方法 基于网格的方法n - 憎1 首先把对象空间量化为有限数目的单元，形成了一个网格 结构。所有的聚类操作都在这个网格结构( 量化空间) 上进行。这类方法的处理 时间不受数据对象数目影响，处理速度较块，其处理时间独立于数据对象的数目， 只与量化空间中每一单元的数目有关。典型的基于网格的聚类方法有s t i n g 、 w a v e c l u s t e r 和c l i q u e 等。 5 基于模型的方法 基于模型的方法“1 为每个类假定了一个模型，寻找数据对给定模型的最佳拟 合。一个基于模型的方法可能通过构建反映数据点空间分布的密度函数来定位聚 类。主要有统计学方法( 如c o b w e b 、c l a s s i t 和a u t o c l a s s ) 或神经网络方法心0 1 ( 例如s o m 、a r t 、l v q ) 。 不同的聚类方法运用不同的相似性定义和技术，一种具体的聚类方法只适用 6 在职人员同等学力硕七学位论文 于一定的环境用户。本章从不同的角度分析比较了几类流行的聚类算法，研究已 有算法的改进，使聚类算法具有更好性能，从而使用户能方便快速地找到解决给 定问题的方法。实践证明没有任何一种聚类算法对所有的数据类型和定义都优于 其他聚类算法，每种算法都有其具体的应用环境。 2 1 3 数据挖掘对聚类分析算法的要求 数据挖掘中的聚类分析主要集中在针对海量数据的有效和实用的聚类方法研 究，聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求，数 据挖掘对聚类算法的典型要求主要有以下几个方面，引。 第一：可伸缩性：聚类算法对小于2 0 0 个数据对象的小量数据集和大于几百力- 个规模数据集都要有同样的聚类效果。 第二：处理不同类型属性的能力：实际应用要求算法能够处理不同类型的数据， 既可处理数值型数据，又可处理非数值型数据如二元类型，分类标称类型，序数 型数据或者是这些数据类型的混合等。 第三：能发现任意形状的聚类：聚类特征的未知性决定聚类算法要能发现球形 的、嵌套的、中空的等任意复杂形状和结构的聚类。 第四：用于决定输入参数的领域知识最小化：由于许多聚类算法要求用户输入 参数( 如产生的簇数) ，而输入参数对聚类结果十分敏感，通常参数很难确定，所 以要尽可能地减少用户估计参数的最佳取值所需要的领域知识。 第五：有效地处理噪声数据的能力：绝大部分数据库都包含了孤立点，空缺， 未知数据或者错误的数据。如果聚类算法不能处理现实世界的数据库中这些噪声 数据，则导致低质量的聚类结果。 第六：对于输入纪录的顺序不敏感：聚类算法应对同一个数据集合以不同的顺 序提交给同一个算法时，应具有相同的聚类结果。 第七：高维性：聚类算法不仅要擅长处理低维的数据集，而且要能处理稀疏且 高度偏斜的高维数据集。 第八：基于约束的聚类：找到既要满足特定的约束，又要具有良好聚类特性的 数据分组是比较有挑战的任务。 第九：可解释性和可用性：聚类结果应该是可解释的、可理解的和可用的。也 就是说聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方 法的选择也是一个重要研究课题。 聚类算法在数据挖掘领域中得到了广泛的应用。由于本文涉及到g p u + c p u 模 式在基于划分聚类算法和基于层次聚类算法应用，所以在以下章节中重点分析这 两类算法。 表2 1 是从上述几个方面对不同的经典算法进行比较。 7 基于图形处理器的聚类分析算法研究 表2 1聚类算法的比较 类别算法聚类可伸缩性聚类形状输 入 噪声处数据 质量敏感性理能力类型 基于划分 k m e a n s 差球状是差数值 基于层次 b i r c h好 好球状是 好 数值 c u r e好好任意不好数值 r o c k好好任意不好分类 基于密度 d b s c a n 好好任意 不 好数值 一 基于网格s t i n g一般好任意不好数值 基于模型c o b w e b好差特定 不 好分类 2 1 4 基于划分的聚类分析算法概述 对于一个给定的月个对象或元组的数据库h 1 ，采用目标函数最小化的策略，通 过迭代把数据分成k 个划分，每个划分为一个簇，并且后拧。也就是说，它将数据 划分为后个组，同时满足两个条件：每个分组至少包含一个对象；每个对象必须 属于且只属于一个组。给定要构建的划分的数目克，划分方法首先创建一个初始划 分。然后采用一种迭代的重定位技术，尝试通过对象在划分问的移动来改进划分。 一个好的划分的一般准则是：在同一个类中的对象尽可能相近或相关，而不同类 中的对象之间尽可能远离或不同。为了达到全局最优，基于划分的聚类会要求穷 举所有尽可能的划分，绝大多数应用采用的是以下两个比较流行的启发式方 法乜一一妇：k 平均算法，在该算法中，每个类用该类中对象的均值来表示，k m e d o i d s ( k 中心点) 算法，在该算法中，每个类用接近聚类中心的一个对象来表示。这 些启发式聚类算法对中小规模的球状簇很适用。而对大规模的数据集进行聚类以 及处理复杂形状的聚类，则要对这两种方法的进一步扩展和改进。 1 k m e a n s 聚类分析算法概述 典型的k m e a n s 聚类算法h 1 ，是一种已知聚类类别数的“无监督学习 算法。 指定类别数为j | ，对n 个对象进行聚类，聚类的结果由尼个聚类中心来表达。基于给 定的聚类效果判别准则，算法采用迭代更新的方法。每一次迭代过程都是向目标 函数值减少的方向进行，使目标函数值取得极小值，达到较优的聚类效果。 k m e 锄s 算法尝试找出使平方误差函数最小的k 个聚类，当样本数据是密集 的，且类与类之间区别特别好的时候，该算法的效果较好。对处理大数据集，该 算法是相对可伸缩和高效率的，因为它的复杂度是o ( 甩加，其中刀表示所有样本点 的个数，腥聚类个数，j 是迭代次数，通常聊，远远小于以。 在职人员同等学力硕十学位论文 算法受初始值的影响很大，聚类的结果往往只是局部最优，即使对不同的初 始值多次执行该算法，也只是在庞大的初值空间里简单地进行搜索，其结果也很 难达到全局最优，解决算法对于初始值的敏感性问题，相当于一个全局优化搜索 问题；k m e a n s 算法需要给出类平均值，因此它不适合处理有分类属性的数据： k m e a n s 算法生成的聚类数是预先给定的，不能动态的添加新的聚类，也是该算法 的一个缺点；此外，该算法对差别很大带有孤立点数据的类及非凸面形状的簇， 聚类效果不是很好，并且对“噪声和孤立点及初始值的选取敏感，因此实际中 使用时需要对该算法加以改进。k m e a n s 算法有很多变种。它们可能在初始庀个平 均值的选择、相异度的计算和计算聚类平均值的策略上有所不同。 以上是对k m e a n s 算法的优缺点简要分析，本文将在第三章详细对k m e a n s 进 行算法描述。 2 k m e d o i d s 聚类分析算法概述 由于k m e a n s 算法对孤立点很敏感；所以设想利用中心点来作为一个参考点代 替k m e a n s 算法中的各聚类的均值( 作为聚类中心) 。从而可以根据各对象与各参考 点之间的距离( 差异性) 之和最小化的原则，继续应用划分方法。这就构成了 k m e d o i d s 算法。 k m e d o i d s 聚类算法的1 基本策略是：首先为每个类随意选择一个代表对象； 剩余的对象根据其与代表对象的距离分配给最近的一个类，然后反复地用非代表 对象来代替代表对象，以改进聚类的质量。一个典型的k m e d o i d s 算法描述3 如下： 输入：聚类个数后，以及包含玎个数据对象的数据库。 输出：满足基于各聚类中心对象的方差最小标准的后个聚类。 ( 1 ) 从，1 个数据对象任意选择k 个对象作为初始聚类( 中心) 代表。 r e p e a t ( 2 ) 指派每个剩余的对象给离它最近的中心点所代表的簇。 ( 3 ) 随机选择一个非中心对象既一面用。 ( 4 ) 计算其与中心对象d ，交换的整个成本s 。 ( 5 ) 若s 为负值则交换d 阳行咖肼，与d ，构成新聚类的尼个中心对象。 ( 6 ) u n t i l 不发生变化 p a m ( p a n i t i o n i n g ar o u n dm e d o i d ，围绕中心点的划分) 是最早提出的七中心算法 之一“1 ，它试图对玎个对象给出七个划分，最初随机选择后个中心点后，该算法反复 地试图找出更好的中心点。所有可能的对象对被分析，每个对中的一个对象被看 作是中心点，而另一个不是。对可能的各种组合，估算聚类结果的质量，一个对 象d ，被可以产生最大平方一误差值减少的对象代替。在一次迭代中产生的最佳对 象的集合成为下次迭代的中心点。当刀和七的值较大时，这样的计算代价相当高。 9 基于图形处理器的聚类分析算法研究 当存在“噪声 和孤立点数据时，k m e d o i d s 方法比k m e a n s 方法更健壮，这是因 为中心点不像平均值那么容易受极端数据的影响。但是，k m e d o i d s 方法的执行代 价比k m e a n s 方法高。此外这两种方法都要求用户指定结果类的数目后。 2 1 5 基于层次的聚类分析算法概述 以数据之问的相似性信息为基础，根据相似性矩阵对数据集进行分层聚类， 类间相似性是层次方法的重要设计内容，它分为凝聚的和分裂的两种方法，自底 向上的凝聚层次方法是将每个数据作为一类，然后将每个对象作为单独的一个组， 然后相继地合并相近的对象或组，直到所有的组合并为一个，或者达到一个终止 条件。自顶向下的分裂层次方法，一开始将所有的对象置于一个类中，在迭代的 每一步中，一个类被分裂为更小的类，直到最终每个对象在单独的一个类中，或 者达到一个终止条件。 层次方法的问题在于：在合并中一旦一个步骤( 合并或分裂) 完成，它就不能 被取消，这样“一招失措，满盘皆输”：合并或分裂点的选择，好的局部合并选择 不能保证高质量的全局聚类结果；不适于非凸型分布数据集，效率不高。而改进 算法( 层次聚类与其他聚类方法结合) 有1 9 9 6 提出的b i r c h 算法：把层次聚类的 形成过程到结果看作一棵树，然后用其他聚类方法来进行修剪；1 9 9 8 年提出的 c u r e 算法：用一定数量的数据来代表一个类，然后将他们收缩为类的中心；1 9 9 9 年提出的c h a m e l e o n 算法：采用动态模型的聚类方法；r o c k 方法，它利用聚 类间的连接进行聚类合并。下面分别介绍b i r c h 算法和c u r e 算法。r o c k 算法将 在第五章介绍。 1 b i r c h 算法概述 b i r c h 是一个综合的层次聚类算法h 3 ，它用聚类特征和聚类特征树( c f ) 来概括 聚类描述，描述如下。聚类特征c ，定义如下：假设某个子聚类中有价d 维数据点 的簇) ( 卢，2 ，3 ，1 ，) ，一个聚类特征用一个三元组来表示，其特征向量定 ， 义为：d 阽( ，s ，跚其中为簇中点的个数；s 表示个点的线性和( q 2 ) ， 拉i ， 嬲是数据点的平方和( q 2 ) 。此外，对于聚类特征有如下定理乜引