《数据仓库与数据挖掘》期末复习总结_数据仓库与数据挖掘复习

《数据仓库与数据挖掘》期末复习总结

---

适用教材：《数据挖掘概念与技术（第3版）》，Jiawei Han，Mieheline Kamber，Jian Pei著，机械工业出版社

提示：与教材内容不完全匹配，有所取舍

---

写在前面： 这份复习总结是笔者根据老师授课内容，结合教材、PPT整理出来的，本意是为了帮助笔者查缺补漏，理解记忆。现将其上传至CSDN博客，希望能对大家有所帮助。另外，内容上可能有遗漏、错误或者错字现象，还请多多包涵，并予以指教！谢绝转载！

---

第一章 引论

1.大数据的4V特征：①大量化；②多样化；③快速化；④价值密度低。

2.定义：数据挖掘（Data Mining）是从海量的数据中抽取感兴趣的（有价值的、隐含的、以前没有用但是潜在有用信息的）模式和知识的过程。

3.数据挖掘的基本步骤：①准备数据，包括准备训练数据和检验数据；②选择一种数据挖掘技术或算法，将数据提交给数据挖掘软件；③解释和评估结果；④模型应用。

4.数据挖掘的对象：面向数据库的数据（如数据库数据、数据仓库、事务仓库）、高级数据集及应用（如数据流和传感数据，时序数据、时间数据、序列数据，结构数据、图、社会网络、多连接数据，对象-关系数据库，异构数据库和历史遗留数据，空间数据和时空数据，多媒体数据，文本数据，WWW）

5.挖掘什么模式：频繁模式、分类、聚类、离群点检测、时间和序列。

6.使用什么技术：机器学习、模式识别、统计学、可视化、高性能计算、数据库技术等。

7.机器学习

①定义：研究计算机怎样模拟或实现人类的学习行为，以获取新的知识或技能，重新组织已有的知识结构使指不断改善自身的性能。

②**分类：监督学习、无监督学习、半监督学习、主动学习。**其中，监督学习是通过对大量已知分类或输出结果值的实例进行训练，调整模型的结构，达到建立能够准确分类或预测未知模型的目的。这种基于归纳的概念学习过程被称为有指导（监督）的学习。无监督学习是在学习训练之前，无预先定义好分类的实例，数据实例按照某种相似性度量方法，计算实例之间的相似程度，将最为相似的实例聚类在一个组——簇（Cluster）中，再解释和理解每个簇的含义，从中发现聚类的意义。

---

第二章 认识数据

1.数据属性：

①枚举或标称属性：其值是符号或者事物的名字，代表某种类别、编码或状态。如：颜色={黑色，白色，灰色，红色}。

②二元属性：仅有两个可能状态的标称属性。如果两个状态同等重要，则是对称二元属性，反之为非对称的。

③序数属性：其可能的值之间具有有意义的序或排位。如：尺寸={小，中，大}。

④数值属性：定量的，用整数或实数表示。其类型可以是区间标度的或比率标度的。区间标度属性的值用固定、相等的单位测量。比率标度属性是具有固有0点的数值属性。

⑤离散属性；⑥连续属性。

2.数据的基本统计描述：中心趋势度量（均值、中位数、众数）、数据的散布（极差、四分位数、方差、标准差、四分数极差、盒图）、可视化的审视数据（饼图、分位数图、分位数-分位数图、直方图、散点图）

3.中位数近似值的计算公式：
$$median=L_1+\frac{n/2-\sum freq}{fre{q}_{median}}\times width$$
其中，$L_1$为中位数所在区间的下界，n为整个数据集包含的样本数，$\sum freq$为低于中位数区间的所有区间的频率和，$fre{q}_{median}$为中位数区间的频率，width为中位数区间的宽度。

4.可视化方法：①基于像素的可视化；②几何投影可视化；③基于图符的可视化；④层次可视化；⑤可视化复杂对象和关系。

5.相似性：衡量两个数据对象之间的相似程度，值越大越相似，常用$sim()$表示。相异性：衡量两个数据对象之间的差别，值越小越相似，常用$d()$表示。邻近性：相似性与相异性都称为邻近性。一般情况下，对于标称数据，$sim(i,j)=1-d(i,j)$.

6.枚举属性的相异性度量：$d(i,j)=\frac{p-m}{p}$，故其相似性度量：$sim(i,j)=1-d(i,j)=\frac{m}{p}$.其中，m是匹配的总数（i=j），p是刻画对象的属性总数。

7.二元属性的相异性度量：$d(i,j)=\frac{r+s}{q+r+s+t}$,故其相似性度量：$sim(i,j)=1-d(i,j)=\frac{q+t}{q+r+s+t}$。其中，q表示$i=j=1$的二元属性个数，r表示$i=1,j=0$的二元属性个数，s表示$i=0,j=1$的二元属性个数，t表示$i=j=0$的二元属性个数，若是非对称的二元属性，t可忽略，此时，$sim(i,j)=\frac{q}{q+r+s}$也被称为Jaccard系数。

8.数值属性的相异性度量：闵可夫斯基距离
$$d(i,j)=\sqrt[h]{{\left|x_{i1}-x_{j1}\right|}^h+{\left|x_{i2}-x_{j2}\right|}^h+\dots +{\left|x_{ip}-x_{jp}\right|}^h}$$
其中，$h=1$时，为曼哈顿距离（L1范数），即：$d(i,j)=\left|x_{i1}-x_{j1}\right|+\left|x_{i2}-x_{j2}\right|+\dots +\left|x_{ip}-x_{jp}\right|$

$h=2$时，为欧式距离（L2范数），即$d(i,j)=\sqrt{{\left|x_{i1}-x_{j1}\right|}^2+{\left|x_{i2}-x_{j2}\right|}^2+\dots +{\left|x_{ip}-x_{jp}\right|}^2}$

$h\to \infty$，为切比雪夫距离或上确界距离，即$d(i,j)={\lim }_{h\to \infty }({\sum }_{f=1}^p{\left|x_{if}+x_{jf}\right|}^h{)}^{\frac{1}{h}}=ma{x}_f^p\left|x_{if}-x_{jf}\right|$

9.序数属性的邻近性度量：数据规格化后，可使用闵可夫斯基距离度量计算。数据规格化方法：$z_{if}=\frac{r_{if}-1}{M_f-1}$,其中$M_f$为有序的状态数,$r_{if}$为该状态对应的排位号。

例如：test有三个状态，排位为 fair、good、excellent，即 $M_f=3$,则 $r_{fair}=\frac{1-1}{3-1}=0$，以此类推，$r_{good}=0.5$,$r_{excellent}=1$

10.涉及稀疏数值数据向量（如词频向量）的应用，余弦度量和Tanimoto系数通常用于相似性评估。

---

第三章 数据预处理

1.衡量数据质量的要素：准确性、完整性、一致性、时效性、可信性、可解释性。

2.数据预处理的主要任务：

（1）数据清理：填充缺失值，平滑噪声数据，识别并删除孤立点，解决不一致问题。

（2）数据集成：将多个数据库或数据文件进行集成。

（3）数据归约：在取得相同结果的条件下，减少特征数量。

（4）数据变换：数据格式、取值区间等的标准化。

3.数据清理的任务：（1）属性选择与处理；（2）填充空缺值；（3）噪声数据的处理。

（1）属性选择与处理：

• 选取原则：①尽可能赋予属性名和属性值明确的含义；②统一多数据源的属性值编码；③处理唯一属性；④去除重复属性。

（2）填充空缺值：

• 填充方法：①忽略元组；②人工填充；③默认值填充；④使用属性的中心度量填充；⑤同一类元组的属性均值或中位数填充；⑥使用最可能的值填充。

（3）噪声数据的处理：

• 处理方法：①分箱；②聚类；③回归。

4.数据集成中常用的相关性分析方法：

（1）对于标称属性，常用卡方检验。${\chi }^2={\sum }_{i=1}^c{\sum }_{j=1}^r\frac{(o_{ij}-e_{ij}{)}^2}{e_{ij}}$，其中，$o_{ij}$和$e_{ij}$分别为观测频度和期望频度。

（2）对于数值属性，常用相关系数分析（皮尔逊相关系数）。$r_{A,B}=\frac{{\sum }_{i=1}^n(a_i-\bar{A})(b_i-\bar{B})}{(n-1){\sigma }_A{\sigma }_B}=\frac{{\sum }_{i=1}^n(a_i{b}_i)-n\bar{A}\bar{B}}{(n-1){\sigma }_A{\sigma }_B}$，其中，$a_i$为样本i的属性A的取值，$b_i$为样本i的属性B的取值，$\bar{A}$和$\bar{B}$分别为属性A和属性B的均值。若：

$r_{A,B}>0$，则属性A和B呈正相关，值越大，相关性越强。

$r_{A,B}=0$，则属性A和B呈相互独立。

$r_{A,B}<0$，则属性A和B呈负相关。

（3）对于数值属性，可用协方差：评估两个属性是如何一起变化的。$Cov(A,B)=\frac{{\sum }_{i=1}^n(a_i-\bar{A})(b_i-\bar{B})}{n}$，若：

$Cov(A,B)>0$，则说明样本X的属性A和B同时大于或小于期望值。

$Cov(A,B)=0$，则说明两者之间相互独立。

$Cov(A,B)<0$，则说明样本X的属性A大于期望值的同时，B的值小于期望值。

5.数据归约的目的：在保持数据完整的前提下，减少原始数据量，从而增加数据挖掘算法的效率。

6.数据归约包括：（1）维归约；（2）数量归约；（3）数据压缩。

（1）维归约：减少所考虑样本的属性个数。方法有：小波变换、主成分分析、属性子集选择。

（2）数量归约：用原始数据的子集进行数据挖掘。方法有：回归、直方图、聚类、采样、数据立方体集成。

（3）数据压缩：使用变换，以得到原始数据的归约或压缩表示。分为有损压缩和无损压缩。

7.数据变换的方法：

（1）光滑：去除噪声。

（2）属性构造：从给定的属性集中构造新属性。

（3）聚集：数据汇总。

（4）规范化：将属性取值映射到一个特定的小区间。

• 最小-最大规范化：$v^{\prime }=\frac{v-mi{n}_A}{ma{x}_A-mi{n}_A}(new\_ma{x}_A-new\_min)+new\_mi{n}_A$
• Z-分数规范化：$v^{\prime }=\frac{v-{\mu }_A}{{\sigma }_A}$
• 小数定标规范化：$v^{\prime }=\frac{v}{10^j}$

（5）离散化：用区间标签或概念标签代替原始的数值属性。

• 方法：①分箱；②直方图；③聚类；④决策树；⑤相关性分析

（6）概念分层：标称属性数据的数据变换。

• 3-4-5规则：

  确定等宽区间的数目：

  ​ 如果一个区间最高有效位上跨越3，6，7或9个不同的值，就将该区间划分为3个等宽子区间；(7 $\to$ 2,3,2)

  ​ 如果一个区间最高有效位上跨越2，4，或8个不同的值，就将该区间划分为4个等宽子区间；

  ​ 如果一个区间最高有效位上跨越1，5，或10个不同的值，就将该区间划分为5个等宽子区间；

  ​ 将该规则递归的应用于每个子区间，产生给定数值属性的概念分层。

---

第四章 数据仓库与联机分析处理

1.数据仓库是一个面向主题的、集成的、时变的、非易失的数据集合，支持管理过程的决策过程。

2.数据库与数据仓库的区别与联系：

（1）数据库用于事务处理。数据库作为数据资源用于管理业务中的事物处理，其中存放的数据基本上保存当前数据，随着业务的变化随时在更新数据库中的数据，而且不同的管理业务需要建立不同的数据库。

（2）数据仓库用于决策分析。与数据库不同，数据仓库既保存过去的数据又保存当前的数据，数据仓库的数据是大量数据库的集成；同时，对数据库的操作比较明确，操作数据量少；对数据仓库操作不明确，操作数据量大。

3.数据仓库中的数据以四个基本特征为基础，分为四个级别：①早期细节级；②当前细节级；③轻度综合级；④高度综合级。

4.数据仓库中保存数据的细化或综合程度的级别称为粒度。细化程度越高，粒度越小；粒度越高，所能回答查询的能力越低。粒度划分的决定因素不是总数据量，而是总的记录数。

5.数据集市是一种更小、更集中的数据仓库。通常是为满足特定部门或用户的需求，按照多维的方式进行存储，包括定义维度、需要计算的指标、维度的层次等，生成面向决策分析需求的数据立方体。可分为独立数据集市和从属数据集市。

6.数据仓库系统是由数据仓库、仓库管理和分析工具三部分组成。

（1）仓库管理：

​ ①数据建模：建立数据仓库的数据模型，数据模型包括数据结构和数据操作。

数据结构的任务是确定数据类型、内容、数据间的关系，描述的是数据的静态特征。

数据操作的任务是确定对数据仓库中数据所允许的操作。如检索、计算等。

​ ②数据抽取、转换、装载：数据仓库中的数据是通过在源数据中抽取数据，按数据仓库的逻辑数据模型的要求进行数据转换，再按物理数据模型的要求装载到数据仓库中去。

（2）分析工具：①查询工具；②多维分析工具（OLAP工具）；③数据挖掘工具。

7.数据仓库的数据模型和数据库的数据模型不同之处在于：①数据仓库只为决策分析用，不包含事务处理的数据；②数据仓库增加了时间属性数据；③数据仓库增加了一些综合数据；④数据仓库的数据建模是适应决策用户使用的逻辑数据模型。

8.数据仓库存储采用多维数据模型，数据一般是数值。数据仓库的数据模型可分为：（1）星型模型；（2）雪花模型；（3）星座模型。

（1）星型模型：大多数的数据仓库都采用星型模型。星型模型是由事实表以及多个维表所组成。其中，事实表中存放大量关于企业的事实数据，包含大批数据但没有冗余的中心表。维表中存放描述性数据。

（2）雪花模型：雪花模型对星型模型的维表进一步层次化，原来的各维表为了减少冗余，进一步分解，形成一些局部的层次区域。

（3）星座模型：将多个星型模型连接起来形成网状结构，多个星型模型通过相同的维，连接多个事实表。

9.在数据仓库系统中，联机分析处理（OLAP）是重要的数据分析工具。其基本思想是从多方面和多角度以多维的形式来观察企业的状态和了解企业的变化。两个特点：①在线性；②多维分析。主要准则：①多维数据分析；②客户/服务器结构；③多用户支持；④一致稳定的报表性能；⑤灵活的报表生成。

10.OLAP是在OLTP的基础上发展起来的。OLTP是以查询数据库为基础的，面对的是操作人员和低层管理人员，对基本数据的查询和增删改等进行处理，属于日常业务系统。而OLAP是以数据仓库为基础的数据分析处理，建立在客户/服务器（C/S）体系结构上的，面向管理者的的决策支持系统。

11.OLAP的基本操作：（1）数据切片；（2）数据切块；（3）数据钻取（下钻）；（4）数据聚合（上卷）；（5）数据旋转。

---

第六章 挖掘频繁模式、关联和相关性：基本概念和方法

1.频繁模式是指频繁地出现在数据集中的模式。

2.一些基本概念：

（1）k-项集：若 I = { i 1 , i 2 , i 3 , … , i m } I=\{i_1,i_2,i_3,…,i_m\} I={i1​,i2​,i3​,…,im​}为m个不同项目的集合，每个$i_k$称为一个项目，I为项目的集合。其元素的个数称为项集的长度，长度为k的项集称为k-项集。

（2）关联规则：$R:X\Rightarrow Y$，其中$X\in I,Y\in I,X\cap Y=\varnothing$。表示项集X在某一交易中出现，导致Y以某一概率也会出现。可用支持度和可信度来衡量。

（3）支持度：$support(X\Rightarrow Y)=\frac{count(X\cup Y)}{|D|}$，表示交易集中同时包含X和Y的交易数与|D|之比。反映了X、Y同时出现的概率。关联规则的支持度等于频繁集的支持度。

（4）可信度：$condfidence(X\Rightarrow Y)=\frac{support(X\Rightarrow Y)}{support(X)}$，表示包含X和Y的交易数与包含X的交易数之比。反映了如果交易中包含X，则交易包含Y的概率。

（5）强关联规则：设定关联规则的最小支持度和最小可信度，若规则R的支持度和可信度均不小于最小支持度和最小可信度，则称规则R为强关联规则。

3.关联规则就是支持度和信任度分别满足用户给定阈值的规则。

4.关联规则挖掘的步骤：①找出所有的频繁项集；②由频繁项集产生强关联规则。

5.Apriori算法是挖掘布尔关联规则频繁项集的算法。利用频繁项集性质的先验知识，通过逐层搜索的迭代方法，即将k-项集用于探查(k+1)-项集，来穷举数据集中的所有频繁项集。

6.频繁项集的所有非空子集也是频繁的。频繁项集的任何子集都是频繁的。

7.Apriori算法的主要挑战：（1）要对数据进行多次扫描；（2）会产生大量的候选项集；（3）对候选项集的支持度计算非常繁琐。

​ 解决思路：（1）减少数据的扫描次数；（2）缩小产生的候选项集；（3）改进对候选项集的支持度计算方法。

​ 方法：（1）基于hash表的项集计数；（2）事务压缩；（3）划分；（4）选样；（5）动态项集计数。

8.FP树：频繁项集的增长方法算法，不产生候选频繁项集的算法。

9.闭频繁项集：如果不存在项集X的超项集Y，使得Y与X在数据集D中具有相同的支持度计数，则称项集X在数据集D中是闭的。

10.极大频繁项集：在一组频繁项集中，不再存在任何一个子集是频繁项集的项集。即极大频繁项集是指最大的频繁项集，不包含在其他的频繁项集中。

11.挖掘闭模式和极大模式：（1）项合并；（2）子项集剪枝；（3）项跳过。

12.模式评估方法：

（1）提升度：$lift=\frac{P(A\cup B)}{P(A)P(B)}$，若提升度大于1，则说明A和B是正相关；小于1，则说明A和B是负相关；等于1，则说明A和B是独立的。

（2）不平衡比：$IR(A,B)=\frac{|sup(A)-sup(B)|}{sup(A)+sup(B)-sup(A\cup B)}$，评价规则蕴含式中两个项集的不平衡程度。

---

第八章 分类：基本概念

1.分类是通过在已标记数据集上学习而构造的模型，并将其用于预测未标记数据的类别，一般属于监督学习。两个步骤：①学习；②预测。

2.CLS算法问题：根据某种策略从训练样本属性表中选择属性A作为测试属性。没有规定采用何种测试属性。实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响。

3.ID3算法主要针对属性选择问题，使用信息增益度选择测试属性。

4.信息量：若一个消息x出现的概率为p，则这一消息所含的信息量为$I=-lo{g}_{2}p$.

5.信源所含有的信息量称为信息熵，是指每个符号所含信息量的统计平均值。对于一个随机事件X，其信息熵的定义为$H(X)=\sum _{i}p(x_i)I(x_i)=-\sum _{i}p(x_i)lo{g}_{2}p(x_i)$.

6.条件自信息量：在事件$y_j$出现的条件下，随机事件$x_i$发生的条件概率为$p(x_i|y_j)$，则它的条件自信息量定义为$I(x_i|y_j)=-lo{g}_{2}p(x_i|y_j)$.

7.条件熵：在给定$y_j$条件下，$x_i$的条件自信息量为$I(x_i|y_j)$，X集合的条件熵$H(X|y_i)=\sum _{i}p(x_i|y_i)I(x_i|y_i)$.

​ 在给定Y（即各个$y_j$）条件下，$X$集合的条件熵$H(X|Y)=\sum _{j}p(y_j)H(X|y_j)$.

8.信息增益是针对一个特征而言，系统有它和没有它时的信息量各是多少，两者的差值就是这个特征给系统带来的信息量，即$I(Y;X)=H(Y)-H(Y|X)$。

9.决策树C4.5在ID3的基础上，使用增益率代替信息增益，它使用分裂信息值将信息增益率进行规范化。即$split{A}_{(D)}=-\sum _{j=1}^v\frac{|D_j|}{|D|}lo{g}_2\frac{|D_j|}{|D|}$，其中属性A有v个取值，$|D|$为样本总量，$|D_j|$为属性A取值为$j$的样本数。则，信息增益率$Gain\_ratio(D,A)=\frac{Gain(D,A)}{split{A}_{(D)}}$.

10.决策树Cart采用基尼指数构建决策树。$Gini(D)=1-\sum _{i=1}^n{p}_i^2$，表示训练集D的不纯度定义。其中，$p_i$表示训练集D中类别$C_i$的概率。基尼指数考虑的是二元属性的划分，对于离散属性a而言，首先需要将其取值转换成两个子集。那么，对于给定属性a的两个子集$D_1,D_2,D$的基尼指数为$Gin{i}_a=\frac{D_1}{D}Gini(D_1)+\frac{D_2}{D}Gini(D_2)$，a的划分导致不纯度的降低为$\Delta Gini(a)=Gini(D)-Gin{i}_a(D)$，选择不纯度降低最大的属性及其子集作为决策树分支准则。

11.剪枝是决策树对付“过拟合”的主要手段。基本策略：①预剪枝：提前终止某些分支的生长。②后剪枝：生成一颗完整树，再回头剪枝。

12.预剪枝和后剪枝进行对比：

（1）时间开销：

• 预剪枝：训练时间开销降低，测试时间开销降低。
• 后剪枝：训练时间开销增加，测试时间开销降低。

（2）过/欠拟合风险：

• 预剪枝：过拟合风险降低，欠拟合风险增加。
• 后剪枝：过拟合风险降低，欠拟合风险基本不变。

（3）泛化性能：后剪枝通常优于预剪枝。

13.贝叶斯方法是用概率表示不确定性，概率规则表示推理或学习，随机变量的概率分布表示推理或学习的最终结果。贝叶斯定理引入了先验概率，后验概率由先验概率和类条件概率表达式计算出。假设有随机变量x和y，$p(x,y)$表示x和y的联合概率，$p(x|y)$和$p(y|x)$表示条件概率，其中$p(y|x)$是后验概率，而$p(y)$称为y的先验概率，x和y的联合概率和条件概率满足下列关系：$p(x,y)=p(y|x)p(x)=p(x|y)p(y)$，即贝叶斯定理：$p(y|x)=\frac{p(x|y)p(y)}{p(x)}$，它提供了从先验概率$p(y)$计算后验概率$p(y|x)$的方法。

14.朴素贝叶斯分类器：$p(Y|X)=\frac{p(Y)\prod _{i=1}^{n}p(X_i|Y)}{p(X)}$，其中，$X$为问题的特征向量， X i = { X 1 , X 2 , … , X n } X_i=\{X_1,X_2,…,X_n\} Xi​={X1​,X2​,…,Xn​}且$X_1,X_2,\dots ,X_n$相互独立，$p(X)$为常数，先验概率$p(Y)$可以通过训练集进行估计。给定Y=y，如果要估计测试样本X的分类，由朴素贝叶斯分类得到y的后验概率为$p(Y=y|X)=\frac{p(Y=y)\prod _{i=1}^{n}p(X_i|Y=y)}{p(X)}$.

15.朴素贝叶斯算法应用流程：①分解出先验数据中的各特征；②计算各类别中，各特征的条件概率；③分解出待分类样本的各特征；④计算类别概率；⑤选取类别概率最大的作为判别类别。

16.令样本数据集中正类样本个数为P，负类样本个数为N，TP代表分类算法正确预测的正类样本的个数，TN代表正确预测的负类样本的个数，FP为错误预测为正类样本的个数，FN为错误预测为负类的样本个数。

混淆矩阵：

准确率（识别率）：$accuracy=\frac{TP+TN}{P+N}$

错误率（误分类率）；$error\_rate=\frac{FP+FN}{P+N}$

灵敏性（召回率）：$sensitivity=\frac{TP}{P}$

特效性（真负例率）：$specificity=\frac{TN}{N}$

精度：$precision=\frac{TP}{TP+FP}$

召回率：$recall=\frac{TP}{TP+FN}=\frac{TP}{P}$

F-score：$F-score=\frac{2\times precision\times recall}{precision+recall}$

17.为了防止分类模型出现过拟合，通常将已有样本划分为训练集和验证集。划分方法包括：（1）留出法；（2）K-折交叉验证；（3）留一法。

18.ROC曲线是一种比较两个分类模型的可视化工具。ROC曲线显示了给定模型的真正例率和假正例率之间的权衡。

19.提高分类准确率的三种方式：装袋、提升、随机森林。

---

第十章 聚类分析：基本概念和方法

1.聚类是把数据对象划分为子集的过程，就是将数据分组成为多个类。一般属于非监督学习。在同一个类内对象之间具有较高的相似度，不同类之间的对象之间的差异较大。

2.聚类分析的要求：①可伸缩性；②处理不同属性类型的能力；③发现任意形状的簇；④对于确定输入参数的领域知识的要求；⑤处理噪声的能力；⑥增量聚类和对输入次序不敏感；⑦聚类高维数据的能力；⑧基于约束的聚类；⑨可解释性和可用性。

3.聚类方法的分类：（1）划分方法；（2）层次方法；（3）基于密度的方法；（4）基于网格的方法。

（1）划分方法：给定一个有n个对象的数据集，划分聚类技术将构造数据k个划分，每一个划分就代表一个簇。典型算法：①k-means算法；②PAM算法。

• k-means算法步骤：
  • 随机选择一个k值，用以确定簇的总数；
  • 在数据集中，任意选取k个实例，作为初始的簇中心；
  • 计算k个簇中心与其他剩余实例的简单欧式距离$Distance(A,B)=\sqrt{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$，将其作为实例之间相似性的度量，并将与某个簇相似度高的实例划分到该簇中，作为该簇的成员之一；
  • 使用每个簇中的实例来计算该簇新的簇中心；
  • 若计算得到的新的簇中心等于上次迭代的簇中心，终止算法。否则，用新的簇中心作为簇中心重复步骤3-5。
• k-means算法特点：
  • 该算法试图找出使平方误差值最小的K个划分，当结果簇是密集的，而簇与簇之间区分明显时，效果较好。
  • 算法复杂度O(nkt)，其中，t是迭代次数。因此其可扩展性较好，对大数据集处理有较高的效率。
  • 算法常以局部最优结束。全局最优要穷举所有可能的划分。
  • 缺点：①不适合发现非凸面状的簇。②不适合大小差别较大的簇。③由于少量的噪声和孤立点对平均值产生较大的影响，故对于噪声和孤立点敏感。

（2）层次方法：创建给定数据对象集的层次分解。一般可分为凝聚法和分裂法。

• 凝聚法：也称自底向上的方法。开始将每个对象形成单独的簇，然后逐次合并相近的对象或簇，直到满足终止条件。
  • 基本思想：先将n个样品各自看成一类，然后规定样品之间的距离和类和类之间的距离。选择距离最近的两类合并成一个新类，计算新类和其它类的距离，再将距离最近的两类合并。这样，每次合并减少一类，直到所有样品归为一类。
  • 基本步骤：
    • 计算n个样本两两间的距离$d_{ij}$，记作 D = { d i j } D=\{d_{ij}\} D={dij​}；
    • 构造n个类，每个类只含一个样品；
    • 合并距离最近的两类为一新类；
    • 计算新类与各当前类的距离；
    • 重复步骤3，4，合并距离最近的两类为新类，直到所有的类并为一类为止；
    • 画聚类系谱图；
    • 决定类的个数和类。
  • 方法：①最短距离法；②最长距离法；③中间距离法；④重心法；⑤类平均法；⑥离差平方和法（Ward法）。
  • 缺点：①聚类过程中不能撤销；②可扩展性差，时间复杂度最小为$O(n^2)$。
• 分裂法：也称自顶向下的方法。开始将所有对象放入一个簇中，每次迭代，簇分裂为更小的簇，直到满足终止条件。

（3）基于密度的方法：从样本密度的角度来考察样本之间的可连接性，并基于可连接性样本不断扩展聚类簇。典型算法：DBSCAN、OPTICS、DENCLUE。基于密度的聚类能够发现任意形状的簇，而基于距离的聚类只适用于球形空间的聚类。

• DBSCAN
  • 基本概念：
    • 核心对象：若$x_j$的$ϵ$邻域至少包含MinPts个样本，即$|N_{ϵ}(x_j)\ge MinPts|$，则$x_j$是一个核心对象。
    • 密度直达：若$x_j$位于$x_i$的$ϵ$邻域，且$x_i$是核心对象，则称$x_j$由$x_i$密度直达。
    • 密度可达：对于$x_i$与$x_j$，若存在样本序列$p_1,p_2,\dots ,p_n$，其中$p_1=x_i,p_n=x_j$且$p_{i+1}$由$p_i$密度直达，则称$x_j$由$x_i$密度可达。
    • 密度相连：对于$x_i$与$x_j$，若存在$x_k$使得$x_i$与$x_j$均由$x_k$密度可达，则称$x_i$与$x_j$密度相连。
  • 算法步骤：
    • 初始化：设定半径ε和最小点数MinPts。
    • 随机选择一个未访问过的点p。
    • 确定点p的ε-邻域内的所有点，如果点数小于MinPts，则将点p标记为噪声点，否则以点p为核心点，创建一个新的簇C，并将点p加入到该簇中。
    • 对于点p的ε-邻域内的所有点，如果这个点还没有被访问过，就标记为已访问，并确定其ε-邻域内的所有点。如果邻域内的点数大于等于MinPts，则将这些点都加入到簇C中。
    • 重复步骤3和4，直到所有的点都被访问过为止。最终，所有被标记为核心点的点都会被聚到一个簇中，而噪声点则不属于任何簇。

（4）基于网格的方法：将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合。每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。典型算法：STING。

• STING：是一个基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。

  • 高层单元的统计变量的计算：

    • 每个网格单元属性的统计信息被预先计算和存储。包括：属性无关的变量 count（计数）；属性相关的变量 m（平均值），s（标准偏差），min（最小值），max（最大值），以及该单元中属性值遵循的分布类型 distribution，例如正态的，均衡的，指数的，或无（如果分布未知）。

    • 然后计算$n=\sum _i{n}_i,m=\frac{\sum _i{m}_i{n}_i}{n},s=\sqrt{\frac{{\sum }_i(s_i^2+m_i^2)n_i}{n}-m^2},min=min(mi{n}_i),max=max(ma{x}_i)$

    • 设dist为对应子单元格多数的分布类型，计算confl。

      若$dis{t}_i\ne dist,m_i\approx m,s_i\approx s,confl=confl+n_i$；

      若$dis{t}_i\ne dist,m_i!\approx m,s_i!\approx s,confl=n$；

      若$dis{t}_i=dist,m_i!\approx m,s_i!\approx s,confl=n$；

      若$dis{t}_i=dist,m_i\approx m,s_i\approx s,confl=confl+0$；

      如果$\frac{confl}{n}>t$（阈值，设为0.05），dist=NONE，否则，dist=dist。

  • 与其他聚类算法相比，STING的优点：

    （1）基于网格的计算是独立查询的。因为存储在每个单元中的统计信息提供了单元中数据汇总信息，不依赖于查询；

    （2）网格结构有利于并行处理和增量更新；

    （3）该方法的主要优点是效率高：STING 扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是O(n)，n 是对象的数目。在层次结构建立后，查询处理时间是O(g)，其中g是最底层网格单元的数目，通常远远小于n。

4.聚类评估的主要任务：

（1）估计聚类趋势：对于给定的数据集，评估该数据集是否存在非随机结构。典型方法：霍普金斯统计量。

（2）确定数据集中的簇数：如k-means算法需要将簇的数目作为参考。典型方法：肘方法、基于信息准则或信息论的方法、使用交叉验证确定。

（3）测定聚类质量：评估结果簇的质量。四项基本标准：①簇的同质性；②簇的完整性；③碎布袋准则；④小簇保持性。外在方法：Bcubed。内在方法：轮廓系数。

---

第十二章 离群点检测

1.离群点：一个显著区别于正常对象的数据对象。

2.离群点与噪声的区别：（1）噪声是一个随机误差或方差；（2）噪声应在离群点检测之前移除。

3.离群点的类型：（1）全局离群点；（2）情境离群点；（3）集体离群点。

（1）全局离群点：如计算机网络中的入侵检测方法中的异常检测。关键在于找到合适的偏离度量标准。

（2）情景离群点：关键在于如何定义有意义的情境。

（3）群体离群点：如计算机网络中的拒绝服务攻击。关键在于不仅要考虑单个数据对象的行为，还要考虑对象群组的行为。

4.离群点检测方法：

（1）监督、半监督和无监督方法；

• 监督方法：对数据的正常性和异常性建模。如分类模型。
• 无监督方法：采用聚类方法等识别离群点。
• 半监督方法：在少量标记样本可行的情况下，可以通过已标记正常样本的邻近无标记对象一起训练一个正常对象模型，再根据该模型检测离群点。

（2）统计方法、基于邻近性的方法和基于聚类的方法。

• 统计方法：对数据的正常性做出假设，不遵守该假设的数据是离群点。类似于入侵检测中的异常检测。
• 基于邻近性的方法：假定一个对象是离群点，则它在特征空间中的最近邻也远离它。包含两种主要方法：基于距离的和基于密度的方法。
• 基于聚类的方法：正常数据对象属于大的稠密的簇，而离群点属于小的或稀疏的簇或不属于任何簇。因而，使用聚类算法将数据集聚类后可判定离群点。

5.统计学方法：统计方法假定正常数据对象由一个随机过程（生成模型）产生，因此正常对象出现在该随机模型的高概率区域中，而离群点出现在低概率区域中。分为参数方法和非参数方法。

（1）参数方法：假定正常数据由一个以θ为参数的参数分布产生，该参数分布的概率密度函数给出对象x被该分布产生的概率，值越小越可能是离群点。

• 单变量：数据集只涉及一个变量或属性。通常假设数据由正态分布产生，从输入数据中学习参数并将概率低的点视为离群点。典型方法：期望最大法估计μ和σ。
• 多变量：数据集涉及两个及两个以上的变量或属性。将多变量检测任务转换成单变量离群点检测问题。典型方法：①计算马氏距离；②使用卡方检验。
• 混合参数

（2）非参数方法：正常数据的模型从输入数据中学习，且无需假设。

• 基于直方图的离群点检测：构造直方图，需指定直方图的类型和个数等，无需指定数据分布的类型，判定数据是否落入直方图中的一个箱子中，若没有则为离群点。
  • 缺陷：很难选择一个合适的箱子尺寸。若箱子太小，则可能导致正常数据检测为离群点。若箱子太大，则难以找到离群点。
  • 解决方法：使用核密度估计数据的概率密度分布。

6.基于聚类的方法：离群点的三种情况：（1）不属于任何簇；（2）离最近的簇的距离较大；（3）属于一个小簇或稀疏簇。

7.基于分类的方法：训练一个能够辨别正常数据和离群点的分类模型。