流数据挖掘综述_孙玉芬
流数据挖掘综述＊)
孙玉芬卢炎生
(华中科技大学计算机科学与技术学院武汉430074)
在这3种模型中,Turnstile是最具一般性的数据流模
型,其适用范围最广,也最难处理。流数据分类与聚类通常使
用的是时序模型,它们将数据流中的每个数据项看作一个独
立的对象。若将A[j]记为信号j出现的次数,则流数据频繁
模式挖掘通常使用的是Cash Register模型,只允许数据的插
入。也有算法研究了同时存在数据插入和删除时的流数据频
繁模式挖掘问题。此时,算法应用的是数据流的Turnstile模
型。
由于数据流是一个长期、动态的过程,部分算法在处理数
据流时并不是将所有的数据流数据作为处理对象,而是根据
应用需求选取某个时间范围内的数据进行处理。按算法处理
数据流时所选取的时序范围,数据流模型可分为以下几类[9]:
(1)快照模型(snapshot model):处理数据的范围限制在
两个预定义的时间戳之间。
(2)界标模型(landmark model):处理数据的范围从某一
个已知的初始时间点到当前时间点为止。
(3)滑动窗口模型(sliding window model):处理数据的范
围由某个固定大小的滑动窗口确定,此滑动窗口的终点永远
为当前时刻。其中,滑动窗口的大小可以由一个时间区间定
义,也可以由窗口所包含的数据项数目定义。
在这3种模型中,界标模型和滑动窗口模型是采用得比
较多的模型。界标模型通常将数据流的起始点作为数据处理
的初始时间点。此时,算法对数据流中所有数据进行处理,数
据流上只存在插入操作。在滑动窗口模型中,窗口随着数据
的流入向前滑动,窗口中存在数据的插入和删除。滑动窗口
模型非常适用于只要求对最近时间段内的数据进行处理的应
用。
3流数据挖掘算法的特点
数据流实时、连续、有序、快速到达的特点以及在线分析
的应用需求,对流数据挖掘算法提出了诸多挑战。数据流对
挖掘算法的典型要求如下:
(1)单次线性扫描。即算法只能按数据的流入顺序依次
读取数据一次。
(2)低的时间复杂度。流算法是在线算法,为了跟上数据
流的流速,算法处理每个数据项的时间不能太长,最好能为常
数时间。
(3)低的空间复杂度。流算法是主存算法,其可用的空间
是有限的,算法的空间复杂度不能随数据量无限增长。
(4)能在理论上保证计算结果具有好的近似程度。
(5)能适应动态变化的数据与流速。产生数据的现象可
能在不断变化,导致数据内容与流速的改变。
(6)能有效处理噪音与空值。这是一个具有健壮的算法
所必须具有的能力。
(7)能作on demand的挖掘。即能响应用户在线提出的
任意时间段内的挖掘请求。
(8)能作anytime的回答。即算法在任何时刻都能给出
当前数据的挖掘结果。
(9)建立的概要数据结构具有通用性。算法所构建的概
要数据结构不仅能支持算法当前的目标计算,而且能支持其他的计算。
在上述要求中,第1至3条是一个流数据挖掘算法所必
须满足的。早期的流数据挖掘算法都是以这三项为目标设计的,如文[10,11]。对于算法的空间复杂度,理想的情况是它
与数据流长度N无关。但是,目前大部分问题都无法找到这样的解。因此,这个要求就让步为找到空间复杂度为O(poly (logN))的算法,即次线性算法。算法的时间复杂度通常以
每个数据项到来时,更新概要数据结构或目标计算结果所需要的时间来衡量,理想的情况是算法处理每个数据项的时间为常数。其中,概要数据结构是算法为支持目标计算而在内存中保存的数据流数据的压缩信息。对于构建概要数据结构的算法,通常没有对在概要数据结构上计算目标函数所需要的时间做严格的要求。
近似性与自适应性是数据流算法的两大特点[3]。由于一
次线性扫描以及时间与空间的限制,数据流算法往往只能得到对所处理的问题的近似计算结果。能在理论上保证其计算结果的近似程度,是算法应该考虑的一个问题。算法的自适应性是指当流数据内容或流速受各种因素的影响而发生改变时,算法能够根据这些改变自动调整计算策略与计算结果。噪音与空值是一个健壮的算法所必须解决的问题。对于
流数据挖掘算法,这个问题显得更为突出。这是因为在挖掘数据库中的静态数据集之前,通常会进行数据的预处理,消除数据中的噪音与空值。而在在线进行的流数据挖掘过程中, 无法在挖掘前对数据进行预处理。而且,数据流中的数据在采集以及传输过程中,都可能出现错误,产生噪音或空值。数据流的动态变化性更进一步增加了噪音识别的困难。当产生数据流的现象发生改变时,新数据无法被现有数据模型所描述,可能被误认为是噪音。
在一些应用中,用户可能在数据流流入过程中提出对某
个时间段内的数据进行挖掘的请求。能回答这种请求的算法被称为具有on demand回答能力的算法。算法通常采用多窗
口技术来近似解决这类问题。能对挖掘请求给出anytime的回答,指算法在任何时刻都能给出对当前数据最精确的计算结果。这要求算法每读取一个数据项,就更新处理结果。
有些算法构建的概要数据结构只能用来支持算法的目标
计算,如文[12]中为计算数据流对之间的滞后关联而保留的统计量。有的概要数据结构是对数据流数据一般性的压缩, 还可用来支持其他计算,如文[13]中保留的多个基本窗口内
数据的傅立叶变换系数。这样的概要数据结构显然比只能支持当前计算的概要数据结构更为有用。
4相关技术
基于对多个流数据挖掘算法的分析,我们总结了算法常
用的一些技术。这些技术主要包括概要数据结构、滑动窗口技术、多窗口技术、衰减因子、近似技术等。
4.1概要数据结构
在流数据处理系统中,由于数据量远大于可用内存,系统
无法在内存中保存所有扫描过的数据,而流数据查询与挖掘经常会要求读取这些数据。为了避免代价昂贵的磁盘存取, 流数据处理系统必须在内存维持一个概要数据结构,以保留扫描过的信息。文[9]已对建立概要数据结构的方法作了综述,本文在这里只作一个简单的介绍。
目前,生成数据流概要数据结构的主要方法包括取样(sampling)、直方图(histogram)、小波变换、Sketching、Load shedding和哈希方法。其中,取样方法将数据流中的数据项以一定概率抽取到概要数据结构中。直方图按照数据项的取值或出现频率将数据项划分为桶,对每个桶压缩表示。小波方法对原有数据做小波变换,将保留原有数据主要信息的少·2·
5.1.2主分量计算
文[15]对多条数据流组成的矩阵作奇异值分解(Singular Value Decomposition,SVD)分析,并使用得到的特征值和特
征向量表达数据流之间的关联。文章采用数据流的十字转门(Turnstile)模型,给出了界标模型和滑动窗口模型下的算法。其中,采用滑动窗口模型的算法将滑动窗口内的数据划分为多个段,分段保存矩阵的组成数据,当某个段的时间戳滑出滑动窗口时,将整个段删去。
文[15]在数据流上进行SVD分析的计算代价过大。文
[2]采用PCA(principal component analysis)技术分析多数据流,将n条数据流用k个隐藏变量表示,其中k n。但是,它
没有使用SVD计算主分量,而是基于自适应过滤技术(adap- tive filtering techniques)实现了一个增量式的主分量获取算法。文中使用指数衰减因子来逐渐消除历史数据对计算结果的影响。
5.1.3多数据流聚类
与定量计算数据流之间的关联统计量不同,另一种多数
据流关联分析方法对多条数据流进行聚类分析[18,19],发现彼此间相似的数据流。文[18]主要讨论了如何减少每个时刻需要计算的数据流对之间的距离。文章采用数据流的界标模型。文[19]提出一个滑动窗口模型下的多数据流聚类方法。此方法基于一个层次概要数据结构支持任意大小滑动窗口内的多数据流聚类。
5.2单数据流挖掘
为避免与已有文献的重复,对于单数据流挖掘,本文只分
析了各项挖掘任务中最具有代表性的算法,更全面的算法介绍请参见文[20]。
5.2.1分类
为了对数据流进行实时处理,要求算法在看到整个数据
流之前就能处理数据并得到处理结果。而传统的判定树构造算法必须从一开始就能够读取整个数据集。文[21]提出一个针对数据流的增量式判定树构造算法。算法基于Hoeffding 不等式,以一定概率保证其增量式生成的判定树与使用传统算法在整个数据集上生成的树相差不大。
设数据中包含c个类别,G(Xi)为构建判定树时为选择
分裂属性所计算的各属性的信息增益。设在读取n个数据后, G(Xa)最大, G(Xb)次大。对于某个指定的δ,若ΔG= G (Xa)- G(Xb)≥(logc)2ln(1/δ)2n,则Hoeffding不等式以概
率1-δ保证选择Xa作为分裂属性是正确的。此时,算法只
使用部分数据项就能以一定概率正确选择树节点的分裂属性,从而将只能在整个数据集进行的批处理式的判定树构造算法改进为一个增量式的判定树构造算法。
文[22]设计了一个基于聚类分析的数据流分类算法。还
有大量文献研究了如何在变化的数据流上建立分类
器[14,23～29],这些文献将在后面详细讨论。
5.2.2频繁项挖掘
在动态数据集上挖掘频繁项是一项困难的任务[30]。数
据流所要求的单次线性扫描进一步增加了这项任务的难度。随着数据的不断流入,频繁项可能会变得不频繁,非频繁项也可能成为频繁项。要精确地计算数据流中的频繁项,算法必须保存所有的历史数据。但是,对于流数据,这是一个无法达到的要求。因此,数据流上的频繁项挖掘算法只能得到近似计算结果。
文[10]提出一个近似的流数据频繁项挖掘算法。算法保
存多个三元组记录:(e,f,Δ),其中,e是数据流中的元素,f
为e的估计频率,Δ是e的最大可能的错误,即若记e的真实频率为fe,则fe≤f+Δ。对于选定的参数ε,每当算法遇到
一个没有被记录的新元素e′时,就生成一个新元组(e′,1, εN);每当算法读取1ε个数据项时,就删除所有f+Δ≤
εN的元组。其中,N为目前已读取的总的数据项数目。通过这种处理,算法保证所有fe>εN的元素都被记录,且f≤
fe≤f+εN。对于任意的频繁度阈值s>ε,输出满足条件f≥(s-ε)N的项就保证所有fe≥sN的项都被输出,且所有输出
项都满足条件fe≥(s-ε)N。在实际应用中,大部分数据的
出现频率都较低,通过采用上述方法,算法不需要记录出现频
率较低的数据,从而既节省了计算空间,同时又保证了输出的
质量。
上述算法采用的是数据流的界标模型,在整个数据流上
进行计算。文[31]将其扩展到数据流的时间窗口模型上,实
现了多时间粒度的频繁项挖掘。
5.2.3聚类
第一个以数据流为分析对象的聚类算法是由斯坦福大学
的Sudipto Guha等人提出的[32]。这个算法采用分而制之(Divide-and-Conquer)的思想,将数据流划分为多个段,算法
对每段分别聚类,得到第一层簇中心。当第一层簇中心达到
一定数目后,对其进行聚类,得到第二层簇中心。这样的过程
伴随数据的流入一直进行,在每个时刻,系统最多维持m个
第i层中心点。此算法在整个数据流上进行计算。由于每次都要积累一定数目的数据后才进行处理,此算法只能看作是
分批批处理算法。
算法CluStream[16]与HPStream[17]是流数据挖掘中的两
个重要的聚类分析算法。这两个算法都在线计算micro-clus- ter[33]。CluStream使用金字塔时间结构(Pyramidal Time Frame)保存一系列micro-clusters的快照,从而能够以较小的
误差计算任意时间段内的聚类,且能够分析随时间推进聚类
的改变。HPStream针对高维聚类问题,动态地选择使聚类
体积最小的那些维与聚类关联,实现了一个子空间聚类算法。与CluStream在整个数据流上计算micro-cluster不同的是, HPStream使用衰减因子随时间推进不断衰减历史数据,并
在聚类数目过多时,删除最早加入的聚类。CluStream与HPStream都是增量式的聚类算法,在每个数据项到来时都
进行处理,因此它们都能作anytime的回答。
在流数据聚类研究中,还出现大量其他的挖掘方法。文[34]和文[35]将基于网格的聚类算法应用到数据流上。文[36]扩展了K-划分算法和CURE算法。文[37]提出K-
means算法的变体以聚类二元数据流。文[38]实现了一个滑动窗口模型上的K-Medians聚类算法。
5.3挖掘变化的数据流
由于数据流是一类流速与数据内容都随时间动态变化的
数据对象,挖掘变化的数据流成为流数据挖掘领域的一个特
有的研究内容。目前,挖掘变化的数据流包括两方面的研究: 模型跟踪[28]和变化挖掘[39]。其中,模型跟踪与机器学习中
的概念跟踪[40～43]可以看作同一个概念。变化挖掘与统计中的改变点检测(change-point detection)[44]和时序数据上的分割(segmentation)[45,46]类似。
在变化的数据流上建立分类模型,是一个研究得比较多
·4·
个小波参数作为概要数据保存。Sketching对数据作垂
直取样。Load shedding在负载过大时直接丢弃一些数据项。哈希方法通过一组哈希函数,将大量数据映射到少量桶中。
4.2滑动窗口技术
使用滑动窗口的需求来自于算法和应用。在算法方面,
滑动窗口减少了算法需要处理的数据量,并对挖掘变化的数据流提供支持。在应用方面,有些应用只对最近的数据感兴趣,要求算法对以当前时间为终点的某个滑动窗口内的数据进行处理。
在滑动窗口上进行数据挖掘最大的困难在于过期数据的
移除。随着数据的流入,滑动窗口中最早到达的数据将滑出窗口的范围,算法需要消除这些数据对滑动窗口上的目标计算所造成的影响。解决这个问题的最直接的做法是保存滑动窗口内的所有数据,当某个数据滑出窗口时,根据这个数据的值,将其从计算结果中消除。目前,多个采用滑动窗口模型的挖掘算法使用这种方法实现滑动窗口上的计算,如
CVFDT[14]。这种方法可以精确地对滑动窗口内的计算结果进行增量式地更新。但是,由于要保存窗口内的所有数据,对于其大小超过可用内存空间的滑动窗口,仍然需要进行磁盘存取。
为减少滑动窗口内数据所占用的空间,另一种方法以降
低滑动窗口上计算的精度为代价,使用小于滑动窗口内数据体积的空间,支持滑动窗口上计算的增量式更新。这种方法将数据流划分为小的固定长度的段(bucket,或basic win- dow),对每个段,仅保存段内数据的概要信息,如StaS-
tream[13]。滑动窗口在这些段上滑动。当流入的数据积累成一段时,抽取这一段的概要信息,将其加入滑动窗口,并从滑
动窗口中删除最早的段。这样,内存中就只需要保存滑动窗口中多个段的概要信息。此时,滑动窗口的增量式更新粒度由一个数据项增大为一个数据段。这种方法通常只支持大小为段大小的整数倍的滑动窗口上的计算[15]。文[13]通过保存每个段的数据的离散傅立叶变换系数,能支持任意窗口大小内的数据流关联系数计算。
4.3多窗口技术
基于滑动窗口的方法一般都要求用户事先指定窗口大
小,算法在运行过程中只能给出此滑动窗口上的计算结果。而在很多应用中,用户可能在线提出某个窗口上的挖掘请求, 此窗口的大小没有事先确定,而且窗口的终点可能也不是当前时刻。为了支持这样的应用需求,学者们提出一种多窗口方法,支持用户的在线挖掘请求。
多窗口技术在内存或磁盘中保存数据流上多个窗口内数
据的概要信息。在有些算法中,每个窗口的范围都是从数据
流起始点到窗口建立的时刻点,窗口中的数据存在重叠,如CluStream所使用的pyramidal时间框架[16]。另一类多窗口
技术将数据流划分为多个固定长度的段,每个段都形成一个
窗口。当内存中的窗口数达到一定数目时,就将这多个窗口
合并,形成概要层次更高的窗口。随着数据流的流入,概要层
次不同的多个窗口形成一个层次结构。此时,每个窗口相当
于对数据流上两个预定义的时间戳之间数据的一个快照。
4.4衰减因子
除了滑动窗口技术,另一种可被用来消除历史数据对当
前计算结果的影响的方法是使用衰减因子[17]。在这种方法中,每个数据项都被赋予一个随时间不断减小的衰减因子,数
据项的值与衰减因子相乘后再参与计算。因此,数据项对计
算结果的影响随时间的推移逐渐减小。这种方法的实现很简单,但是,与滑动窗口技术相比,其计算结果的意义不是非常
明确。在使用滑动窗口的算法中,用户明确地知道他是在对
哪些数据进行处理。而在使用衰减因子的方法中,每项数据
都只是部分地参与了计算,用户无法确定计算结果到底由哪
些数据得到。
4.5近似技术
由于数据流处理严格的时间与空间限制,确定且精确的
数据流算法比较少见。对于大多数算法,只能以降低计算结
果的精度为代价,换取算法时空复杂度的降低。能在理论上
保证近似程度的算法是比较理想的近似算法。
目前,有多种近似技术可用来降低算法的时空复杂度。
例如,基于概要数据结构的算法都是近似算法。这是因为在
构建概要数据结构时,不可避免地存在着信息的损失。概要
数据结构只能近似还原原有数据。基于多窗口技术和衰减因
子的算法也是近似算法。除了使用这些通用的压缩技术,也
可针对具体的挖掘任务,设计相应的近似算法[10]。
4.6自适应技术
由于数据流是动态变化的,处理数据流的算法必须能够
根据数据分布的变化以及数据流流速的变化自动调节算法的
处理策略。动态系统中的自适应技术根据系统的反馈自动调
节系统参数。目前,在处理变化的数据流时,算法通常将分类
器的分类精度作为反馈,在精度下降时重新建立分类模型。
5流数据挖掘算法
流数据挖掘的对象可以是多条数据流,也可以是单条数
据流。挖掘多条数据流的主要目的是分析多条并行到达的数
据流之间的关联[2,12,13,15,18,19]。对单数据流的挖掘则涵盖了分类、频繁模式挖掘、聚类等多项传统数据挖掘中的主要任务。挖掘变化的数据流是一项特殊的任务,目前主要是以单
数据流为对象进行研究的。
5.1多数据流关联分析
现有的多数据流关联分析主要采用3种方法,即计算数
据流对之间的关联系数[12,13]、计算多条数据流的主分
量[2,15],以及计算多条数据流中存在的聚类[18,19]。
5.1.1关联度计算
关联度计算指在多条数据流中,计算每对数据流之间的
关联系数,从而发现具有高的正关联或负关联的数据流对。
当数据流数目较大时,在线计算每对数据流之间的关联系数
是不现实的。文[13]实现的StaStream系统通过使用离散傅
立叶变换的保距特性与系数的对称特性,推导出数据流对傅
立叶变换系数之间的距离与关联系数之间的关系。系统只对
傅立叶变换系数之间距离满足一定条件的数据流对计算关联
系数。StaStream采用数据流的滑动窗口模型,并将每条数据
流划分为小的固定长度为b的段(基本窗口),对每个段,保存
段内数据的离散傅立叶变换系数。系统将滑动窗口内的段作
为数据流的概要数据结构。这个概要数据结构还可为其他计
算提供支持。
StaStream没有对数据流对之间存在滞后关联的情况作
太多讨论,但是这种情况在应用中比较常见。文[12]提出的
BRAID方法,讨论了滞后关联(lag correlation)的计算。
BRAID采用界标模型,对数据流从起始到当前时刻所有的数
据进行处理。其概要数据结构只能用来计算数据流对之间的
关联系数。
·3·
本文得到湖北省自然科学基金项目“时空数据库的关键技术研究与实验”(ABA048)的资助。孙玉芬博士生,研究方向为流数据挖掘和聚
类分析;卢炎生教授,博导,研究方向为特种数据库、数据挖掘和软件测试。
题[14,23～27,29]。文[14]中提出的CVFDT基于文[21]中
的VFDT算法,在一个动态调节大小的滑动窗口上,增量式
地建立一个随数据变化动态变化的判定树。为消除历史数据
对判定树计算的影响,算法必须保留整个滑动窗口内的所有
数据。
另一类在变化的数据流上建立分类模型的方法通过建立
多个分类模型来实现模型的跟踪[24～29]。文[27]第一个将机
器学习中的集成方法(ensemble methods)用来对变化的数据
流分类。算法在数据流上维持一个由固定数目的分类模型组
成的ensemble。每当算法读取一定量的数据后,就在此段数
据上建立一个分类模型。若此分类模型能够提高ensemble
的分类性能,则用其替换ensemble中性能最差的一个分类模
型。Ensemble使用无权重的majority voting投票规则对数
据进行分类。文[24]与文[25]根据各分类模型在当前数据段
上的预测错误期望,赋予它们适当的权重。文[28]使用logis-
tic回归技术,通过最大化数据的似然给ensemble中的各个分
类模型赋予最优的权重。文[26]在ensemble中的所有分类
模型中找出其训练数据集与当前数据最相似的分类模型。为
了实现这个分类模型选择策略,算法为每个分类模型保存相
应的训练数据集。这种选择策略可有效减少ensemble中的冗余信息,尽可能扩大ensemble中分类模型的数据覆盖范围。在对当前数据进行分类时,文[24～28]都是使用多个分
类模型分类结果的组合,文[29]在多个分类模型中选择对当
前数据分类效果最好的分类模型进行分类。
文[47]按数据流中是否发生概念转移以及训练模型的数
据是否充分这几种不同的情况,使用不同的数据集训练得到多个分类模型,然后选择分类正确度最高的模型作为当前最优模型。
文[48]研究了如何发现数据流中数据分布的改变并将其
可视化。文章通过计算数据流入时数据空间中各数据点密度的改变情况,发现数据点的转移轨迹与趋势,并将这些转移以图形的形式表示出来。
比较两个数据集的数据分布是否相同,是统计上曾经研
究过的一个问题[49]。通过在数据流上维持多个数据窗口,文[50]将检测数据流中的变化转化为比较两个数据集的分布是否相同的问题,并提出一个非参数方法来解决这个问题。文[51]更进一步,设计了一个新的数据结构来度量两个数据集
之间的相似度。
结束语本文介绍了现有的数据流模型,总结了流数据
挖掘算法的九大特点,并讨论了算法中常用的几种技术。文中还针对不同的挖掘任务,分析了其代表性算法。这些内容对于深入了解流数据挖掘并提出新的挖掘算法,都有重要意义。
参考文献
1 Henzinger M R,Raghavan P,Rajagopalan https://www.wendangku.net/doc/fe6672234.html,puting on data streams.SRC Technical Note 1998-011.Digital systems research center:Palo Alto,California,1998
2 Papadimitriou S,Sun J,Faloutsos C.Streaming Pattern Discov- ery in Multiple Time-Series.In:Proc of the 31st VLDB Conf, 2005.697～708
3 Babcock B,et al.Models and issues in data stream systems.In: Proc of 21st ACM Symposium on Principles of Database Systems (PODS 2002),2002.1～16
4 Chandrasekaran S,et al.TelegraphCQ:Continuous Dataflow Processing for an Uncertain World.Proc of The Conf on Innova- tive Data Systems Research(CIDR),2003
5 Abadi D J,et al.Aurora:A New Model and Architecture for Da- ta Stream Management.The Intl Journal on Very Large Data Ba- ses,2003,12(2):120～139
6 Cai Y D,et al.MAIDS:Mining Alarming Incidents from Data Streams.In:Proc of the 2004 ACM SIGMOD Intl Conf on Man- agement of data,2004.919～920
7 O'Callaghan L.Approximation algorithms for clustering streams
and large data sets:[Ph D Thesis].The Department of Computer Science,Stanford University,2003
8 Muthukrishnan S.Data streams:Algorithms and applications. In:Proc of the fourteenth annual ACM-SIAM symposium on dis- crete algorithms,2003.413～413
9金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学报, 2004,15(8):1172～1181
10 Manku G S,Motwani R.Approximate frequency counts over da- ta streams.In:Proc of the 28th VLDB Conf,2002.346～357
11 O'Callaghan L,et al.Streaming-Data Algorithms for High-Qual- ity Clustering.In:Proc of the 18th Intl Conf on Data Engineering (ICDE'02),2002.685～694
12 Sakurai Y,Papadimitriou S,Faloutsos C.BRAID:Stream Min-
ing through Group Lag Correlations.In:Proc of the 2005 ACM SIGMOD Intl Conf on Management of Data,2005.599～610
13 Zhu Y,Shasha D.StatStream:Statistical Monitoring of Thou- sands of Data Streams in Real Time.In:Proc of the 28th VLDB Conf,2002.358～369
14 Hulten G,Spencer L,Domingos P.Mining Time-Changing Data Streams.In:Proc of the 7th ACM SIGKDD Intl Conf on Knowl- edge Discovery and Data Mining,2001.97～106
15 Guha S,Gunopulos D,Koudas N.Correlating Synchronous and Asynchronous Data Streams.In:Proc of The 9th ACM SIGKDD
Intl Conf on Knowledge Discovery and Data Mining,2003.529～534
16 Aggarwal C C,et al.A Framework for Clustering Evolving Data Streams.In:Proc of the 29th VLDB Conf,2003.81～92
17 Aggarwal C C,et al.A Framework for Projected Clustering of High Dimensional Data Streams.In:Proc of the 30th VLDB Conf,2004.852～863
18 Yang J.Dynamic Clustering of Evolving Streams with a Single Pass.In:Proc of the 19th IEEE Intl Conf on Data Engineering (ICDE'03),2003.695～697
19 Dai B-R,et al.Clustering on Demand for Multiple Data Streams. In:Proc of the Fourth IEEE Intl Conf on Data Mining(ICDM' 04),2004.367～370
20 Gaber M M,Zaslavsky A,Krishnaswamy S.Mining data streams:A review.SIGMOD Record,2005,34(2):18～26
21 Domingos P,Hulten G.Mining High-Speed Data Streams.In: Proc of the sixth ACM SIGKDD Intl Conf on Knowledge Discov- ery and Data Mining,2000.71～80
22 Aggarwal C C,et al.On Demand Classification of Data Streams. In:Proc of the 2004 ACM SIGKDD Intl Conf on Knowledge Dis- covery and Data Mining,2004.503～508
23 Yang Y,et https://www.wendangku.net/doc/fe6672234.html,bining Proactive and Reactive Predictions for Data Streams.Proc of the 2005 ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining,2005
24 Wang H,et al.Mining Concept-Drifting Data Streams using En- semble Classifier.In:Proc of the 9th ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining,2003.226～235
25 Kolter J Z,Maloof M A.Dynamic Weighted Majority:A New Ensemble Method for Tracking Concept Drift.In:Proc of the Third IEEE Intl Conf on Data Mining,2003.123～130
26 Rushing J,et al.A Coverage Based Ensemble Algorithm(CE- BA)for Streaming Data.In:Proc of the 16th IEEE Intl Conf on Tools with Artificial Intelligence(ICTAI'04),2004.106～112
27 Street W N,Kim Y.A Streaming Ensemble Algorithm(SEA)
for Large-Scale Classification.In:Proc of the Seventh ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining, 2001.377～382
28 Chu F,Wang Y,Zaniolo C.An Adaptive Learning Approach for Noisy Data Streams.In:Proc of the Fourth IEEE Intl Conf on
Data Mining(ICDM'04),2004.351～354
29 Zhu X,Wu X,Yang Y.Dynamic Classifier Selection for Effective Mining from Noisy Data Streams.In:Proc of the Fourth IEEE
Intl Conf on Data Mining,2004.305～312
30 Cormode G,Muthukrishnan S.What's hot and what's not: Tracking most frequent items dynamically.ACM Trans.on Da- tabase Systems,2005,30(1):249～278
(下转第11页)
·5·
ble inversion:[Master's thesis].Massachusetts Institute of Technology,available from https://www.wendangku.net/doc/fe6672234.html,/～cis/cis- theses.html,2003
8 Kuwakado H,Tanaka H.Transitive signature scheme for direct- ed trees.IEICE TransFundamental,2003,E86-A(5):1120～
1126
9 Van Heijst E,Pedersen T P,Pfitzmann B.New constructions of
fail-stop signatures and lower bounds.In:Crypto'92.Berlin: Springer-Verlag,1993,LNCS 740:15～30
10 Zhou S J.Transitive Signatures Based on Non-adaptive Standard Signatures.Cryptography ePrint Archive.Report 2004/044/
11 Zhu H.Model for undirected transitive signatures.IEE Proceed- ings Communications,2004,151(4):312～315
12 Shahandashti S F,Salmasizadeh M,Mohajeri J.A Provably Se- cure Short Transitive Signature Scheme from Bilinear Group Pairs.In:SCN 2004.Berling:Springer-Verlag,2005,LNCS
3352:60～76
13 Bellare M,Neven G.Transitive signatures:New Schemes and Proofs.IEEE Transactions on Information Theory,2005,51(
6):2133～2151
14黄振杰,郝艳华.一个高效的有向传递签名方案.电子学报, 2005,33(8):1497～1501
15 Ma C G,Wu P,Gu G C.A New Method for the Design of State- less Transitive Signature Schemes.In:APWeb Workshops 2006. Berlin:Springer-Verlag,2006,LNCS 3842:897～904
16 Aho A V,Garey M R,Ullman J.The transitive reduction of a directed graph[J].SIAM Journal of Computing,1972,1(2):
131～137
17 Goldwasser S,Micali S,Rivest R.A digital signature scheme se- cure against adaptive chosen-message attacks.SIAM Journal on Computing,1988,17(2):281～308
18 Schnorr C P.Efficient identification and signatures for smart- cards.In:Brassard G.editor.Advances in Cryptology-CRYP-
TO 1989.Berlin:Springer-Verlag,1990,LNCS 435:239～252
19 Bellare M,Namprempre C,Pointcheval D,et al.The one-more- RSA-inversion problems and the security of Chaum's blind signa- ture scheme.Journal of Cryptology,2003,16(3):185～215
20 Bellare M,Rogaway P.Random oracles are practical:A para- digm for designing efficient protocols.In:ACM.editor.Proceed- ings of the First Conference on Computer and Communications Se- curity.Fairfax,1993.62～73
21 Canetti R,Goldreich O,Halevi S.The Random Oracle Method- ology,Revisited.Journal of the ACM,2004,51(4):557～594
22 Cramer R,Shoup V,Signature schemes based on the strong RSA assumption.ACM Transactions on Information and System Secu- rity(ACM TISSEC),2000,3(3):161～185
23 Fischlin M.The Cramer-Shoup Strong-RSA signature scheme re- visited.In:Public Key Cryptography-PKC'03.Berlin:Spring-
er,2003,LNCS 2567:116～129
24 Boldyreva A.Threshold signatures,multisignatures and blind signatures based on the gap-Diffie Hellman-group signature scheme.In:Desmedt Y.editor.Advances in Cryptology-Pub-
lic-Key Cryptography 2003.Berlin:Springer-Verlag,2003,
LNCS 2567:31～46
25 Boneh D,Franklin M.Identity Based Encryption from the Weil Pairing.SIAM Journal of Computing,2001,32(3):586～615
26 Boneh D,Lynn B,Shacham H.Short signatures from the Weil pairing.In:Boyd C.editor.Advances in Cryptology-ASIA-
CRYPT 2001.Berlin:Springer-Verlag,2001,LNCS 2248:514～
532
27 Boneh D,Mironov I,Shoup V.A Secure Signature Scheme from
Bilinear Maps.In:Proceedings of RSA-CT'03,Berlin:Springer- Verlag,2003,LNCS 2612:98～110
28 Goldreich O,Goldwasser S,Micali S.How to construct random functions.Journal of the ACM,1986,33(4):792～807
29 Yi X,Tan C H,Okamoto E.Security of Kuwakado-Tanaka Transitive Signature Scheme for Directed Trees.IEICE Transac- tions on Fundamentals,2004,E87-A(4):955～957
30马春光,杨义先.可转移离线电子现金.计算机学报,2005,28 (3):301～308
31马春光,杨义先,胡正名,等.可直接花费余额的电子支票系统. 电子学报,2005,33(9):1562～1566
(上接第5页)
31 Giannella C,et al.Mining frequent patterns in data streams at multiple time granularities.In:Next Generation Data Mining, 2003.191～212
32 Guha S,et al.Clustering Data Streams.In:Proc of the 41st An- nual Symposium on Foundations of Computer Science,2000.359 ～366
33 Zhang T,Ramakrishnan R,Livny M.BIRCH:An Efficient Data Clustering Method for Very Large Databases.In:Proc of the
1996 ACM SIGMOD Intl Conf on Management of Data,1996. 103～114
34 Park N H,Lee W S.Statistical Grid-Based Clustering over Data Streams.ACM SIGMOD Record,2004,33(1):32～37
35 Lu Y,et al.A Grid-Based Clustering Algorithm for High-Dimen- sional Data Streams.In:Proc of the 1st Intl Conf on Advanced Data Mining and Applications(ADMA),2005.824～831
36 Wang Z,et al.Clustering Data Streams on the Two-Tier Struc- ture.In:Advanced Web Technologies and Applications:6th A-
sia-Pacific Web Conf(APWeb 2004),2004.416～425
37 Ordonez C.Clustering Binary Data Streams with K-Means.In: Proc of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery,2003.12～19
38 Babcock B,et al.Maintaining Variance and k-Medians over Data Stream Windows.In:Proc of the twenty-second ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Sys- tems,2003.234～243
39 Dong G,et al.Online Mining of Changes from Data Streams:Re- search Problems and Preliminary Results.Proc of the 2003 ACM SIGMOD Workshop on Management and Processing of Data Streams.2003
40 Widmer G.Tracking Context Changes through Meta-Learning. Machine Learning,1997,27(3):259～286
41 Widmer G,Kubat M.Learning in the Presence of Concept Drift
and Hidden Contexts.Machine Learning,1996,23(1):69～101
42 Bartlett P L,Ben-David S,Kulkarni S R.Learning Changing Concepts by Exploiting the Structure of Change.Machine Learn- ing,2000,41(2):153～174
43 Harries M,Horn K.Learning Stable Concepts in a Changing World.In:Selected Papers from the Workshop on Reasoning
with Incomplete and Changing Information and on Inducing Com- plex Representations,1996.106～122
44 Gerencser L,Molnar-Saska G.Change detection of Hidden Markov Models.In:43rd IEEE Conf on Decision and Control, 2004.1754～1758
45 Keogh E,Kasetty S.On the Need for Time Series Data Mining Benchmarks:A Survey and Empirical Demonstration.Data Min- ing and Knowledge Discovery,2003,7(4):349～371
46 Yamanishi K,Takeuchi J-I.A Unifying Framework for Detecting Outliers and Change Points from Non-Stationary Time Series Da- ta.In:Proc of the 8th ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining,2002.676～681
47 Fan W.Systematic Data Selection to Mine Concept-Drifting Data Streams.In:Proc of the 10th ACM SIGKDD Intl Conf on Knowledge Discovery and Data Mining,2004.128～137
48 Aggarwal C C.A Framework for Diagnosing Changes in Evolving Data Streams.In:Proc of the 2003 ACM SIGMOD Intl Conf on Management of Data,2003.575～586
49 Batu T,et al.Testing That Distributions are Close.In:Proc of
the 41st Annual Symposium on Foundations of Computer Science, 2000.259～269
50 Kifer D,Ben-David S,Gehrke J.Detecting Change in Data Streams.In:Proc of the 30th VLDB Conf,2004.180～191
51 Wang H,Pei J.A Random Method for Quantifying Changing Distributions in Data Streams.The 9th European Conf on Princi- ples and Practice of Knowledge Discovery in Databases(PKDD). 2005
数据挖掘研究现状综述
数据挖掘 引言 数据挖掘是一门交叉学科，涉及到了机器学习、模式识别、归纳推理、统计学、数据库、高性能计算等多个领域。 所谓的数据挖掘（Data Mining）指的就是从大量的、模糊的、不完全的、随机的数据集合中提取人们感兴趣的知识和信息，提取的对象一般都是人们无法直观的从数据中得出但又有潜在作用的信息。从本质上来说，数据挖掘是在对数据全面了解认识的基础之上进行的一次升华，是对数据的抽象和概括。如果把数据比作矿产资源，那么数据挖掘就是从矿产中提取矿石的过程。与经过数据挖掘之后的数据信息相比，原始的数据信息可以是结构化的，数据库中的数据，也可以是半结构化的，如文本、图像数据。从原始数据中发现知识的方法可以是数学方法也可以是演绎、归纳法。被发现的知识可以用来进行信息管理、查询优化、决策支持等。而数据挖掘是对这一过程的一个综合性应用。
目录 引言 (1) 第一章绪论 (3) 1.1 数据挖掘技术的任务 (3) 1.2 数据挖掘技术的研究现状及发展方向 (3) 第二章数据挖掘理论与相关技术 (5) 2.1数据挖掘的基本流程 (5) 2.2.1 关联规则挖掘 (6) 2.2.2 .Apriori算法：使用候选项集找频繁项集 (7) 2.2.3 .FP-树频集算法 (7) 2.2.4.基于划分的算法 (7) 2.3 聚类分析 (7) 2.3.1 聚类算法的任务 (7) 2.3.3 COBWEB算法 (9) 2.3.4模糊聚类算法 (9) 2.3.5 聚类分析的应用 (10) 第三章数据分析 (11) 第四章结论与心得 (14) 4.1 结果分析 (14) 4.2 问题分析 (14) 4.2.1数据挖掘面临的问题 (14) 4.2.2 实验心得及实验过程中遇到的问题分析 (14) 参考文献 (14)
GIS技术的研究现状及未来发展趋势.
GIS 技术的研究现状及未来发展趋势 摘要:GIS 是随着计算机技术发展而形成的一门新兴技术,其应用程度和范围也随之渗透、延伸,得到了人们的广泛关注。该文综述了地理信.息的发展现状,从多个角度分析当前 GIS 技术发展存在的不足,并在此基础上研究分析了 GIS 技术的未来发展趋势。 关键词:GIS 研究现状发展趋势 0 引言 随着计算机技术的飞速发展、空间技术的日新月异及计算机图形学理论的日渐完善, GIS(Geographic Information System技术也日趋成熟,并且逐渐被人们所认识和接受。近年来, GIS 被世界各国普遍重视,尤其是“数字地球”概念的提出,使其核心技术 GIS 更为各国政府所关注。目前,以管理空间数据见长的 GIS 已经在全球变化与监测、军事、资源管理、城市规划、土地管理、环境研究、农作物估产、灾害预测、交通管理、矿产资源评价、文物保护、湿地制图以及政府部门等许多领域发挥着越来越重要的作用。当前 GIS 正处于急剧发展和变化之中,研究和总结 GIS 技术发展,对进一步开展 GIS 研究工作具有重要的指导意义。因此,本文就目前 GIS 技术的研究现状及未来发展趋势进行总结和分析。 1 GIS 研究现状及其分析 1.1 GIS研究现状 世纪 90年代以来,由于计算机技术的不断突破以及其它相关理论和技术的完善, GIS 在全球得到了迅速的发展。在海量数据存储、处理、表达、显示及数据共享技术等方面都取得了显著的成效,其概括起来有以下几个方面 [1]:①硬件系统采用服务器 /客户机结构,初步形成了网络化、分布式、多媒体 GIS ; ②在 GIS 的设计中, 提出了采用“开放的 CIS 环境” 的概念, 最终以实现资源共享、数据共享为目标; ③高度重视数据标准化与数据质量的问题, 并已形成一些较为可行的数据标准; ④ 面向对象的数据库管理系统已经问世, 正在发展称之为“对象 --关系 DBMS (数据库
文献综述_数据挖掘
数据挖掘简介 数据挖掘的任务 数据挖掘的任务就是从实例集合中找出容易理解的规则和关系。这些规则可以用于预测未来趋势、评价顾客、评估风险或简单地描述和解释给定的数据。通常数据挖掘的任务包括以下几个部分: 数据总结目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或者用直方图、饼图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。数据泛化目前主要有两种技术:多维数据分析方法和面向属性的归纳方法。 多维数据分析方法是一种数据仓库技术，也称作联机分析处理(OLAP，onLineAnalysisProeess)。数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大。因此一种很自然的想法是，把汇集操作结果预先计算并存储起来，以便于决策支持系统使用。存储汇集操作结果的地方称作多维数据库。多维数据分析技术已经在决策支持系统中获得了成功的应用，如著名的SAS数据分析软件包、Businessobject公司的决策支持系统Businessobjeet，以及IBM公司的决策分析工具都使用了多维数据分析技术。 采用多维数据分析方法进行数据总结，它针对的是数据仓库，数据仓库存储的是脱机的历史数据。为了处理联机数据，研究人员提出了一种面向属性的归纳方法。它的思路是，直接对用户感兴趣的数据视图(用一般的SQL查询语言即可获得)进行泛化，而不是像多维数据分析方法那样预先就存储好了泛化数据。方法的提出者对这种数据泛化技术称之为面向属性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关系，它从较高的层次上总结了在低层次上的原始关系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足用户需要的知识，如在泛化关系基础上生成特性规则、判别规则、分类规则，以及关联规则等。数据挖掘的分类 数据挖掘所能发现的知识有如下几种: .广义型知识，反映同类事物共同性质的知识; .特征型知识，反映事物各方面的特征知识; .差异型知识，反映不同事物之间属性差别的知识; .关联型知识，反映事物之间依赖或关联的知识; .预测型知识，根据历史的和当前的数据推测未来数据; .偏离型知识。揭示事物偏离常规的异常现象。 所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。 数据挖掘的方法 数据挖掘并非一个完全自动化的过程。整个过程需要考虑数据的所有因素和其预定的效用，然后应用最佳的数据挖掘方法。数据挖掘的方法很重要。在数据挖掘的领域里.有一点已经被广泛地接受，即不管你选择哪种方法，总存在着某种协定。因此对实际情况，应该具体分析，根据累积的经验和优秀的范例选择最佳的方法。数据挖掘中没有免费的午餐，也没
数据挖掘算法综述
数据挖掘方法综述 [摘要]数据挖掘（DM，DataMining）又被称为数据库知识发现（KDD,Knowledge Discovery in Databases）,它的主要挖掘方法有分类、聚类、关联规则挖掘和序列模式挖掘等。 [关键词]数据挖掘分类聚类关联规则序列模式 1、数据挖掘的基本概念 数据挖掘从技术上说是从大量的、不完全的、有噪声的、模糊的、随机的数据中提取隐含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的过程。这个定义包括好几层含义: 数据源必须是真实的、大量的、含噪声的、发现的是用户感兴趣的知识, 发现的知识要可接受、可理解、可运用, 并不要求发现放之四海皆准的知识, 仅支持特定的发现问题, 数据挖掘技术能从中自动分析数据进行归纳性推理从中发掘出潜在的数据模式或进行预测, 建立新的业务模型帮助决策者调整策略做出正确的决策。数据挖掘是是运用统计学、人工智能、机器学习、数据库技术等方法发现数据的模型和结构、发现有价值的关系或知识的一门交叉学科。数据挖掘的主要方法有分类、聚类和关联规则挖掘等 2、分类 分类（Classification）又称监督学习（Supervised Learning）。监
督学习的定义是：给出一个数据集D，监督学习的目标是产生一个联系属性值集合A和类标（一个类属性值称为一个类标）集合C的分类/预测函数，这个函数可以用于预测新的属性集合（数据实例）的类标。这个函数就被称为分类模型（Classification Model），或者是分类器（Classifier）。分类的主要算法有：决策树算法、规则推理、朴素贝叶斯分类、支持向量机等算法。 决策树算法的核心是Divide-and-Conquer的策略，即采用自顶向下的递归方式构造决策树。在每一步中，决策树评估所有的属性然后选择一个属性把数据分为m个不相交的子集，其中m是被选中的属性的不同值的数目。一棵决策树可以被转化成一个规则集，规则集用来分类。 规则推理算法则直接产生规则集合，规则推理算法的核心是Separate-and-Conquer的策略，它评估所有的属性-值对（条件），然后选择一个。因此，在一步中，Divide-and-Conquer策略产生m条规则，而Separate-and-Conquer策略只产生1条规则，效率比决策树要高得多，但就基本的思想而言，两者是相同的。 朴素贝叶斯分类的基本思想是：分类的任务可以被看作是给定一个测试样例d后估计它的后验概率，即Pr（C=c j︱d），然后我们考察哪个类c j对应概率最大，便将那个类别赋予样例d。构造朴素贝叶斯分类器所需要的概率值可以经过一次扫描数据得到，所以算法相对训练样本的数量是线性的，效率很高，就分类的准确性而言，尽管算法做出了很强的条件独立假设，但经过实际检验证明，分类的效果还是
空间聚类的研究现状及其应用_戴晓燕
空间聚类的研究现状及其应用＊ 戴晓燕1 过仲阳1 李勤奋2 吴健平1 (1华东师范大学教育部地球信息科学实验室 上海 200062) (2上海市地质调查研究院 上海 200072) 摘 要 作为空间数据挖掘的一种重要手段,空间聚类目前已在许多领域得到了应用。文章在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 关键词 空间聚类 K-均值法 散度 1 前言 随着GPS、GI S和遥感技术的应用和发展,大量的与空间有关的数据正在快速增长。然而,尽管数据库技术可以实现对空间数据的输入、编辑、统计分析以及查询处理,但是无法发现隐藏在这些大型数据库中有价值的模式和模型。而空间数据挖掘可以提取空间数据库中隐含的知识、空间关系或其他有意义的模式等[1]。这些模式的挖掘主要包括特征规则、差异规则、关联规则、分类规则及聚类规则等,特别是聚类规则,在空间数据的特征提取中起到了极其重要的作用。 空间聚类是指将数据对象集分组成为由类似的对象组成的簇,这样在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大,即相异度较大。作为一种非监督学习方法,空间聚类不依赖于预先定义的类和带类标号的训练实例。由于空间数据库中包含了大量与空间有关的数据,这些数据来自不同的应用领域。例如,土地利用、居住类型的空间分布、商业区位分布等。因此,根据数据库中的数据,运用空间聚类来提取不同领域的分布特征,是空间数据挖掘的一个重要部分。 空间聚类方法通常可以分为四大类:划分法、层次法、基于密度的方法和基于网格的方法。算法的选择取决于应用目的,例如商业区位分析要求距离总和最小,通常用K-均值法或K-中心点法;而对于栅格数据分析和图像识别,基于密度的算法更合适。此外,算法的速度、聚类质量以及数据的特征,包括数据的维数、噪声的数量等因素都影响到算法的选择[2]。 本文在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。 2 划分法 设在d维空间中,给定n个数据对象的集合D 和参数K,运用划分法进行聚类时,首先将数据对象分成K个簇,使得每个对象对于簇中心或簇分布的偏离总和最小[2]。聚类过程中,通常用相似度函数来计算某个点的偏离。常用的划分方法有K-均值(K-means)法和K-中心(K-medoids)法,但它们仅适合中、小型数据库的情形。为了获取大型数据库中数据的聚类体,人们对上述方法进行了改进,提出了K-原型法(K-prototypes method)、期望最大法EM(Expectation Maximization)、基于随机搜索的方法(ClAR ANS)等。 K-均值法[3]根据簇中数据对象的平均值来计算 ——————————————— ＊基金项目:国家自然科学基金资助。(资助号: 40371080) 收稿日期:2003-7-11 第一作者简介:戴晓燕,女,1979年生,华东师范大学 地理系硕士研究生,主要从事空间数 据挖掘的研究。 · 41 · 2003年第4期 上海地质 Shanghai Geology
大数据时代的空间数据挖掘综述
第37卷第7期测绘与空间地理信息 GEOMATICS ＆SPATIAL INFOＲMATION TECHNOLOGY Vol．37，No．7收稿日期：2014－01－22 作者简介：马宏斌（1982－），男，甘肃天水人，作战环境学专业博士研究生，主要研究方向为地理空间信息服务。 大数据时代的空间数据挖掘综述 马宏斌1 ，王 柯1，马团学 2（1．信息工程大学地理空间信息学院，河南郑州450000；2．空降兵研究所，湖北孝感432000） 摘 要：随着大数据时代的到来，数据挖掘技术再度受到人们关注。本文回顾了传统空间数据挖掘面临的问题， 介绍了国内外研究中利用大数据处理工具和云计算技术，在空间数据的存储、管理和挖掘算法等方面的做法，并指出了该类研究存在的不足。最后，探讨了空间数据挖掘的发展趋势。关键词：大数据；空间数据挖掘；云计算中图分类号：P208 文献标识码：B 文章编号：1672－5867（2014）07－0019－04 Spatial Data Mining Big Data Era Ｒeview MA Hong －bin 1，WANG Ke 1，MA Tuan －xue 2 （1．Geospatial Information Institute ，Information Engineering University ，Zhengzhou 450000，China ； 2．Airborne Institute ，Xiaogan 432000，China ） Abstract ：In the era of Big Data ，more and more researchers begin to show interest in data mining techniques again．The paper review most unresolved problems left by traditional spatial data mining at first．And ，some progress made by researches using Big Data and Cloud Computing technology is introduced．Also ，their drawbacks are mentioned．Finally ，future trend of spatial data mining is dis-cussed． Key words ：big data ；spatial data mining ；cloud computing 0引言 随着地理空间信息技术的飞速发展，获取数据的手 段和途径都得到极大丰富，传感器的精度得到提高和时空覆盖范围得以扩大，数据量也随之激增。用于采集空间数据的可能是雷达、红外、光电、卫星、多光谱仪、数码相机、成像光谱仪、全站仪、天文望远镜、电视摄像、电子 显微镜、CT 成像等各种宏观与微观传感器或设备，也可能是常规的野外测量、人口普查、土地资源调查、地图扫描、 地图数字化、统计图表等空间数据获取手段，还可能是来自计算机、 网络、GPS ，ＲS 和GIS 等技术应用和分析空间数据。特别是近些年来，个人使用的、携带的各种传感器（重力感应器、电子罗盘、三轴陀螺仪、光线距离感应器、温度传感器、红外线传感器等），具备定位功能电子设备的普及，如智能手机、平板电脑、可穿戴设备（GOOGLE GLASS 和智能手表等），使人们在日常生活中产生了大量具有位置信息的数据。随着志愿者地理信息（Volunteer Geographic Information ）的出现，使这些普通民众也加入到了提供数据者的行列。 以上各种获取手段和途径的汇集，就使每天获取的 数据增长量达到GB 级、 TB 级乃至PB 级。如中国遥感卫星地面站现在保存的对地观测卫星数据资料达260TB ，并以每年15TB 的数据量增长。比如2011年退役的Landsat5卫星在其29年的在轨工作期间，平均每年获取8．6万景影像，每天获取67GB 的观测数据。而2012年发射的资源三号（ZY3）卫星，每天的观测数据获取量可以达到10TB 以上。类似的传感器现在已经大量部署在卫 星、 飞机等飞行平台上，未来10年，全球天空、地空间部署的百万计传感器每天获取的观测数据将超过10PB 。这预示着一个时代的到来，那就是大数据时代。大数据具有 “4V ”特性，即数据体量大（Volume ）、数据来源和类型繁多（Variety ）、数据的真实性难以保证（Veracity ）、数据增加和变化的速度快（Velocity ）。对地观测的系统如图1所示。 在这些数据中，与空间位置相关的数据占了绝大多数。传统的空间知识发现的科研模式在大数据情境下已经不再适用，原因是传统的科研模型不具有普适性且支持的数据量受限， 受到数据传输、存储及时效性需求的制约等。为了从存储在分布方式、虚拟化的数据中心获取信息或知识，这就需要利用强有力的数据分析工具来将
数据挖掘课程论文综述
海南大学 数据挖掘论文 题目：股票交易日线数据挖掘 学号：20100602310002 姓名： 专业：10信管 指导老师： 分数：
目录 目录 (2) 1. 数据挖掘目的 (3) 2.相关基础知识 (3) 2.1 股票基础知识 (3) 2.2 数据挖掘基础知识 (4) 2.2.2数据挖掘的任务 (5) 3.数据挖掘方案 (6) 3.1. 数据挖掘软件简介 (6) 3.2. 股票数据选择 (7) 3.3. 待验证的股票规律 (7) 4. 数据挖掘流 (8) 4.1数据挖掘流图 (8) 4.2规律验证 (9) 4.2.2规律2验证 (10) 4.2.3规律三验证 (12) 4.3主要节点说明 (14) 5.小结 (15)
1.数据挖掘目的 数据挖掘的目的就是得出隐藏在数据中的有价值的信息，发现数据之间的内在联系与规律。对于本次数据挖掘来说，其目的就是学会用clementine对股票的历史数据进行挖掘，通过数据的分析，找出存在股票历史数据中的规律，或者验证已存在的股票规律。同时也加深自己对股票知识的了解和对clementine软件的应用能力。为人们决策提供指导性信息，为公司找出其中的客户为公司带来利润的规律，如二八原则、啤酒与尿布的现象等。 2.相关基础知识 2.1 股票基础知识 2.1.1 股票 是一种有价证券，是股份公司在筹集资本时向出资人公开或私下发行的、用以证明出资人的股本身份和权利，并根据持有人所持有的股份数享有权益和承担义务的凭证。股票代表着其持有人（股东）对股份公司的所有权，每一股同类型股票所代表的公司所有权是相等的，即“同股同权”。股票可以公开上市，也可以不上市。在股票市场上，股票也是投资和投机的对象。对股票的某些投机炒作行为，例如无货沽空，可以造成金融市场的动荡。 2.1.2 开盘价 开盘价又称开市价，是指某种证券在证券交易所每个交易日开市后的第一笔买卖成交价格。世界上大多数证券交易所都采用成交额最大原则来确定开盘价。 2.1.3 收盘价 收盘价是指某种证券在证券交易所一天交易活动结束前最后一笔交易的成交价格。如当日没有成交，则采用最近一次的成交价格作为收盘价，因为收盘价是当日行情的标准，又是下一个交易日开盘价的依据，可据以预测未来证券市场行情；所以投资者对行情分析时，一般采用收盘价作为计算依据。
数据挖掘技术及应用综述
作者简介：韩少锋，男，１９８０年生，中北大学在读硕士研究生。研究方向：人工智能技术。 引言 “人类正被信息淹没，却饥渴于知识．”这是１９８２年 趋势大师ＪｏｈｎＮａｉｓｂｉｔｔ的首部著作《大趋势》（Ｍｅｇａ－ｔｒｅｎｄｓ）中提到的。 随着数据库技术的迅速发展，如何从含有海量信息的数据库中提取更有价值、更直观的信息和知识？人们结合统计学﹑数据库﹑机器学习﹑神经网络﹑模式识别﹑模糊数学﹑粗糙集理论等技术，提出‘数据挖掘’这一新的数据处理技术来解决这一难题。数据挖掘（ＤａｔａＭｉｎｉｎｇ）就是从大量的﹑不完全的﹑有噪声的﹑模糊的﹑随机的数据中，提取隐含在其中的﹑人们事先不知道的﹑但又是潜在的有用的信息和知识的过程。这些数据可以是：结构化的，半结构化的，分布在网络上的异构性数据。数据挖掘在许多领域得到了成功的应用，使数据库技术进入了一个更高级的发展阶段，很多专题会议也把数据挖掘和知识发现列为议题之一。 １数据挖掘技术概述 １．１数据挖掘的概念 数据挖掘的概念有多种描述，最常见的有两种：（１）Ｇ．ＰｉａｔｅｔｓｋｙＳｈａｐｉｏｒ，Ｗ．Ｊ．Ｆｒａｗｌｅｙ数据挖掘定义为：从数据库的大量数据中揭示出隐含的、先进而未知的、潜在有用信息的频繁过程。（２）数据挖掘的广义观点：数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程。数据挖掘的特点有：１）用户需要借助数据挖掘技术从大量的信息中找到感兴趣的信息；２）处理的数据量巨大；３）要求对数据的变化做出及时的响应；４）数据挖掘既要发现潜在的规则，也要管理和维护规则，规则的改变随着新数据的不断更新而更新；５）数据挖掘规则的发现基于统计规律，发现的规则不必适用于全部的数据。 数据挖掘要面对的是巨大的信息来源；通过数据挖 掘，有价值的知识、规则或高层次的信息就能从数据库的相关数据集合中抽取出来，并从不同角度显示，从而使大型数据库作为一个丰富可靠的资源为知识归纳服务。 １．２数据挖掘的简史 从数据库中知识发现（ＫＤＤ）一词首先出现在１９８９ 年举行的第十一届国际联合人工智能学术会议上。目前为止，由美国人工智能协会主办的ＫＤＤ国际研讨会已经召开了８次，规模由原来的专题讨论会发展到国际学术大会，研究重点也从发现方法转向系统应用。１９９９年，亚太地区在北京召开的第三届ＰＡＫＤＤ会议收到１５８篇论文，研讨空前热烈。 目前，数据挖掘技术在零售业的购物篮分析﹑金融风险预测﹑产品质量分析﹑通讯及医疗服务﹑基因工程研究等许多领域得到了成功的应用。 １．３数据挖掘的对象 数据挖掘的对象包含大量数据信息的各种类型数 据库。如关系数据库，面向对象数据库等，文本数据数据源，多媒体数据库，空间数据库，时态数据库，以及 Ｉｎｔｅｒｎｅｔ等类型数据或信息集均可作为数据挖掘的对 象。 １．４数据挖掘的工具 许多软件公司和研究机构，根据商业的实际需要 开发出许多数据挖掘工具。例如：有多种数据操控和转换特点的ＳＡＳＥｎｔｅｒｐｒｉｓｅＭｉｎｅｒ；采用决策树、神经网络和聚类技术综合的数据挖掘工具集－ＩＢＭＩｎｔｅｒｌｌｉｇｅｎｔＭｉｎｅｒ；可以提供多种统计分析、 决策树和回归方法，在Ｔｅｒａｄａｔａ数据库管理系统上原地挖掘的Ｔｅｒａｄａｔａ ＷａｒｅｈｏｕｓｅＭｉｎｅｒ；以及同时具有数据管理和数据概括能力，能够用于多种商业平台的ＳＰＳＳＣｌｅｍｅｎｔｉｎｅ。以上 主流数据挖掘工具都能提供常用的挖掘过程和挖掘模 数据挖掘技术及应用综述 韩少锋 陈立潮 （中北大学计算机科学与技术系 山西 太原 ０３００５１） 【摘要】介绍了数据挖掘技术的背景、概念、流程、数据挖掘算法，并阐述了数据挖掘技术的应用现状。 【关键词】数据挖掘 知识发现 人工智能 数据仓库 【中图分类号】ＴＰ３１１．１３８ 【文献标识码】Ｂ 【文章编号】１００３－７７３Ｘ（２００６）０２－００２３－０２ 第２期（总第８９期）机械管理开发 ２００６年４月Ｎｏ．２（ＳＵＭＮｏ．８９）ＭＥＣＨＡＮＩＣＡＬＭＡＮＡＧＥＭＥＮＴＡＮＤＤＥＶＥＬＯＰＭＥＮＴ Ａｐｒ．２００６ ２３??
数据挖掘中的文本挖掘的分类算法综述
数据挖掘中的文本挖掘的分类算法综述 摘要 随着Internet上文档信息的迅猛发展，文本分类成为处理和组织大量文档数据的关键技术。本文首先对数据挖掘进行了概述包括数据挖掘的常用方法、功能以及存在的主要问题；其次对数据挖掘领域较为活跃的文本挖掘的历史演化、研究现状、主要内容、相关技术以及热点难点问题进行了探讨；在第三章先分析了文本分类的现状和相关问题，随后详细介绍了常用的文本分类算法，包括KNN 文本分类算法、特征选择方法、支持向量机文本分类算法和朴素贝叶斯文本分类算法；；第四章对KNN文本分类算法进行深入的研究，包括基于统计和LSA降维的KNN文本分类算法；第五章对数据挖掘、文本挖掘和文本分类的在信息领域以及商业领域的应用做了详细的预测分析；最后对全文工作进行了总结和展望。 关键词：数据挖掘，文本挖掘，文本分类算法 ABSTRACT With the development of Web 2.0, the number of documents on the Internet increases exponentially. One important research focus on how to deal with these great capacity of online documents. Text classification is one crucial part of information management. In this paper we first introduce the basic information of data mining, including the methods, contents and the main existing problems in data mining fields; then we discussed the text mining, one active field of data mining, to provide a basic foundation for text classification. And several common algorithms are analyzed in Chapter 3. In chapter 4 thorough research of KNN text classification algorithms are illustrated including the statistical and dimension reduction based on LSA and in chapter 5 we make some predictions for data mining, text mining and text classification and finally we conclude our work. KEYWORDS： data mining, text mining, text classification algorithms，KNN 目录 摘要 (1) ABSTRACT (1) 目录 (1)
数据挖掘中的软计算方法及应用综述
摘要文章对数据挖掘中软计算方法及应用作了综述。对模糊逻辑、遗传算法、神经网络、粗集等软计算方法，以及它们的混合算法的特点进行了分析，并对它们在数据挖掘中的应用进行了分类。 关键词数据挖掘；软计算；模糊逻辑；遗传算法；神经网络；粗集 1 引言 在过去的数十年中，随着计算机软件和硬件的发展，我们产生和收集数据的能力已经迅速提高。许多领域的大量数据集中或分布的存储在数据库中[1][2]，这些领域包括商业、金融投资业、生产制造业、医疗卫生、科学研究，以及全球信息系统的万维网。数据存储量的增长速度是惊人的。大量的、未加工的数据很难直接产生效益。这些数据的真正价值在于从中找出有用的信息以供决策支持。在许多领域，数据分析都采用传统的手工处理方法。一些分析软件在统计技术的帮助下可将数据汇总，并生成报表。随着数据量和多维数据的进一步增加，高达109的数据库和103的多维数据库已越来越普遍。没有强有力的工具，理解它们已经远远超出了人的能力。所有这些显示我们需要智能的数据分析工具，从大量的数据中发现有用的知识。数据挖掘技术应运而生。 数据挖掘就是指从数据库中发现知识的过程。包括存储和处理数据，选择处理大量数据集的算法、解释结果、使结果可视化。整个过程中支持人机交互的模式[3]。数据挖掘从许多交叉学科中得到发展，并有很好的前景。这些学科包括数据库技术、机器学习、人工智能、模式识别、统计学、模糊推理、专家系统、数据可视化、空间数据分析和高性能计算等。数据挖掘综合以上领域的理论、算法和方法，已成功应用在超市、金融、银行[4]、生产企业 [5]和电信，并有很好的表现。 软计算是能够处理现实环境中一种或多种复杂信息的方法集合。软计算的指导原则是开发利用那些不精确性、不确定性和部分真实数据的容忍技术，以获得易处理、鲁棒性好、低求解成本和更好地与实际融合的性能。通常，软计算试图寻找对精确的或不精确表述问题的近似解[6]。它是创建计算智能系统的有效工具。软计算包括模糊集、神经网络、遗传算法和粗集理论。 2 数据挖掘中的软计算方法 目前，已有多种软计算方法被应用于数据挖掘系统中，来处理一些具有挑战性的问题。软计算方法主要包括模糊逻辑、神经网络、遗传算法和粗糙集等。这些方法各具优势，它们是互补的而非竞争的，与传统的数据分析技术相比，它能使系统更加智能化，有更好的可理解性，且成本更低。下面主要对各种软计算方法及其混合算法做系统性的阐述，并着重强调它们在数据挖掘中的应用情况。 2.1 模糊逻辑 模糊逻辑是1965年由泽德引入的，它为处理不确定和不精确的问题提供了一种数学工具。模糊逻辑是最早、应用最广泛的软计算方法，模糊集技术在数据挖掘领域也占有重要地位。从数据库中挖掘知识主要考虑的是发现有兴趣的模式并以简洁、可理解的方式描述出来。模糊集可以对系统中的数据进行约简和过滤，提供了在高抽象层处理的便利。同时，数据挖掘中的数据分析经常面对多种类型的数据，即符号数据和数字数据。nauck[7]研究了新的算法，可以从同时包含符号数据和数字数据中生成混合模糊规则。数据挖掘中模糊逻辑主要应用于以下几个方面： （1）聚类。将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。聚类分析是一种重要的人类行为，通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的关系。模糊集有很强的搜索能力，它对发现的结构感兴趣，这会帮助发现定性或半定性数据的依赖度。在数据挖掘中，这种能力可以帮助
文本数据挖掘综述
文本数据挖掘综述 陈光磊 （专业:模式识别与智能系统） 摘要:作为从浩瀚的信息资源中发现潜在的、有价值知识的一种有效技术，文本挖掘已悄然兴起，倍受关注。目前,文本挖掘的研究正处于发展阶段，尚无统一的结论，需要国内外学者在理论上开展更多的讨论。本文首先引出文本挖掘出现的缘由,再对文本挖掘的的概念、组成及其具体实现过程。着重分析了文本挖掘的预处理、工作流程与关键技术。 关键词: web挖掘，文本挖掘 1引言 面对今天浩如烟海的文本信息，如何帮助人们有效地收集和选择所感兴趣的信息，如何帮助用户在日益增多的信息中自动发现新的概念，并自动分析它们之间的关系，使之能够真正做到信息处理的自动化，这已经成为信息技术领域的热点问题。 有数据表明，一个组织80%的信息是以文本的形式存放的，包括WEB页面、技术文档、电子邮件等。由于整个文本集合不能被方便地阅读和分析，而且由于文本经常改变，要跟上变化的节奏，就要不停地回顾文本的内容，处理数量巨大的文本变得越来越来困难。人们迫切需要能够从大量文本集合中快速、有效地发现资源和知识的工具。在这样的需求驱动下，文本挖掘的概念产生了。 2文本挖掘的概述 2.1文本挖掘的定义 文本挖掘是抽取有效、新颖、有用、可理解的、散布在文本文件中的有价值知识，并且利用这些知识更好地组织信息的过程。1998年底，国家重点研究发展规划首批实施项目中明确指出，文本挖掘是“图像、语言、自然语言理解与知识挖掘”中的重要内容。
文本挖掘是数据挖掘的一个研究分支，用于基于文本信息的知识发现。文本挖掘利用智能算法，如神经网络、基于案例的推理、可能性推理等，并结合文字处理技术，分析大量的非结构化文本源（如文档、电子表格、客户电子邮件、问题查询、网页等），抽取或标记关键字概念、文字间的关系，并按照内容对文档进行分类，获取有用的知识和信息。 文本挖掘是一个多学科混杂的领域，涵盖了多种技术，包括数据挖掘技术、信息抽取、信息检索，机器学习、自然语言处理、计算语言学、统计数据分析、线性几何、概率理论甚至还有图论。 文本挖掘(Text Mining)是一个从非结构化文本信息中获取用户感兴趣或者有用的模式的过程，文本挖掘涵盖多种技术,包括信息抽取,信息检索,自然语言处理和数据挖掘技术。它的主要用途是从原本未经使用的文本中提取出未知的知识，但是文本挖掘也是一项非常困难的工作,因为它必须处理那些本来就模糊而且非结构化的文本数据,所以它是一个多学科混杂的领域,涵盖了信息技术、文本分析、模式识别、统计学、数据可视化、数据库技术、机器学习以及数据挖掘等技术。 2.2文本挖掘的组成 文本挖掘可以通过下图有个大致理解。它由三部分组成：底层是文本挖掘的基础领域，包括机器学习、数理统计、自然语言处理；在此基础上是文本挖掘的基本技术，有五大类，包括文本信息抽取、文本分类、文本聚类、文本数据压缩、文本数据处理；在基本技术之上是两个主要应用领域，包括信息访问和知识发现，信息访问包括信息检索、信息浏览、信息过滤、信息报告，知识发现包括数据分析、数据预测。如图2.1。
数据挖掘分类算法研究综述终板
数据挖掘分类算法研究综述 程建华 (九江学院信息科学学院软件教研室九江332005 ) 摘要：随着数据库应用的不断深化,数据库的规模急剧膨胀,数据挖掘已成为当今研究的热点。特别是其中的分类问题,由于其使用的广泛性,现已引起了越来越多的关注。对数据挖掘中的核心技术分类算法的内容及其研究现状进行综述。认为分类算法大体可分为传统分类算法和基于软计算的分类法两类。通过论述以上算法优缺点和应用范围，研究者对已有算法的改进有所了解，以便在应用中选择相应的分类算法。 关键词：数据挖掘；分类；软计算；算法 1引言 1989年8月，在第11届国际人工智能联合会议的专题研讨会上，首次提出基于数据库的知识发现(KDD，Knowledge DiscoveryDatabase)技术[1]。该技术涉及机器学习、模式识别、统计学、智能数据库、知识获取、专家系统、数据可视化和高性能计算等领域，技术难度较大，一时难以应付信息爆炸的实际需求。到了1995年，在美国计算机年会(ACM)上，提出了数据挖掘[2](DM，Data Mining)的概念，由于数据挖掘是KDD过程中最为关键的步骤，在实践应用中对数据挖掘和KDD这2个术语往往不加以区分。 基于人工智能和信息系统，抽象层次上的分类是推理、学习、决策的关键，是一种基础知识。因而数据分类技术可视为数据挖掘中的基础和核心技术。其实，该技术在很多数据挖掘中被广泛使用，比如关联规则挖掘和时间序列挖掘等。因此，在数据挖掘技术的研究中，分类技术的研究应当处在首要和优先的地位。目前，数据分类技术主要分为基于传统技术和基于软计算技术两种。 2传统的数据挖掘分类方法 分类技术针对数据集构造分类器，从而对未知类别样本赋予类别标签。在其学习过程中和无监督的聚类相比，一般而言，分类技术假定存在具备环境知识和输入输出样本集知识的老师，但环境及其特性、模型参数等却是未知的。 2.1判定树的归纳分类 判定树是一个类似流程图的树结构，其中每个内部节点表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点代表类或类分布。树的最顶层节点是根节点。由判定树可以很容易得到“IFTHEN”形式的分类规则。方法是沿着由根节点到树叶节点的路径，路径上的每个属性-值对形成“IF”部分的一个合取项，树叶节点包含类预测，形成“THEN”部分。一条路径创建一个规则。 判定树归纳的基本算法是贪心算法，它是自顶向下递归的各个击破方式构造判定树。其中一种著名的判定树归纳算法是建立在推理系统和概念学习系统基础上的ID3算法。 2.2贝叶斯分类 贝叶斯分类是统计学的分类方法，基于贝叶斯公式即后验概率公式。朴素贝叶斯分类的分类过程是首先令每个数据样本用一个N维特征向量X={X1，X2，?X n}表示，其中X k是属性A k的值。所有的样本分为m类：C1，C2，?，C n。对于一个类别的标记未知的数据记录而言，若P(C i/X)>P(C j/X)，1≤ j≤m，j≠i，也就是说，如果条件X下，数据记录属于C i类的概率大于属于其他类的概率的话，贝叶斯分类将把这条记录归类为C i类。 建立贝叶斯信念网络可以被分为两个阶段。第一阶段网络拓扑学习，即有向非循环图的——————————————————— 作者简介：程建华（1982-），女，汉族，江西九江，研究生，主要研究方向为数据挖掘、信息安全。
基于matlab的数据挖掘技术研究【文献综述】
毕业论文文献综述 信息与计算科学 基于matlab的数据挖掘技术研究 数据挖掘是用于大规模数据处理的一种新的思维方式和技术手段，他是在现实生活中各种数据量呈指数级不断增长，以及以数据库(database)技术为核心的信息技术逐渐成熟的背景下产生的。数据挖掘可以帮助用户发现影藏在大型数据库中的规律和模式，它融合了人工智能(artificial intelligence)、统计（statistics）、机器学习（nachine learning）、模式识别（pattern recognition）和数据库等多种学科的理论、方法与技术，已经在商业、企业、政府、科研及体育等多种不同类型的组织机构和领域中获得了非常广泛的应用。即使在日常生活中，数据挖掘技术也已经潜移默化地参与到人们的生活质量改善过程中。 数据挖掘有很多种技术和计算方法，包括决策树方法（decision tree）、人工神经网络方法（artificial neural metwork，ANN）、聚类分析、模糊集合方法、遗传算法（genetic algorithm）、模拟退火算法(simulated annealing,SA)、进化式程序设计(evolutionary programming)等。这里主要介绍一下聚类分析、遗传算法和人工神经网络算法。 聚类分析也称无监督学习，或无教师学习，或无指导学习，因为和分类学习相比，聚类的样本没有标记，需要由聚类学习算法来自动确定。聚类分析是研究如何在没有训练的条件下把样本划分为若干。聚类（clustering）是对物理的或抽象的样本集合分组的过程。聚类分析有很多种目标，但都涉及把一个样本集合分组或分割为子集或簇（cluster）。从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。聚类分析主要针对的数据类型包括区间标度变量、二值变量、标称变量、序数型变量、比例标度型变量以及由这些变量类型构成的复合类型。聚类算法应具有以下几个特点：1处理不同字段类型的能力；2可伸缩性；3处理高维数据的能力；4发现具有任意簇的形状的族类能力；5能够处理异常数据；6对数据顺序的不敏感性；7输入参数对领域知识的弱依赖性；8聚类结果的可解释性和实用性；9增加限制条件后的聚类分析能力。 基因算法起源于对生物系统进行的计算机模拟研究，是一种受生物进化启发，使用计算机模拟生物进化的学习方法。基因算法是模拟生物进化过程的计算模型，是自然遗传学与计算机科学互相结合、互相渗透而形成的新的计算方法。基因算法的最大优点是问题求解与初始条件无关，搜索最优解的能力极强。从数学的角度看，基因算法是一种概率型搜索算法：从工程学角度看，它是一种自适应的迭代寻优过程。基因算法需要完成两种数据转换，算法实施之前进行从表现型到基因型的转换，即将搜索空间中的参数或可行解转化成遗传空间中的染色体或个体，完成编码操作；在算法
数据挖掘中的聚类算法综述
收稿日期:2006201204;修返日期:2006203219基金项目:国家自然科学基金资助项目(60473117) 数据挖掘中的聚类算法综述 3 贺 玲,吴玲达,蔡益朝 (国防科学技术大学信息系统与管理学院,湖南长沙410073) 摘 要:聚类是数据挖掘中用来发现数据分布和隐含模式的一项重要技术。全面总结了数据挖掘中聚类算法的研究现状,分析比较了它们的性能差异和各自存在的优点及问题,并结合多媒体领域的应用需求指出了其今后的发展趋势。 关键词:数据挖掘;聚类;聚类算法 中图法分类号:TP391 文献标识码:A 文章编号:100123695(2007)0120010204 Survey of Clustering A lgorith m s in Data M ining HE L ing,WU L ing 2da,CA I Yi 2chao (College of Infor m ation Syste m &M anage m ent,N ational U niversity of D efense Technology,Changsha Hunan 410073,China ) Abstract:Clustering is an i m portant technique in Data M ining (DM )f or the discovery of data distributi on and latent data pattern .This paper p r ovides a detailed survey of current clustering algorith m s in DM at first,then it makes a comparis on a mong the m,illustrates the merits existing in the m,and identifies the p r oblem s t o be s olved and the ne w directi ons in the fu 2ture according t o the app licati on require ments in multi m edia domain .Key works:Data M ining;Clustering;Clustering A lgorith m 1 引言 随着信息技术和计算机技术的迅猛发展,人们面临着越来越多的文本、图像、视频以及音频数据,为帮助用户从这些大量数据中分析出其间所蕴涵的有价值的知识,数据挖掘(Data M ining,DM )技术应运而生。所谓数据挖掘,就是从大量无序 的数据中发现隐含的、有效的、有价值的、可理解的模式,进而发现有用的知识,并得出时间的趋向和关联,为用户提供问题求解层次的决策支持能力。与此同时,聚类作为数据挖掘的主要方法之一,也越来越引起人们的关注。 本文比较了数据挖掘中现有聚类算法的性能,分析了它们各自的优缺点并指出了其今后的发展趋势。 2 DM 中现有的聚类算法 聚类是一种常见的数据分析工具,其目的是把大量数据点的集合分成若干类,使得每个类中的数据之间最大程度地相似,而不同类中的数据最大程度地不同。在多媒体信息检索及数据挖掘的过程中,聚类处理对于建立高效的数据库索引、实现快速准确的信息检索具有重要的理论和现实意义。 本文以聚类算法所采用的基本思想为依据将它们分为五类,即层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法以及用于高维数据的聚类算法,如图1所示。 聚类 层次聚类算法 聚合聚类:Single 2L ink,Comp lete 2L ink,Average 2L ink 分解聚类 分割聚类算法基于密度的聚类基于网格的聚类 基于图论的聚类 基于平方误差的迭代重分配聚类:概率聚类、最近邻 聚类、K 2medoids 、K 2means 基于约束的聚类算法 机器学习中的聚类算法 人工神经网络方法 基于进化理论的方法:模拟退火、遗传算法用于高维数据的聚类算法 子空间聚类 联合聚类 图1 聚类算法分类示意图 211 层次聚类算法 层次聚类算法通过将数据组织成若干组并形成一个相应的树状图来进行聚类,它又可以分为两类,即自底向上的聚合层次聚类和自顶向下的分解层次聚类。聚合聚类的策略是先将每个对象各自作为一个原子聚类,然后对这些原子聚类逐层进行聚合,直至满足一定的终止条件;后者则与前者相反,它先将所有的对象都看成一个聚类,然后将其不断分解直至满足终止条件。 对于聚合聚类算法来讲,根据度量两个子类的相似度时所依据的距离不同,又可将其分为基于Single 2L ink,Comp lete 2L ink 和Average 2L ink 的聚合聚类。Single 2L ink 在这三者中应用最为广泛,它根据两个聚类中相隔最近的两个点之间的距离来评价这两个类之间的相似程度,而后两者则分别依据两类中数据点之间的最远距离和平均距离来进行相似度评价。 CURE,ROCK 和CHAME LE ON 算法是聚合聚类中最具代 表性的三个方法。 Guha 等人在1998年提出了C URE 算法 [1] 。该方法不用 单个中心或对象来代表一个聚类,而是选择数据空间中固定数目的、具有代表性的一些点共同来代表相应的类,这样就可以