V ol.15, No.1 ?2004 Journal of Software 软 件 学 报 1000-9825/2004/15(01)0000 时序数据上的数据挖掘
? 黄书剑1+
1(南京大学 计算机科学与技术系 江苏 南京 210093)
Data Mining on Time-series Data
HUANG Shu-Jian 1+
1(Department of Computer Science and technology, Nanjing University, Nanjing 210093, China)
+ Corresponding author: Phn +86-**-****-****, Fax +86-**-****-****, E-mail: ****, http://****
Abstract : Data mining has been developing rapidly in the recent years. Since time related data occurs frequently in various areas, there has been “an explosion” of interest in mining time-series data, which is a popular branch of data mining. In this paper we present an overview of the major research areas and tasks in mining time-series data, such as preprocessing, representation, segmentation, similarity, classification, clustering, anomaly detection, rule discovery, etc. Some solutions of several tasks are also included in this paper.
Key words : data mining; time-series
摘 要: 近年来数据挖掘得到了蓬勃的发展。由于越来越多的数据都与时间有着密切的关系，时序数据的挖掘作为数据挖掘的一个分支，正在受到越来越高的重视。本文概述了时序数据上的数据挖掘这个领域内的主要研究方向和课题，包括数据预处理、数据表示、分割、相似度度量、分类、聚类、异常检测、规则识别等。并对部分课题的主要解决方案进行了一些介绍。
关键词: 数据挖掘;时序数据挖掘
中图法分类号: **** 文献标识码: A
1 引言
近几十年来，计算机运算存储能力不断提高，数据产生和采集的速度也越来越快，因而数据量越来越大；而与此同时，人们面对巨量数据，能够直接获得的信息量却越来越有限。单纯的人力已经很难胜任对这样巨量的数据进行分析并提取出相关信息的任务。为了解决这种数据与信息之间的矛盾，数据挖掘应运而生。所谓数据挖掘，即从巨量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程[1]。数据挖掘的目的就在于找出巨量数据中的潜在规律，以对未来的分析和决策提供支持，其在分析处理中的优势以
? Supported by the **** Foundation of China under Grant No.****, **** (基金中文完整名称); the **** Foundation of China
under Grant No.****, **** (基金中文完整名称)
作者简介: 黄书剑(1984),男,江苏盐城人,硕士生,主要研究领域为自然语言处理.
2 Journal of Software软件学报 2004,15(1)
及结论的正确性、有效性已经被越来越多的实践所证明。数据挖掘可以处理各种各样形式的数据，包括关系数据库、数据仓库、事务数据库中的数据，面向对象数据库、对象关系数据库以及空间数据库、时序数据库、文本数据库和多媒体数据库等面向应用的专用数据库中的数据，以及普通文本，互联网中的数据在内的各种数据都可以作为数据挖掘的对象[2]。本文着重讨论与时序数据的数据挖掘相关的一些内容。
简单的说，时序数据就是和时间相关的数据。在数据挖掘的实际应用中，很多的数据都是与时间相关的，比如股票市场的交易数据，传感器网络收集到的状态数据，商店的消费统计数据，电话通信量统计数据等等。这些数据中往往都蕴含着一些跟时间相关的现象甚至规律。研究这些数据对分析问题的现状(如分析股票交易情况、发现异常交易，总结顾客消费规律等)，以及预测问题将来的发展(如销售决策，传感器分布调整等)，都有很大的帮助[3][4][5]。时序数据的数据挖掘就是对这些与时间相关的数据进行分析并从中获取相关的信息的过程[4][6]。
本文的后续部分组织如下：第二部分是对时序数据挖掘的目的和过程的进一步介绍；第三部分主要介绍了时序数据挖掘中的主要研究方向和课题，并对部分课题的解决方案及算法进行了一些介绍；第四部分是对时序数据挖掘的一个简单讨论；第五部分是本文的总结。
2 时序数据挖掘概述
2.1 时序数据挖掘的概念
时序数据广义上是指所有与时间相关，或者说含有时间信息的数据。但在具体的应用中，时序数据往往是指用数字或符号表示的时间序列[6]，但有的时候特指由连续的实值数据元素组成的序列[4]。当然连续的实值数据元素在实际处理时可以通过一定的离散化手段，转换成离散的值数据再进行处理。在大部分情况下，时序数据一般都以时间为基准呈序列状排列，因而，对时序数据的挖掘也可以看作一种比较特殊的序列数据挖掘(Sequence Data Mining)。
2.2 时序数据挖掘的目的
时序数据是随着时间连续变化的数据，因而其反映的大都是某个待观察过程在一定时期内的状态或表现。其研究的目的主要是以下两个方面：其一是学习待观察过程过去的行为特征，比如顾客的消费习惯等；其二是预测未来该过程的可能状态或表现，比如顾客是否会在短时间内进行大规模购物等。这两个目的直接带来了时序数据挖掘中的一个重要的问题：查找相似的行为模式(Rule Discovery)。另一个相关的问题就是异常活动检测(Outlier Detection or Anomaly Detection)。关于这两个问题的详细阐述请参见第三部分。
3 时序数据挖掘中的主要课题
时序数据挖掘中的课题，涉及从处理初始数据开始，到通过各种方法分析数据，直至得到所需要的信息的整个过程。本部分以下内容将介绍时序数据挖掘中的如下几个主要任务：数据预处理(Preprocessing)，时序数据表示(Time-series Representation)，分割(Segmentation)，相似度度量(Similarity)，分类(Classification)，聚类(Clustering)，异常检测(Anomaly detection)，规则识别(Rule Discovery)等。其他一些时序数据挖掘中的任务，如文献[6][7][8]中提到的：子序列匹配(subsequence matching)，内容查询(retrieval by content)等，限于篇幅，本文不作介绍。
3.1 数据预处理
数据预处理泛指对得到的原始数据进行一定的加工处理，使之能够为其他数据挖掘方法所用的过程。和其他类型的数据挖掘一样，时序数据在进行处理前往往要先进行一些数据预处理，例如去除噪音，填补缺失数值等。去除噪音可以在数域或频域上采用一定的阈值过滤来完成，而缺失数值则通常可以采用插值的方法进行估计和填补。这些操作的目的就在于保证数据的可靠性和完整性，在进行进一步分析时，不会因为一些明显不合理的噪音而影响整体结果，也不会因为存在数值确实而影响一些学习方法的正常执行。
作者名等:题目 3
数据预处理要涉及的另一个可能的任务就是重新采样(Re-sampling)。一些研究工作中，并不把时序数据中的时间信息作为主要的研究对象，而是仅要求这些数据按照时间序排列，甚至有的时候要求按照等时间间隔排列，这就涉及到在原数据基础上进行重新采样的问题。
3.2 时序数据表示
对时序数据采取有别于原来实值序列的表示方法的原因是：希望能新的表示形式能更好、更简洁的表达出原有数据的主要性质。
有些情况下，研究者会采取特征(feature)的形式来描述时序数据，这就牵涉到特征提取(Feature Extraction)的问题，同时，对于特征数量较为庞大的时候，往往还会通过一些方法来进行维数约简，来提高特征表达能力，并减少特征数量。常用的方法有奇异值分解(Singular Value Decomposition SVD)、离散傅立叶变换(Discrete Fourier Transform DFT)、离散小波变换(Discrete Wavelet Transform DWT)。Keogh等人提出了一种称为
Piece-wise Aggregate Approximation(PAA)的方法，是一种基于对时序数据进行等距离分割，并在分割内求均值的降维方法，取得了一定的效果[8]。
常见的时序数据表示分为如下几类：Model-Based Representation、Non-Data-adaptive Representation、Data-adaptive Representation以及Data-dictated Representation.
3.2.1 Model-Based Representation
基于模型的数据表示假设时序数据是由某个模型生成的。模型被用来与数据拟和，并计算出相应的模型参数，这些参数也会在之后的数据挖掘过程中起到重要的作用。常用的模型有隐马尔科夫模型(Hidden Markov Model HMM)[9][10]、ARMA(Auto Regressive Moving Average)等。
3.2.2 Non-Data-adaptive Representation
Non-Data-adaptive Representation是指用和数据独立的转换方法和系数选择，把时序数据转换到一个不同的空间之中表示的方法[8]。这一工作在很大程度上是为了对数据的进行进一步的降维，在本节开头中提到的几种降维方法如DFT、DWT、PAA等都是基于相应的non-data-adaptive representation的。此外，文献[11][12]中还使用了一种称为的随机投影(Random projection)的方法进行了时序数据的表示。
3.2.3 Data-adaptive Representation
Data-adaptive的方法依赖于一个时间序列或者多个时间序列的整体的时序数据进行系数的选择。在3.2.2中的提到的几种方法中有一些(如DFT)只需在选取系数时取局部或全局的最大项，而不是某一个固定的项(如第一项)，就可以将结果看作Data-adaptive的表示形式。相应的PAA等方法也有对应的Data-adaptive的形式，此外还有许多不同的方法如基于奇异值分解的方法，Symbolic Aggregate Approximation(SAX)方法，Piecewise Linear Approximation(PLA)方法等，都有各自的特点和优势。
总的来说依赖于数据的表示方法在一定程度上保留了数据中比较显著的部分特征为后续分析所用，直觉上可以对整个系统的性能有较大帮助，因而受到了较为广泛的关注。
3.2.4 Data-dictated Representation
Data-dictated实际上可以看作是数据离散化的过程。在这种表示形式中，数据的表示粒度和表示结果的大小是自动决定的。数据离散化的方法很多，文献[13][14]中描述了一种基于两维规则网格的方法，将数据按照规则网格划分的bins存放，最后用bins来代替具体的数值实现离散化。文献[15][16]则分别是采用中间值和平均值作为阈值进行clipping的方法。
3.3 时序数据分割
时序数据的分割大体上有三种类型：滑动窗口、自顶向下、自底向上。目前流行的各种方法虽然名称各异，实现也各不相同，但基本上都可以包含在这三类中[17]。
滑动窗口模型指分割以循环的方式进行，每次处理一个没有被最新分割包含的数据，分割不断的增长知道超出某个界限而停止。滑动窗口模型的效果通常跟数据集合本身有很大的关系，而且滑动窗口的大小选择也是一个比较难确定的问题。自顶向下的模型中，数据不断的按照某种规则被划分，直到满足一定的停止条
4 Journal of Software软件学报 2004,15(1)
件。在自底向上模型中，将最底层的数据作为原始分割，然后不断的合并小的分割直到满足一定的停止条件为止。光从时间性能上比较通常自底向下的方法要好于自顶向下的方法[8]。Himberg等人在实践中采用了一种贪婪算法来改进其他方法产生的分割，也取得了不错的效果[18]。
以上所提到的三种方法都需要人为的提供参数或者停止条件等信息，而这些信息往往都是难以用经验描述的。因此，一些基于统计的方法也逐渐开始发展，一些方法通过比较k个分类和k-1个分类的好坏来自动的确定分类的个数，也有一些通过建立某个符合数据的随机过程模型的方法来完成分割过程。对此本文不作进一步阐述。
3.4 相似度度量
相似度和距离是相对的两个概念，是用来衡量两个(通常是两个，也有可能是多个)数据或实例之间关系的标准。在一定意义上，相似度和距离的表示能力是等价的，他们分别适用于一定的环境，也可以通过一定的方法互相转换。相似度度量问题是数据挖掘中的一个重要问题，是整个数据挖掘过程中的许多其他工作(比如聚类问题等)的基础，相似度度量的好坏对这些问题的解决有着非常大的影响。
以数值时间序列(numeric time-series)为例，相似度的度量可以分为如下几类：基于形状的(Shape-based)相似度、基于特征的(Feature-based)相似度、基于模型的(Model-based)相似度、基于数据压缩的(Compression-based)相似度[8]。
3.4.1 基于形状的相似度
欧式距离(Euclidean distance)是对于数值的时间序列而言最简单却应用最广泛的基于形状的距离。此外Manhattan的p=1和Maximum的p=∞时的Lp范式也是常用的距离度量。但是，直接使用这种度量也有一些共同的缺点，这些距离在对数据进行缩放或转换时容易受到影响，而且距离受噪声、特殊值以及数据是否归一化的影响也较大。因此人们开始寻找适当的转换使得这些Lp距离能够在以上这些变化发生时保持不变，对于不同的应用来说，找到一个有意义的转换方式也是一个很重要的课题[8]。
跟Lp距离相关的有另外两个距离定义：Correlation和Cosine distance。Correlation的定义是基于衡量线性相关性的Pearson correlation系数，要求时间序列都是独立的，而且所有的时间点是符合同一个概率分布的独立样本。Cosine distance则将不同的时间序列描述为多维空间中的向量，并用他们之间的夹角来表示距离。
对于大量的长度不一的时序数据，基于形状的相似度度量效果往往不好，这时，就得考虑基于特征或者基于模型的相似度。
3.4.2 基于特征的相似度
抽取特征并比较特征集合的相似度计算方法和具体的应用领域有很大的关系。对于一些具有某些重要特征的时序数据，选取合适的特征来表示可以收到很好的效果。除了人工抽取比较重要的特征以外，也可以像上文3.2.3节中提到一样，取DFT或者DWT后得到的最大的系数作为特征，用来表示整个数据。文献[19]中提到了一种通过对时间点加上偏向最近时间的权重，从而自动选取独立于数据的系数作为特征的方法。从整体来说，目前，基于特征的相似度度量还是一个有很强的领域相关性，需要较多人为干预的过程。
3.4.3 基于模型的相似度
与基于特征的相似度相比，基于模型的相似度有一个很大的优势，那就是基于模型来计算相似度可以将预先得到的关于数据产生的知识结合进来。通常计算相似度时，对每一个时间序列建模，并用对某个序列所建模型生成另一序列的概率值来衡量这两个序列间的相似度。常用的模型有上文提到过的HMM，AMRA等，近年来对这些模型本身及使用方法的研究和改进也是一个重要的研究课题。
基于模型的方法往往需要较长的时间序列来完成较好的参数估计，对于较短的、采样不规则的时间序列，文献[20][21]提供了一种将形状和模型相结合的方法。文献[22]则描述了一种将形状和特征相结合的相似度度量方法。这些混合模型的方法在某些应用中会收到意想不到的效果。
3.4.4 基于压缩的相似度
基于压缩的时序数据相似度来自于生物信息学和计算理论研究的一些结果，是一个较新的想法[8]。
作者名等:题目 5
Compression-Based Dissimilarity Measure (CDM)的基本思想认为对相似数据的连接和压缩，应该得到比在相差较大的数据上做同样操作更高的压缩比率。Kolmogorov复杂度是指生成所得数据的最短程序长度。基于条件Kolmogorov 复杂度，Keogh等人定义了CDM，并说明了其在聚类、分类、异常检测等工作上的优越性能[23]。
3.4.5 符号时序数据(symbolic time-series)的相似度
对于符号时序数据，可以直接通过对符号序列的比较来计算两个时间序列的距离，被称为Proximity-based method。较典型的例子是计算编辑距离(edit distance)的方法，定义两个时间序列的距离为将其中一个转换为另一个所需要的最少转换数。
此外对符号时序数据也可以使用上文所提到的基于特征、基于模型或者基于压缩的方法，只是根据方法类型不同需要在符号数据和数值数据之间做一些转换。
3.5 分类问题
分类就是根据某个训练好的模型给数据选择某种已知类型标记的过程。按照处理的对象不同，时间序列的分类问题有两种，一种是对整个时间序列的分类问题，由一组时间序列训练一个分类器来标注新的时间序列，其中每个序列只有单独的一个标记。另一种分类问题是对时间序列中的时间点进行分类，训练集合中每一个时间序列的每一个时间点都一个标记，训练成的分类器会对新到的序列数据中的每一个时间点进行分类[8]。
3.5.1 时间序列的分类问题
常见的时间序列的分类问题大都由提取时间序列特征加上某个机器学习的分类算法组成。特征提取的方法可以参见上文3.2时序数据的表示一节，常用的分类算法则范围较为广泛，由经典的C4.5决策树算法到近几年较为流行的支持向量机(Support Vector Machine SVM)的方法都可以应用到该问题中。
以往大部分的分类方法都将特征的选择提取与统计学习的方法分开处理，近年来，将时序结构与学习算法更紧密结合起来的想法也渐渐被人们关注，文献[24]中就提到了一种采取上述思想的决策树算法。此外，文献[25]中提出，对一个完整的时间序列可能比抽取出来的特征更具有价值，由这种思想出发，采用整个序列作为独立节点进行训练的k近邻分类器在一些数据集上也取得了不错的效果。
3.5.2 时间点的分类问题
对于时间点的分类问题往往采用基于滑动窗口的特征选择方法，将每个时间点及周围相邻时间点的特征用向量进行表示，然后再采用一些分类方法进行分类。常见的分类模型有：隐马尔可夫模型，条件随机场模型，最大熵马尔可夫模型等。Cotofrei和Stoffel提出了一种基于一阶逻辑的分类模型，将时间序列用等频直方图来离散化，再通过差分或分割获得每个时间点的特征向量用以进行分类器训练。训练时，通过滑动窗口来保持数据的时间顺序[26]。
3.6 聚类问题
聚类的目的是为了发现数据集合内部的某种联系。聚类过程一般以某种距离或相似度度量为基础，结果中每个类的内部应该尽可能类似，而类与类之间应该保证尽量大的差别。和分类问题一样，聚类问题也可以按照操作的对象进行分类：以一组时间序列集合进行聚类，可以称为全序列聚类(whole series clustering)；对某一个时间序列的若干分割即子序列进行聚类，称为子序列聚类(sub-series clustering)；对某一个时间序列中的若干时间点进行聚类，称为时间点聚类(time point clustering)[8]。
全序列聚类问题的情况和分类问题很像，主要分为距离表示和聚类算法选择两个方面。欧式距离和DTW 距离是常用的距离表示，更多的距离问题参见3.4节。常用的聚类算法有k均值，k中值等。如何更合适的定义距离，更有效的利用时序数据表示中的信息，使得聚类更能反映数据的本质情况是这一方向研究的重点问题之一。文献[23]中就是一种利用基于压缩的距离表示进行聚类的例子。
子序列聚类由于是在同一个时间序列的内部进行聚类，往往会采用滑动窗口的方法，因而窗口的大小以及窗口之间间隔的大小选择问题，对这种聚类的结果有着非常大的影响。
时间点聚类的过程跟时间序列的分割比较相近，所不同的是，聚类是按照内部联系将一个时间序列内的
6 Journal of Software软件学报 2004,15(1)
时间点聚集成几个类别，而不是简单的分割成几段。因此时间点聚类中即使是有一定距离的两个或多个时间点也能拥有同样的类别。此外，时间点聚类中，往往还允许某些时间点被标记为噪音点，这也是分割和其他时序数据聚类中比较少有的。
3.7 异常检测
所谓异常检测就是找出大量数据中少数与其他数据不相符合的部分，在应用中经常涉及到错误检测或入侵检测等方面。异常检测最大的特点就是需要被识别的时间是较少发生的。很多数据挖掘的方法都容易产生错误的演绎偏差，从而导致结果并不理想。文献[27]中，对类似异常检测这样的工作及工作中的难题作了一个很好的介绍。
在异常检测中一个比较简单的方法是先对正常的时间序列建模，在通过检测那些与模型不符合的数据来发现异常。但这一方法有个前提是需要获得关于正常的时间序列的知识。变通的办法就是对所有拥有的数据进行建模，再用这个模型对数据进行筛选。文献[28]介绍了一种基于状态的方法，通过对时间序列进行时间点聚类得到一个近似的分割，然后基于这些分割和分割之间的关联建立一个包含异常状态的有穷状态自动机。再通过这个自动机来识别异常。此外，异常检测中还可以用反向选择等方法进行，详细内容参见文献[8][27]。
3.8 规则识别
时序数据的规则大致可以分为关于时间点的规则和关于时间间隔(time interval)的规则两类。规则识别就是指从时序数据中发现这两类规则的过程。具体的讲，规则描述的就是时间序列中的事件(比如：事件的起始，持续时间等)和事件间的关系(比如：事件发生的先后顺序，事件的并行性，事件的一致性等)。
规则识别是数据挖掘中一个非常重要的过程，因为其结果往往直接用来对人们提供信息，帮助人们决策。同时为了便于用户理解，规则往往需要通过某种抽象表述为自然语言或者可以比较容易的表述为自然语言的形式[8]。
对时序数据的规则识别可以分为有指导的(supervised)和无指导的(unsupervised)两类，有指导的规则识别方法中，通常有一些关于规则的先验知识，这种类型的方法通常和预测事件的发生有关。而无指导的规则识别则在数据中寻找可以被表述为规则的模式，并将这种模式转换成规则。具体的规则识别方法取决于知识表示和目标规则的类型。
4 时序数据挖掘的讨论
从整体上讲，时序数据挖掘作为一个数据挖掘的一个分支已经受到了人们的广泛关注，其中的很多重要问题已经有了很多不同的解决办法，并取得了一定的效果。但是，我们应该看到，在这些方法中有很多有待于进一步完善，这个领域中还有很多问题值得人们继续关注。
在整个时序数据挖掘体系中，时序数据的表示和相似度度量是两个非常基本而且重要的任务。许多上层的任务比如分类、聚类、异常检测都直接依赖于数据的表示形式和相似度度量。虽然对这两项工作已经有大量的研究和文献，提出了很多很实用的解决办法。但由于这两项工作都与实际问题有着很大的关系，实际应用中总是还有大量的提升空间，针对不同的问题找到比较合适的表示形式和相似度度量才能取得较为满意的结果。能否找到一个相对通用的解决办法，使之对大部分的问题都能有比较好的效果是大家普遍关心的问题。
对分类和聚类这样的任务来说，很多时候面临的是怎样将已有的机器学习方法应用到实际的数据表示或者特征表示上的问题。这类问题的解决应该依靠多方面的力量，一方面，我们希望有更好的，表达能力更强的模型来对数据进行建模；另一方面，我们也要寻找更有力的特征表示方法来描述数据的性质；更有吸引力的研究就在于如何更好的把以上两个方面结合起来，使我们离目标更进一步。
异常检测用来自动识别异常现象，可以作为自动监测的一个重要手段，有了这项技术的帮助，我们可以比较容易的从海量的数据中找出可以的现象，并加以分析。但这也对异常检测的准确性和可靠性提出了进一步的要求。针对不同的应用领域不断的提高异常识别率和识别的准确率，应该是这个方向上不变的追求。
规则识别过程所得到规则的可理解性是一个非常重要的问题，3.8节中已有所描述。在这个问题上，寻
作者名等:题目7
求可解释的、更容易被人们理解的规则已经成为人们研究的主要目标。一个不知道含义的规则是无法对人们的决策起到帮助作用的。从这个意义上讲不仅是规则识别，其他时序数据挖掘得到的知识也应该更具可理解性，才能使数据挖掘这个过程更好的为人们的决策服务。
5 总结
本文首先给出了时序数据的概念以及时序数据挖掘的目的。随后概要的介绍了时序数据挖掘中的几个主要问题，并对其中的一些问题列出了一些已有的解决办法。最后本文还对这个领域的一些问题作了一个简要的讨论。随着研究的不断深入，时序数据的数据挖掘必将得到进一步的发展，对实际生产生活的指导帮助作用也必将越来越重大。
References:
[1] 周志华. 数据挖掘课程讲义. 2006年秋学期.
[2] Han Jiawei, Kamber M. Data Mining: Concepts and Techniques. Morgan Kaufmann Publishers. 2000
[3] M. Gavrilov, D. Anguelov, P. Indyk, and R. Motwani. Mining the Stock Market: Which Measure is Best? In Proceedings of the
Association for Computing Machinery Sixth International Conference on Knowledge Discovery and Data Mining, pages 487-496, 2000.
[4] Antunes, M., and Oliveira, L., "Temporal Data Mining: an Overview", KDD 2001 Workshop on Temporal Data Mining, 2001
[5] Gautam Das, King-Ip Lin, Heikki Mannila, Gopal Renganathan, and Padhraic Smyth. Rule discovery from time-series. In
Proceedings of the Fourth International Conference on Knowledge Discovery and Data Mining (KDD-98), 1998
[6] M?rchen, F. Time-series Knowledge Mining, Phd thesis, Dept. of Mathematics and Computer Science, University of Marburg,
Germany, 2006
[7] J. Lin, E. Keogh, S. Lonardi, and B. Chiu. A symbolic representation of time-series, with implications for streaming algorithms. In
Proceedings of the 2003 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery，pages 2-11, ACM Press, 2003.
[8] E. Keogh, K. Chakrabarti, M. J. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time-series
databases. Knowledge and Information Systems, 3(3):263-286, 2001.
[9] P. Smyth. Clustering sequences with Hidden Markov Models. In M. C. Mozer, M. I. Jordan, and T. Petsche, eds, Advances in
Neural Information Processing Systems, volume 9, page648. MIT Press, 1997.
[10] A. Panuccio, M. Bicego, and V. Murino. A Hidden Markov Model-based approach to sequential data clustering. In T. Caelli, A.
Amin, R. P. W. Duin, M. S. Kamel, and D. de Ridder, eds, Proceedings Joint IAPR International Workshops Structural, Syntactic, and Statistical Pattern Recognition, pages 734-742. Springer, 2002
[11] P. Indyk, N. Koudas, and S. Muthukrishnan. Identifying representative trends in massive time-series data sets using sketches. In A.
E. Abbadi, M. L. Brodie, S. Chakravarthy, U. Dayal, N. Kamel, G. Schlageter, and K.-Y. Whang, eds, Proceedings of the 26th
International Conference on Very Large Data Bases (VLDB'00), pages 363-372. Morgan Kaufmann, 2000.
[12] D. Dasgupta and S. Forrest. Novelty detection in time-series data using ideas from immunology. In Proceedings of the 5th
International Conference on Intelligent Systems, 1996.
[13] J. An, H. Chen, K. Furuse, N. Ohbo, and E. Keogh. Grid-based indexing for large time-series databases. In J. Liu, Y. Ming Cheung,
and H. Yin, eds, Proceedings of the 4th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL'03), pages 614-621. Springer, 2003.
[14] J. An, Y.-P. P. Chen, and H. Chen. DDR: An index method for large time-series datasets. Information Systems, 30(5):333-348,
2005.
[15] A. Bagnall, G. Janakec, and M. Zhang. Clustering time-series from mixture polynomial models with discretised data. Technical
Report CMP-C03-17, School of Computing Sciences, University of East Anglia, Norwich, UK, 2003.
[16] C. Ratanamahatana, E. Keogh, A. J. Bagnall, and S. Lonardi. A novel bit level time-series representation with implication of
similarity search and clustering. In T. B. Ho, D. Cheung, and H. Liu, eds, Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'05), pages 771-777. Springer, 2005.
8 Journal of Software软件学报 2004,15(1)
[17] E. Keogh, S. Chu, D. Hart, and M. Pazzani. Segmenting time-series: A survey and novel approach. In M. Last, A. Kandel, and H.
Bunke, eds, Data Mining In Time-series Databases, pages 1-22. World Scientific, 2004.
J. Himberg, K. Korpiaho, H. Mannila, J. Tikanm aki, and H. T. Toivonen. Time-series segmentation for context recognition in [18]
mobile devices. In N. Cercone, T. Y. Lin, and X. Wu, eds, Proceedings of the 1st IEEE International Conference on Data Mining (ICDM'01), pages 203-210. IEEE Press, 2001.
[19] Y. Zhao, C. Zhang, and S. Zhang. A recent-biased dimension reduction technique for time-series data. In T. B. Ho, D. Cheung, and
H. Liu, eds, Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD'05), pages 75-757.
Springer, 2005.
[20] S. Gaffney and P. Smyth. Trajectory clustering with mixtures of regression models. In Proceedings of the 5th ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining (KDD'99), pages 63-72. ACM Press, 1999.
[21] S. Gaffney and P. Smyth. Curve clustering with random effects regression mixtures. In C. M. Bishop and B. J. Frey, eds,
Proceedings of the 9th International Workshop on Artificial Intelligence and Statistics. Society for Artificial Intelligence and Statistics, 2003.
[22] V. Megalooikonomou, G. Li, and Q. Wang. A dimensionality reduction technique for efficient similarity analysis of time-series
databases. In D. Grossman, L. Gravano, C. Zhai, O. Herzog, and D. A. Evans, eds, Proceedings of the 13th International Conference on Information and Knowledge Management (CIKM'04), pages 160-161. ACM Press, 2004.
[23] E. Keogh, S. Lonardi, and C. Ratanamahatana. Towards parameter-free data mining. In W. Kim, R. Kohavi, J. Gehrke, and W.
DuMouchel, eds, Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'04), pages 206-215. ACM Press, 2004b.
[24] Y. Yamada and E. Suzuki. Decision-tree induction from time-series data based on a standard example split test. In T. Fawcett and
N. Mishra, eds, Proceedings of the 20th International Conference on Machine Learning (ICML'03), pages 840-847. Morgan Kaufmann, 2003.
[25] C. A. Ratanamahatana and E. Keogh. Making time-series classi_cation more accurate using learned constraints. In M. W. Berry, U.
Dayal, C. Kamath, and D. B. Skillicorn, eds, Proceedings of the 4th SIAM International Conference on Data Mining (SDM'04), pages 11-22. SIAM, 2004.
[26] P. Cotofrei and K. Sto_el. First-order logic based formalism for temporal data mining. In T. Lin, S. Ohsuga, C.-J. Liau, X. Hu, and
S. Tsumoto, eds, Foundations of Data Mining and Knowledge Discovery, pages 193-218. Springer, 2005.
[27] G. M.Weiss. Mining with rarity: A unifying framework. ACM SIGKDD Explorations Newsletter, 6(1):7-19, 2004.
[28] S. Salvador, P. Chan, and J. Brodie. Learning states and rules for time-series anomaly detection. In V. Barr and Z. Markov, eds,
Proceedings 17th International Florida AI Research Society Conference (FLAIRS'04). AAAI Press, 2004.
数据挖掘考试题目——聚类 一、填空题 1、密度的基于中心的方法使得我们可以将点分类为：__________、________ 、_________。 2、DBSCAN算法在最坏的情况下，时间复杂度是__________、空间复杂度是__________。 3、DBSCAN算法的优点是_______、__________________________。 4、DBSCAN算法的缺点是处理_________________、_____________的数据效果不好。 5、DBSCAN算法的参数有：___________、____________。 6、簇的有效性的非监督度量常常可以分为两类：__________、__________，它常采用的指标为__________。 7、簇的有效性的监督度量通常称为___________，它度量簇标号与外部提供的标号的匹配程度主要借助____________。 8、在相似度矩阵评价的聚类中，如果有明显分离的簇，则相似度矩阵应当粗略地是__________。 9、DBSCAN算法的参数确定的基本方法是观察____________________的特性。 10、不引用附加的信息，评估聚类分析结果对数据拟合情况属于__________技术。 答案： 1、核心点边界点噪声点 2、O(n2) O(n) 3、耐噪声能够处理任意大小和形状的簇 4、高维数据变密度的 5、EPS MinPts 6、簇的凝聚性簇的分离性均方差(SSE) 7、外部指标监督指标的熵 8、块对角的 9、点到它的第K个最近邻的距离（K-距离） 10、非监督 二、选择题 1、DBSCAN算法的过程是（B）。 ①删除噪声点。 ②每组连通的核心点形成一个簇。 ③将所有点标记为核心点、边界点和噪声点。 ④将每个边界点指派到一个与之关联的核心点的簇中。 ⑤为距离在Eps之内的所有核心点之间赋予一条边。 A：①②④⑤③ B：③①⑤②④ C：③①②④⑤ D：①④⑤②③ 2、如果有m个点，DBSCAN在最坏的情况下的时间复杂度度为（C）。 A O(m) B O(mlogm) C O(m2) D O(logm) 3、在基本DBSCAN的参数选择方法中，点到它的K个最近邻的距离中的K选作为哪一个参数（B）。 A Eps B MinPts C 质心 D 边界
第28卷第3期2005年6月 测绘与空间地理信息 G E O M A T I C S ＆S P A T I A LI N F O R M A T I O NT E C H N O L O G Y V o l .28,N o .3 J u n .,2005 收稿日期:2004-09-14 基金项目:国家重点基础研究发展规划(973)资助项目(2001C B 309404) 作者简介:汤海鹏(1979-),男,湖南沅江人,本科,主要从事信息化管理和信息化建设等方面的研究。 空间数据挖掘工具浅谈 汤海鹏1 ,毛克彪 2,3 ,覃志豪2,吴 毅 4 (1.公安部出入境管理局技术处,北京100741;2.中国农业科学院自然资源与农业区划研究所农业遥感实验室, 北京100081;3.中国科学院遥感所,北京100101;4.黑龙江乌苏里江制药有限公司,黑龙江哈尔滨150060) 摘要:数据挖掘是一个利用各种分析工具在海量数据中发现模型和数据间关系的过程,这些模型和关系可以 用来做出预测。空间数据挖掘有十分广阔的应用范围和市场前景,目前已出现大量的数据挖掘工具用于企业决策、科学分析等各个领域。文中对2个数据挖掘工具进行讨论,介绍它们的功能、所使用的技术以及如何使用它们来进行数据挖掘。 关键词:数据挖掘;空间数据挖掘;数据立方体;知识库引擎 中图分类号:P 208 文献标识码:A 文章编号:1672-5867(2005)03-0004-02 AS u r v e y o f D a t a Mi n i n g T o o l s T A N GH a i -p e n g 1 ,M A OK e -b i a o 2,3 ,Q I NZ h i -h a o 2 ,W UY i 4 (1.B u r e a uo f E x i t a n dE n t r y A d m i n i s t r a t i o n ,M i n i s t r y o f P u b l i c S e c u r i t y ,B e i j i n g 100741,C h i n a ;2.T h e K e y L a b o r a t o r y o f R e m o t e S e n s i n g a n d D i g i t a l A g r i c u l t u r e ,C h i n a A c a d e m y o f A g r i c u l t u r e R e m o t e S e n s i n g L a b o r a t o r y ,B e i j i n g 100081,C h i n a ; 3.I n s t i t u t eo f R e m o t e S e n s i n g A p p l i c a t i o n s ,C h i n e s e A c a d e m y o f S c i e n c e s ,B e i j i n g 100101,C h i n a ; 4.H e i l o n g j i a n g Wu s u l i j i a n g P h a r m a c e u t i c a l C o .L t d .,H a r b i n 150060,C h i n a ) A b s t r a c t : B e c a u s e o f c o m m e r c i a l d e m a n d s a n dr e s e a r c hi n t e r e s t ,a l l k i n d s o f s p a t i a l d a t a m i n i n g s o f t w a r e t o o l s e m e r g e .I n o r d e r t o g e t u s e o f t h e d a t a m i n i n g t o o l s ,t w o o f t h e ma r e i n t r o d u c e d i n t h i s p a p e r a n d m a k e p r o s p e c t o f i n t e g r a t i o n o f G I S ,R S ,G P S a n d d a t a m i n -i n g .K e yw o r d s :d a t a m i n i n g ;s p a t i a l d a t a m i n i n g ;d a t a c u b e ;d a t a b a s e e n g i n e 0 引 言 随着数据获取手段(特别是对地观测技术)及数据库 技术的快速发展,科研机构、政府部门在过去的若干年里都积累了大量的数据,而且,目前这些数据仍保持迅猛的增长势头。如此大量的数据已远远超过传统的人工处理能力,怎样从大量数据中自动、快速、有效地提取模式和发现知识显得越来越重要。数据挖掘与知识发现作为一个新的研究领域和新的技术正方兴未艾,用于从巨量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式[1～2],很好地满足了海量数据处理的需要。 具体应用中,数据挖掘工具很多。它们在功能和方法等方面差别很大。如何选择适合具体挖掘需求的工具,是进行挖掘工作必须考察的前提。选择某一工具时,应考虑数据类型,主要是考察工具能处理的数据:①关系 数据库的数据。包括数据仓库数据、文本文档、空间数据、 多媒体数据、W e b 数据等;②功能和方法。数据挖掘功能是数据挖掘工具(或系统)的核心,一些数据挖掘工具仅提供一种功能(如分类),另一些工具可能支持另外的挖掘功能(如描述、关联、分类、预测和聚类等);③其他考虑的方面如:系统问题、数据源、可伸缩性、可视化、数据挖掘查询语言和图形用户接口、工具和数据库或数据仓库系统等。 在众多的数据中,有近80%的数据可以通过空间关系表达。现在,通过卫星扫描地球,每天都能获得大量的关于地表的遥感图像。要从大量的数据中判读出每一个图片所潜藏的信息,就必然要用到数据挖掘技术。本文将通过介绍专业的航空遥感图像处理系统E r d a s 和D B -M i n e r 来阐述处理空间数据和关系数据的这一过程及这2种软件的特点。
计算机工程应用技术本栏目责任编辑：贾薇薇 数据挖掘中的聚类分析方法 黄利文 （泉州师范学院理工学院，福建泉州３６２０００） 摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。 关键词：聚类分析；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇ ＨＵＡＮＧＬｉ－ｗｅｎ （ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ． Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ １引言 聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。 本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。 ２聚类的分类 聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。 ２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ） 给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。 ２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ） 层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ） 该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ） 这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ） 基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概 收稿日期：２００８－０２－１７ 作者简介：黄利文（１９７９－），男，助教。
科技广场2010.9 0引言 随着数据库技术的飞速发展，人们在各种应用领域所拥有的数据量急剧增加，这些数据对人们的工作和研究有着重要的作用，但是由于对这些数据进行高级处理的工具比较少，使它们的重要性没有能够充分的发挥。当前多数的数据库系统只是可以对数据库中已有的数据进行存取、查询和统计等简单操作，通过这些操作人们可以获得数据的一些简单信息。但这些信息是从数据表面直观表现出来，对于隐藏于数据背后的如数据之间的关系、数据整体特征的描述以及寻找未来数据发展趋势的预测等信息并不能通过这些手段得到，而这些往往是人们更加需要的并且在决策支持的过程中更有价值。 数据挖掘是信息技术自然演化的结果，正是从存放在数据库、数据仓库或其他信息库中挖掘有用知识的过程。 1数据挖掘的主要步骤 数据挖掘工作作为一个完整的挖掘过程，可分为以下几个主要步骤： (1)陈述问题和阐明假设：多数基于数据的模型研究都是在一个特定的应用领域里完成的。因此在设计数据挖掘算法之前，需要事先确定一个有意义的问题陈述。模型建立者通常会为未知的相关性指定一些变量，如果可能还会指定相关性的一个大体形式作为初始假设。对当前问题可能会有几个阐明的假设，这要求将应用领域的专门技术和数据挖掘模型相结合。实际上，这往往意味数据挖掘人员与应用专家之间密切地协作，在开始数据处理过程之前明确实际工作对数据挖掘结果的要求，根据此要求，确定数据收集过程的具体方法和数据挖掘采用的具体算法。 (2)数据准备和预处理：数据准备和预处理又可分为三个步骤：数据选取、数据预处理、数据变换。 数据选取的目的是确定数据挖掘的处理对象，即目标数据，它是根据由问题陈述中得到的用户需求，从原始数据库中抽取一定的数据用于数据挖掘， 数据挖掘算法的分析与研究 Analysis and Research of Data Mining Algorithms 喻云峰 Yu Yunfeng (江西省商务学校，江西南昌330100) （Jiangxi Commercial School,Jiangxi Nanchang330100） 摘要：本文对数据挖掘的基本理论进行了分析研究，总结了数据挖掘的基本步骤，归纳了数据挖掘的基本方法，并在此基础上，提出了用数据挖掘进行数据分析的通用策略。 关键词：数据挖掘；通用策略 中图分类号：TP311文献标识码：A文章编号：1671-4792-(2010)9-0054-03 Abstract:In this thesis,the basic theory of data mining is researched.Based on this,the basic steps of data min-ing is summarized and the basic method of data mining is generalized.At last,a general tactic of data mining is given. Keywords:Data Mining;General Tactic 54
《海量数据挖掘技术及工程实践》题目 一、单选题（共80题） 1)( D )的目的缩小数据的取值范围，使其更适合于数据挖掘算法的需要，并且能够得到 和原始数据相同的分析结果。 A.数据清洗 B.数据集成 C.数据变换 D.数据归约 2)某超市研究销售纪录数据后发现，买啤酒的人很大概率也会购买尿布，这种属于数据挖 掘的哪类问题？(A) A. 关联规则发现 B. 聚类 C. 分类 D. 自然语言处理 3)以下两种描述分别对应哪两种对分类算法的评价标准？ (A) (a)警察抓小偷，描述警察抓的人中有多少个是小偷的标准。 (b)描述有多少比例的小偷给警察抓了的标准。 A. Precision,Recall B. Recall,Precision A. Precision,ROC D. Recall,ROC 4)将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务？(C) A. 频繁模式挖掘 B. 分类和预测 C. 数据预处理 D. 数据流挖掘 5)当不知道数据所带标签时，可以使用哪种技术促使带同类标签的数据与带其他标签的数 据相分离？(B) A. 分类 B. 聚类 C. 关联分析 D. 隐马尔可夫链 6)建立一个模型，通过这个模型根据已知的变量值来预测其他某个变量值属于数据挖掘的 哪一类任务？(C) A. 根据内容检索 B. 建模描述 C. 预测建模 D. 寻找模式和规则 7)下面哪种不属于数据预处理的方法？ (D) A.变量代换 B.离散化
C.聚集 D.估计遗漏值 8)假设12个销售价格记录组已经排序如下：5, 10, 11, 13, 15, 35, 50, 55, 72, 92, 204, 215 使用如下每种方法将它们划分成四个箱。等频（等深）划分时，15在第几个箱子内？ (B) A.第一个 B.第二个 C.第三个 D.第四个 9)下面哪个不属于数据的属性类型：(D) A.标称 B.序数 C.区间 D.相异 10)只有非零值才重要的二元属性被称作：( C ) A.计数属性 B.离散属性 C.非对称的二元属性 D.对称属性 11)以下哪种方法不属于特征选择的标准方法： (D) A.嵌入 B.过滤 C.包装 D.抽样 12)下面不属于创建新属性的相关方法的是： (B) A.特征提取 B.特征修改 C.映射数据到新的空间 D.特征构造 13)下面哪个属于映射数据到新的空间的方法？ (A) A.傅立叶变换 B.特征加权 C.渐进抽样 D.维归约 14)假设属性income的最大最小值分别是12000元和98000元。利用最大最小规范化的方 法将属性的值映射到0至1的范围内。对属性income的73600元将被转化为：(D) A.0.821 B.1.224 C.1.458 D.0.716 15)一所大学内的各年纪人数分别为：一年级200人，二年级160人，三年级130人，四年 级110人。则年级属性的众数是： (A) A.一年级 B.二年级 C.三年级 D.四年级
V ol.15, No.1 ?2004 Journal of Software 软 件 学 报 1000-9825/2004/15(01)0000 时序数据上的数据挖掘 ? 黄书剑1+ 1(南京大学 计算机科学与技术系 江苏 南京 210093) Data Mining on Time-series Data HUANG Shu-Jian 1+ 1(Department of Computer Science and technology, Nanjing University, Nanjing 210093, China) + Corresponding author: Phn +86-**-****-****, Fax +86-**-****-****, E-mail: ****, http://**** Abstract : Data mining has been developing rapidly in the recent years. Since time related data occurs frequently in various areas, there has been “an explosion” of interest in mining time-series data, which is a popular branch of data mining. In this paper we present an overview of the major research areas and tasks in mining time-series data, such as preprocessing, representation, segmentation, similarity, classification, clustering, anomaly detection, rule discovery, etc. Some solutions of several tasks are also included in this paper. Key words : data mining; time-series 摘 要: 近年来数据挖掘得到了蓬勃的发展。由于越来越多的数据都与时间有着密切的关系，时序数据的挖掘作为数据挖掘的一个分支，正在受到越来越高的重视。本文概述了时序数据上的数据挖掘这个领域内的主要研究方向和课题，包括数据预处理、数据表示、分割、相似度度量、分类、聚类、异常检测、规则识别等。并对部分课题的主要解决方案进行了一些介绍。 关键词: 数据挖掘;时序数据挖掘 中图法分类号: **** 文献标识码: A 1 引言 近几十年来，计算机运算存储能力不断提高，数据产生和采集的速度也越来越快，因而数据量越来越大；而与此同时，人们面对巨量数据，能够直接获得的信息量却越来越有限。单纯的人力已经很难胜任对这样巨量的数据进行分析并提取出相关信息的任务。为了解决这种数据与信息之间的矛盾，数据挖掘应运而生。所谓数据挖掘，即从巨量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程[1]。数据挖掘的目的就在于找出巨量数据中的潜在规律，以对未来的分析和决策提供支持，其在分析处理中的优势以 ? Supported by the **** Foundation of China under Grant No.****, **** (基金中文完整名称); the **** Foundation of China under Grant No.****, **** (基金中文完整名称) 作者简介: 黄书剑(1984),男,江苏盐城人,硕士生,主要研究领域为自然语言处理.
第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所示。 在这些数据中，与空间位置相关的数据占了绝大多数。传统的空间知识发现的科研模式在大数据情境下已经不再适用，原因是传统的科研模型不具有普适性且支持的数据量受限， 受到数据传输、存储及时效性需求的制约等。为了从存储在分布方式、虚拟化的数据中心获取信息或知识，这就需要利用强有力的数据分析工具来将
聚类分析和关联规则属于数据挖掘这个大概念中的两类挖掘问题， 聚类分析是无监督的发现数据间的聚簇效应。 关联规则是从统计上发现数据间的潜在联系。 细分就是 聚类分析与关联规则是数据挖掘中的核心技术； 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用k-均值、k-中心点等算法的聚类分析工具已被加入到许多著名的统计分析软件包中，如SPSS、SAS等。 从机器学习的角度讲，簇相当于隐藏模式。聚类是搜索簇的无监督学习过程。与分类不同，无监督学习不依赖预先定义的类或带类标记的训练实例，需要由聚类学习算法自动确定标记，而分类学习的实例或数据对象有类别标记。聚类是观察式学习，而不是示例式的学习。 聚类分析是一种探索性的分析，在分类的过程中，人们不必事先给出一个分类的标准，聚类分析能够从样本数据出发，自动进行分类。聚类分析所使用方法的不同，常常会得到不同的结论。不同研究者对于同一组数据进行聚类分析，所得到的聚类数未必一致。 从实际应用的角度看，聚类分析是数据挖掘的主要任务之一。而且聚类能够作为一个独立的工具获得数据的分布状况，观察每一簇数据的特征，集中对特定的聚簇集合作进一步地分析。聚类分析还可以作为其他算法（如分类和定性归纳算法）的预处理步骤。 关联规则挖掘过程主要包含两个阶段：第一阶段必须先从资料集合中找出所有的高频项目组(FrequentItemsets)，第二阶段再由这些高频项目组中产生关联规则(AssociationRules)。 关联规则挖掘的第一阶段必须从原始资料集合中，找出所有高频项目组(LargeItemsets)。高频的意思是指某一项目组出现的频率相对于所有记录而言，必须达到某一水平。 关联规则挖掘的第二阶段是要产生关联规则(AssociationRules)。从高频项目组产生关联规则，是利用前一步骤的高频k-项目组来产生规则，在最小信赖度(MinimumConfidence)的条件门槛下，若一规则所求得的信赖度满足最小信赖度，称此规则为关联规则。
实验三 一、实验原理 K-Means算法是一种 cluster analysis 的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。 在数据挖掘中，K-Means算法是一种cluster analysis的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。 算法原理： (1) 随机选取k个中心点； (2) 在第j次迭代中，对于每个样本点，选取最近的中心点，归为该类； (3) 更新中心点为每类的均值； (4) j<-j+1 ,重复(2)(3)迭代更新，直至误差小到某个值或者到达一定的迭代步 数，误差不变. 空间复杂度o(N) 时间复杂度o(I*K*N) 其中N为样本点个数，K为中心点个数，I为迭代次数 二、实验目的： 1、利用R实现数据标准化。 2、利用R实现K-Meams聚类过程。 3、了解K-Means聚类算法在客户价值分析实例中的应用。 三、实验内容 依据航空公司客户价值分析的LRFMC模型提取客户信息的LRFMC指标。对其进行标准差标准化并保存后，采用k-means算法完成客户的聚类，分析每类的客户特征，从而获得每类客户的价值。编写R程序，完成客户的k-means聚类，获得聚类中心与类标号，并统计每个类别的客户数
四、实验步骤 1、依据航空公司客户价值分析的LRFMC模型提取客户信息的LRFMC指标。
2、确定要探索分析的变量 3、利用R实现数据标准化。 4、采用k-means算法完成客户的聚类，分析每类的客户特征，从而获得每类客户的价值。
五、实验结果 客户的k-means聚类，获得聚类中心与类标号，并统计每个类别的客户数 六、思考与分析 使用不同的预处理对数据进行变化，在使用k-means算法进行聚类，对比聚类的结果。 kmenas算法首先选择K个初始质心，其中K是用户指定的参数，即所期望的簇的个数。 这样做的前提是我们已经知道数据集中包含多少个簇. 1.与层次聚类结合 经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果
数据挖掘论文 题目：数据挖掘技术在电子商务中的应用系别：计算机学院 专业：11网络工程1班 学生姓名：黄坤 学号：1110322111 指导教师：江南 2014年11月06 日
数据挖掘技术在电子商务中的应用 一、研究原因 电子商务在现代商务活动中的正变得日趋重要，随着大数据时代的到来，商务信息显得尤为重要，在电子商务中谁掌握了有利的市场信息，谁就能在这个竞争激烈电商行业中占据绝对的优势。而数据挖掘技术是获取信息的最有效的技术工具。本文讨论了数据挖掘的主要方法，具体阐述了数据挖掘技术在电子商务中的作用及应用。 在信息经济时代，对企业来说，谁对市场变化反应速度快，谁将在激烈的市场竞争中占据有利的地位，竞争的结果最终将促使企业价值从市场竞争输家转移到赢家，这样就使企业面临一个问题：如何才能把大量的数据资源，转化成自身价值呢？要想使数据真正成为一个公司的资源，只有充分利用它为公司自身的业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥饿于知识”的挑战，数据挖掘和知识发现(DMKD)技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 二、2.1国内研究现状 KDD（从数据库中发现知识）一词首次出现在1989年8月举行的第11届国际联合人工智能学术会议上。迄今为止,由美国人工智能协会主办的KDD已经召开了7次,规模由原来的专题讨论会发展到国际学术大会,人数由二三十人到七八百人,论文收录比例从2X1到6X1,研究重点也逐渐从发现方法转向系统应用,并且注重多种发现策略和技术的集成,以及多种学科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题之一,成为当前计算机科学界的一大热点。此外,数据库、人工智能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟了KDD专题或专刊。IEEE的Knowledge and Data Engineering 会刊领先在1993年出版了KDD技术专刊,所发表的5篇论文代表了当时KDD研究的最新成果和动态,较全面地论述了KDD 系统方法论、发现结果的评价、KDD系统设计的逻辑方法,集中讨论了鉴于数据库的动态性冗余、高噪声和不确定性、空值等问题,KDD系统与其它传统的机器学习、专家系统、人工神经网络、数理统计分析系统的联系和区别,以及相应的基本对策。6篇论文摘要展示了KDD在从建
可视化空间数据挖掘研究综述 贾泽露1，2 刘耀林2 （1. 河南理工大学测绘与国土信息工程学院，焦作，454000；2. 武汉大学资源与环境科学学院，武汉，430079）摘要：空间数据挖掘针对的是更具有可视化要求的地理空间数据的知识发现过程，可视化能提供同用户对空间目标心理认知过程相适应的信息表现和分析环境，可视化与空间数据挖掘的结合是该领域研究发展的必然，并已成为一个研究热点。论文综述了空间数据挖掘和可视化的研究现状，重点阐述了空间数据挖掘中的可视化化技术及其应用，并对可视化空间数据挖掘的发展趋势进行了阐述。 关键词：数据挖掘；空间数据挖掘；数据可视化；信息可视化；GIS； 空间信息获取技术的飞速发展和各种应用的广泛深入，多分辨率、多时态空间信息大量涌现，以及与之紧密相关的非空间数据的日益丰富，对海量空间信息的综合应用和处理技术提出了新的挑战，要求越来越高。空间数据挖掘技术作为一种高效处理海量地学空间数据、提高地学分析自动化和智能化水平、解决地学领域“数据爆炸、知识贫乏”问题的有效手段，已发展成为空间信息处理的关键技术。然而，传统数据挖掘“黑箱”作业过程使得用户只能被动地接受挖掘结果。可视化技术能为数据挖掘提供直观的数据输入、输出和挖掘过程的交互探索分析手段，提供在人的感知力、洞察力、判断力参与下的数据挖掘手段，从而大大地弥补了传统数据挖掘过程“黑箱”作业的缺点，同时也大大弥补了GIS重“显示数据对象”轻“刻画信息结构”的弱点，有力地提高空间数据挖掘进程的效率和结果的可信度[1]。空间数据挖掘中可视化技术已由数据的空间展现逐步发展成为表现数据内在复杂结构、关系和规律的技术，由静态空间关系的可视化发展到表示系统演变过程的可视化。可视化方法不仅用于数据的理解，而且用于空间知识的呈现。可视化与空间数据挖掘的结合己成为必然，并已形成了当前空间数据挖掘1与知识发现的一个新的研究热点——可视化空间数据挖掘(Visual Spatial Data Mining，VSDM)。VSDM技术将打破传统数据挖掘算法的“封闭性”，充分利用各式各样的数据可视化技术，以一种完全开放、互动的方式支持用户结合自身专业背景参与到数据挖掘的全过程中，从而提高数据挖掘的有效性和可靠性。本文将对空间数据挖掘、可视化的研究概况，以及可视化在空间数据挖掘中的应用进行概括性回顾总结，并对未来发展趋势进行探讨。 一、空间数据挖掘研究概述 1.1 空间数据挖掘的诞生及发展 1989年8月，在美国底特律市召开的第一届国际联合人工智能学术会议上，从事数据库、人工智能、数理统计和可视化等技术的学者们，首次出现了从数据库中发现知识(knowledge discovery in database，KDD)的概念，标志着数据挖掘技术的诞生[1]。此时的数据挖掘针对的 作者1简介：贾泽露（1977,6－），男，土家族，湖北巴东人，讲师，博士，主要从事空间数据挖掘、可视化、土地信息系统智能化及GIS理论、方法与应用的研究和教学工作。 作者2简介：刘耀林(1960,9- ),男，汉族，湖北黄冈人，教授，博士，博士生导师，武汉大学资源与环境科学学院院长，现从事地理信息系统的理论、方法和应用研究和教学工作。
数据挖掘实验报告（三） 聚类分析 姓名：李圣杰 班级：计算机1304 学号：1311610602
一、实验目的 1、 掌握k-means 聚类方法； 2、 通过自行编程，对三维空间内的点用k-means 方法聚类。 二、实验设备 PC 一台，dev-c++5.11 三、实验内容 1.问题描述： 立体空间三维点的聚类. 说明：数据放在数据文件中(不得放在程序中)，第一行是数据的个数，以后各行是各个点的x,y,z 坐标。 2.设计要求 读取文本文件数据，并用K-means 方法输出聚类中心 3. 需求分析 k-means 算法接受输入量k ；然后将n 个数据对象划分为 k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 k-means 算法的工作过程说明如下：首先从n 个数据对象任意选择k 个对象作为初始聚类中心，而对于所剩下的其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类。然后，再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值），不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具体定义如下： 2 1∑∑=∈-=k i i i E C p m p (1) 其中E 为数据库中所有对象的均方差之和，p 为代表对象的空间中的一个点，m i 为聚类C i 的均值(p 和m i 均是多维的)。公式(1)所示的聚类标准，旨在使所获得的k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 四、实验步骤 Step 1.读取数据组，从N 个数据对象任意选择k 个对象作为初始聚类中心； Step 2.循环Step 3到Step 4直到每个聚类不再发生变化为止； Step 3.根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离，并根据最小距离重新对相应对象进行划分； Step 4.重新计算每个（有变化）聚类的均值（中心对象）。 代码 #include
第八章聚类分析 设想要求对一个数据对象的集合进行分析，但与分类不同的是，它要划分的类是未知的。聚类(clustering)就是将数据对象分组成为多个类或簇(cluster)，在同一个簇中的对象之间具有较高的相似度，而不同簇中的对象差别较大。相异度是基于描述对象的属性值来计算的。距离是经常采用的度量方式。聚类分析源于许多研究领域，包括数据挖掘，统计学，生物学，以及机器学习。 在本章中，大家将了解基于大数据量上进行操作而对聚类方法提出的要求，将学习如何计算由各种属性和不同的类型来表示的对象之间的相异度。还将学习几种聚类技术，它们可以分为如下几类：划分方法（partitioning method），层次方法(hierarchical method)，基于密度的方法(density-based method)，基于网格的方法(grid-based method)，和基于模型的方法(model-based method)。本章最后讨论如何利用聚类方法进行孤立点分析(outlier detection)。 8．1 什么是聚类分析？ 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。在许多应用中，一个簇中的数据对象可以被作为一个整体来对待。 聚类分析是一种重要的人类行为。早在孩提时代，一个人就通过不断地改进下意识中的聚类模式来学会如何区分猫和狗，或者动物和植物。聚类分析已经广泛地用在许多应用中，包括模式识别，数据分析，图像处理，以及市场研究。通过聚类，一个人能识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间的有趣的相互关系。 “聚类的典型应用是什么？”在商业上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险持有者的分组，及根据房子的类型，价值，和地理位置对一个城市中房屋的分组上也可以发挥作用。聚类也能用于对Web上的文档进行分类，以发现信息。作为一个数据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇作进一步的分析。此外，聚类分析可以作为其他算法（如分类等）的预处理步骤，这些算法再在生成的簇上进行处理。 数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘，统计学，机器学习，空间数据库技术，生物学，以及市场营销。由于数据库中收集了大量的数据，聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。 作为统计学的一个分支，聚类分析已经被广泛地研究了许多年，主要集中在基于距离的聚类分析。基于k-means(k-平均值)，k-medoids(k-中心)和其他一些方法的聚类分析工具已经被加入到许多统计分析软件包或系统中，例如S-Plus，SPSS，以及SAS。在机器学习领域，聚类是无指导学习(unsupervised learning)的一个例子。与分类不同，聚类和无指导学习不依赖预先定义的类和训练样本。由于这个原因，聚类是通过观察学习，而不是通过例子学习。在概念聚类（conceptual clustering）中，一组对象只有当它们可以被一个概念描述时才形成一个簇。这不同于基于几何距离来度量相似度的传统聚类。概念聚类由两个部分组成：（1）发现合适的簇；（2）形成对每个簇的描述。在这里，追求较高类内相似度和较低类间相似度的指导原则仍然适用。