数据挖掘常见算法整理 (国科大刘莹)

数据预处理

- 四分位法

例子：

3、5、9、11、17、19、35

先计算位置，在通过位置计算对应的数值

Q1：(n+1)*0.25=2

Q2：(n+1)*0.5=4

Q3：(n+1)*0.75=6

当下标正好为整数时，对应的数值为Q1=5、Q2=11、Q3=19

13, 15, 16, 16, 19, 20, 20, 21

Q1：(n+1)*0.25=2.25

Q2：(n+1)*0.5=4.5

Q3：(n+1)*0.75=6.75

当计算的下标不是整数时，介于第二和第三位之间，但是更靠近第二位。所以第二位数权重占75%，第三位数权重占25%

Q1=（15*0.75+16*0.25）=15.25、Q2=17.5、Q3=（20*0.25+20*0.75）= 20

IQR = Q3-Q1

five-number-summary: min Q1 middle Q3 max

处理异常数据的常见方法：bin方法，回归，聚类，人机检查结合

Bin方法

(a)

Bin1 5,10,11,13 mean:9.75

Bin2 15,15,15,55 mean:25

Bin3 60,60,65,65 mean:62.5

(b)

Bin1 5,13,13,13

Bin2 15,15,15,55

Bin3 60,60,65,65

Bin1: 5,10,11,13,15,15,15 mean:12

Bin2: NULL

Bin3: 55,60,60,65,65 mean:61

Normalization归一化

(a) 0 0.125 0.25 0.5 1

(b) 200-500/316.2 300-500/316.2 400-500/316.2 600-500/316.2 1000-500/316.2

数据相关系分析-皮尔逊系数

数据仓库

钻取(Drill-down) 使统计维度降到更细的层级，如下图时间维度从“季度”降到了“月份”层级，能降到多细要看底层数据有多细；

上卷(Roll-up) 则是反过程，“浙江”、“上海”、“江苏”的数据被汇总到了“江浙沪” 地区层级；

切片(Slice) 的过程则非常直观，三层cube被切出了一层。意思是在某些维度为定值时，在其他维度上观察数据。如图，确定商品种类为"电子产品", 从"时间"、“地点”上做观察统计；

切块(Dice) 类似于切片，不同点在于固定维度由定值变为范围值；

ppt例题

BitMAp

决策树

ID3

C4.5

GINI index

决策树评价
1.相对快
2.可以转换为简单易懂的规则
3.准确度相对较好
4.可扩展性较好，可扩展性：不同的分⽀计算互相独⽴互不影响，所以可以把任务分配给不同的机器上，保持时间的稳定
决策树的优化
1.允许连续值属性：动态定义新的离散值属性，该属性将连续属性值划分为离散的间隔集

2. 处理缺失值，基于已有的属性创建新属性

决策树过拟合处理方法：

提前剪枝：尽早停止构建树-如果会导致优度度量值低于阈值，就不要拆分节点；但是很难确定阈值
后剪枝：从“完全生长”的树上移除树枝-得到一系列逐渐修剪的树，就是把节点一个个去掉看评估结果；使用一个和训练集不同的集合来决定哪个是最好的剪枝

朴素贝叶斯：

贝叶斯优点
容易实现
结果一般较好
缺点：
假设属性独立，因此损失精度
实际上，变量之间确实存在依赖关系，但是朴素贝叶斯无法对其建模
解决这些依赖：
贝叶斯信念网络

Confusion Matrix

Cluster

K-means

优点：

1、简单，运算速度快，聚类效果较优

2、可解释性强

3、需要调节的参数少，仅 k 值

缺点：

1、k 值难以把握

2、非凸的数据集比较难收敛

3、数据不均衡会影响聚类效果

4、可能会得到局部最优解

5、异常值、噪音敏感

K-medioids

优点：当存在噪音和孤立点时, K-medoids 比 K-means 更健壮。
缺点：K-medoids 对于小数据集工作得很好, 但不能很好地用于大数据集，计算质心的步骤时间复杂度是O(n^2)，运行速度较慢

CURE

优点：

1）可以发现复杂空间的簇

2）受噪点影响小

缺点：

1）参数较多，包括采样的大小、聚类的个数、收缩的比例等；

2）抽样有误差；

3）难以发现形状非常复杂的空间簇（如中空形状），对空间数据密度差异敏感

4）虽然 CURE 聚类是针对大规模数据库设计的算法，但是当数据量剧增时，效率仍然不能满足需求

BIRCH(层次聚类)

优点：

1) 节约内存，所有的样本都在磁盘上，CF Tree仅仅存了CF节点和对应的指针。
2) 聚类速度快，只需要一遍扫描训练集就可以建立CF Tree，CF Tree的增删改都很快。
3) 可以识别噪音点，还可以对数据集进行初步分类的预处理
4) 可以不用输入类别数K值。如果不输入K值，则最后的CF元组的组数即为最终的K，否则会按照输入的K值对CF元组按距离大小进行合并。

缺点：

1) 由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同，一个CF数节点并不总是对应于用户所考虑的一个自然簇
2) 对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means
3) 因为其使用半径或者直径的概念来定义簇的边界，所以如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。
4) BIRCH适合于处理需要数十上百小时聚类的数据，但在整个过程中算法一旦中断，一切必须从头再来。

DBSCAN

优点：

1、不需要指定簇的个数

2、对噪音不敏感，可以在聚类的同时发现异常点

3、初始值对算法无影响

缺点：

如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
2）如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
3）调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对 (ε,MinPts) 联合调参，不同的参数组合对最后的聚类效果有较大影响。

异常点检测方法：

关联规则

fp-growth对比Apriori
FP-Growth的效率比Apriori高，尤其是最小支持度比较低的时候。
相比Apriori方法，FP-Growth通过记录树结构，根据到目前为止获得的频繁模式分解挖掘任务和数据库，同时，没有像Apriori那样产生候选子集，也不用去测试候选集是否满足最小支持度。
关键的是，在扫描数据库方面，FP-Growth只需要扫描数据库两次，降低了运行时间。
最后，FP-Growth是计算本地频繁项集并以此构建子FP树，无模式搜索和匹配。

数据预处理