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