当前位置：文档之家 › 数据流挖掘中的聚类方法综述

数据流挖掘中的聚类方法综述

  • 格式：pdf
  • 大小：750.67 KB
  • 文档页数：12

数据流挖掘中的聚类方法综述

徐天音∗

(南京大学 计算机科学与技术系, 南京 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,...,

kXX

。

每一个数据点

iX

是一个包括d维的多维数据记录（record），表示为1

1(,...,)d

ikXxx=

。

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

合集下载

面向大规模数据集的聚类算法研究

面向大规模数据集的聚类算法研究

面向大规模数据集的聚类算法研究

随着互联网和物联网技术的迅速发展，海量数据的产生与存储成为了现代社会一个重要的特征。对于这些海量的、高维度的数据，如何自动发现其中潜藏的内在结构，显得尤为重要。而这也正是聚类算法所要解决的问题。本文将就面向大规模数据集的聚类算法研究作一探讨。

一、聚类算法简介

聚类算法是一种被广泛应用于数据挖掘中的无监督学习算法。组合学、机器学习、数据挖掘、人工智能等不同领域均对其进行了研究。不同于有监督学习，聚类是一种自主学习的方法，尝试在没有标记或基准点的数据中，找到数据的内在规律或模式。

目前比较流行的聚类方法包括K-means、层次聚类、基于密度聚类等。其中，K-means是最广泛使用的算法之一。在任意欧几里得空间中，K-means算法通过把n个观测值分成k个类别来对数据进行分组。每个观测值都属于距其最近均值的类别，而这些类别则由其对应数据点的均值标识。K-means算法的时间复杂度为O(nkt)，其中k是簇的个数，t是算法重复迭代的次数。层次聚类是指在没有预先定义聚类数的情况下，以自底向上或自上向下的方式将数据样本分组。基于密度的聚类是通过密度相连点的组合来划分数据集，是一种特殊的层次聚类算法。

二、大规模数据集聚类算法的挑战

但是，对于大规模数据集，聚类算法面临很多挑战，在现有算法的基础上还亟需更严谨、高效、可扩展的算法。挑战包括但不限于：

1.高维度问题：随着数据维数增加，聚类问题变得更加困难。

2.数据稀疏性问题：大多数情况下，数据集中只有少量的数据点是有意义的，而其他数据点则大多是噪声和无意义的。 3.可伸缩性问题：对于大型数据集，一次性对所有数据进行聚类是不可行的，需要采用一些优化策略。

4.质量问题：聚类算法产生的结果往往需要专家进行修正和优化。

三、面向大规模数据集的聚类算法研究

针对上述挑战，面向大规模数据集的聚类算法研究已经成为研究热点之一。以下将从四方面介绍这方面的最新研究。

聚类分析法

聚类分析法

- 1 - 聚类分析法

聚类分析法（ClusterAnalysis）是一种基于模式识别及统计学理论的数据挖掘技术，它通过让数据集中的项以有联系的方式归入不同的簇（Cluster）来呈现其特征，以此发掘出隐藏在数据背后的所谓的“模式”和知识。聚类分析法主要应用于定性分析（Qualitative Analysis）、模式识别、决策分析（Decision

Analysis）、图象处理（Image Processing）、系统自动推理（System Inference）等领域，其主要性质属于非监督式学习。

基本流程

聚类分析法的基本流程包括：数据准备（Data Preparation）、预处理（Pre-processing）、聚类（Clustering）、结果评估（Result Evaluation）等步骤。

在数据准备阶段，需要完成原始数据的清洗、转换、结构化以及标准化等操作。而预处理步骤同样很重要，在此步骤中，可以得到样本的特征数据，并用于聚类模型的建立。

接下来，便是聚类的核心步骤了，完成聚类需要确定聚类的具体方法，例如层次聚类（Hierarchical Clustering）、基于密度的聚类（Density-Based Clustering）、均值聚类（K-means

Clustering）等。

最后便是评估结果，在这一步中，会根据聚类的执行情况以及聚类的结果，采用相应的评估指标，对聚类结果做出评价，确定聚类模型的合理性。 - 2 - 工作原理

聚类分析法的工作原理，主要是利用距离函数（Distance

Function）来度量数据项之间的距离，从而将数据项归入不同的簇。

常用的距离函数有欧氏距离（Euclidean Distance）、曼哈顿距离（Manhattan Distance）、闵可夫斯基距离（Minkowski

聚类分析的基本概念与方法

聚类分析的基本概念与方法

聚类分析的基本概念与方法

聚类分析（Cluster Analysis）是一种将数据分组或分类的统计学方法，通过将相似的对象归为同一组，使得组内的对象之间更加相似，而不同组之间的对象则差异较大。它是数据挖掘和机器学习领域中常用的技术之一，被广泛应用于市场分析、生物信息学、图像处理等领域。

一、聚类分析的基本概念

聚类分析基于相似性的概念，即认为具有相似特征的对象更有可能属于同一类别。在聚类分析中，每个对象都被视为一个数据点，而聚类则是将这些数据点分组。基本概念包括以下几点：

1. 数据点：数据集中的每个样本或对象都被看作是一个数据点，它具有多个特征或属性。

2. 相似性度量：聚类分析的关键是如何计算数据点之间的相似性或距离。常用的相似性度量包括欧氏距离、曼哈顿距离、闵可夫斯基距离等。

3. 簇/类别：将相似的数据点归为一组，这个组被称为簇或类别。簇内的数据点相似度较高，而不同簇之间的数据点相似度较低。

4. 聚类算法：聚类分析依赖于具体的算法来实现数据点的分组。常见的聚类算法有K均值聚类、层次聚类、密度聚类等。

二、聚类分析的方法 1. K均值聚类（K-means Clustering）：K均值聚类是一种迭代的聚类方法，它将数据点分成K个簇，每个簇代表一个样本集。算法的基本思想是通过最小化簇内数据点与簇中心之间的平方误差来确定最优的簇中心位置。

2. 层次聚类（Hierarchical Clustering）：层次聚类是一种基于树状结构的聚类算法，它根据数据点之间的相似性逐步合并或分割簇。层次聚类分为凝聚型和分裂型两种方法，其中凝聚型方法从单个数据点开始，逐步合并最相似的簇；分裂型方法从所有数据点开始，逐步分割最不相似的簇。

3. 密度聚类（Density-Based Clustering）：密度聚类基于密度可达的概念，将具有足够高密度的数据点归为一簇。核心思想是在数据空间中通过密度连通性来确定簇的边界，相对于K均值聚类和层次聚类，密度聚类能够有效处理不规则形状和噪声数据。

什么是聚类分析,它有哪些应用？

什么是聚类分析,它有哪些应用？

什么是聚类分析，它有哪些应用？

一、聚类分析的实现方式

聚类分析的实现方式有很多种，如下面几种：

1. 基于距离的聚类：

这种方法将数据点之间的距离作为相似性的度量，然后将距离最近的数据点聚在一起，并逐渐地将距离较远的数据点加入到不同的簇中。

2. 基于密度的聚类：

这种方法通过计算数据点的密度来确定簇边界，而不是使用距离来度量相似性。将密度较高的数据点聚集在一起，而将密度较低的数据点单独作为一个簇。

3. 基于层次的聚类：

这种方法将数据点逐层进行聚合，每一层都是由多个子层组成的。聚类过程一直持续到所有数据点都被分配到一个簇中，或者簇的数量达到预设的值。

二、聚类分析的应用领域

聚类分析作为一种重要的数据挖掘技术，在多个领域中都有着广泛的应用，下面介绍一些主要应用领域：

1. 市场细分： 聚类分析可以帮助企业将市场分割成不同的细分市场，然后根据每个细分市场的特点定制相应的市场策略。

2. 生物分类：

聚类分析在生物学领域中应用非常广泛，例如，可以用于分类分子或组分、成本分析以及微生物学等方面。

3. 网络流量分析：

聚类分析可以帮助网络管理员对网络流量进行分类，以便更好地了解网络中流动的数据类型，从而更好地优化网络性能。

4. 风险评估：

聚类分析可以用于对风险进行分类和评估，例如，可以将客户分类成高风险、中风险和低风险客户，以快速响应某些意外事件。

结论

聚类分析是一种非常有用的技术，可以用于许多不同的领域。以上只是聚类分析的一些基本理解和应用，随着技术的不断发展，聚类分析在未来也将有着更广泛的应用。