数据流挖掘中的聚类方法综述
徐天音?
(南京大学计算机科学与技术系, 南京 210093)
A Survey of Clustering Methods in Mining Data Streaming
Tianyin Xu*
(Department of Computer Science and Technology, Nanjing University, Nanjing 210093, China)
Abstract: The research to data streaming model has recently gained a high attraction due to its applications, including real-time surveillance systems, network intrusion detection and click streams. Clustering, one of the most important problems in streaming mining, has recently been highly explored because its application to data summarization and outlier detection. Due to the characteristics of data streaming against traditional data mining technique, new requirements and challenges have been proposed. This paper is a survey of various kinds of clustering methods in mining data streaming. In this paper, we’ll make an effort to review the state-of-the-art of clustering methods of data streaming mining and provide a big picture of this domain. To achieve this goal, we’ll first introduce the basic concepts, requirements and fundamental techniques. Then, we’ll look back into history to track the development of the clustering methods. After describing some classic and popular clustering algorithms, we’ll discuss what problems have already been solved. At last, we’ll put forward some further research issues in this domain.
Key words: Clustering; Data Streaming; Data Mining; Clustering Data Streaming; Streaming Mining
摘 要: 近期，随着诸如实时监控系统、网络入侵检测和web上用户点击流等动态的应用环境源源不断地产生海量的、时序的、快速变化的和潜在无限的数据流，对数据流挖掘的研究变得重要而富有意义。聚类分析作为数据流挖掘领域的一个重要问题，在近期被高度重视和广泛研究。由于数据流模型不同于传统数据集的特殊性质，新的要求和挑战应运而生。本文对数据流挖掘中各种聚类分析算法和处理框架做了综述。文章力图回顾数据流聚类分析领域的最近发展水平，提供给读者该领域的一个清晰的蓝图。为了实现这个目标，我们将首先介绍数据流聚类的基本概念、要求和底层的支撑技术。然后，我们将回顾历史，追寻各类数据流聚类算法和处理框架的发展轨迹将有助于深入理解这些算法。在详细描述一些经典和流行的聚类算法和处理框架后，我们将讨论该领域中哪些问题已经得到解决。最后，我们将展望未来，提出数据流聚类领域中进一步的研究热点和研究方向。
关键词: 聚类; 数据流; 数据挖掘; 数据流聚类; 数据流挖掘
?作者简介: 徐天音，南京大学计算机科学与技术系，研究生
2
1 引言（Introduction）
1.1 数据流
随着通信技术和硬件设备的不断发展，尤其是小型无线传感设备的广泛应用，数据采集变得越来越便捷和趋于自动化。新兴的应用领域，诸如实时监控系统、气象卫星遥感、网络通信量监测和电力供应网等等，每时每刻都在源源不断地产生大量的数据。与传统的数据集不同，这些数据是海量的（massive）、时序的（temporally ordered）、快速变化的和潜在无限的（potentially infinite）。[1]我们称这样的数据形态为数据流（Data Steaming，简称Streaming），并用数据流模型（Data Streaming Model）来描述它。
1.2 数据流挖掘算法的特点
由于数据流的特性，将传统的OLAP和数据挖掘方法用之于数据流是不可行的。其主要表现在：
（a）数据流中的数据是海量的，所以不可能在内存及硬盘上存储整个流数据集。甚至问题不仅在与有太多的数据，而在于需要记录的属性值的定义域（全域）都相当大[1]；
（b）同样因为数据量巨大，传统的多遍扫描数据的挖掘方法是不切实际的。所以对数据流的挖掘应该是一个单遍扫描的过程（one-pass scan）；
（c）数据流是快速变化的，所以不可能看到数据流的中的每一个数据元素（data point），我们只能通过分析部分数据元素来做出决策；
（d）数据流是时序的，所以对流中数据元素的访问只能是单次线性的（linear scan）。即数据元素只能按其流入顺序依次读取一次，随机访问是不现实的；
（e）大多数应用要求很快的响应时间，并且挖掘应该是一个连续、在线的过程，而不是偶然进行一次[2]；
（f）数据流往往天生就是高维的（High-Dimensional）[3]。
1.3 聚类分析
聚类分析（Clustering Analysis）是数据挖掘领域中一个重要的研究课题。聚类（Clustering）是指对一个已给的数据对象集合，将其中相似的对象划分为一个或多个组（称为“簇”，Cluster）的过程[3]。同一个簇中的元素是彼此相似的，而与其它簇中的元素相异[1]。聚类分析作为独立的工具有着广泛的应用场景，并且可以（并且常常）作为数据挖掘中的其他部分（如特征和预测）的预处理过程[1]。
1.4 数据流挖掘中的聚类分析及其要求
聚类分析已经被广泛研究了许多年，已经有许多有效的方法用于聚类静态数据集。但是由于上述的数据流本身的特性（见 1.2）造成的诸多限制，传统的聚类方法不能直接运用到数据流聚类上。我们需要的是适合于数据流模型的、仅使用有界内存和有界处理时间的单遍扫描数据的高效聚类方法。
文献[4]中总结了除满足前述数据流本身的特性外，一个好的数据流聚类算法应该具备的3个要求：（a）对已发现的簇提供一个简洁的表示方法（representation）；
（b）对新的数据元素的处理应该是个增量式的方式（incremental processing），并且应该它是快速的；
（c）有清晰而快速地孤立点检测（outlier detection）的能力。
随着逐渐增多的应用领域持续不断地产生大量的数据流信息，计算机系统的存储、计算和通信能力受到了极大的挑战。在最近几年里，越来越多的数据流聚类分析算法被提出和发展以面对这些挑战。本文将回顾历史、展望未来，深入讨论数据流聚类分析算法的昨天、今天和明天。
1.5 文章的组织（Overview of the Paper）
本文余下部分组织如下：第2部分介绍了数据流聚类的预备知识，包括一些基本概念和支撑技术。我们将在第3部分回顾历史，追寻各类方法的发展轨迹能让我们更好地理解这些数据流聚类算法。而各种具体的聚类分析算法和技术将分别在第4部分详细地介绍和描述。第5部分讨论了已经解决的问题。在第6部分中，我们将展望未来的工作，包括已经提出的问题和更具开放性的主题。最后，第7部分总结了这篇综述。
3 2 预备知识（Preliminaries ）
2.1 基本概念（Basic Concepts ）
1). 数据流模型
数据流模型（data streaming model ）是一个带有时间戳（Time Stamp ）的多维数据点集合
1,...,k X X 。每一个数据点
i X 是一个包括d 维的多维数据记录（record ），表示为11(,...,)d i k X x x =。 2). 孤立点
孤立点（outlier ）是指这样的数据点：它与数据集的一般行为和模型不一致。它可能是度量或执行错误所导致，在数据挖掘中将其视为噪声或异常。
2.2 支撑技术（Fundamental Techniques ）
为了有效地处理数据流，我们需要新的数据结构、技术和算法[1]。我们没有无限大的空间去存储整个数据流，这就需要在精度和存储空间之间进行折衷。一般而言，近似的结果在很多应用领域已经足以满足要求。
Gaber 等在文献[6]中将底层的支撑技术分为两类：基于数据的（Data-based ）和基于任务的（Task-based ）。基于数据的技术力图仅仅处理整个数据集中的小部分数据或将数据转换成某种近似的小尺寸表示形式；而基于任务的技术则将目标瞄准了在时间和空间上更高效的解决方法。
2.2.1 基于数据的技术（Data-based Techniques ）
1). 抽样（Sampling ）
抽样作为一个经典的统计学方法，通过一定概率来决定一个数据元素是否被处理。这样可以避免处理整个数据流。但是在数据流模型中，抽样技术的问题是不可能预先知道流的长度。可以使用水库抽样（reservior sampling ）的技术来解决这个问题[1]：在“水库”中维护s 个候选的样本，形成目前看到的流的随机样本集，随着数据流的流动，新的数据元素都有一定的概率替代水库中的元素。
在数据流中使用抽样技术的另一个问题是数据流的流动速率是不稳定的。所以，对于那些需要监测不规则且上下浮动的数据流的应用，抽样技术并不是一个很好的选择。
2). 梗概（Sketching ）
梗概是一个将数据流中的数据向量做一个随机投影的过程。它建立这些分布向量（如直方图）的小空间汇总[1]。梗概广泛用于不同数据流的比较和聚集查询。梗概是对精度和存储空间进行折衷的极佳范例，但是同时，精度问题是它的主要缺陷。
3). 大纲数据结构（Synopsis Data Structure ）
大纲数据结构是通过应用概要技术（summarization techniques ），生成的比当前数据流小得多的数据结构。它是当前数据流的概要描述。已经被提出的概要技术包括：小波分析、直方图（histogram ）和频率矩（frequency moment ）等等。
当然，由于大纲数据结构不可能表示出原数据流的所有特性，使用大纲数据结构只能得到一个近似结果。
4). 聚集运算（Aggregation ）
聚集运算试图通过计算一些统计度量，诸如平均数和方差等来概括当前的数据流。不过类似所有统计学的方法，它不适合速率高度摇摆和分布式的数据流。但它仍然是数据流挖掘中的重要工具。
2.2.2 基于任务的技术（Task-based Techniques ）
1). 滑动窗口（Sliding Window ）
滑动窗口模型基于这样一个事实：“用户对于最近的数据更感兴趣。”这样，我们可以对少量的近期数据做细节分析，而对大量的历史数据，仅仅给出一个概要试图[6]。这样，只需存储小的数据窗口，减少了对内
4
存的需求。滑动窗口的一个缺陷是要求用户预先指定窗口的尺寸，而在很多应用中，窗口的大小不可能事先知道。
2). 衰减函数（Fading Function）
另一种强调近期数据的重要性、消减历史数据对计算结果影响的方法是衰减因子和衰减函数。数据元素在参与计算前，先经过衰减函数的作用。因此，每个数据元素对最终结果的影响将随着时间的推移逐渐减小。一种常用的衰减函数形式为指数形式，比如文献[7]中提出的Den-Stream算法使用的衰减函数为λ>。
()2t
f tλ??
=，其中0
3). 倾斜时间框架（Titled Time Frame）
滑动窗口和衰减函数都只能在单一时间维的窗口上得到计算结果。然而，很多应用要求在不同的时间粒度层上进行分析和挖掘。比如，用户通常对细粒度层上的当前变化感兴趣，而在粗粒度层上对长期变化感兴趣[1]。
为此，我们可以构建不同层次的时间粒度窗口。最近的数据在最细的粒度层上记录和运算，较久远的数据在较粗的粒度上记录和运算[1]。这样，我们不仅可以满足需求，而且不会占用太多的存储空间。更重要的是，我们可以构建适合应用需要和当前存储条件的粒度层。这样的时间维模型被称为“倾斜时间框架”。
Han和Kamber在文献[1]中介绍了三种倾斜时间框架模型：自然倾斜时间框架模型（natural）、对数尺度倾斜时间框架模型（logarithmic scale）和渐进对数时间框架模型（progressive logarithmic）。如下图所示：
图1[1]倾斜时间框架的三种模型
Aggarwal等在文献[8]中提出的CluStream聚类算法就是基于一种称为Pyramidal Time Frame的渐进对数倾斜时间框架模型，如下表所示：
Table 1 [8]An example of snapshots stored for α=2
表1 [8] 金字塔时间框架模型（α=2）
让我们来看看被广泛使用的渐进对数时间框架：在表1[8]中，流数据快照（snapshot）按照不同的时间粒度被存储在不同的时间粒度层上。令i=Order of Snapshot（表格左边一栏的数据），则快照的时间间隔为αi（这里，底数α=2）。这样，距离当前越近的时间戳，快照存储的密度就越高。并且，渐进对数时间框架维护了一个替代算法，使新的流数据到来时能插入正确的时间粒度层，以替代最老的数据。
注意到表1[8]中的金字塔时间框架模型与图1[1](c)中的渐进时间框架模型有所不同：即不同时间粒度层中的数据存在重叠（表中划横线的数据即为重叠数据）。并且可知，重叠数据为每层上能被αi+1整除的数据。
5 3 发展和演化历史（History）
忘记过去的人，注定要重蹈覆辙。——George Santayana
创造新方法的一个绝佳途径是扩展和改进原有的方法，以适应新的应用和需求。事实上，大多数面向数据流的聚类算法正是通过扩展传统数据集上的聚类算法，使之适应数据流模型而得到的。回顾一下数据流的发展和演化历史，将有助于我们更深入地理解隐藏在各类数据流聚类算法背后的思想和灵感。
Han和Kamber在文献[1]中将传统的聚类算法分为5类：划分方法、层次方法、基于密度的方法、基于网格的方法和基于模型的方法。通过扩展这些类别中的各种算法，大量面向数据流应用的聚类算法破茧而出。
下面，让我们看看各类数据流聚类算法的发展和演化过程。
3.1 扩展划分方法（extending Partitioning Methods）
划分方法将包含n个数据元素的数据集组织成k个划分（k≤n），其中每个划分代表一个簇[1]。已提出的划分方法包括k-平均算法（k-Means）和k-中心点算法（k-Medoids）等。
Guha等在文献[9,10]中扩展了k-平均算法来处理数据流。他们提出的算法仅仅使用单遍扫描，并且需要存储空间相对较少。算法的时间复杂度和空间复杂度分别为O(nk)和O(nε)，其中n是数据元素的个数、k 是簇中心点的个数，ε<1。
Babcock等在文献[11]中使用一种称为指数直方图（EH, exponential histogram）的数据结构来改进Guha等人的算法。算法思想没有改变，仅仅用EH结构来实现簇的合并。
Charikar等在文献[12]中使用分而治之（Divide and Conquer）的策略改进了k-平均算法的性能。该算法首先将数据分块，然后通过计算各个小数据块的汇总信息来得到最终的结果。
基于k-平均算法，O’Challagham等在文献[13]中提出了STREAM算法。STREAM算法采用分级聚类的技术，并引入LSEARCH算法改进了k-Means算法，得到了更好的性能和更高质量的结果簇。
3.2 扩展层次方法（extending Hierarchical Methods）
层次方法对数据元素集合进行层次的分解，形成一棵由聚类组成的树[1]。典型的层次方法是BIRCH算法（Balanced Iterative Reducing and Clustering using Hierarchies），此外还有ROCK、Chameleon和CURE等。
Aggarwal等在文献[8]中扩展了BIRCH算法中聚类特征（clustering feature）的概念，提出了CluStream 算法。这是一个数据流聚类的处理框架，它把聚类过程分为两个部分：联机的微聚类（microclustering）和脱机的宏聚类（macroclustering）（后面的部分将会详细地介绍）。CluStream的提出的这个两阶段处理框架被许许多多后来的数据流聚类算法所采用和遵循。
在文献[3]中，Aggarwal等针对高维数据流，改进了CluStream算法，提出了HPStream算法。HPStream基于“众多数据流天生就是高维的。[3]”这个事实，通过引入投影技术（project clustering）和衰减簇结构（fading cluster structure），来更好地支持高维数据流的聚类分析。CluStream和HPStream是两种被广泛认可、并且十分流行的数据流聚类算法。
Udommanetanakit等在文献[5]中提出的E-Stream算法，是对HPStream的一个很好的补充。
3.3 扩展基于密度的方法（extending Density-Based Methods）
绝大部分的聚类算法是基于对象之间的距离度量，这样的聚类方法只能发现球状的簇，但是在对任意形状的簇进行聚类时会遇到困难[1]。基于密度的方法旨在解决这个问题。这类方法将簇看作数据空间中被低密度区域分割开的高密度数据元素区域[1]。DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法是一个被广泛使用的基于密度的聚类方法。此外还有OPTICS、DENCLUE等基于密度的算法。
Cao F等在文献[7]中扩展了DBSCAN算法，提出了面向数据流的基于密度的聚类算法DenStream。它采用CluStream算法中提出的两阶段处理框架，并引入了潜在簇结构和孤立点簇结构。实际上，当聚类请求到达时，DenStream仍然采用DBSCAN算法来得到最后的聚类结果。
6
3.4 扩展基于网格的方法（extending Grid-Based Methods）
基于网格的方法把数据元素空间量化为有限数目的单元，形成一个网格结构[1]。所有的聚类操作都在这个网格结构上进行[1]。基于网格的算法往往跟基于密度的算法结合使用，如CLIQUE算法。这类算法的一个显著优点是它的运行速度很快。
Chen等在文献[14]中提出的D-Stream就是一个基于网格和密度的数据流聚类算法。它使用密度网格（Density grid），基于密度和网格产生高质量的聚类结果。
Bhatnagar等在文献[15]中提出的ExCC（Exclusive and Complete Clustering of Streams）算法也是基于网格和密度的数据流聚类算法。ExCC算法将目标瞄准了簇聚类的完备性（completeness）和排他性（exclusiveness），提出了完备性聚类的概念。
3.5 基于模型的方法（Model-Based Methods）
基于模型的方法试图为数据集假定一个数学模型，诸如统计学模型和神经网络模型[1]。基于模型的方法如EM算法（Expectation-Maximization）、COBWEB等。目前还没有类似的方法被扩展应用到数据流聚类分析中。但如果必须生硬的划分，下面介绍的回顾分析的方法是基于数据模型的。
3.6 回归分析方法（Regression Analysis Methods）
Motoyoshi等在文献[17]中提出了利用回归分析实现数据流聚类的算法CFR（Clustering using F-value by Regression analysis）。回归分析的方法在预先假设数据元素具有局部线性（local linearity）的前提下，利用数学函数来进行一个多变量分析（multi-variable analysis）。回归分析方法分为初始化和合并两个步骤。此外，它的初始簇集是通过数学函数构建的，而不像基于k-平均的算法那样近似地得到。
图2数据流聚类算法的发展与演化示意图
图2总结了从传统数据集的聚类算法到面向数据流的聚类算法的发展和演化过程。我们的罗列是不完全的，还有一些在发展过程中的优秀算法和思想没有出现在图中。诸如，Domingos等扩展了机器学习中的算法，提出的基于Hoeffding界和k-平均算法的VFKM算法（Very Fast K-Means）；Gaber等提出的基于AOG（Algorithm Output Granularity）的面向传感器网络中数据流的LWC算法（Lightweight Clustering）等等[6]。
7 4 数据流聚类算法（Methods and Algorithms ）
我们将在这个部分中相对深入和详细地介绍具体的数据流聚类算法。由于已经存在大量的数据流聚类算法，所以介绍不可能面面俱到。我们的原则是选择有代表性的经典算法，如果它还是流行的，那就再好不过了。对于在第3部分中划分出的4个类别，每个类别将至少有一个算法出现在本部分中。
4.1 STREAM 算法
STREAM 算法聚焦于解决k-中位数问题（k-medians ），即把度量空间中的n 个数据点聚类成k 个簇，使得数据点与其簇之间的误差平方和（SSQ ）最小[1]。
STREAM 算法处理m 个数据点的桶中的数据流，桶的大小与内存相符。算法把每个桶的数据点分成k 个簇，并且仅仅保留k 个簇中心点（而丢弃其余的数据）来汇总桶中的所有数据。每个中心点的权（weight ）为该簇中数据点的个数。随着数据流的流入，这个过程不断地被重复，每次处理的数据个数为m 个。
此外，STREAM 算法使用LSEARCH 算法改进了k-平均算法，使“k ”更灵活：在算法的中间步骤中，簇的个数不再是一个固定的值，而是一个更合理的值，仅仅在算法结束时趋向于k 。
如上所述，STREAM 算法实现了单次扫描，时间复杂度为O(kn)。
STREAM 算法与传统数据的聚类算法相比（O’Challaghan 在文献[13]与BIRCH 相比较），有更好的性能，并能产生更高质量的聚类结果。但是，STREAM 算法没有考虑数据流的演变，即算法没有给予最近的数据较大的权重。这样，聚类的结果可能受控于过期的数据点。此外，STREAM 算法更趋近与一个批处理的过程，无法给出一个anytime 的回应，即算法无法在任意时刻给出当前数据流的聚类结果。最后，STREAM 的不足还包括无法给出不同时间粒度的聚类结果等等。
4.2 CluStream 算法框架
确切地说，CluStream 远非算法这么简单，而是一个数据流的聚类分析框架。CluStream 算法解决了STREAM 算法的两个问题。即它是增量式（incremental ）的聚类算法，在每个数据项到来时进行处理，能给出anytime 的回应；并且，它使用Pyramidal 时间框架（见2.2.2(3)部分），能给出不同时间粒度的聚类结果。这对于希望分别考察诸如上周、上月以及去年的聚类分析结果的用户意义重大！
CluStream 算法的开创性贡献是提出了将聚类分析的过程分为联机和脱机两个部分的处理框架。联机部分使用微簇（microcluster ）计算和存储数据流的汇总统计信息，实现增量的联机聚类查询；脱机部分则进行宏聚类（macroclustering ），利用Pyramidal 时间框架提供用户感兴趣的不同时间粒度上的聚类结果。CluStream 的这个两阶段处理框架被许许多多后来的数据流聚类算法所效仿和采纳。
CluStream 中的微簇由聚类特征（CF ，Clustering Feature Vector ）来定义，该“聚类特征”是BIRCH 算法中的CF 在时间域上的扩展。带时间戳T 的d 维数据点集的微簇被定义为(2? d + 3)元组( CF21n i i T ...i 1n i X X (x)
, CF1x , CF2t , CF1t , n )。其中，矢量CF2x 和CF1x 分别是每维数据值的平方和及累加和，如第p 维的CF2x 和CF1x 分别是和21()j n p i j x =∑1j n
p i j x =∑；类似的，标量CF2t 和CF1t 分别是时间戳的平方和及累加和；n 则是数据点的个数。所有的微簇将作为整个数据流的快照被存储在Pyramidal 时间框架的相应时间点上。
由BIRCH 中CF 的可加减性，不难推导出CluStream 中的聚类特征的可加减性。籍此，CluStream 算法成为一个增量式的处理过程。回顾1.4节，这是数据流聚类算法的基本要求之一。
联机的微簇维护过程由初始化和更新阶段组成：首先初始化q 个微簇M 1…M q ，q 根据内存的情况取尽可能大的值，q 个微簇根据当前数据的统计信息用k-平均算法得到。然后，更新微簇。每个新数据点根据是否落在某个微簇的边界之内，选择加入某个微簇或者新建一个微簇。前者根据可加性被已存在的微簇“吸收”，后者则需要删除一个最近最少用的微簇或者合并存在的微簇以保持q 值不变。
8
脱机部分实现用户指导的宏聚类和聚类演变分析[1]。宏聚类提供用户要求的不同时间粒度的聚类结果；聚类演变分析考察聚类结果如何随时间变化。通过Pyramidal时间框架和聚类特征的可加减性，这两点都不难实现。前者根据当前时间t c和用户指定的时间范围h，在Pyramidal时间框架中找到t时刻的快照S(t)和(t c-h)时刻的快照S(t c-h)，相减得到(t c-h)到t c之间生成的微簇集N(t c, h)。N(t c, h)即是加权虚拟点集。然后用STREAM算法进行聚类，得到h时间范围内的数据流聚类结果。
聚类演变分析（Evolution Analysis）告诉用户在哪些数据点在t1时刻的簇中出现而在t2时刻的簇中消失，哪些数据点在两个时刻的簇中都存在。给定t1、t2和h，计算出N(t1, h)和N(t2, h)。通过比较N(t1, h)和N(t2, h)，就不难回答上述的问题。
CluStream通过使用倾斜时间框架，保存了数据流演变的历史信息，在数据流变化剧烈时仍可以产生高质量的聚类结果，并且提供了丰富的功能[1]。但是，它没有考虑历史数据的衰减问题，即没有体现出近期数据的重要性。此外，当被应用于高维数据流的聚类时，CluStream算法往往表现不佳。
4.3 HPStream算法框架
针对CluStream的两点不足，Aggarwal等在次年提出了HPStream算法框架（High-dimensional Projected Stream Clustering method）。HPStream针对高维数据流，较之CluStream主要做了如下改进：首先，HPSream 引进了投影聚类技术（projected clustering）来处理高维的数据流，这比STREAM和CluStream中对所有相关维做全维聚类（full dimensional clustering）要高效和合理。其次，与CluStream在整个数据流上计算微簇不同的是，HPStream使用衰减簇结构（fading cluster structure）来保存历史数据。衰减簇结构使用衰减因子，随着时间的推进，不断衰减历史数据对当前聚类结果的影响，更好地将当前数据和历史数据集成起来。
文献[3]中通过对网络入侵检测和森林覆盖类型两种流数据集进行实验。结果表明HPStream在存储性能和处理速度上都优于CluStream。HPStream算法目前已成为主流的数据流聚类算法之一。
4.4 E-Stream算法
E-Stream算法将目光瞄准了数据流的演化过程描述。算法主要通过定义和支持5种不同的演化类型来表示数据流聚类的演化行为，以此改进目前存在的数据流聚类算法。这5种类型分别为：出现（Appearance）、消失（Disappearance）、自演化（Self-evolution）、合并（Merge）和分裂（Split）。
算法的主要流程框架见图3：
图3 E-Stream数据流聚类算法主框架[5] 图4 DenStream的联机处理框架[7]算法以接受一个新的数据元素作为开始（第1行）；然后衰减所有簇，并删除没有足够权值的簇（第2行）；第3行进行直方图分析，执行簇的分裂；第4行检测且合并交迭的簇；第5行检测簇的数量是否超过限制，如果超过则合并最相近的簇；第6行检测各个簇的是否处于活跃状态；7-10行将新的数据点插入到最邻近的簇中，如果找不到最邻近的簇，则将该数据点视为孤立点；最后，控制流返回算法的顶部重新等待新的数据。其中，FCH是E-Stream算法中使用的直方图衰减结构（Fading Cluster structure with Histogram）。
9
4.5 DenStream算法
扩展划分和层次的方法，诸如STREAM、CluStream和HPStream等算法的主要问题在于：它们仅仅对球形的数据流进行聚类分析时表现良好，但由于采用距离度量，它们不能很好地处理任意形状的数据流。
DenStream算法扩展了传统数据集聚类算法中基于密度的方法DBSCAN，着眼于处理任意形状的数据流聚类问题。同时，它强调了孤立点检测问题，将孤立点与正常数据元素区分开来。
DenStream算法沿袭了CluStream的处理框架，把聚类分析的过程划分为联机和脱机两个部分。
在联机部分中，算法维护了两类微簇结构：潜在微簇（p-micro-cluster）和孤立点微簇（o-micro-cluster），这两个微簇结构的不同之处仅仅在于其约束条件——密度小于某个阈值的簇被当作孤立点簇，而密度超过该阈值的簇被视为潜在微簇。当一个新的数据点到来时，算法（1）首先试图将它合并到其最邻近的p-micro-cluster 中；若失败，则（2）试图将其合并到最邻近的o-micro-cluster中去。若合并成功，检测该o-micro-cluster的密度是否大于阈值，若是，则将该o-micro-cluster转换为p-micro-cluster；（3）如果仍然无法找到最邻近的o-micro-cluster，则新建一个o-micro-cluster来容纳该数据点。该子算法的流程见图4。
对于脱机部分，当用户的聚类要求到来时，DenStream算法先忽略密度不足够的两类微簇，然后使用DBSCAN算法，对当前的p-micro-cluster和o-micro-cluster进行处理，得到聚类结果并返回。
4.6 D-Stream算法
D-Stream算法是一个基于密度和网格的算法。与DenStream算法一样，D-Stream算法也着力解决对任意形状的数据流聚类问题、强调了孤立点探测，并且依据密度来判断聚类。所不同的是，它是一个基于网格的算法，使用密度网格（Density Grid）结构。
D-Stream算法同样分为联机和脱机两个部分。联机部分将接受到的每个数据元素映射到某个网格中，而脱机部分计算这些网格的密度，并且基于密度将这些网格进行聚类。
Figure 5 Illustration of the use of density grid[14]
使用密度网格来进行聚类的过程如图5所示。联机部分持续地读入新的数据元素，并将多维的数据元素映射到多维空间内对应的离散的密度网格中，同时更新密度网格的特征向量。脱机部分在每隔一个时间隙（gap time）后动态地调整当前的簇。初始簇在第一个时间隙后形成，此后算法周期性地移除零星的簇，并调节已经生成的簇。通过使用网格结构，我们无需保留大量的原始数据，而仅仅需要对网格进行操作。
由于联机部分仅仅是将数据元素映射到相应的网格中，而无需计算距离或权值，D-Stream相比不使用网格的算法更高效。并且它的可扩展性更好，即算法不会随着数据量的增大而变慢。但是，D-Stream算法的问题是对于高维数据流，所需要的网格的数量可能会非常大。
4.7 CFR算法
CFR算法是一个基于回归分析的数据流分析算法。它预先假定数据元素集具有局部线性的性质。然后通过数学函数的方法实现聚类分析。算法使用Mahalanobis距离决定不同簇的相似度，同时考虑中心点和方差。
CFR算法的一个优势是它的初始簇集是通过数学函数构建的，而不似其它算法只能使用一个近似的或限定数目的初始簇集。但是CFR算法的前提注定了它的巨大局限性。
10
5 讨论（Discussion）
通过前述两部分的介绍，我们已经大体了解了数据流聚类技术的最新发展水平。这个部分对当前数据流聚类算法已经解决的问题进行了总结。
前述的面向数据流的聚类算法都是针对数据流的特点，旨在使用有界内存对潜在无限的数据流进行聚类分析。这些算法基本上都实现了单遍扫描，并且顺序地访问数据流中的元素。
几乎所有2003年以后的数据流聚类算法都实现了增量式的处理方式，可以满足用户anytime的聚类请求。E-Stream算法实现对数据流演化的表示方式。CluStream算法框架实现了数据流的聚类演变分析，这在网络入侵检测中非常有用，可以识别网络上新的攻击类型[1]。通过使用倾斜时间框架，聚类算法可以提供不同时间粒度的聚类结果。而使用衰减函数，近期的数据得到了更大的重视。几乎所有的两阶段聚类算法都可以支持用户的联机聚类请求。
为了处理高维数据流，HPStream算法使用了投影聚类技术。而大多数基于密度及网格的方法都能对任意形状的数据流进行聚类分析。
6 研究主题（Further Research Issues）
尽管已经提出了大量的算法和处理框架，数据流聚类分析依然是个极富挑战和快速发展的研究领域。随着大量的数据流产生于愈加广泛的应用领域，越来越多的研究主题不断涌现出来。在这个部分中，我们将对已经提出的研究问题和更具开放性的研究主题进行讨论。我们将这部分的内容一分为二：一般性（general）主题和面向具体应用领域的主题。值得一提的是，这些主题和研究点大都不仅仅局限与聚类分析这个方面，而可以被扩展到整个数据流挖掘的其它方面。
6.1 一般性主题
一般性主题主要针对理想的数据流模型（见2.1（1）），提出一些普遍适用的研究主题。
1). 数据流预处理
数据预处理技术（Data Pre-processing）被广泛应用于传统的数据挖掘中。数据预处理可以改进数据的质量，从而有助于提高其后的挖掘过程的精度和性能[1]。但在数据流挖掘中，预处理技术应用得并不广泛。问题在于如何设计一个轻量级的预处理过程，使其能够较好地面向数据流，以改进聚类分析及其它挖掘结果。
2). 模型拟合：扩展基于模型的方法
注意3.5节，传统数据集聚类方法中的基于模型的聚类方法很少被扩展到数据流聚类领域。扩展基于模型的方法，找到一个适用于数据流聚类分析的模型是一个可供选择的方向。
3). 形式化数据流的计算
数据流挖掘的一个主要目标是将数据流挖掘技术形式化为计算理论。这种形式化将推动数据流挖掘算法的设计和发展[6]。近似技术和统计学习理论（statistical learning theory）是这种形式化的潜在基础[6]。
4). 更细的划分：聚类不同形式的数据流
可以对数据流进行进一步的划分，如时间序列流、空间时间数据流、多媒体数据流等等。针对特定的数据流，特别是附加了语义信息的数据流，将会出现更多聚类算法和其它挖掘算法[1]。
6.2 面向具体应用领域的问题
已经提出的很多研究热点都是针对具体的应用领域，如高精度应用、无线传感器网络和分布式环境等等。特定的应用领域有着特定的需求。要想让数据流聚类分析以及其它数据流挖掘技术在特定领域有用武之地，就需要将领域知识与数据流挖掘技术很好的结合在一起。
1). 高精度需求
由于数据流是海量的和潜在无限的，而我们的存储空间和时间需求是有限的。所以，一般采用近似技术（如采样）来解决这个矛盾。几乎所有的数据流聚类算法都使用了某种程度上的近似，并且保证了误差界。
11
但在某些实际应用中，对聚类结果的精度会有一个比较高的要求。如何设计数据流聚类的算法，以满足特殊的高精度的需求，是一个有待解决的问题。遗憾的是，高精度往往意味着高的存储和时间代价。
2). 实时聚类
与高精度需求相似，某些关键的应用领域对反馈时间有着严格的要求。诸如事故检测、航空交通控制等应用领域必须“实时（Real-time）”给出数据流的聚类结果区域。虽然目前大多数的数据流聚类算法都已经实现了用户的联机聚类查询，但这些算法在时间上远远无法满足实时应用的需求。
3). 移动及无线设备的资源受限
随着数据流在移动和无线设备，特别是无线传感器网络中的大量生成，文献[6]把解决移动及无线设备中资源受限问题也归入数据流挖掘领域待解决的问题中。如何充分利用和节省这些设备的有限资源，如电池寿命和传输带宽等等。这些都需要更好的知识表示形式和传输方式。
4). 分布式数据流聚类算法
在实际的应用场景中，众多数据流在地理位置上是分布式的，比如交通检测、用户电话记录等等[4]。如何实现高效的分布式聚类算法是一个重要的研究主题。文献[20]对分布式数据流挖掘中的问题进行了详尽的讨论，并提出了四个研究方向。
7 结束语（Conclusions）
本文系统地介绍了数据流挖掘中聚类分析的基本概念、支撑技术、发展历史和最新的发展水平，展示了数据流聚类分析的发展现状和整体蓝图。并且，详细地探究了一些经典的、主流的聚类算法。在最后的部分中，文章展望了未来，提出了一些开放性的主题和进一步的研究热点。
数据流聚类，以及整个数据流挖掘都仍然处在一个起始阶段。不难预测，在未来几年中，越来越多更巧妙、更先进、更高效的新技术和新算法将会不断涌现出来。随着该领域中各个研究热点和存在问题的一一解决，势必推动相关应用领域诸如物理、天文、商业和金融等实际应用的飞速发展。
References
[1] Han J, Kamber M. Data Mining: Concepts and Techniques (Second Edition). Morgan Kaufmann , Elsevier Inc, 2006, 467-589.
[2] Yang Q, Wu X. 10 Challenging Problems in Data Mining Research. International Journal of Information Technology & Decision
Making.World Scientific Publishing Company, 2006. Vol.5,No.4(2006)597-604.
[3] Aggarwal C, Han J, Wang J, and Yu P. A Framework for Projected Clustering of High Dimensional Data Streams. Proceedings of
the 30th VLDB Conference, Toronto, Canada. 2004.
[4] Barbará D. Requirements for Clustering Data Streams. SIGKDD Explorations, 2003, 3(2), 23-27.
[5] Udommanetanakit K, Rakthanmanon T and Waiyamai K. E-Stream: Evolution-Based Technique for Stream Clustering.
Springer-Verlag Berlin Heidelberg, 2007, 605-615.
[6] Gaber M, Zaslavsky A and Krishnaswamy S. Mining Data Streams: A Review. SIGMOD Record, 2005, Vol.34,No.2 .
[7] Cao F, Ester M, Qian W and Zhou A. Density-Based Clustering over an Evolving Data Stream with Noise. Proceedings of the
SIAM Conference on Data Ming, 2006.
[8] Aggarwal C, Han J, Wang J, and Yu P. A Framework for Clustering Evolving Data Streams. Proceedings of the 29th VLDB
Conference, Berlin, Germany, 2003.
[9] Guha S, Mishra N, Motwani R and O’Callaghan. Clustering data streams. In Proceedings of the Annual Symposium on Foundations
of Computer Science, IEEE, 2000
[10] Guha S, Meyerson A, Mishra N, Motwani R and O’Callagham L. Clustering Data Streams: Theory and Practice. IEEE Transactions
on Knowledge and Data Engineering, 2003. VOL.15,NO.3,515~528
[11] Babcock B, Datar M, Motwani R and O'Callaghan L. Maintaining Variance and k-Medians over Data Streams Windows,
Proceedings of the 22nd Symposium on Principles of Database Systems, 2003.
[12] Charikar M, O'Callaghan L and Panigrahy R. Better streaming algorithms for clustering problems In Proc. of 35th ACM
Symposium on Theory of Computing, 2003.
12
[13] O'Callaghan L, Mishra N, Meyerson A, Guha S and Motwani R. Streaming-data algorithms for high quality clustering. Proceedings
of IEEE International Conference on Data Engineering, March 2002.
[14] Chen Y, Tu L. Density-Based Clustering for Real-Time Stream Data. KDD’07, August 12–15, 2007, San Jose, California,
USA.133-142.
[15] Bhatnagar V, and Kaur S. Exclusive and Complete Clustering of Streams. Springer-Verlag Berlin Heidelberg 2007, pp 629–638
[16] Lu Y, Huang Y. Mining Data Streams Using Clustering. Proceedings of the Fourth International Conference on Machine Learning
and Cybernetics, Guangzhou, 2005.
[17] Motoyoshi M, Miura T and Shioya I. Clustering Stream Data by Regression Analysis. The Australasian Workshop on Data Mining
and Web Intelligence (DMWI2004), Dunedin, New Zealand
[18] Lu Y, Huang Y. Mining Data Streams Using Clustering. Proceedings of the Fourth International Conference on Machine Learning
and Cybernetics, Guangzhou, 18-21 August 2005. .
[19] Dong G, Han J, Lakshmanan L, Pei J, Wang H and Yu P. Online Mining of Changes from Data Streams: Research Problems and
Preliminary Results. In Proceedings of the 2003 ACM SIGMOD Workshop on Management and Processing of Data Streams. In cooperation with the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, CA, Jun 8, 2003.
[20] Parthasarathy S, Ghoting A, Otey M. A Survey of Distributed Mining of Data Streams. Data Streams: Models and Algorithms,
Chapter 13, 289-305..
附中文参考文献
[21] 范明, 孟小峰等译. Han J, Kamber M. 数据挖掘:概念与技术. 机械工业出版社. 2005
[22] 孙玉芬, 卢炎生. 流数据挖掘综述. 计算机科学. 2007. Vol 34, No 1
[23] 蒋盛益, 李庆华, 李新. 数据流挖掘算法研究综述. 计算机工程与设计. Vol 26, No 5..
数据挖掘考试题目——聚类 一、填空题 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 边界
数据挖掘 引言 数据挖掘是一门交叉学科，涉及到了机器学习、模式识别、归纳推理、统计学、数据库、高性能计算等多个领域。 所谓的数据挖掘（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)
数据挖掘聚类问题(Plants Data Set)实验报告 1.数据源描述 1.1数据特征 本实验用到的是关于植物信息的数据集，其中包含了每一种植物(种类和科属)以及它们生长的地区。数据集中总共有68个地区，主要分布在美国和加拿大。一条数据(对应于文件中的一行)包含一种植物(或者某一科属)及其在上述68个地区中的分布情况。可以这样理解，该数据集中每一条数据包含两部分内容，如下图所示。 图1 数据格式 例如一条数据:abronia fragrans,az,co,ks,mt,ne,nm,nd,ok,sd,tx,ut,wa,wy。其中abronia fragrans是植物名称(abronia是科属，fragrans是名称)，从az一直到wy 是该植物的分布区域，采用缩写形式表示，如az代表的是美国Arizona州。植物名称和分布地区用逗号隔开，各地区之间也用逗号隔开。 1.2任务要求 聚类。采用聚类算法根据某种特征对所给数据集进行聚类分析，对于聚类形成的簇要使得簇内数据对象之间的差异尽可能小，簇之间的差距尽可能大。 2.数据预处理 2.1数据清理 所给数据集中包含一些对聚类过程无用的冗余数据。数据集中全部数据的组织结构是：先给出某一科属的植物及其所有分布地区，然后给出该科属下的具体植物及其分布地区。例如： ①abelmoschus,ct,dc,fl,hi,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ②abelmoschus esculentus,ct,dc,fl,il,ky,la,md,mi,ms,nc,sc,va,pr,vi ③abelmoschus moschatus,hi,pr 上述数据中第①行给出了所有属于abelmoschus这一科属的植物的分布地区，接下来的②③两行分别列出了属于abelmoschus科属的两种具体植物及其分布地区。从中可以看出后两行给出的所有地区的并集正是第一行给出的地区集
计算机工程应用技术本栏目责任编辑：贾薇薇 数据挖掘中的聚类分析方法 黄利文 （泉州师范学院理工学院，福建泉州３６２０００） 摘要：聚类分析是多元统计分析的重要方法之一，该方法在许多领域都有广泛的应用。本文首先对聚类的分类做简要的介绍，然后给出了常用的聚类分析方法的基本思想和优缺点，并对常用的聚类方法作比较分析，以便人们根据实际的问题选择合适的聚类方法。 关键词：聚类分析；数据挖掘 中图分类号：ＴＰ３１１文献标识码：Ａ文章编号：１００９－３０４４（２００８）１２－２０５６４－０２ ＣｌｕｓｔｅｒＡｎｌａｙｓｉｓＭｅｔｈｏｄｓｏｆＤａｔａＭｉｎｉｎｇ ＨＵＡＮＧＬｉ－ｗｅｎ （ＳｃｈｏｏｌｏｆＳｃｉｅｎｃｅ，ＱｕａｎｚｈｏｕＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｑｕａｎｚｈｏｕ３６２０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｌｕｓｔｅｒａｎａｌｙｓｉｓｉｓｏｎｅｏｆｔｈｅｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｓｏｆｍｕｌｔｉｖａｒｉａｔｅｓｔａｔｉｓｔｉｃａｌａｎａｌｙｓｉｓ，ａｎｄｔｈｉｓｍｅｔｈｏｄｈａｓａｗｉｄｅｒａｎｇｅｏｆａｐｐｌｉｃａ－ｔｉｏｎｓｉｎｍａｎｙｆｉｅｌｄｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｔｈｅｃｌｕｓｔｅｒｉｓｉｎｔｒｏｄｕｃｅｄｂｒｉｅｆｌｙ，ａｎｄｔｈｅｎｇｉｖｅｓｓｏｍｅｃｏｍｍｏｎｍｅｔｈｏｄｓｏｆｃｌｕｓｔｅｒａｎａｌｙｓｉｓａｎｄｔｈｅａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓｏｆｔｈｅｓｅｍｅｔｈｏｄｓ，ａｎｄｔｈｅｓｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｗｅｒｅｃｏｍｐａｒｅｄａｎｄａｎｓｌｙｚｅｄｓｏｔｈａｔｐｅｏｐｌｅｃａｎｃｈｏｓｅｓｕｉｔａｂｌｅｃｌｕｓｔｅｒｉｎｇｍｅｔｈｏｄｓａｃｃｏｒｄｉｎｇｔｏｔｈｅａｃｔｕａｌｉｓｓｕｅｓ． Ｋｅｙｗｏｒｄｓ：ＣｌｕｓｔｅｒＡｎａｌｙｓｉｓ；ＤａｔａＭｉｎｉｎｇ １引言 聚类分析是数据挖掘中的重要方法之一，它把一个没有类别标记的样本集按某种准则划分成若干个子类，使相似的样品尽可能归为一类，而不相似的样品尽量划分到不同的类中。目前，该方法已经被广泛地应用于生物、气候学、经济学和遥感等许多领域，其目的在于区别不同事物并认识事物间的相似性。因此，聚类分析的研究具有重要的意义。 本文主要介绍常用的一些聚类方法，并从聚类的可伸缩性、类的形状识别、抗“噪声”能力、处理高维能力和算法效率五个方面对其进行比较分析，以便人们根据实际的问题选择合适的聚类方法。 ２聚类的分类 聚类分析给人们提供了丰富多彩的分类方法，这些方法大致可归纳为以下几种［１，２，３，４］：划分方法、层次方法、基于密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。 ２．１划分法（ｐａｒｔｉｔｉｏｎｇｉｎｇｍｅｔｈｏｄｓ） 给定一个含有ｎ个对象（或元组）的数据库，采用一个划分方法构建数据的ｋ个划分，每个划分表示一个聚簇，且ｋ≤ｎ。在聚类的过程中，需预先给定划分的数目ｋ，并初始化ｋ个划分，然后采用迭代的方法进行改进划分，使得在同一类中的对象之间尽可能地相似，而不同类的中的对象之间尽可能地相异。这种聚类方法适用于中小数据集，对大规模的数据集进行聚类时需要作进一步的改进。 ２．２层次法（ｈｉｅｔａｒｃｈｉｃａｌｍｅｔｈｏｄｓ） 层次法对给定数据对象集合按层次进行分解，分解的结果形成一颗以数据子集为节点的聚类树，它表明类与类之间的相互关系。根据层次分解是自低向上还是自顶向下，可分为凝聚聚类法和分解聚类法：凝聚聚类法的主要思想是将每个对象作为一个单独的一个类，然后相继地合并相近的对象和类，直到所有的类合并为一个，或者符合预先给定的终止条件；分裂聚类法的主要思想是将所有的对象置于一个簇中，在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者符合预先给定的终止条件。在层次聚类法中，当数据对象集很大，且划分的类别数较少时，其速度较快，但是，该方法常常有这样的缺点：一个步骤（合并或分裂）完成，它就不能被取消，也就是说，开始错分的对象，以后无法再改变，从而使错分的对象不断增加，影响聚类的精度，此外，其抗“噪声”的能力也较弱，但是若把层次聚类和其他的聚类技术集成，形成多阶段聚类，聚类的效果有很大的提高。２．３基于密度的方法（ｄｅｎｓｉｔｙ－ｂａｓｅｄｍｅｔｈｏｄｓ） 该方法的主要思想是只要临近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对于给定的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法就可以用来滤处＂噪声＂孤立点数据，发现任意形状的簇。２．４基于网格的方法（ｇｒｉｄ－ｂａｓｅｄｍｅｔｈｏｄｓ） 这种方法是把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构上进行。用这种方法进行聚类处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。 ２．５基于模型的方法（ｍｏｄｅｌ－ｂａｓｅｄｍｅｔｈｏｄ） 基于模型的方法为每个簇假定一个模型，寻找数据对给定模型的最佳拟合。该方法经常基于这样的假设：数据是根据潜在的概 收稿日期：２００８－０２－１７ 作者简介：黄利文（１９７９－），男，助教。
数据挖掘简介 数据挖掘的任务 数据挖掘的任务就是从实例集合中找出容易理解的规则和关系。这些规则可以用于预测未来趋势、评价顾客、评估风险或简单地描述和解释给定的数据。通常数据挖掘的任务包括以下几个部分: 数据总结目的是对数据进行浓缩，给出它的紧凑描述。传统的也是最简单的数据总结方法是计算出数据库的各个字段上的求和值、平均值、方差值等统计值，或者用直方图、饼图等图形方式表示。数据挖掘主要关心从数据泛化的角度来讨论数据总结。数据泛化是一种把数据库中的有关数据从低层次抽象到高层次上的过程。数据泛化目前主要有两种技术:多维数据分析方法和面向属性的归纳方法。 多维数据分析方法是一种数据仓库技术，也称作联机分析处理(OLAP，onLineAnalysisProeess)。数据仓库是面向决策支持的、集成的、稳定的、不同时间的历史数据集合。决策的前提是数据分析。在数据分析中经常要用到诸如求和、总计、平均、最大、最小等汇集操作，这类操作的计算量特别大。因此一种很自然的想法是，把汇集操作结果预先计算并存储起来，以便于决策支持系统使用。存储汇集操作结果的地方称作多维数据库。多维数据分析技术已经在决策支持系统中获得了成功的应用，如著名的SAS数据分析软件包、Businessobject公司的决策支持系统Businessobjeet，以及IBM公司的决策分析工具都使用了多维数据分析技术。 采用多维数据分析方法进行数据总结，它针对的是数据仓库，数据仓库存储的是脱机的历史数据。为了处理联机数据，研究人员提出了一种面向属性的归纳方法。它的思路是，直接对用户感兴趣的数据视图(用一般的SQL查询语言即可获得)进行泛化，而不是像多维数据分析方法那样预先就存储好了泛化数据。方法的提出者对这种数据泛化技术称之为面向属性的归纳方法。原始关系经过泛化操作后得到的是一个泛化关系，它从较高的层次上总结了在低层次上的原始关系。有了泛化关系后，就可以对它进行各种深入的操作而生成满足用户需要的知识，如在泛化关系基础上生成特性规则、判别规则、分类规则，以及关联规则等。数据挖掘的分类 数据挖掘所能发现的知识有如下几种: .广义型知识，反映同类事物共同性质的知识; .特征型知识，反映事物各方面的特征知识; .差异型知识，反映不同事物之间属性差别的知识; .关联型知识，反映事物之间依赖或关联的知识; .预测型知识，根据历史的和当前的数据推测未来数据; .偏离型知识。揭示事物偏离常规的异常现象。 所有这些知识都可以在不同的概念层次上被发现，随着概念树的提升，从微观到中观再到宏观，以满足不同用户、不同层次决策的需要。例如，从一家超市的数据仓库中，可以发现的一条典型关联规则可能是“买面包和黄油的顾客十有八九也买牛奶”，也可能是“买食品的顾客几乎都用信用卡”，这种规则对于商家开发和实施客户化的销售计划和策略是非常有用的。 数据挖掘的方法 数据挖掘并非一个完全自动化的过程。整个过程需要考虑数据的所有因素和其预定的效用，然后应用最佳的数据挖掘方法。数据挖掘的方法很重要。在数据挖掘的领域里.有一点已经被广泛地接受，即不管你选择哪种方法，总存在着某种协定。因此对实际情况，应该具体分析，根据累积的经验和优秀的范例选择最佳的方法。数据挖掘中没有免费的午餐，也没
一、解答题（满分3０分，每小题5分) 1. 怎样理解数据挖掘和知识发现的关系?请详细阐述之 首先从数据源中抽取感兴趣的数据，并把它组织成适合挖掘的数据组织形式;然后,调用相应的算法生成所需的知识;最后对生成的知识模式进行评估，并把有价值的知识集成到企业的智能系统中。 知识发现是一个指出数据中有效、崭新、潜在的、有价值的、一个不可忽视的流程，其最终目标是掌握数据的模式。流程步骤:先理解要应用的领域、熟悉相关知识，接着建立目标数据集，并专注所选择的数据子集;再作数据预处理，剔除错误或不一致的数据；然后进行数据简化与转换工作；再通过数据挖掘的技术程序成为模式、做回归分析或找出分类模型；最后经过解释和评价成为有用的信息。 2.时间序列数据挖掘的方法有哪些，请详细阐述之 时间序列数据挖掘的方法有: １)、确定性时间序列预测方法:对于平稳变化特征的时间序列来说，假设未来行为与现在的行为有关，利用属性现在的值预测将来的值是可行的。例如，要预测下周某种商品的销售额，可以用最近一段时间的实际销售量来建立预测模型。 ２）、随机时间序列预测方法：通过建立随机模型,对随机时间序列进行分析,可以预测未来值。若时间序列是平稳的,可以用自回归(Auto Ｒegressiｖe，简称AR)模型、移动回归模型(Ｍovｉng Ａveｒage,简称ＭＡ）或自回归移动平均(Aｕto Regrｅssive Moｖiｎg Aｖeraｇe，简称AＲMＡ)模型进行分析预测。 3)、其他方法:可用于时间序列预测的方法很多,其中比较成功的是神经网络。由于大量的时间序列是非平稳的,因此特征参数和数据分布随着时间的推移而变化。假如通过对某段历史数据的训练，通过数学统计模型估计神经网络的各层权重参数初值，就可能建立神经网络预测模型,用于时间序列的预测。
海南大学 数据挖掘论文 题目：股票交易日线数据挖掘 学号：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 收盘价 收盘价是指某种证券在证券交易所一天交易活动结束前最后一笔交易的成交价格。如当日没有成交，则采用最近一次的成交价格作为收盘价，因为收盘价是当日行情的标准，又是下一个交易日开盘价的依据，可据以预测未来证券市场行情；所以投资者对行情分析时，一般采用收盘价作为计算依据。
聚类分析和关联规则属于数据挖掘这个大概念中的两类挖掘问题， 聚类分析是无监督的发现数据间的聚簇效应。 关联规则是从统计上发现数据间的潜在联系。 细分就是 聚类分析与关联规则是数据挖掘中的核心技术； 从统计学的观点看，聚类分析是通过数据建模简化数据的一种方法。传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、有序样品聚类、有重叠聚类和模糊聚类等。采用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.与层次聚类结合 经常会产生较好的聚类结果的一个有趣策略是，首先采用层次凝聚算法决定结果
第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所示。 在这些数据中，与空间位置相关的数据占了绝大多数。传统的空间知识发现的科研模式在大数据情境下已经不再适用，原因是传统的科研模型不具有普适性且支持的数据量受限， 受到数据传输、存储及时效性需求的制约等。为了从存储在分布方式、虚拟化的数据中心获取信息或知识，这就需要利用强有力的数据分析工具来将
数据挖掘实验报告（三） 聚类分析 姓名：李圣杰 班级：计算机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
摘要文章对数据挖掘中软计算方法及应用作了综述。对模糊逻辑、遗传算法、神经网络、粗集等软计算方法，以及它们的混合算法的特点进行了分析，并对它们在数据挖掘中的应用进行了分类。 关键词数据挖掘；软计算；模糊逻辑；遗传算法；神经网络；粗集 1 引言 在过去的数十年中，随着计算机软件和硬件的发展，我们产生和收集数据的能力已经迅速提高。许多领域的大量数据集中或分布的存储在数据库中[1][2]，这些领域包括商业、金融投资业、生产制造业、医疗卫生、科学研究，以及全球信息系统的万维网。数据存储量的增长速度是惊人的。大量的、未加工的数据很难直接产生效益。这些数据的真正价值在于从中找出有用的信息以供决策支持。在许多领域，数据分析都采用传统的手工处理方法。一些分析软件在统计技术的帮助下可将数据汇总，并生成报表。随着数据量和多维数据的进一步增加，高达109的数据库和103的多维数据库已越来越普遍。没有强有力的工具，理解它们已经远远超出了人的能力。所有这些显示我们需要智能的数据分析工具，从大量的数据中发现有用的知识。数据挖掘技术应运而生。 数据挖掘就是指从数据库中发现知识的过程。包括存储和处理数据，选择处理大量数据集的算法、解释结果、使结果可视化。整个过程中支持人机交互的模式[3]。数据挖掘从许多交叉学科中得到发展，并有很好的前景。这些学科包括数据库技术、机器学习、人工智能、模式识别、统计学、模糊推理、专家系统、数据可视化、空间数据分析和高性能计算等。数据挖掘综合以上领域的理论、算法和方法，已成功应用在超市、金融、银行[4]、生产企业 [5]和电信，并有很好的表现。 软计算是能够处理现实环境中一种或多种复杂信息的方法集合。软计算的指导原则是开发利用那些不精确性、不确定性和部分真实数据的容忍技术，以获得易处理、鲁棒性好、低求解成本和更好地与实际融合的性能。通常，软计算试图寻找对精确的或不精确表述问题的近似解[6]。它是创建计算智能系统的有效工具。软计算包括模糊集、神经网络、遗传算法和粗集理论。 2 数据挖掘中的软计算方法 目前，已有多种软计算方法被应用于数据挖掘系统中，来处理一些具有挑战性的问题。软计算方法主要包括模糊逻辑、神经网络、遗传算法和粗糙集等。这些方法各具优势，它们是互补的而非竞争的，与传统的数据分析技术相比，它能使系统更加智能化，有更好的可理解性，且成本更低。下面主要对各种软计算方法及其混合算法做系统性的阐述，并着重强调它们在数据挖掘中的应用情况。 2.1 模糊逻辑 模糊逻辑是1965年由泽德引入的，它为处理不确定和不精确的问题提供了一种数学工具。模糊逻辑是最早、应用最广泛的软计算方法，模糊集技术在数据挖掘领域也占有重要地位。从数据库中挖掘知识主要考虑的是发现有兴趣的模式并以简洁、可理解的方式描述出来。模糊集可以对系统中的数据进行约简和过滤，提供了在高抽象层处理的便利。同时，数据挖掘中的数据分析经常面对多种类型的数据，即符号数据和数字数据。nauck[7]研究了新的算法，可以从同时包含符号数据和数字数据中生成混合模糊规则。数据挖掘中模糊逻辑主要应用于以下几个方面： （1）聚类。将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称为聚类。聚类分析是一种重要的人类行为，通过聚类，人能够识别密集的和稀疏的区域，因而发现全局的分布模式，以及数据属性之间有趣的关系。模糊集有很强的搜索能力，它对发现的结构感兴趣，这会帮助发现定性或半定性数据的依赖度。在数据挖掘中，这种能力可以帮助
数据挖掘综述 1、产生背景 随着计算机的产生和大量数字化的存储方法的出现，我们借助计算机来收集和分类各种数据资料，但是不同存储结构存放的大量数据集合很快被淹没，便导致了结构化数据库以及DBMS的产生。 但是随着信息时代的到来，信息量远远超过了我们所能处理的范围，从商业交易数据、科学资料到卫星图片、文本报告和军事情报，以及生活中各种信息，这也就是“数据爆炸但知识贫乏”的网络时代，面对巨大的数据资料，出现了新的需求，希望能够更好的利用这些数据，进行更高层次的分析，从这些巨大的数据中提取出对我们有意义的数据，这就是知识发现（KDD,Knowledge Discovery in Databases），数据挖掘应运而生。 2、数据库系统技术的演变 1）20世纪60年代和更早 这个时期是数据收集和数据库创建的过程，原始文件的处理2）20世纪70年代---80年代初期 有层次性数据库、网状数据库、关系数据库系统 3）20世纪80年代中期—现在 高级数据库系统，可以应用在空间、时间的、多媒体的、主动的、流的和传感器的、科学的和工程的。 4）20世纪80年代后期—现在
高级数据分析：数据仓库和数据挖掘 5）20世纪90年代—现在 基于web的数据库，与信息检索和数据信息的集成6）现在---将来 新一代的集成数据域信息系统 3、数据挖掘概念 数据挖掘（Data Mining），就是从大量数据中获取有效的、新颖的、潜在的有用的，最终可以理解的模式的非平凡过程。数据挖掘，又称为数据库中知识发现（KDD,Knowledge Discovery in Databases），也有人把数据挖掘作为数据库中知识发现过程的一个基本步骤。 数据挖掘基于的数据库类型主要有：关系型数据库、面向对象数据库、事务数据库、演绎数据库、时态数据库、多媒体数据库、主动数据库、空间数据库、遗留数据库、异质数据库、文本型、Internet信息库以及新兴的数据仓库等。 4、数据挖掘特点和任务 4.1数据挖掘具有以下几个特点： 1）处理的数据规模十分庞大，达到GB,TB数量级，甚至更大2）查询一般是决策制定者（用户）提出的即时随机查询，往往不能形成精确的查询要求，需要靠系统本身寻找其可能感兴 趣的东西。 3）在一些应用（如商业投资等）中，由于数据变化迅速，因此
第八章聚类分析 设想要求对一个数据对象的集合进行分析，但与分类不同的是，它要划分的类是未知的。聚类(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）形成对每个簇的描述。在这里，追求较高类内相似度和较低类间相似度的指导原则仍然适用。
数据挖掘论文聚类分析论文 摘要：结合数据挖掘技术的分析，对基于数据挖掘的道路交通流分布模式问题进行了探讨，最后进行了实验并得出结果。 关键词：数据挖掘；聚类分析；交通流 road traffic flow distribution mode research based on data mining chen yuan (hunan vocational and technical college,changsha410004,china) abstract:combinded with the analysis of data mining technology,the distirbution model of traffic flow is discussed,and an experiment is carried out and its related conclusions are made in this paper. keywords:data mining;clustering analysis;traffic flow 道路网络上不同空间上的交通流具有相异的空间分布 模式，如“线”性模式主要代表有城市主干道，“面”状模式主要出现在繁华地段等。本文设计了一个道路交通流空间聚类算法以挖掘道路交通流分布模式，在真实数据和模拟数据上的实验表明spanbre算法具有良好的性能。
数据挖掘（datamining），也称数据库的知识发现（knowledgediseoveryindatabase）是指从随机、模糊的受到一定影响的大容量实际应用数据样本中，获取其中隐含的事前未被人们所知具有潜在价值的信息和知识的过程。 数据挖掘非独立概念，它涉及很多学科领域和方法，如有人工智能、数据统计、可视化并行计算等。数据挖掘的分类有很多，以挖掘任务为区别点，可以划分为模型发现、聚类、关联规则发现、序列分析、偏差分析、数据可视化等类型。 一、基于数据挖掘的道路交通流分布模式问题分析 类似化整为零各个击破的思想，交通区域划分通常会将整个交通网络分为若干个相互联系的子区域，再通过协调子区域各监测点交通信号配时方案，对个区域内运行的交通流在整体上进行管理与控制，从而达到优化整个道路网络的交通流。但是人为划定子区域的方案在实时改变因缺少自学习与自组织功能而导致整体方案出现滞后性。所以要加强路网通行能力，必须寻找突破人为划分、有效获取道路网络上交通流的空间分布模式的方法，以实现根据交通流的空间分布特点，合理划分路网交通区域，缓解交通拥挤的现状的目标。 在智能交通系统中应用最广泛的交通流信息采集方法 是电磁感应技术支撑的环形感应线圈检测器。这种流行甚广
Web数据挖掘综述 摘要：过去几十年里，Web的迅速发展使其成为世界上规模最大的公共数据源，因此如何从Web庞大的数据中提取出有价值的信息成为一大难题。Web数据挖掘正是为了解决这一难题而提出的一种数据挖掘技术。本文将从Web数据挖掘的概念、分类、处理流程、常用技术等几方面对Web数据挖掘进行介绍，并分析了Web数据挖掘的应用及发展趋势。 关键词：Web数据挖掘；分类；处理流程；常用技术；应用；发展趋势 Overview of Web Data Mining Abstract:Over the past few decades,the rapid development of Web makes it becoming the world’s largest public data sources.So how to extract valuable information from the massive data of Web has become a major problem.Web data mining is the data mining technology what is in order to solve this problem.This article introduces the Web data mining from its concept, classification,processing,and common techniques,and analyzes the application and the development tendency of Web data mining. Key words:Web Data Mining;Classification;Processing;Common Techniques;Application; Development Tendency 0.引言 近些年来，互联网技术的飞速发展，带来了网络信息生产和消费行为的快速拓展。电脑、手机、平板电脑等终端的普及，SNS、微博等Web2.0应用的快速发展，促进了互联网信息数量的急剧增长，信息资源前所未有的丰富。但同时，海量级、碎片化的信息增加了人们获取有效信息的时间和成本[1]。因此，迫切需要找到这样的工具，能够从Web上快速有效地发现资源，发现隐含的规律性内容，提高在Web上检索信息、利用信息的效率，解决数据的应用问题，Web数据挖掘正是一个很好的解决方法。 1.Web数据挖掘概念 Web数据挖掘，简称Web挖掘，是由Oren Etzioni在1996年首先提出来的[2]。Web数据挖掘是数据挖掘在Web上的应用，它利用数据挖掘技术从与Web相关的资源和行为中抽取感兴趣的、有用的模式和隐含信息，涉及数据库技术、信息获取技术、统计学、机器学习和神经网络等多个研究领域的技术[3]。 2.Web数据挖掘分类 Web上包括三种类型数据：Web页面数据、Web结构数据和Web日志文件[4]。依据在挖掘过程中使用的数据类别，Web数据挖掘可以分为Web内容挖掘，Web结构挖掘，Web 使用挖掘三类。 2.1Web内容挖掘 Web内容挖掘是从文档内容或其描述中抽取有用信息的过程。Web内容挖掘有两种策略：直接挖掘文档的内容和在其他工具搜索的基础上进行改进。根据挖掘出来的数据可以将