数据挖掘复习（包括一些课本习题）[通俗易懂]

大家好，又见面了，我是你们的朋友全栈君。

第一章

1.数据挖掘定义

	在大量的数据中提取潜在有用的信息的过程

2.任务

分类，聚类，关联，离群点

3.对象

空间数据库，时间序列数据库，流数据，多媒体数据库，文本数据，万维网

4.知识发现

(1)数据清洗
(2)数据集成
(3)数据转换
(4)数据挖掘
(5)模式评估
(6)知识表示

1.1.数据挖掘处理的对象有哪些？
处理某一专业领域中积累的数据；
1.2.数据挖掘在电子商务中的客户关系管理起到非常重要的作用；

第二章

(1)数据挖掘中使用的数据是数据对象及其属性的集合，属性为对象的特性
(1)类属性和数值属性，标称，序数，区间，比例

数据预处理

(1)数据清理
(2)数据集成
(3)数据变换
(4)数据规约
(5)离散化及特征选择

噪声处理方法
（1）分箱，聚类，回归
（2）

数据集是具有相同属性的数据的集合；
数据集属性：维度（数据有多少个属性）；分辨率（在不同分辨率或粒度下得到的数据）；稀疏性（在某些数据集中，有意义的数据非常少，大部分数据属性上取值为0；）
数据集分类：
(1)记录数据
a.事务数据或购物篮数据
b.数据矩阵
(2)图形数据
a.带有对象之间联系的数据
b.具有图形对象的数据
(3)有序数据
a.时序数据
b.序列数据
c.时间序列数据
d.空间数据
e.流数据

数据统计特征（汇总统计）

中列数：(最大+最小)/2
极差：最大-最小
方差：绝对平均偏差，中位数绝对偏差；四分位数极差；

数据清理

(1)缺失值处理：删除该元组；忽略该属性；填充-》该属性对应的均值或众数；使用可能值；
(2)噪声数据：分箱；聚类删除离群点；

分类型数据（标称型数据和序数型数据）和数值型（区间型和比率型）数据；

数据聚合（数据集成）

数据变换

(1)平滑：去除数据中的噪声，分箱，回归，聚类…
(2)聚集：对数据进行汇总或聚集；
(3)数据泛化：概念分层，如对年龄可替换为 少年，青年，中年，老年…

(4)规范化：将属性数据依比例缩放；

(5)属性构造：利用已知属性构造新的属性，提高对高维数据的理解；

(6)数据离散化：有时需要的数据为分类型数据，因此需要对数值型数据进行离散化；
等宽离散化：会导致实例分布不均匀；有些区间分布很多实例，有些区间几乎没有实例；
等频离散化：将相同数量的对象放进某个区间；

2.2.规范化

	通过将属性数据按比例缩放，通过一个函数将给定属性的整个值域映射到一个新的值域中

2.2.1.最小-最大规范化 Z = (x-min)/(max-min)

2.2.2.Z-score规范化 Z=(x-Ex)/6 (6:属性标准差;EX:属性平均值)

2.2.3.小数定标规范化 V = v/Math.pow(10,n) ( n为使得Max(|v|)<1的最小整数)

986 -》0.986

数据规约(得到数据集的简约表示)

（1）维规约：删掉不相干的属性特征或减少数据量
（2）数据压缩：用数据编码变换得到原始数据的压缩
（3）数值规约：
（4）离散化和概念分层

抽样：压缩数据量

规约的到的数据应产生几乎和源数据集相同的分析结果
规约所节省的时间应>=数据挖掘原本处理这部分数据的时间
特征提取：由原始数据集创建新的特征集
特征选择：从已知的特征集合中选择最具代表性的特征子集-》维数灾难
离散化：等宽离散化；等高离散化
概念分层；高层概念代替低层概念，如青年->(18-35)

距离与相似性：
Manhanttan距离；
欧式距离；
切比雪夫距离；
Canberra距离；
d(p,q) = 
(1)Cosine余弦相似度
(2)相关系数：为余弦相似度的变种；
(3)Pearson相关系数：

将距离转换为相似性度量：s(p,q) = 1/(1+d(p,q))
距离函数
欧式距离:
曼哈顿距离
Canbeera距离

二值属性

		1    	0
 1      n11    n10			n11+n10
 0      n01    n00			n01+n00	
 		n11+n01	n10+n00

简单相关系数：d(p,q) = (n01+n10)/(n11+n00+n01+n10)
Jaccard系数:d(p,q) = (n01+n10)/(n11+n01+n10)

第三章:分类

1.分类的定义

分类是对数据集进行学习并构造一个拥有预测功能的分类模型，用于预测未知样本的类标号；
分类和回归均有预测的功能，但分类预测的输出为离散或标称的数据；回归预测的为连续属性值。
步骤：
(1)将数据集划分为训练集和测试集
(2)对训练集进行学习，构建分类模型
(3)用模型对测试集进行分类
(4)选用准确度高的模型

2.分类算法

2.1.决策树

训练训练集样本，生成一颗二叉树或多叉树，其中每个分支表示非叶节点属性取不同值下的样本子集，每个叶节点存放一个类标号值；关键是如何选择测试属性和划分样本集。->C4.5,ID3,CART
决策树属性选择标准包括信息增益和Gini系数
信息增益和Gini系数均容易偏向具有多分支的属性，因为多个分支能降低熵或Gini系数，因此C4.5采用信息增益率；

(1)贝叶斯分类方法：基本概率模型，用以给出某样本属于某个类标号的概率值；朴素贝叶斯是基于贝叶斯定理的统计分类方法，假定属性间相互独立;
(2)k-最近邻分类算法
一种基于实例的学习方法，直接使用训练集对样本数据进行分类，找出最接近的k个训练样本，即k个最近邻，多数投票机制；

2.1.1.ID3

使用信息增益作为属性的选择标准；
思想:首先检测所有属性，选择信息增益最大的属性产生决策树结点，由该属性不同取值建立分支，再对该分支的自己递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一个类别的数据为止。
熵：度量一个属性的信息量；
信息熵:E(S) = E(p1,p2,…pn) =

求play ball的熵？
play ball= {yes,no}，其中yes出现9次，no出席那了5
次；因此信息熵 = -9/14*log_2_9/19 – 5/14 * log_2_5/14 = 0.940
若所有记录均属于同一个类，则训练集S的熵值为0，表示很纯。

信息增益:Gain(S,A) = E(S) – EA(S)
划分前样本数据集的不纯程度 – 划分后样本数据集的不纯程度

a.wind = {weak(8) – >{yes:6;no:2},strong(6)->{yes:3;no:3}}
E(wind = weak) = -6/8log_2_6/8 – 2/8lob_2_2/8 = 0.8113
E(wind = strong) =-3/6log_2_3/6 – 3/6log_2_3/6 = 1
E(wind) = 8/14 *E(wind = weak) + 6/14 * E(wind =strong) = 0.8921;
ID3算法为所有可能的决策树空间中一种自顶向下，贪婪的搜索方法；
Gain(S,wind) = 0.940 – 0.8921 = 0.047;

TODO 例3-4-

ID3算法仅能处理分类属性数据，无法处理连续属性数据；
ID3算法对测试属性的每个取值均产生一个分支，且划分相应数据样本集会导致产生产生更多小的子集；
ID3采用信息增益作为决策树节点属性选择标准，由于信息增益在类别值多的属性上计算结果大于类别值少的属性上的计算结果，导致决策树算法偏向于有较多分支的属性；

2.1.2.C4.5（预剪枝）

对ID3算法的改进

(1)能够处理连续型属性数据和离散型属性数据
(2)使用信息增益率作为属性选择标准
(3)能够处理具有缺失值的数据(a.抛弃具有缺失值的数据;b.以某种方式填充（通常为该属性的均值或众数）)
(4)对生成的树进行剪枝处理
(5)决策树到规则均为自动生成
算法:
(1)对数据集进行预处理，将连续属性离散化
(2)计算属性的信息增益和信息增益率
(3)根节点每一个可能的取值均对应一个子集，对样本子集递归执行(2)，直到划分的每个子集中的观测数据都属于同一个类标号，生成决策树
(4)根据构造的决策树提取分类规则，对新的数据集进行分类

若某个属性有较多的分类取值，则它的信息熵会偏大，但由于信息增益率考虑了分裂信息而降低，进而消除了属性取值数目所带来的影响。

2.1.3.CART算法(建立二叉树，后剪枝)

使用Gini系数来度量对某个属性变量测试输出的两组取值的差异性，理想的分组应该尽量使两组中样本输出变量取值的差异性总和达到最小，即使得两组输出变量取值的差异性下降最快
Gini系数：

TODO 3-5

2.1.4.优缺点

(1)构造代价低
(2)在分类未知记录时非常快
(3)对于一些比较小的树容易理解
(4)在许多简单的数据集中测试发现，决策树分类技术准确率和其他分类技术相当。

2.2.贝叶斯分类算法

使用概率统计知识进行学习分类的方法，属于统计的学习方法，
即预测一个数据对象属于某个类别的概率
取概率大的为预测结果-》朴素贝叶斯分类算法，贝叶斯信念网络分类算法

2.2.1.贝叶斯定理(属性间相互独立)

P(X,Y) = P(Y|X)P(X) = P(X|Y)P(Y) 
P(Y|X) = P(X|Y)P(Y)/P(X)

P(X|Ci) = P(x1,x2,x3,…,xn|Ci) = P(x1|Ci)P(x2|Ci)P(x3|Ci)…P(xn|Ci)
此处Xk表示样本X在属性Ak下的取值。对于每个属性，需观察其为分类还是连续的。
~若Ak为分类属性：则P(Xk|Ci) = sik/si,其中sik是D中属性Ak的值为Xk的Ci类的样本个数，si为D中属于Ci类的样本个数。
~若属性Ak为连续值属性，则假设该连续值属性服从高斯分布，因而

为对未知样本X分类，对每个类Ci，计算P(X|Ci),样本X被指派到类别Ci中，当且仅当 P(X|Ci)P(Ci) >P(X|Cj)P(Cj) 1<=j<=m,j!=1
这样X被指派到最大的类别中。

参考前表的play ball，使用朴素贝叶斯算法预测{rainy, hot,normal,weak,?}

2.2.2.优缺点

简单，容易实现，在大多数情况下所获得的结果比较好；
前提是属性间相互独立；

2.3.K邻近分类算法

不需要先使用训练样本进行分类器的设计，直接用训练接对样本进行分类，以确定其类标号, 多数表决法；
思想：对于未知的样本，找出在所有的训练集中的k个最近邻，将该未知样本的类标号分为邻近中出现次数最多的样本。

2.3.1.优缺点

思想简单，容易实现；对于每个属性指标采用相同的权重，然而一般来说不同属性可能需要赋予不同的权值，每次加入到k集合中时，可用权值即两点间距离来替代；由于knn使用训练集来计算相似度，并未生成模型，因此时间开销大；
KNN改进主要从提高分类的速度和准确度下手，可事先对训练样本进行聚类；

回归

一元线性回归：最小二乘法；
多元线性回归；
逻辑回归；

2.4.分类模型评价

2.4.1.分类准确率

模型正确预测新的或之前未见过的数据的类标号的能力

2.4.2.时间空间复杂度

2.4.3.可解释性

分类结果只有可解释性好，容易理解才能更好用于决策支持

2.4.4.可伸缩性

指在给定内存和磁盘空间等可用的系统资源的前提下，算法的运行时间应当随数据库大小线性增加；

2.4.5.稳定性

模型不会随数据的变化而剧烈变化

2.4.6.健壮性

型在数据集中含有噪声和空缺值的情况下，仍有较好的正确分类数据的能力；

2.4.7.成本

预测错误所带来的的代价；

2.5.评价指标

混合矩阵

分类准确度:Accuracy = 分类正确/所有
分类差错率：Error rate = 1 – Accuracy = 分类错误/分类总数
查准率：Precision = 正例中分类正确/分成正例的数量

查全率：Recall = 被正确分类的正例样本个数/实际正例样本个数

2.5.分类模型评估方法

2.5.1.保持方法

将数据集分为2个相互独立的子集，训练集以及测试集。通常情况下，2/3为训练集，1/3为测试集。使用测试集来评估模型的分类准准确率；

2.5.2.随机子抽样

保持方法的多次迭代，每次讲数据集分开，随机子抽样形成测试集以及训练集

2.5.3.K-折交叉验证

将初始数据集随机划分成k个不相交的子集，每个子集的大小大致相同，然后进行k次训练和检验的过程。
每个样本用于训练的次数相同，并且用于检验一次；
对于分类，准确率估计是k次迭代正确分类的总数除以初始数据中的样本总数。对于回归预测，误差估计可以用k次迭代的总损失除以初始总样本来计算。

3.1.简述决策树分类主要步骤？
(1)对数据源进行数据预处理，得到训练集和测试集
(2)训练训练集
(3)剪枝
(4)提取分类规则
(5)测试评估决策树模型
3.2.给定决策树，选项有：1.将决策树转换成规则，然后对结果剪枝；2.对决策树剪枝，然后将剪枝后的树转换为规则？
由于第一种方法已将决策树转换成规则，通过规则，可以快速评估决策树及其子树紧凑程度，不能提高规则的估计准确率的任何条件都可以减掉，从而泛化规则；
3.3.计算决策树算法在最坏情况下的时间复杂度是重要的。
假设训练集拥有|d|实例以及m个属性，我们需要对树的尺寸做一个假设，假设树的深度是由log|D|决定。考虑一个属性在树的所有节点上所要做的工作量。当然不必在每一个节点上考虑所有的实例。但在树的每一层，必须考虑含有|D|个实例的整个数据集。由于树有log|D|个不同的层，处理一个属性所需工作量|D|log|D|，因此总工作量为m|D|*log(|D|)

3.4.

(1)计算属性A和属性B的信息增益。
E(S) = -4/10Math.log2(4/10) – 6/10Math.log2(6/10) = 0.9709505944546686
Ea(S) = 7/10*(-4/7Math.log2(4/7) – 3/7Math.log2(3/7)) + 3/10*(-3/3*Math.log(3/3) – 0) = 0.6896596952239761
Gain(S,A) = E(S) – Ea(S) = 0.2812908992306925

Eb(S) = 4/10*(-3/4Math.log2(3/4)-1/4Math.log2(1/4)) + 6/10*(-1/6Math.log2(1/6)-5/6Math.log2(5/6)) = 0.7145247027726656
Gain(S,B) = E(S) – Eb(S) = 0.256425891682003

Gini系数：
划分前Gini系数：
1- Math.pow(4/10,2) – Math.pow(6/10,2) = 0.48;
属性A：
A-T=>1 – Math.pow(4/7,2) – Math.pow(3/7,2) = 0.49;
A-F =>1 -Math.pow(3/3,2) – Math.pow(0,2) = 0;
Gini增益 = 0.48 – 7/10 * 0.49 – 3/10 0＝　0.137；
属性B：
B-T=>1 – Math.pow(3/4,2) – Math.pow(1/4,2) = 0.375
B-F =>1 – Math.pow(1/6,2) – Math.pow(5/6,2) =0.278
Gini增益：0.48 – 4/100.375 – 6/10 * 0.278 = 0.1632;
因此决策树会选择B；

3.5.证明：将节点划分为更小的后续节点后，结点的熵不会增加；
由定义可知，熵值越大，类分布越均匀；熵值越小，类分布越不平衡。将节点划分为更小的后续节点后，结点分布更加不平衡，熵值减小；，

3.6.朴素贝叶斯的朴树？简述朴素贝叶斯思想。
朴素贝叶斯，属性间是相互独立的，使用贝叶斯定理；

3.7.

(1)P(A|+) = 3/5;
P(B|+) = 1/5;
P(C|+) = 4/5;
P(C|-) = 1;
P(B|-) = 2/5;
P(A|-) = 2/5;
(2)预测P(A=0,B=1,C=0)，设X= {A=0,B=1,C=0}
P(+|X) = P(X|+)P(+)/P(X) = 2/51/51/51/2 = 1/75
P(-|X) = P(X|-)P(-)/P(X) = 3/52/50 = 0
因此为+；
(3)使用Laplace估计方法，其中p=1/2,l= 4;pl = 2;
P(A|+) = (3+2)/(5+4) = 5/9;
P(B|+) = (1+2)/(5+4) = 3/9;
P(B|-) = (2+2)/(5+4) = 4/9;
P(A|-) = (2+2)/(5 +４) = 4/9;

3.8.

x = 5.0;
1-最近邻：+
2-最近邻:+,-
3-最近邻=>+，-，-
50最近邻：

3.9. TODO

(1)建立该数据集的决策树。该决策树能捕捉到’’+”或“-”的概念吗？
根节点错误率：1 – Math.max(20/520,500/520) = 20/520;
deltax = 20/520 – 0/200200/520 – 0/1010/520 – 310/520* 10/310

3.10.什么是提升？陈述它为何能提高决策树归纳的准确性？
提升是指为每个训练元组赋值，迭代地学习k个分类器序列，学习到分类器Mi之后，更新权重，使得其后的分类器Mi+1更关注Mi误分的训练元组

3.11.

3.12.通过对预测变量变换，有些非线性回归模型可以转换为线性模型。指出如何将非线性回归方程 y=ax^b转换为可以用最小二乘法求解的线性回归方程？

第四章.聚类

聚类是将数据集划分为若干个相似对象组成的多个类或组或簇的过程，一个簇是由相似的一组对象构成的集合，不同簇中的对象相似度通常很低；
聚类分析任务：
(1)模式表示
(2)适合于数据领域的模式相似性定义
(3)聚类或划分算法
(4)数据摘要
(5)输出结果评估
硬划分：将每个对象严格地划分到不同的簇中；
软划分：不明确地将一个对象划分到某个簇中；

聚类有效性评估：
外部评估：将聚类获得的结构与先验结构进行比较来实现；
内部评估：确定一个结构是否本质地符合数据；
(1)可伸缩性：
(2)处理不同类型属性的能力
(3)发现任意形状的聚类
(4)决定输入参数的领域知识最小化；
(5)对输入记录的顺序不敏感
(6)高纬度
(7)基于约束的聚类
(8)可解释性和可用性

聚类方法的目的是寻找数据中潜在的自然分组结构和感兴趣的关系；
应用于：金融分析，市场营销；决策支持；信息检索；WEB挖掘
聚类方法：
基于划分：K-means,一趟算法；
基于层次：BIRCH算法，
基于密度：DBSCAN算法
基于图：Chameleon；SNN
基于网格：STING
基于模型：EM
基于神经网络：谱聚类算法，蚁群聚类算法

基于划分（每个对象至少属于一个组，每个组至少包含一个对象）

(1)每个组至少包含一个对象
(2)每个对象必须属于一个组
划分式聚类算法需要预先指定簇数目或簇中心，通过反复迭代运算，逐步降低目标函数的误差值，当目标函数值收敛时，得到最终聚类结果，分为基于质心的划分方法和基于中心的划分方法；
在同一个簇中，对象之间的距离尽可能小，在不同簇中，对象之间的距离尽可能大；

K-means

<n,mean>,n->簇中包含的对象个数，mean表示簇中对象的平均值
优缺点：
(1)算法简单，快速
(2)簇的个数k难以确定
(3)簇类结果对初始簇中心的选择较敏感
(4)对噪声和异常数据敏感
(5)不能用于发现非凸形状的簇，或具有各种不同大小的簇
(6)时间复杂度高
(7)仅用于处理数值属性
使用误差平方和作为度量聚类质量的目标函数

适用于纯分类属性的数据集：k-modes算法采用众数代替数值属性的均值；（mode：取值频度最大的属性值）
适用于混合属性的数据集：k-prototype算法将k-modes算法和k-means结合在一起；
k-summary：处理混合属性数据集，处理混合属性数据集；

一趟聚类算法

仅需扫描数据集一趟即可得到结果聚类，具有线性时间复杂度，高效，参数选择简单，对噪声不敏感的优点；但这一算法是将数据划分为大小几乎相同的超球体，不能用于发现非凸形状的簇，或具有各种不同大小的簇。

基于层次

凝聚层次聚类：最初将每个对象作为一个簇，然后将这些簇进行聚合以构造越来越大的簇，直到所有的对象均聚合为一个簇，或满足一定终止条件；
AGENS;
分裂层次聚类算法：最初将所有对象看成一个簇，将其不断分解以使其变成越来越小但个数越来越多的小簇，直到所有对象均独自构成一个簇或满足一定终止条件；
DIANA;
合并和分裂点的选择十分重要；

BIRCH

BIRCH方法通过集成层次聚类和其他聚类算法来对大量数据进行聚类，其中层次聚类用于初始的微聚类阶段，而其他方法如迭代划分用于在后面的宏聚类阶段；
聚类特征（Cluster Feature）：三维向量，汇总了对象簇的信息，给定簇中n个m维对象或点，则该簇的CF定义如下：CF = <n,LS,SS>n为簇中元素个数，LS为n个数据点线性和（等价于平均值），SS为数据点的平方和。SS用于计算误差平方和；
聚类特征具有可加性；
BIRCH采用多阶段聚类技术；数据集合的单遍扫描产生一个基本好的簇，一或多遍的额外扫描用于进一步改进聚类质量
(1)扫描数据库建立一棵存放于内存的初始CF树，可以看作数据的多层压缩，试图保留数据的内在聚类结构；
(2)采用某个聚类算法对CF树的叶节点进行聚类，把稀疏的簇当做离群点删除并把稠密的簇聚集成一个更大的簇；

基于密度

将簇看作是数据空间中被低密度区域分隔开的稠密对象区域，DBSCAN为一种典型的基于密度的方法
DBSCAN是一种基于高密度连通区域的聚类算法，该算法将具有高密度的区域划分为簇，并在具有噪声的空间数据中发现任意形状的簇，将簇定义为密度相连的样本点的最大集合；
3领域：给定对象半径内的领域称为该对象的3领域。
核心对象：如果对象的3领域至少包含最小数目MinPts的对象，则称该对象为核心对象；
DBSCAN是一种基于高密度连通区域的聚类方法；
Eps邻域：给定对象半径Eps内的邻域称为该对象的Eps邻域；
MinPts：给定邻域N§包含的点的最小数目，用于决定点p是簇的核心部分还是边界点或噪声；
核心对象：若对象的Eps邻域包含至少MinPts个对象；
边界点：
噪声点：
直接密度可达：直接密度可达
密度可达：链接密度可达
密度相连：
基于密度的簇是基于密度可达性的最大密度相连对象的集合。不包含在任何簇中的对象认为是噪声

基于图的聚类算法

(1)稀疏化邻近度图
(2)基于共享的最近邻个数定义两个对象之间的相似性度量
(3)定义核心对象并构造环绕它们的簇
(4)使用邻近度图中的信息，提供两个簇是否应当合并的更复杂的评估；
TODO Chameleon算法：
TODO　SNN算法：

基于模型的聚类算法

试图将给定数据与某个数学模型达成最佳拟合；

聚类算法评价

高质量的簇其特点是簇内相似度高和簇间相似度度低，因此评估聚类结果质量的准则有2中：
(1)内部质量评价准则，通过计算簇内部平均相似度，簇间平均相似度或整体相似度来评价聚类效果；
(2)外部质量评价准则：基于一个已经分好类的人工数据集进行评价；
ch指标
I指标
Xie-Beni指标
Dunn指标

例：4-2
p = {男，广州，18}
q = {女，深圳，20}
C1 = {男：25，女：5；广州：20；深圳：6；韶关：4；19}
C2 = {男：3，女：12；汕头：12；深圳：1；湛江：2；24}
相同：０；不同：１；
d(p,q) = 1 + 1＋２　＝　４；
d(p,C1) = (1 – 25/30) +　(1-20/30) + 19-18 = 1.5;
d(p,C2) = (1 – 1/5) + (1 – 0) + 6 = 7.8;
d(q,C1) = (1 – 5/30) + (1-6/30) + 1 = 25/30 + 24/30 +1 = 49/30 +1 = 79/30;
d(q,C2) = (1 – 12/15) + (1-1/15) + 4 = 3/15 + 14/15 + 4 =17/15 + 60/15 = 77/15;
d(C1,C2) = 1-(253 + 512)/(3015) + 1 – (6)/(3015) + 5 = 6.689;

4.1.什么是聚类？简单描述如下聚类方法，基于划分，基于密度，基于层次，基于模型？
聚类：将数据集依照其相似度划分成若干个对象组的过程；
基于划分：每个组至少包含一个元素；每个元素至少属于一个组；
基于层次：
凝聚聚类算法：一开始将每个元素都看作一个簇，通过不断计算簇与簇之间的相似度而凝聚某些簇直至达到某一阈值；
分裂聚类算法：一开始将所有元素看作一个簇，通过不断地分裂这个醋直至达到某一阈值；
基于密度：通过计算每一元素的密度来判定它是否属于某个簇，只要某一个区域中的点的密度大于某个阈值，则将其加入到相应聚类中；
基于模型：将数据集中的数据与某一数学模型相拟合，它的一个潜在假设是：目标数据集是由一系列概率分布所决定；

4.2.将下列8个点聚为3个簇；距离函数是Euclidean函数，假设初始我们选择A1,B1,C1作为3个中心；使用k-means算法；
A1(2,10)
A2(2,5)
A3(8,4)
B1(5,8)
B2(7,5)
B3(6,4)
C1(1,2)
C2(4,9)

4.3.聚类被广泛地认为是一种重要的数据挖掘方法，有着广泛的应用，对如下如每种情况给出一个应用例子。
a.采用聚类的数据挖掘方法的应用；
电子商务网站的客户群体划分；依照客户的个人信息，消费习惯将客户们划分成不同群体，相关店主就可以依据同类客户的消费习惯去推荐同类中其他用户商品；
b.采用聚类作为预处理工具，为其他数据挖掘任务作数据准备的应用；
电子商务网站的推荐系统。采用关联规则或隐含马尔可夫模型对每个客户群生成的消费习惯将客户划分为不同群体以便检测出不同客户群体的消费习惯用于商品推荐；

4.4.假设你将在一个给定的区域分配一些自动取款机以满足需求。住宅区或工作区可以被聚类以便每个簇被分配一个ATM。但是，这个聚类可能被一些因素所约束，包括可能影响ATM可达性的桥梁，河流和公路的位置。其他的约束可能包括对形成的一个区域每个地域的ATM数目的限制。给这些约束，如何修改聚类算法以实现基于约束的聚类？
约束的存在会使得原来被定义在同一个簇的对象之间的距离发生变化，此时可考虑将这些约束融入到距离的计算公式中，如存在桥梁，河流和公路的区域中，可通过对象之间的连通性以及路径来计算距离；而地域ATM数目的限制问题则可在聚类的初始化阶段解决，如k-means可依照地域的个数设置初始的k值；

4.5.给出一个数据集例子，它包含三个自然簇。对于该数据集，k-means能够发现正确的簇，但二分k-means不能。
给出三个完全一样的球形簇，k-means算法能很好地找到这三个簇，而二分k-means算法则会将处于对称中心的哪个簇分成两份；

4.6.总SSE是每个属性SSE之和。如果对于所有的簇，某变量的SSE都很低，这意味着什么？若对所有的簇都很高？若仅对某个簇很高？如何使用每个变量的SSE信息改进聚类？
(1)若某SSE属性对所有聚类都很低，则说明该属性无太大意义，本质上等于常量；
(2)若某SSE属性对所有聚类都很高，则说明该属性为噪声属性；
(3)若某属性的SSE仅对某一个簇高，说明该属性与该簇定义的该属性多提供的信息不一致，说明该属性不利于簇的定义；
(4)消除簇中具有最小分辨力的属性，对于某属性的SSE值对所有簇都高或低，则说明该属性对该簇作用不大；

4.7.使用基于中心，邻近和密度的方法，识别下图中的簇，对于每种情况指出簇的个数，并简要给出你的理由。
基于中心的为k均值，基于密度的为DBSCAN

(a)基于中心：有2个簇，矩形对半切分，同时2部分簇均包含噪声；
基于邻近：一个簇，因为两个圆圈受噪声数据影响；
基于密度：2个簇，每个圆圈代表一个簇，噪声被忽略；
(b)基于中心：一个簇，该簇包含一个圆环+一个圆；
基于邻近：2个簇，圆环和圆；
基于密度：2个簇，圆环+圆；
©基于中心：3个簇，每个三角一个簇；
基于邻近：1个簇
基于密度：3个簇，每个三角形一个簇
(d)基于中心：2个簇
基于邻近：5个簇，相互缠绕的线被分到同一个簇；
基于密度：2个簇；

4.8.传统的凝聚层次聚类过程每步合并2个簇，这样的方法能正确地捕获数据点集的簇结构吗？若不能，解释如何对结果进行后处理，以便得到簇结构更正确的视图？
传统的凝聚层次聚类过程关键是每步合并2个最相似的簇，直至剩下一个簇才停止；该聚类方法无法产生嵌套的簇结构；但我们可以采用树结构来记录形成的层次结构，每次合并都记录父子簇之间的关系，最终形成一个清晰的树状层次簇结构；

4.9.我们可以将一个数据集表示成对象节点的集合和属性节点的集合，其中每个对象与每个属性之间有一条边，该边的全职是对象在该属性上的值，对于稀疏数据，如果权值为0，则忽略该边。双划分聚类视图将该视图划分成不相交的簇，其中每个簇由一个对象节点和一个属性节点集组成。目标是最大化簇中对象节点和属相节点之间的权值，并最小化不同簇的对象节点和属性节点之间的边的权值，这种聚类称为协同聚类，因为对象和属性之间同时聚类。
(a)双划分聚类与对象和属性集分别聚类有何不同？
对于普通聚类，只有一组约束条件被运用，要么是对对象的约束或是对属性的约束；对于协同聚类，两种约束同时被使用。
(b)是否存在某些情况，这些方法产生相同的结果？
存在，若一组属性仅与某一个特定的簇对象相关，如在所有其他簇中的对象权值为0；相反地，这组对象在一个簇中对所有其他属性的权值为0，那么由协同聚类发现的簇会与分别通过对象和属性的聚类的结果一样。以文本聚类为例，有一组文本组成的簇仅包含了某部分的词或短语，相反地，某些词或短语也仅出现在部分文本中。

©协同聚类的优点是能自动产生由属性描述的簇，这种描述信息带有更强的表达能力，在现实应用中，较由对象描述的簇更有用。但具有强区分能力的属性有时候出现严重的重叠现象，这种情况下协同聚类产生的结果并不理想；

4.10.下表列出了4个点的两个最近邻，使用SNN相似度定义，计算每两点之间的SNN（共享最近邻个数）相似度。
SNN定义：当两个对象都在对方的最近邻列表时，SNN相似度就是它们共享的近邻个数；

点	第一个近邻	第二个近邻
1	4	3
2	3	4
3	4	2
4	3	1

点1-点2 -》0
点1-点3 -》1
点1-点4 -》1
点2-点3 -》1
点2-点4 -》1
点3-点4 -》 0

4.11.对于SNN相似度定义，SBB距离计算没有考虑两个最近邻表中共享近邻的位置。换言之，可能希望基于以相同或粗略的次序共享最近邻的两个点以更高的相似度；
TODO

4.12.一种稀疏化邻近度矩阵的方法如下：对于每个对象，除对应于对象的k-最近邻的项之外，所有的项都设置为0.然而，稀疏化之后的邻近度矩阵一般是不对称的；
a.若对象a在对象b的k-最近邻中，为什么不能保证b在对象a的k-最近邻中？
可能出现对象a的密度较大而对象b的密度较小的情况；
b.至少建议2种方法，可以用来使稀疏化的矩阵是对称的。
i.在两个对象a，b之中，只要其中一个对象在另一个对象的最近列表中，我们就设置Mba = Mab = 1;
ii.当某个对象a不在另一个对象b的k最近邻列表中，不论另一对象b是否在该对象a的最近邻中，我们设置Mba = Mab = 0;

第五章.关联分析

关联分析用于发现隐藏在大型数据集中令人感兴趣的联系。联系的表示方式一般为关联规则或频繁项集；
应用：挖掘市场销售数据，发现商品间的联系，帮助商场进行促销及货架的摆放；
挖掘医疗诊断数据，用于发现某些病症与某种疾病间的关系，为医生进行疾病诊断和治疗提供线索；
网页挖掘：揭示不同浏览网页之间的有趣联系；

基本概念

规则的支持度关于规则的前件和后件是对称的，但置信度不对称；
强关联规则：大于最小支持度阈值和最小置信度阈值的关联规则；
布尔关联规则：仅考虑数据项间是否同时出现；
量化关联规则：考虑数据项间是否存在某种数量上的关系；
单维关联规则：仅涉及数据项中的一个维；
多维关联规则：涉及数据项中两个或多个维度；
单层关联规则：仅针对具体数据项；
多层关联规则：考虑数据项的层次关系；

(1)项集：包含k个数据的项集称为k-项集；
(2)支持度计数：整个交易数据集中包含该项集的事务数
(3)频繁项集：一个项集在数据集中出现的次数大于某个阈值；
(4)支持度： S(X->Y) = 6(XUY)/N;
整个交易数据集中包含该项集的事务数除以所有事务数
置信度： S(X->Y) = 6(XUY)/6(X);
关联分析用于找出元数据集中隐藏的强规则，通常首先在数据集中找出频繁项集，然后从频繁项集中提取所有高置信度的规则；

Apriori

先验原理：如果一个项集是频繁的，那么它所有的子集也是频繁的；相反，如果一个项集是非频繁的，则它的所有超集也一定是非频繁的。
使用先验原理对树进行了部分剪枝；
关联规则的评估：
(1)通过统计论据来评估，支持度，置信度，提升度
支持度：反映了关联规则是否具有普遍性；
置信度：反映了关联规则的可靠性；
存在问题：支持度过高会导致一些潜在的有价值的关联规则被删去，置信度有时不能正确反映前件和后件之间的关联；
提升度：反映规则前后件的相关性，若提升度小于1说明前后件存在负相关关系，否则正相关；
lift(A,B) = P(AUB)/(P(A)P(B))
(2)主观评价
可视化：领域专家解释和检验被发现的模式，与数据挖掘系统交互；
基于模版的方法：允许用户限制挖掘算法提取的模式模型，只把满足用户指定的模板的规则提供给用户，而不是报告所提取的所有模式；
主观兴趣度度量：通过主观度量如概念分层，商品利润等，使用这些度量来过滤那些没有价值的模型；

FP-growth

使用频繁模式树(FP-Tree)的数据结构，并直接从该结构中提取出频繁项集，

非二元属性的关联规则分析

将其转换为二元属性
(1)标称属性取值过多；
(2)连续属性离散区间划分太宽或太窄；

关联规则评价

(1)客观兴趣度量：涉及相互独立的项或覆盖少量事务的模式被认为是不令人感兴趣的；
(2)主观兴趣度量：其表示的关联规则显而易见；

相关性分析

提升度：lift(A,B) = P(AUB)/P(A)P(B) = c(A->B)/s(B)
相关系数（适用于二元变量）：@ = (f11f00 – f01f10) /Math.sqrt(f1+f+1f0+f+0)
余弦定理：cosine(A,B) = s(A->B)/Math.sqrt(s(A)*s(B))

辛普森悖论

对数据集依照某个变量进行分组后，之前得到的关联规则可能就又不适用了；

频繁序列叫做序列模式；
Apriori性质：每个序列模式的非空子序列也为序列模式；
(1)排序阶段
(2)频繁项集阶段
(3)转换阶段
(4)序列阶段

5.1.列举关联规则在不同领域中应用的例子：
医学领域，发现病症与疾病之间的关联；
商业领域：发现商品之间的联系；

5.2.给出以下几种关联规则例子，说明它们是否有价值？
(a)高支持度和高置信度
主观兴趣度量，规则显而易见，无意义；
(b)高支持度与低置信度
无价值；
©低支持度与低置信度
无价值
(4)低支持度与高置信度
有价值；

5.3.数据集如图所示
1 0001 {a,d,e}
1 0024 {a,b,c,e}
2 0012 {a,b,d,e}
2 0031 {a,c,d,e}
3 0015 {b,c,e}
3 0022 {b,d,e}
4 0029 {c,d}
4 0040 {a,b,c}
5 0033 {a,d,e}
6 0038 {a,b,e}

a.将每一个事务当作一个购物篮，计算{e},{b,d},{b,d,e}的支持度；
s({e}) = 8/10 = 0.8
s{b,d} = 2/10 = 0.2
s({b,d,e}) = 2/10 = 0.2

b.使用a中的结果计算关联规则的置信度{b,d}->{e},{e}->{b,d}
c({b,d}->{e}) = s({b,d,e})/s({b,d}) = 0.2/0.2 =1
c({e}->{b,d}) = s({e,b,d})/s({e}) = 0.2/0.8 = 0.25

c.将每一个用户购买的所有商品看作一个购物篮，计算项集{e},{b,d},{b,d,e}的支持度
1 {a,b,c,d,e}
2 {a,b,c,d,e}
3 {b,c,d,e}
4 {a,b,c,d}
5 {a,b,d,e}
s({e}) = 4/5 = 0.8
s({b,d}) = 5/5 = 1;
s({b,d,e}) = 4/5 = 0.8

d.使用b中结果计算关联规则 {b,d}->{e}和{e}->{b,d}的置信度，置信度是一个对称的度量吗？
c({b,d}->{e}) = s({b,d,e})/s({b,d}) = 0.8/1 = 0.8;
c({e}->{b,d}) = s({b,d,e})/s({e}) = 0.8/0.8 = 1

5.4.关联规则是否满足传递性和对称性？举例说明？
不满足；

5.5.Apriori算法使用先验性剪枝，讨论如下类似性质。
a.证明频繁项集所有非空子集也为频繁项集；
support(s) = count(s)/N ,若s‘为s子集，则count(s)<=count(s’),因此support(s)<=support(s’)

b.项集s的任何非空子集s’的支持度不小于s的支持度；

c.给定频繁项集1和它的子集s，证明规则s’ ->(1-s’)的置信度不高于 s->(1 – s),其中s’为s的子集；
c(s -> (1-s)) = s(s,1,s)/s(s) = 1/s(s)
c(s’ -> (1-s’)) = s(s’,1,s’)/s(s’) = 1/s(s’)

s(s) = count(s)/N
s(s’) = count(s’)/N
因此 s(s) < s(s’); 1/s(s) > 1/s(s’)
因此 c(s -> (1-s)) > c(s’ -> (1-s’))

d.Apriori算法的一个变形是采用划分方法将数据集D中事务分为n个不相交的字数据集；证明D中任何一个频繁项集至少在D的某一个子数据集中是频繁的；

TODO 5.6.考虑如下3-项集 {1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5},{2,3,4},{2,3,5},{3,4,5}
a.根据Apriori算法的候选集生成方法，写出利用频繁3-项集生成所有的频繁4-项集
{1,2,3,4,5}
{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5}
b.经过剪枝后的4-项集
{1,2,3,4},{1,2,3,5}

5.7.一个数据库由5个事务，设置min_sup = 0.6;min_conf = 0.8;
T100 {M,O,N,K,E,Y}
T200 {D,O,N,K,E,Y}
T300 {M,A,K,E}
T400 {M,U,C,K,Y}
T500 {C,O,O,K,I,E}

a.使用APriori算法找出所有频繁项集合
M:3/5 = 0.6;
O:3/5 = 0.6;
N:2/5 = 0.4;
K:5/5 = 1;
E:4/5 = 0.8;
Y:3/5 = 0.6;
D:1/5= 0.2;
A:1/5 = 0.2;
U:0.2;
C:0.2;
I:04.2;
0频繁1-项集:M,O,K,E,Y
{M,O}:0.2
{M,K}:0.6@
{M,E}:0.4
{M,Y}:0.4
{O,K}:0.6@
{O,E}:0.6@
{O,Y}:0.4
{K,E}:0.8@
{K,Y}:0.6@
{E,Y}:0.4

频繁二项集：
{M,K},{O,K},{O,E},{K,E},{K,Y}

{M,K,O,E,Y}
{M,K,O}:0
{M,K,E}0.4
{M,K,Y}:0.4
{M,O,E}:0.2
{M,O,Y}:0.2
{M,E,Y}:0.2
{K,O,E}0.6@
{K,O,Y}:0.4
{K,E,Y}:0.4
{O,E,Y}:0.4

频繁三项集
{O,K,E}

(2)穷举法:Math.pow(2,11) – 1;
Apriori:23

(3)生成所有强关联规则和对应的支持度和置信度
s({O,K}->{E}) = s({O,K,E})/s({O,K}) = 0.6/0.6 = 1;
s({O,E}->{K}) = s({O,E,K})/s({O,E}) = 0.6/0.6 = 1;
s({K,E}->{O}) = s({O,K,E})/s({K,E}) = 0.6/0.8 = 0.75(小于min_conf，删去)

5.8.购物篮分析只针对所有属性为二元布尔类型的数据集。如果数据集中某个属性为连续型变量时，说明如何利用离散化的方法将连续属性转化为二元布尔属性。比较不同离散方法对购物篮的影响；
等高，等宽离散化：将连续属性离散化，然后将离散化后的每个区间映射为一个二元属性；
离散化时，若区间太宽，可能因为缺乏置信度而失去某些模式；若区间太窄，则可能因为缺乏支持度而失去某些模式；

5.9.使用置信度和支持度和提升度
置信度：
衡量一个关联规则是否可靠；缺点是会找到负相关的关联规则；
支持度：
衡量一个关联规则是否普遍；
若支持度阈值过高，则很多潜在的有意义的关联规则都会被删去；若支持度阈值过低，则会产生大量的无意义的关联规则；
提升度：可以用于评估项集A的出现是否会促进项集B的出现；缺点是会出现伪相互独立的规则；

5.10.下表展示了市场的食物数据

	hot dogs	!hot dogs	row
hamburgers	2000	500	2500
!hamburgers	1000	1500	2500
col	3000	2000	5000

关联规则=》 (hot dogs->hamburgers)
min_support= 0.25
min_conf = 0.50;

s(hot dogs,hamburgers) = 2000/5000 = 0.4;
c(hot dogs=>hamburgers) = s(hot dogs,hamburgers)/s(hot dogs) = 2000/3000 = 0.667;
0.4 > 0.25
0.667 > 0.50
是强关联规则;
lift(hot dogs=>hanburgers) = c(hot dogs->hamburgers)/s(hamburgers) = (2/3)/(1/2) = 4/3;

lift值大于1，说明hot dogs和hamburgers之间存在正相关关系，他们之间不相互独立；

**TODO 5.11.min_support = 2;

Sequence ID	Sequence ID
1	<a(abc)(ac)d(cf)>
2	<(ad)c(bc)(ae)>
3	<(ef)(ab)(df)>
4	<eg(af)cbc>

频繁1-项集:
a:3
b:4
c:3
d:3
e:3
f:3
g:1(去除)
(ab)
(bc)
频繁2-项集：
<>**

第六章.离群点挖掘

离群点是在数据集中偏离大部分数据的数据，使人怀疑这些数据的偏离并非由随机因素产生，而是产生于完全不同的机制。
离群点数据可能是由于测量，输入错误或系统运行错误而造成的，也可能是数据内在特性所决定的，或因客体的异常行为所导致；
基于统计的方法，基于距离的方法，基于密度的方法，基于聚类的方法，基于偏差的方法，基于深度的方法；

基于统计的方法

假定所给定的数据集存在一个分布或概率模型，然后将与模型不一致的数据标识为异常数据；
如果一个对象关于数据的概率分布模型具有低概率值时，则认为其是离群点；此类方法要求数据的分布是已知的，适用于低维数据，且不适用于混合类型数据；

基于距离的方法

判断一个对象是否为偏离点，如果一个对象远离大部分的点，则认为是离群点；
(1)采用给定领域半径，依据点的领域中包含的对象的多少来判定异常；
(2)利用k-最近邻邻域中对象距离大小来判定异常；
优缺点：
(1)简单
(2)时间复杂度O(n^2)，不适合于大型数据集，不能处理不同密度区域的数据集；
(3)检测结果对参数k的选择敏感
(4)需要有关离群因子阈值或数据集中离群点个数的先验知识

基于统计的方法和基于距离的方法都是从全局的观点来判定对象的异常，不能处理不同密度区域的数据集。当数据集含有多种分布或数据集由不同密度子集混合而成时，数据是否异常不仅仅取决于它与周围数据的距离大小，而且与邻域内的密度状况有关！

基于相对密度的方法

一个对象的邻域密度可以用包含固定节点个数的邻域半径或指定半径邻域中包含的节点数来度量；离群点是在低密度区域中的对象；
缺点：对参数近邻个数k的选择很敏感；时间复杂度较高，难以用于大规模数据集；需要有关异常因子阈值或数据集中异常数据个数的先验知识；

基于聚类的方法

中心极限定理：由大量微笑且独立的随机因素引起并积累而成的变量，必服从正太分布；

习题：
6.1.为什么离群点挖掘是重要的？
离群点可能对应于稀有事件或异常行为，离群点挖掘会带给我们新的视角和发现，离群点往往具有特殊的意义和很高的实用价值；
6.2.讨论如下方法的离群点检测方法的时间复杂u度：

    (1)基于聚类的：
		a.先采用特殊的聚类算法处理输入数据而得到簇，再在聚类的基础上检测离群点；
		b.仅需扫描数据集若干次，效率较高，适用于大规模数据集；
		
	(2)基于距离的：
		a.一个对象的k-最近邻的距离越大，越有可能远离大部分数据，因此可以将对象的k-最近邻距离看成是它的离群程度；
		b.时间复杂度为O(n^2)，难以用于大规模数据集；

	(3)基于密度的：
		a.一个对象是否为离群点不仅取决于它与周围数据的距离大小，而且与邻域内密度有关；从基于密度的观点来看，离群点是在低密区域中的对象。
		b.此处我认为其时间复杂度与基于距离的相同均为O(n^2)。

6.3.许多用于离群点检测的统计检验方法实在这样一种环境下开发的：数百个观测就是一个大数据集。我们考虑这种方法的局限性：
(1)如果一个值与贫均值的距离超过标准差的3倍，则检测称它为离群点。对于1000_000个值的集合，有离群点的可能性有多大？（假定服从正态分布）
0.0027 ->2700个离群点；
(2)一种方法称离群点是具有不寻常低概率的对象。处理大型数据时，该方法需要调整吗？如果需要，如何调整？
具有百万个对象的数据集中，有成千上万个离群点，可接受它们作为离群点或降低临界值用以减少离群点；

6.4.假定正常对象被分类为离群点的概率为0.01， 而离群点被分类为离群点概率为0.99，如果99%的对象都是正常的，那么假警告率或误报率和检测率各为多少？
检测率 = 检测出的离群点个数/离群点的总数 = 0.01*0.99/0.01 = 99%;
假警告率 = (1-0.99)*0.01 / 0.01 = 50%

6.5.从包含大量不同文档的集合中选择一组文档，使得它们尽可能彼此相异。如果我们认为相互之间不高度相关的文档是离群点，那么我们选择的所有文档可能都被分类为离群点。一个数据集仅由离群点对象组成可能吗？或者，这是误用术语吗？

6.6.考虑一个点集，其中大部分点在低密度区域，少量点在高密度区域。如果我们定义离群点为低密度区域的点，则大部分点被划分为离群点。这是对基于密度的离群点定义的适当使用吗？是否需要用某种方式修改该定义？
若密度有一个绝对意义，比如被指定到某一定义域内，那么它可能会非常合理的考虑将大部分点作为异常。然而，在很多情况下，为了能够使用异常检测技术，通常使用相对密度；

6.7.一个数据分析者使用一种离群点检测算法发现了一个离群子集。出于好奇，该分析者对这个离群子集使用离群点检测算法。
(1)讨论本章介绍的每种离群点检测技术；
在某些情况下，以统计学为基础的异常检测计数，在离群子集上使用这将是无效的，因为这种检测方法的假设将不再成立。对于那些依赖于模型的方法也是如此。以邻近点为基础的方法主要取决于特定的技术。如果保留原来的参数，使用距离或密度的绝对阈值的方法会将异常归类为一个异常对象的集合。其他相关方法会将大部分异常归类为普通点或将一部分归类为异常。
(2)当运用于离群点对象的集合时，离群点检测算法将作何反应？
一个对象是否异常取决于整个对象的集合。因此，期望一种异常检测技术能够辨别一个异常集合，就像原始集合中并不存在这样一个异常集合，这是不合理的；