本书面向数据库知识发现的聚类任务，针对高维数据普遍具有的稀疏特征，系统阐述高维稀疏数据聚类知识发现的理论和方法。全书共12章，第1章和第2章系统总结聚类知识发现、高维稀疏数据聚类知识发现理论体系；第3～5章阐述高维稀疏数据聚类原理及分类属性数据、数值属性数据的系列聚类算法；第6～10章将高维稀疏数据聚类原理拓展到不完备数据、大规模数据、过程调整和参数自适应聚类；第11章阐述聚类趋势发现；第12章介绍高维稀疏数据聚类知识发现面向管理问题的应用、面向数据组织的应用及相关实现技术。 本书适用于数据挖掘领域的研究人员和应用人员，也可作为相关专业博士研究生、硕士研究生和本科生的参考书。

第1章　聚类知识发现
　　本章介绍数据库知识发现及其主要任务——聚类知识发现，给出聚类知识发现任务实现过程中不同取值类型数据差异度的计算方法，讨论几种主要的经典聚类方法及聚类方法的一些新进展。
　　1.1　数据库知识发现
　　本节首先介绍数据库知识发现的产生与发展及以数据挖掘为核心环节的处理过程，然后给出数据库知识发现的主要任务，*后讨论数据仓库与数据挖掘。
　　1.1.1　数据库知识发现的产生与发展
　　数据库的广泛应用和数据量的飞速增长，使人们迫切地感到需要新的技术和工具以支持从大量的数据中自动地、智能地抽取出有价值的信息或知识，于是数据库知识发现（knowledge discovery in database，KDD）技术应运而生。
　　数据库知识发现是从大量原始数据中挖掘出隐含的、有用的、尚未发现的信息和知识，其不仅被许多研究人员看作是数据库系统和机器学习等方面一个重要的研究课题，而且被许多工商界人士看作是一个能带来巨大回报的重要领域。“数据库知识发现”一词第一次出现是在1989年8月美国底特律召开的第十一届国际人工智能联合会议的专题讨论会上。1991年、1993年和1994年又分别举行过数据库知识发现专题讨论会。由于参加会议的人数逐渐增多，所以从1995年开始，每年都要举办一次数据库知识发现国际会议。随着研究的不断深入，人们对数据库知识发现的理解越来越全面，对数据库知识发现的定义也不断修改，下面是对数据库知识发现比较公认的一个定义：数据库知识发现是从数据集中识别出可信、有效、新颖、潜在有用以及*终可理解模式的高级处理过程。
　　作为一门交叉性学科，数据库知识发现受到来自各种研究领域学者的关注，所以有很多不同的名称。其中，*常用的术语是数据库知识发现和数据挖掘。相对来讲，数据挖掘[3]主要流行于统计学、数据分析、数据库和管理信息系统界；而数据库知识发现则主要流行于人工智能和机器学习界。随着数据库知识发现的迅速发展和逐渐被各界所了解，较为普遍的观点认为：数据挖掘是数据库知识发现中专门负责发现知识的核心环节；而数据库知识发现是一个交互式、循环反复的整体过程，除了包括数据挖掘，还包括数据准备和发现结果的解释评估等诸多环节。
　　1.1.2　数据库知识发现的处理过程
　　数据库知识发现的处理过程如图1-1所示，整个过程可以理解为三个阶段：数据准备（data preparation）、数据挖掘（data mining）、解释评估（interpretation and evaluation）[4]。
　　数据准备阶段的工作包括四个方面的内容：数据的净化、数据的集成、数据的应用变换和数据的精简。
　　数据的净化是清除数据源中不正确、不完整或其他方面不能达到数据挖掘质量要求的数据，如推导计算缺值数据、消除重复记录等。数据净化可以提高数据的质量，从而得到更准确的数据挖掘结果。
　　数据的集成是在数据挖掘所应用的数据来自多个数据源的情况下，将数据进行统一存储，并需要消除其中的不一致性。
　　数据的应用变换就是为了使数据适用于计算的需要而进行的数据转换。这种变换可能是现有数据不满足分析需求而进行的，也可能是所应用的具体数据挖掘算法对数据提出的要求。
　　数据的精简是对数据的数量进行缩减，或从初始特征中找出真正有用的特征来消减数据的维数，从而提高数据挖掘算法的效率与质量。
　　数据挖掘阶段首先要确定挖掘的任务或目的，如数据总结、分类、聚类、关联规则发现或序列模式发现等。在确定了数据挖掘任务后，就要决定使用什么样的数据挖掘算法。同样的，数据挖掘任务可以用不同的数据挖掘算法来实现，一般要考虑多方面的因素来确定具体的挖掘算法，例如，不同的数据有不同的特点，因此需要采用与之相关的算法来挖掘；用户对数据挖掘有着不同的要求，有的用户可能希望获取描述性的、容易理解的知识，而有的用户（或系统）的目的是获取预测准确度尽可能高的预测性知识。
　　需要指出的是，尽管数据挖掘算法是数据库知识发现的核心，也是目前研究人员主要努力的方向，但要获得好的挖掘效果，必须对各种数据挖掘算法的要求或前提假设有充分的理解。
　　数据挖掘阶段发现得到的模式，经过用户或机器的评估，可能存在冗余或无关的模式，这时需要将其剔除；也有可能模式不满足用户要求，这时则需要整个发现过程退回到发现阶段之前，如重新选取数据、采用新的数据变换方法、设定新的数据挖掘参数值，甚至换一种数据挖掘算法。另外，数据库知识发现*终是面向用户的，因此可能要对发现的模式进行可视化，或者把结果转换为用户易懂的方式进行表达。
　　1.1.3　数据库知识发现的主要任务
　　数据库知识发现的核心部分——数据挖掘，按照挖掘任务可以分为聚类知识发现、分类知识发现、关联规则发现、数据总结、序列模式发现、依赖关系或依赖模型发现、异常发现和趋势预测等。
　　聚类是一种基本的人类行为，在悠久的人类发展史中发挥着不可替代的作用[5]，其将数据对象分成若干个类或簇（cluster），使得同一类中的对象具有较高的相似度，而不同类中的对象差异度较大，进而识别隐藏在数据中的内在结构，应用非常广泛[6-8]，既可作为独立的方法来分析数据的分布情况，也可作为其他分析方法的数据预处理工具[9]。聚的依据是“物以类聚”，即按个体或数据对象间的相似性，将研究对象划分为若干类。在数据挖掘之前，数据类划分的数量与类型均是未知的，因此在数据挖掘后需要对数据挖掘结果进行合理的分析与解释。
　　分类知识发现是根据样本数据寻求相应的分类规则，然后根据获得的分类规则确定某一非样本个体或对象是否属于某一特定的组或类。在这种分类知识发现中，样本个体或对象的类标记是已知的。数据挖掘的任务在于从样本数据的属性中发现个体或对象分类的一般规则，从而根据该规则对非样本数据对象进行分类应用。
　　关联规则发现是在数据库中寻找数据对象间的关联模式，例如，在购买个人计算机的顾客中，90%也购买了打印机就是一种关联模式。关联规则发现主要用于零售业交易数据分析，以进行物品更合理的摆放，*终提高销售量，该方法此时也直接称为货篮分析。
　　数据总结是将数据库中的大量相关数据从较低概念层次抽象到较高概念层次的过程。计数、求和、求平均值、求*大值和*小值等计算都是数据总结的具体化。由于数据库中的数据所包含的信息往往是*原始、*基本的信息，而有时人们需要从较高的层次上浏览数据，这就要求从不同的层次上对数据进行总结以满足分析需要。
　　序列模式发现是在数据库中寻找基于一段时间区间的关联模式，例如，在某一时间购买个人计算机的所有顾客中，60%会在三个月内购买应用软件就是一种序列模式。序列模式与关联模式非常相似，区别在于序列模式表述基于时间的关系，而不是基于数据对象间的关系，在有些文献中也称其为基于时间的关联规则发现。
　　依赖关系或依赖模型发现是通过对数据库中数据的分析，获取数据间的某种因果联系。这种因果联系既可能是内在的某种概率分布关系的描述，也可能是数据对象间存在的确定的函数关系。
　　异常发现用于在数据库中发现数据中存在的偏差或异常。例如，下列几种偏差或异常就应引起人们的关注：不符合任何一个标准类的异常，有时可能意味着严重的错误或欺诈；相邻时间段内信息的异常变动，如二月份与一月份相比销售收入的骤然升高。
　　趋势预测是根据数据库中的历史信息对未来信息做出估计。实际上，预测这一数据挖掘任务并不一定是独立的。一般来讲，上述几种数据挖掘任务的结果皆可以在分析后用于趋势预测。
　　1.1.4　数据仓库与数据挖掘
　　数据挖掘与数据库新技术——数据仓库（data warehouse）有着密切的关系。数据仓库技术是近年来信息技术领域迅速发展起来的一种数据组织和管理技术。数据仓库是面向主题的、综合的、不同时间的、稳定的数据集合，它主要用于支持经营管理中的决策制定过程。数据仓库中存储面向分析型应用的集成数据，一般包含5～10年的历史数据。
　　数据仓库技术源于数据库技术，它的主要设计思想是将分析决策所需的大量数据从传统的操作环境中分离出来，把分散的、难以访问的操作数据转换成集中统一的、随时可用的信息而建立的一种数据库存储环境。可以说，数据仓库是一种专门的数据存储，用于支持分析型的数据处理。如何将数据仓库与数据挖掘结合在一起来更好地支持分析决策也得到了研究人员的普遍关注。数据仓库为数据挖掘提供了数据基础，在数据仓库中进行数据挖掘也对数据挖掘算法提出了更高的要求。
　　（1）数据仓库中集成和存储着来自若干异构的数据源的信息。这些数据源本身就可能是一个规模庞大的数据库，有着比一般数据库系统更大的数据规模。这就要求在数据仓库中进行数据挖掘的算法必须更有效、更快速。
　　（2）在一般的数据库中，为了提高系统的效率，一般会尽可能少地保留历史信息。而数据仓库具有一个重要的特征，即具有长时间的历史数据存储。存储长时间历史数据的目的就是进行数据长期趋势的分析，数据仓库为决策者的长期决策行为提供了有力的数据支持。然而，数据仓库中的数据在时间轴上的特征，在一定程度上增加了数据挖掘的难度。
　　另外，数据仓库也为数据挖掘创造了更方便的数据条件，体现在如下方面。
　　（1）从一个企业的角度来看，数据仓库集成了企业内各部门全面的、综合的数据。数据挖掘要面对企业全局模式的知识发现。从这一点上讲，基于数据仓库的数据挖掘能更好地满足高层战略决策的要求，而且数据仓库大大地降低了数据挖掘的障碍。数据挖掘一般要求大量的数据准备工作，而数据仓库中的数据已经被充分收集起来，进行了整理、合并，并且有些还进行了初步的分析处理。这样，可以集中精力在数据挖掘核心处理阶段。另外，数据仓库中对数据不同粒度的集成和综合，更有效地支持了多层次、多种知识的挖掘。
　　（2）数据仓库是面向决策支持的，因此它的体系结构努力保证查询和分析的有效性；而一般的联机事务处理系统则主要要求更新的实时性。一般的数据仓库设计成只读方式，*终用户不能更新数据。数据仓库中的数据更新由专门的一套机制来实现。数据仓库对查询的强大支持使数据挖掘效率更高，挖掘过程可以做到实时交互，使决策者的思维保持连续，有可能发现更深入、更有价值的知识。
　　数据仓库完成了数据的收集、集成、存储、管理等工作，数据挖掘面对经过初步加工的数据，能更专注于知识的发现过程；另外，由于数据仓库所具有的新特点，又对数据挖掘技术提出了更高的要求。可以说，数据挖掘技术和数据仓库技术结合起来，能够更充分地发挥其潜力。
　　1.2　数据类型及差异度计算
　　聚类的主要依据是对象间的相似性。确定对象之间是否相似，一般是通过计算对象之间的差异度来完成的。当对象属性取值类型不同时，差异度的计算方法也不相同。下面给出对象属性取值分别为二值属性、分类属性、数值属性和混合属性时的差异度计算方法。
　　1.2.1　二值属性
　　二值属性（binary attribute）是指只能有两种取值的属性，一般用1来表示其中的一种取值，用0来表示另外一种取值。
　　假设有个对象，描述每个对象的个属性值皆为二值属性，则计算对象与对象（）之间的差异度需要通过下面两个步骤来完成。
　　1.统计二值属性取值
　　二值属性取值统计如表1-1所示，其中，为对象和对象取值皆为1的属性个数，为对象取值为1而对象取值为0的属性个数，为对象取值为0而对象取值为1的属性个数，为对象和对象取值皆为0的属性个数。的和为每个对象的属性总数。
　　2. 根据统计结果进行差异度的计算
　　对象与对象之间的差异度可以通过下面的公式来计算：
　　（1-1）
　　实际上，式（1-1）更适用于二值属性取值对称的情况，即二值属性取值为1或0是同等重要的，没有主次之分，因此（和同时取值为1）和（和同时取值为0）两个统

目录
前言
第1章　聚类知识发现　1
1.1　数据库知识发现　1
1.1.1　数据库知识发现的产生与发展　1
1.1.2　数据库知识发现的处理过程　2
1.1.3　数据库知识发现的主要任务　3
1.1.4　数据仓库与数据挖掘　4
1.2　数据类型及差异度计算　5
1.2.1　二值属性　5
1.2.2　分类属性　7
1.2.3　数值属性　7
1.2.4　混合属性　8
1.3　主要的聚类方法　10
1.3.1　分割聚类　10
1.3.2　层次聚类　12
1.3.3　基于密度的聚类　14
1.4　聚类方法的新进展　15
1.4.1　智能聚类　15
1.4.2　大数据聚类　16
1.5　本章要点　17
第2章　高维稀疏数据聚类知识发现理论体系　18
2.1　聚类研究的重点和难点　18
2.2　高维稀疏数据聚类问题　20
2.3　二值属性高维稀疏数据聚类原理　22
2.4　高维稀疏数据聚类拓展　24
2.4.1　分类、数值和混合属性数据　24
2.4.2　不完备数据　25
2.4.3　大规模数据　26
2.4.4　聚类过程调整　27
2.4.5　参数自适应　27
2.5　本章要点　29
第3章　二值属性高维稀疏数据聚类　30
3.1　概念基础　30
3.1.1　集合的稀疏差异度　30
3.1.2　集合的稀疏特征向量　31
3.1.3　稀疏特征向量的可加性　32
3.2　聚类过程　34
3.2.1　算法的两层结构　35
3.2.2　算法步骤　36
3.3　算法示例　37
3.3.1　聚类过程　38
3.3.2　聚类结果及分析　39
3.4　本章要点　40
第4章　分类属性高维稀疏数据聚类　42
4.1　基于稀疏特征向量的聚类　42
4.1.1　概念基础　42
4.1.2　算法步骤　44
4.1.3　分类属性数据聚类示例　45
4.1.4　分类属性稀疏数据聚类示例　47
4.2　基于集合差异度的聚类　48
4.2.1　概念基础　48
4.2.2　算法步骤　50
4.2.3　算法示例　51
4.3　拓展稀疏差异度聚类　53
4.3.1　集合的拓展稀疏差异度　53
4.3.2　集合的拓展稀疏特征向量　54
4.3.3　相关定理　55
4.3.4　算法步骤　55
4.4　稀疏性指数排序聚类　56
4.4.1　稀疏性指数相关概念　57
4.4.2　稀疏性指数排序　57
4.4.3　算法步骤　58
4.4.4　算法示例　58
4.5　不干涉序列加权排序聚类　60
4.5.1　不干涉序列指数　60
4.5.2　相关定理　61
4.5.3　排序示例　64
4.5.4　算法步骤　65
4.6　基于位集的聚类　66
4.6.1　分类属性数据对象的位集表示　66
4.6.2　位集差异度的定义及其性质　66
4.6.3　相关定理　67
4.6.4　算法步骤　69
4.7　本章要点　70
第5章　数值属性高维稀疏数据聚类　71
5.1　稀疏特征聚类　71
5.1.1　聚类思想　71
5.1.2　稀疏特征　72
5.1.3　对象的稀疏差异度　73
5.1.4　两阶段处理过程　74
5.1.5　算法步骤　75
5.1.6　算法示例　76
5.2　模糊离散化数据聚类　81
5.2.1　属性组合　81
5.2.2　模糊离散化　82
5.2.3　隶属度下限　83
5.2.4　算法步骤　83
5.2.5　算法示例　84
5.3　本章要点　88
第6章　不完备分类属性数据聚类　89
6.1　容差集合差异度聚类　89
6.1.1　容差集合差异度　89
6.1.2　容差集合精简　90
6.1.3　相关定理　91
6.1.4　算法步骤　92
6.2　约束容差集合差异度聚类　93
6.2.1　约束容差集合差异度　93
6.2.2　约束容差集合精简　95
6.2.3　相关定理　96
6.2.4　算法步骤　98
6.3　基于约束容差集合差异度聚类的缺失数据填补　99
6.3.1　填补思想　99
6.3.2　约束容差集合精简不变定理　101
6.3.3　填补过程　102
6.4　缺失数据填补实验分析　103
6.4.1　数据集　103
6.4.2　补齐率分析　104
6.4.3　填补正确率分析　106
6.4.4　填补后聚类正确率分析　109
6.4.5　时间效率分析　111
6.4.6　参数分析　113
6.5　本章要点　115
第7章　不完备混合属性数据聚类　116
7.1　对象混合差异度聚类　116
7.1.1　聚类思想　116
7.1.2　对象混合差异度　117
7.1.3　基于*近邻的初始原型对象选择　118
7.1.4　算法步骤　119
7.2　集合混合差异度聚类　119
7.2.1　集合混合差异度　120
7.2.2　集合混合特征向量　121
7.2.3　集合混合特征向量的可加性　122
7.2.4　算法步骤　123
7.3　基于集合混合差异度聚类的缺失数据填补　124
7.3.1　填补思想　124
7.3.2　概念基础　125
7.3.3　填补过程　126
7.4　缺失数据填补实验分析　127
7.4.1　数据集　127
7.4.2　分类属性填补分析　128
7.4.3　数值属性填补分析　129
7.5　本章要点　131
第8章　大规模高维稀疏数据聚类　132
8.1　基于抽样的聚类　132
8.1.1　基于抽样的聚类思想　132
8.1.2　确界表示的概念基础　136
8.1.3　高维稀疏类的确界表示　137
8.1.4　基于确界表示的非样本对象分配　138
8.1.5　非样本对象分配示例　139
8.2　并行聚类　141
8.2.1　并行策略　141
8.2.2　算法步骤　142
8.2.3　聚类正确性实验分析　143
8.2.4　规模扩展性实验分析　145
8.3　本章要点　147
第9章　参数自适应的高维稀疏数据聚类　148
9.1　稀疏差异度启发式聚类　148
9.1.1　启发式聚类思想　148
9.1.2　内部有效性评价指标　149
9.1.3　概念基础　151
9.1.4　聚类过程　153
9.2　拓展位集差异度聚类　155
9.2.1　拓展位集差异度　156
9.2.2　算法步骤　159
9.2.3　差异度调整指数分析　160
9.2.4　阈值确定方法　161
9.3　无参数聚类　162
9.3.1　稀疏差异度阈值范围的确定　162
9.3.2　考虑数据排序的调整稀疏特征向量　163
9.3.3　无参数聚类过程　164
9.3.4　算法计算时间复杂度　165
9.4　本章要点　166
第10章　高维稀疏数据调整聚类　167
10.1　高维稀疏数据双向聚类　167
10.1.1　集合的双向稀疏特征向量　167
10.1.2　双向稀疏特征向量的可加性　168
10.1.3　双向稀疏特征向量的可减性　170
10.1.4　聚类过程　171
10.1.5　算法示例　172
10.2　高维稀疏数据优化调整聚类　174
10.2.1　聚类思想　174
10.2.2　聚类过程　176
10.2.3　算法示例　177
10.3　本章要点　179
第11章　聚类趋势发现　180
11.1　聚类趋势发现问题　180
11.1.1　问题提出　180
11.1.2　问题难点　181
11.1.3　聚类趋势发现思想　182
11.2　概念基础　182
11.2.1　稳定原子类　182
11.2.2　距离趋势的计算　183
11.3　聚类过程　184
11.3.1　算法步骤　184
11.3.2　数据关系　185
11.4　算法示例　187
11.4.1　问题描述　187
11.4.2　过程及结果　188
11.5　本章要点　189
第12章　高维稀疏数据聚类知识发现应用　190
12.1　面向管理问题的应用　190
12.1.1　高维稀疏客户数据存储　190
12.1.2　图书馆读者群划分　193
12.1.3　汉语词汇聚类分析　195
12.1.4　文献知识结构识别　197
12.2　面向数据组织的应用　200
12.2.1　多维数据建模　200
12.2.2　数据准备　203
12.2.3　聚类数据预处理　205
12.2.4　维表数据生成　206
12.2.5　事实表数据生成　208
12.2.6　数据分析实现　209
12.3　本章要点　212
参考文献　213
索引　218
后记　224