《基于尺度转换机制的多尺度聚类挖掘算法》由会员分享，可在线阅读，更多相关《基于尺度转换机制的多尺度聚类挖掘算法（4页珍藏版）》请在金锄头文库上搜索。
1、基于尺度转换机制的多尺度聚类挖掘算法摘要：提出了一种基于重要尺度的多尺度聚类挖掘算法iMSCA(important MultiScaleClustering Algorithm),同传统的多尺度聚类挖掘算法不同，基于重要尺度的多尺度聚类挖掘算法首先 在指定的重要尺度实现聚类挖掘结果，再通过尺度转换机制求得用户感兴趣的其它尺度的聚 类结果。实验数据表明，木文提出的算法iMSCA同传统的多尺度聚类挖掘算法相比具较好 的性能。关键词：聚类挖掘、多尺度、尺度转换机制Abstract：An important MultiScale Clustering Algorithm (iMSCA) is prop
2、osed Unlike the traditionalmultiscale clustering algorithms, iMSCA clusters the data on an important scale, then obtains the clustering results on the other scales which users are interested in with the help of Scale Convert Mechanism. The experiments turns out that iMSCA presented in this paper doe
3、s well compared with the traditional multiscale clustering algorithms.Key Words： Clustering Mining, Multiscale, Scale Convert Mechanism1.引言聚类挖掘是数据挖掘研究领域重要的纽成部分，而多尺度聚类挖掘是解决具有多尺度特 性的空间或时空数据的挖掘算法，亦将数据挖掘理论研究推向了另一个新的研究层次与方向。在国外，针对空问或时空数据的多尺度特性进行的研究大多集中于多尺度效应与多尺度 建模方血等应用方面,如以非监督多尺度数据流算法基于数据驷动的数据流对涉及时间尺度 的
4、数据流进行趋势预测U,并将这种算法成功地应用于股票数据的分析。另有学者将平稳小 波变换M用于多尺度分析提出了皿用性强的尺度选择方法进而构建了两种分类器一SVM分 类器和Bayes分类器5通过引入多尺度超像索分割生成中问点，有学者提出了一种从杂乱 影像中恢复和分组物体对称部分的方法“。但对多尺度聚类挖掘的理论研究还比较缺乏，在 国内有学者通过引入多尺度控制参数来调节聚类挖掘的尺度特性而提出的多尺度谱聚类算 法】，基于多尺度并行免疫克隆优化聚类算法实现了在不同的进化时期分别以大小不同的多 种尺度并行地实现最优解空问的快速定位与精确查找，基于小波分解和领域信息的多尺度 FCM聚类算法】大大提高了图像
5、分割的效率、抗噪性和均匀性。但这些基于数据的多尺度特 性进行的聚类挖掘人多是通过引入调节聚类尺度的控制参数U来实现在每种尺度上的聚类挖 掘。但这种挖掘算法需要在每一种尺度上进行挖掘，计算量大，在用户不感兴趣的尺度上进 行的挖掘结果得不到用户的认可，造成资源浪费，也不能实现在某一指定尺度上的实时聚类 挖掘。针对这些多尺度聚类挖掘算法的不足，本文提出了一种基于尺度转换机制的多尺度聚类 挖掘算法 iMSCA(important Multi-Scale based Clustering Algorithm),算法先在指定的基尺度 BS(Basic Scale)上进行聚类挖掘，再借助于尺度转换机制SCM
6、(Scale Convert Mechanism)对 瓦它尺度进行挖掘。实验数据表明，木算法很好地克服了传统多尺度聚类算法存在的不足, 聚类效果亦能得到保证。木文第二部分对算法思想进行阐述，并引入了基尺度的概念和尺度 转换机制；第三部分详细描述了木文的算法过稈；第四部分对木文算法的性能进行了分析和 验证；最后对木文研究工作进行了总结和展望。2.基尺度与尺度转换机制针对传统多尺度聚类挖掘存在的不足,木文通过引入基尺度与尺度转换机制具有多尺度 特性的空间或时空数据库进行挖掘。尺度在学术界并没有一个确定的概念，1992年，Lam 和Quattrochi对尺度总结了四种含义”尺度阪机疝及耐町，分别是a
7、)传统意义下的制图比例尺或 地图比例尺，b)地理范用或研究问题的域，c)空间分辨率，d洌I：究对彖的尺度。鉴于此并结 合木文研究的需要有必要对尺度的一些基木概念进行定义,并在此基础上引入尺度转换机制。定义1尺度(Scale)：是指对某一事物或现象0 (Qbjeci)进行研究时所采用的空间或时间 单位，记作S (文中若无特殊说明均指研究所采用的空间单位，如某地区5m x 5m的影像数 据，对某省人口数据按村级单位进行统计等)。定义2大、小尺度：设S、S是研究某一事物或现象0时所采用的空间尺度，若尺度 s所表示的空间单位比尺度s 更大(更小)，则称尺度s比尺度s 更大(更小)，记作s(1 (SyS
8、)，而尺度S比尺度S更小(更大)。相应地对基于这两种尺度所研究的事物或现 彖0称为大尺度数据和小尺度数据。例如对某地区进行降水量研究时采用的5m X 5m的影像数据和10m x 10m的影像数据， 前者所表示的尺度更小，示者表示的尺度更大。可以看岀，大尺度对数据进行研究时更具有 一整体性，注重事物的宋观特性，而小尺度对数据进行研究时更具有细节性，注重事物的微观 特性。定义3基尺jg(Basic Scale)：设S是研究某一事物或现象0时所采用的空间尺度，在对 这一事物或现象O的以它尺度S进行研究时，nf以将尺度S表示成尺度S某种线性或非线 性函数，则尺度S称为研究此事物或现象O时的基尺度，记作
9、BS。例如某地区采用5m x 5m的煤像数据对该地区的降水量进行研究，当研究此地区10m x 10m时的降水量时，可以将原来的影像数据进行两两合并表出后者的影像数据，则尺度5m x 5m称为研究此地区降水量时的基尺度。定义4尺度转换(Scale Convert)：设S、S是研究某一事物或现彖O时所采用的空间 尺度，且尺度S所表示的空间单位比尺度S更大，即SS,称实现从尺度S到尺度S时 所做的转换为尺度转换，记作STS。由大尺度S到小尺度S所做的尺度转换称为尺度下 推SD(ScaleDown),记作反Z,由小尺度S到大尺度S所做的尺度转换称为尺 度上推 SU(Scale Up),记作 S f S
10、。基于基尺度与尺度转换机制，借助于向量空间的知识提出了算法iMSCAQmportant MultiScaleClustering Algorithm),由于N维向量空间中的任何八下向量均可以由这个向量空 间中的一组向量基(个互不相关的N维向量)表示。基于此思想，木文提出了基尺度的 概念，将其它尺度由基尺度进行表示，对空间或时空数据进行多尺度挖掘时，先对基尺度进 行挖掘，再由基尺度的挖掘结果通过尺度转换机制(Scale Convert Mechanism)获得其它尺度 的挖掘结果3算法iMSCA3.1 iMSCA木文提出的算法iMSCA是在对基尺度进行聚类挖掘的基础上实现的，因此先选择基尺 度B
11、S。，并对空间或时空数据进行聚类挖掘，再对用户感兴趣的其它尺度进行挖掘。输入：具有多尺度特性的空间或时空数据对象0输出：用八感兴趣的乞尺度上的聚类结果1 Choose the Basic Scale of O, BS()2 Make clusters of 0 on the scale BS()3For the other scale S of O, which is not the Basic Scale4 我SY()BS()5 thenSD( BS0 S )6 in versec lustersof 0 onscale S7 ifS ()BS()8 thenSU( BSO S )9 inv
12、erseclustersofO onscale S10 exitwhenthereisnoanyscale算法中第4步如果尺度S比基尺度BS0更小,则由第5步中的SD尺度下推(ScaleDown) 算法，通过基尺度下推出尺度S,并在笫6步反演出尺度S上的聚类结果；同样，若 尺度S比基尺度更大(由第7步进行判断)，则由第8步中的SUX度上推算法，通过 基尺度BS。上推出尺度S,并在第9步反演出尺度S上的聚类结果；若用户感兴趣的尺度 均已聚类完毕(第10步)，则算法退出并返冋在各尺度上的聚类结果。3.2尺度上推与下推上述算法的核心就是基于基尺度上推或下推出其它尺度S的数据，并反演出在尺 度S上的聚类结果，因此有必要对尺度上推与下推方法进行研究。尺度上推与尺度下推均属于尺度转换，尺度转换是地学领域中重要的研究内容，国内外 已经针对尺度转换提出了很多方法，有基于分形理论的分形法，基于地统计学理论的半变异 函数法和白相关分析法，克里金法，以及小波分析法等。其中克里金法在尺度上推与下推当 中M用广泛，如尺度下推时基于空间局部估计的点普通克里金法，尺度上推时的块状克里金 法。结合上述算法的需要，本文分别选择点普通克里金法和块状克里金法进行尺度下推与尺 度下推。4.算法性能分析5 总结与展望
