基于网格和密度的优化聚类算法研究及其在电信数据分析中的应用

摘要

数据挖掘是指从海量数据中提取有效的、新颖的、潜在有用的和最终可被理解的知识或信息模式的非平凡过程，是20世纪90年代初针对“数据丰富、知识贫乏”问题应运而生的一种新技术。为了有效地从海量数据中提取信息，数据挖掘算法必须具有良好的可伸缩性，也就是说，数据挖掘算法的运行时间必须是可预计的、可接受的。 聚类分析是数据挖掘的最主要功能之一，现有的典型聚类算法大致可以分为以下几种：划分的聚类方法、层次的聚类方法、基于模型的聚类方法、基于网格的聚类方法和基于密度的聚类方法等。在众多方法中，基于网格和密度的方法因聚类速度快，能处理噪声及发现任意形状的空间聚簇而受到了比较广泛的关注。然而，这些方法仍然存在着某些不足，对基于网格的方法而言：第一，由于空间划分时产生的单元数与维数呈指数增长，该方法多适用于维数相对较低的数据。第二，在一些基于空间划分的数据挖掘方法中，如基于单元的聚类算法，如果划分粒度越细，则聚类精度越高，但同时粒度越细生成的单元数也越多，造成算法效率下降。如果划分的粒度变粗，则算法精度难以保证；对基于密度的方法而言：第一，密度阈值τ的选择对聚类结果的影响非常大。如果τ值太高，则簇可能丢失。如果τ值太低，则本应分开的两个簇可能被合并。第二，如果存在不同密度的簇，那么很难找到一个适用于数据空间所有部分的单个τ值。 针对目前基于网格和密度聚类方法存在的问题，本文先后提出了三种新的改进算法，并通过广泛的实验，验证了提出的聚类算法的高效性，证实它们对具有不同分布特性的数据集都有非常好的适应性，能够输出理想的聚类结果。本文的主要工作和贡献点总结如下： (1)提出了空间密度单元的概念，并在此基础上提出了SUDBC算法。首先将被聚类的数据划分成若干个空间单元，然后基于空间单元密度将密度超过给定阈值的邻居单元合并为一个类。在存储空间单元时，通过建立哈希表提高查找速度。算法具有如下优点：不用计算两点间的距离；只需对数据进行一遍扫描，具有近似线性的时间复杂性；主要基于空间单元密度信息进行聚类，而空间单元密度信息比实际数据小得多，可以直接存储在内存中，因此适合聚类大规模数据集。 (2)提出了基于引力概念的聚类结果评估方法，并在此基础上提出了SECDU算法。通过遍历两个取值范围有限的整形参数，对数据集进行多遍聚类，然后利用提出的基于引力概念的评估函数对全部聚类结果进行评估，找到聚类质量最高的一个作为聚类算法的最终输出。这种利用引力概念对聚类结果进行质量评估的方法在国内外尚属首创。它将数据点看作具有单位质量的质点，将聚类结果看作质点分布的一种格局，认为一个高质量的聚类结果，其各个有效聚类内部的“凝聚力”应该尽可能的大，而噪音点受到的“吸引力”应该尽可能的小。 (3)提出了SECDU算法的改进算法SECDUF。通过爬山算法对SECDU进行优化，在保持聚类结果具有较高质量的同时，大大地加快了聚类速度。与SECDU相比，SECDUF的另一个优点是可以产生多个高质量聚类结果，这是因为爬山算法可以找到多个局部最优值。这个特点在聚类具有层次分布特性的数据集(如DS2)时，表现为能够找出不同密度的多个聚类结果。另外，SECDUF算法还具有聚类参数自行调整，无需人工干预等优点。 (4)最后，本文设计并实现了一个中国电信数据分析系统，主要包括聚类分析和OLAP两大部分。聚类分析部分将之前提出的几种聚类算法用于真实的电信数据分析，并针对存在的某些不足，进一步提出了一种改进的基于特征点分布的聚类算法CFPD，以使聚类分析模块达到识别具有相似特征的客户群，成为分析客户和形成市场策略基础的目的，真正做到了在恰当的时间，通过恰当的渠道，为恰当的客户提供恰当的服务，以满足其需要和愿望。OLAP部分针对客户发展情况、业务情况、收益情况、市场竞争分析和营销管理分析等几个主题，根据数据本身具有的语义特性来压缩生成包含各种“维度(Dimension)”的“立方体(CUBE)”，实现对电信CUBE的高效存储，并在此基础上，对电信数据CUBE以“钻取、切片、维度转换”等手段进行相关主题的OLAP多维动态查询、分析，以达到决策辅助支持的目的。

目录

文摘

英文文摘

声明

第一章前言

1.1问题提出

1.2数据挖掘概述

1.2.1数据挖掘过程

1.2.2数据挖掘方法分类

1.2.3数据挖掘的主要研究问题

1.3数据挖掘与其它相关技术

1.3.1数据挖掘与OLAP

1.3.2数据挖掘与数据仓库

1.4数据挖掘在电信业中的应用

1.4.1客户行为分析

1.4.2客户信用度分析

1.4.3交叉销售分析

1.4.4市场竞争分析

1.4.5客户流失分析

1.5本文研究的问题及组织结构

1.5.1研究的问题

1.5.2本文的贡献

1.5.3本文的结构组织

第二章聚类分析算法概述

2.1聚类分析的基本概念

2.1.1聚类的定义

2.1.2数据挖掘对聚类分析算法的典型要求

2.1.3相似性度量方法

2.2典型聚类算法及其研究进展评述

2.2.1划分聚类方法

2.2.2层次聚类方法

2.2.3基于密度的聚类方法

2.2.4基于网格的聚类方法

2.2.5基于模型的聚类方法

2.2.6聚类算法小结

2.3本章小结

第三章基于空间单元密度的聚类算法SUDBC

3.1问题提出

3.2相关概念

3.3数据存储结构

3.4 SUDBC算法

3.4.1数据预处理

3.4.2聚类过程

3.4.3参数的确定

3.4.4算法的复杂度分析

3.5 SUDBC算法的扩展

3.5.1对增量的数据处理

3.5.2数据流上的聚类

3.6性能测试与分析

3.6.1测试平台与测试方案

3.6.2测试结果与分析

3.7本章小结

第四章基于密度单元的自扩展聚类算法SECDU和SECDUF

4.1问题提出

4.2聚类质量评估

4.2.1相关概念

4.2.2基于引力概念的评估算法

4.3基本概念

4.4 SECDU算法

4.4.1聚类过程

4.4.2参数选择

4.4.3 SECDU算法举例

4.5 SECDUF算法

4.5.1基本爬山算法

4.5.2改进的爬山算法

4.5.3 SECDUF算法

4.6性能测试与分析

4.6.1测试平台与测试方案

4.6.2聚类及评估性能分析

4.6.3聚类质量测试

4.6.4聚类速度比较

4.6.5 SECDU和SECDUF的效率比较

4.6.6对具有层次分布特性数据集的聚类

4.6.7实验结论

4.7本章小结

第五章聚类算法及基于CUBE压缩的OLAP技术在电信数据中的应用

5.1项目背景

5.2聚类算法在电信数据中的应用

5.2.1系统的运行环境

5.2.2电信业客户特征的数据模型

5.2.3聚类分析

5.2.4聚类分析的进一步改进

5.3 OLAP在电信数据中的应用

5.3.1电信联机分析处理系统的架构设计

5.3.2电信联机分析处理系统的功能设计

5.3.3多维CUBE建模

5.3.4多维CUBE压缩存储

5.3.5多维CUBE查询算法

5.3.6 OLAP前端多维分析展示

5.4本章小结

第六章结束语

6.1本文的主要贡献与结论

6.2进一步的工作

参考文献

致 谢

攻读博士学位期间发表的论文

作者简介