基于网格的聚类：STING

基本思想：将对象空间量化为有限数目的单元，形成一个网格结构，所有的聚类都在这个网格结构中上进行。

其优点是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。

在网格聚类方法中有利用存储在网格单元中的统计信息进行聚类的STING算法和在高维数据空间基于网格和密度的聚类方法等。

STING是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。高层单元的统计参数可以很容易的从底层单元的计算得到。这些参数包括属性无关的参数count、属性相关的参数m（平均值）、s(标准偏差)、min(最小值)、max(最大值)以及该单元中属性值遵循的分布类型。

lSTING算法采用了一种多分辨率的方法来较粗，则聚类质量会受到影响。进行聚类分析，该聚类算法的质量取决于网格结构最低层的粒度。如果粒度比较细，处理的代价会显著增加；

STING算法的主要优点是效率高，通过对数据集的一次扫描来计算单元的统计信息，因此产生聚类的时间复杂度是O(n)。在建立层次结构以后，查询的时间复杂度是O(g), g远小于n。STING算法采用网格结构，有利于并行处理和增量更新。

基于层次的办法

层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。

• 凝聚的层次聚类：

  • 一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足，
  • 代表是AGNES算法

  

  最小距离法（Single Linkage）

  • 定义：在两个簇之间的所有可能配对样本点中，选择距离最小的一对样本点的距离作为簇间距离。

  • 特点

    ：

    • 链状效应：由于只考虑最接近的一对点，最小距离法容易形成链状结构，即若干个样本逐个连接在一起，形成较长的“链”。
    • 噪声敏感：对噪声和离群点（outliers）较为敏感，因为离群点可能会导致簇之间的最小距离变小，从而错误地合并簇。
    • 效率较高：计算简单，效率较高，但结果可能不稳定。

  • 适用场景：适用于数据集中的簇呈现不规则形状或链状结构的情况。

  最大距离法（Complete Linkage）

  • 定义：在两个簇之间的所有可能配对样本点中，选择距离最大的一对样本点的距离作为簇间距离。

  • 特点

    ：

    • 紧密簇：最大距离法倾向于形成紧密、球形的簇，因为它考虑了簇中最远样本点之间的距离，从而避免形成链状结构。
    • 抗噪声能力强：对噪声和离群点较为鲁棒，不容易被离群点影响，因为离群点的存在不会显著改变簇的最大距离。
    • 计算复杂度高：由于需要计算所有样本点的最大距离，计算复杂度相对较高。

  • 适用场景：适用于数据集中簇的形状较为规则、且希望得到更紧密的簇的情况。

• 分裂的层次聚类：

  • 采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。

  • 代表是DIANA算法;

  1 2 3 4 5 6 7 8 9 10 11 12 13

  算法 DIANA（自顶向下分裂算法） 输入：包含n个对象的数据库，终止条件簇的数目k。 输出：k个簇，达到终止条件规定簇数目。 （1）将所有对象整个当成一个初始簇； （2） FOR （i=1; i≠k; i++) DO BEGIN （3） 在所有簇中挑出具有最大直径的簇C； （4） 找出C中与其它点平均相异度最大的一个点p并把p放入splinter group，剩余的放在old party中； （5）. REPEAT （6） 在old party里找出到最近的splinter group中的点的距离不大于到old party中最近点的距离的点，并将该点加入splinter group。 （7） UNTIL 没有新的old party的点被分配给splinter group； （8） splinter group和old party为被选中的簇分裂成的两个簇，与其它簇一起组成新的簇集合。 （9） END.

基于密度的聚类算法：DBSCAN

只要一个区域中的点的密度大于某个阈值，就把它加到与之相近的聚类中去。

对于一个类中的每个对象，在其给定半径的领域中包含的对象不能少于某一给定的最小数目；

概念：

设置半径阈值$r$,数量阈值$m$;

核心对象的$r$-邻域至少包$m$个对象；

从核心对象出发，对任何$r$邻域内的点直接密度可达；

如果存在一个对象链$p_1，p_2，…，p_n，p_1=q，p_n=p$，对$p_i∈D，1\le i\le n$，$p_{i+1}$是从$p_i$关于$r,m$直接密度可达的，则对象$p$是从对象$q$​相互密度可达的。

如果存在一个对象$o$，使得对象$p$和$q$是从$o$关于$r,m$密度可达的，那么对象$p$和$q$​是密度相连的。

一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合 ;

• 连接性：$x_i\in C,x_j\in C \Rightarrow x_i,x_j$密度相连；
• 最大性：$x_i\in C,x_j$由$x_i$密度可达，$\Rightarrow x_j \in C$

DBSCAN算法先任选数据集中的一个核心对象为“种子” ,再由此出发确定相应的聚类簇;

算法类似于BFS搜索，维护一个队列；

优点：

• 能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类；
• 对噪声数据不敏感；

缺点：

• 计算复杂度大，需要建立空间索引来降低计算量；
• 数据维数的伸缩性较差；
• 对参数$r,m$非常敏感；
• 如果数据库比较大的时候要进行大量的I/O 开销;
• 很难找到不同密度的簇;

基于划分的聚类算法：K-means

基于划分的办法

算法初始化一个划分，之后通过迭代的办法优化这个划分方式；

如何定义优化？我们需要一个聚类目标函数作为指标：簇对象到簇中心平方误差
$$
E=\sum_{i=1}^{k} \sum_{x \in C_{i}}\left|x-\bar{x}_{i}\right|^{2}
$$
对于$K-means$算法，实现初始均值-簇分配-更新均值-收敛，如下：

一个直观的例子如图所示：

优点：

• 经典算法，简单、快速。
• 对处理大数据集，该算法是相对可伸缩和高效率的。

缺点：

• 初始值敏感；
• K需要预先设定，不是**Parameter-free **的；
• 只能发现类球状簇,不适合于发现非球形状的簇或者大小差别很大的簇；
• 离群点敏感；

绪论

为什么进行数据挖掘

• 数据挖掘把大型数据集转化成知识；
• 从大量的数据中挖掘那些令人感兴趣的、有用的、隐含的、先前未知的和可能有用的模式或知识 。
• 并非所有数据分析都是“数据挖掘”：查询处理，专家系统或是小型的数学计算/统计程序

大数据的特征

Big data is a buzzword, or catch-phrase, used to describe a massive volume of both structured and unstructured data that is so large that it’s difficult to process using traditional database and software techniques.

数据量volume,数据种类variety,数据速度velocity,数据真实性varacity

知识发现KDD：

• 数据清理：消除噪声和删除不一致数据

• 数据集成：多种数据源可以组合在一起

• 数据选择：从数据库中提取与分析任务相关的数据

• 数据变换：把数据变换和统一成适合挖掘的形式

• 数据挖掘：核心步骤，使用智能方法提取数据模式

• 模式评估：根据兴趣度度量，识别真正有趣的模式

• 知识表示：使用知识表示技术，向用户提供挖掘的知识

数据挖掘的主要任务

• 关联分析
• 聚类分析
• 分类/回归预测
• 离群点分析

数据挖掘与其他学科

离群点检测：cell-based挖掘DB(r,p)离群点

Background

循环嵌套发现$DB(r,\pi)$离群点在离群点数目较少时，表现出线性的性能，因为循环经常提前退出，尽管它的算法复杂度为$O(N^2)$。当数据集很大时，开销主要来源是不能将数据集放入主存，而对检查每个对象都需要潜在地遍历整个数据集

Content

将数据空间划分为$l$维网络，网络单元格对角线长度为$\frac r2$,边长为$\frac{r}{2\sqrt l}$;

对于单元格$c$，其余单元可以分为两类：

• $C_1$层：直接与$c$连接的单元；
• $C_2$层：$c$任意方向远离1格/2格的单元；

有两条几何上的先验性质(凸包)：

• $\forall x\in c,y\in C_1$,必有$dis(x,y)\le r$;
• $\forall x\in c, dis(x,y)\ge r$,必有$y\in C_2$

那么有两条相应的启发式剪枝规则：

• $|c|+|C_1|>\left \lceil \pi N \right \rceil$,说明$c$内对象均不离群的；
• $|c|+|C_1|+|C_2|<\left \lceil \pi N \right \rceil+1$,说明$c$内对象均离群的；

大部分点经过两个规则的判断都可以确定是否是离群点了；

算法如何降低空间开销？

答案是三次数据集的扫描；

• 第一次扫描：忽略掉空间内没有对象的单元格；
• 第二次扫描：排除掉已经可以剪枝确认是否离群的点；
• 第三次扫描：检查剩下的单元，找到所有离群点，

离群点(Outlier)和异常(Anomaly)检测

Background

异常数据通常作为噪音而忽略，但是在欺诈检测，入侵检测等领域，离群点能带来新的启发。

Content

概念

离群点：显著不同于其它数据对象，好像它是被不同的机制产生的一样；

噪声：观测变量的随机性产生；

分类

• 全局离群点：显著地偏移其他对象
• 情景离群点：依赖情景属性和行为属性，例如夏天的28℃和冬天的28℃
  • 局部离群点：密度偏离所在局部区域的密度；
• 集体离群点：数据集中的一个子集偏移整个数据集；

挑战

• 合适的建模
• 如何分辨噪声和离群点？
• 可解释性，针对应用

监督，半监督和无监督的方法

pass

基于统计学的检测

事先对数据集进行分布上的假设，采用不一致性检验(Discordancy test)；

例如经验告诉我们，假设数据集服从正态分布，需要参数如下：

• 数据集参数: 例如, 假设的数据分布
• 分布参数: 例如平均值和方差
• 和预期的孤立点的数目

缺点：

• 难以挖掘多维属性；
• 数据集分布未知，但有效性高度依赖于给定数据所做的统计模型假设是否成立。
• 不保证所有离群点被发现；

基于距离的检测

数据对象的给定半径的邻域内，如果没有足够多的邻居，那么被认定为离群点；

• 距离阈值$r$;
• 分数阈值$\pi$;
• 距离度量$dis(o,o’)$;

若$o$被认为是数据集$D$中的$DB(r,\pi)$离群点，即
$$
\frac{|{o’|dis(o,o’)}|}{|D|}\le \pi
$$
常见算法：

• K-d Tree
• 嵌套循环：遍历对象，计算对象半径内的邻居数，若中途超出阈值提前退出；
• 一种cell-based算法：先验性质剪枝

注意：$o_1,o_2$并不能被基于距离的算法检测到离群

基于偏离的检测

检查对象的主要特征，与给出的描述偏离大的对象被认为是离群点；

基于密度的检测

非离群对象周围的密度与其邻域周围密度类似，而离群点密度显著不同于邻域周围的密度；

• 对象$o$的$k-distance$:第$k$个最近邻之间的距离$dis_k(o)$；

  • 注意集合$N_k(o)={o’\in D-{o}|dis(o,o’)\le dis_k(o)}$可能大小超过$k$;

• 对象$p$相对于对象$o$的可达距离：$reachDis_k(p,o)=\max{dis_k(o),dis(p,o)}$

• 对象$o$的局部可达密度:$lrd_k(o)=\frac{|N_k(o)|}{\sum_{p\in D} reachDis_k(p,o)}$

  • 对象$o$的局部异常因子（Local Outlier Factor）:

    $LOF_k(o)=\frac{1}{|N_k(o)|}{\sum_{o’\in N_k(o)}\frac{lrd_k(o’)}{lrd_k(o)}}$​

    • 表示对象$o$的异常程度；

      • 簇中心的点LOF接近1，但是不能认为这样的点是异常的；

期末复习

简介

• 什么是大数据？
• 大数据的特征（4V,IBM）
• 什么是数据挖掘？
• 知识发现的流程
• 数据挖掘的主要任务
  • 关联规则挖掘
  • 分类/回归
  • 聚类分析
  • 离群点检测
• 数据挖掘和其他学科的关系

认识数据和数据预处理

• 属性类型
• 数据类型

• 相似性度量

  • 欧式距离

  • 曼哈顿距离

  • 闵可夫斯基距离

  • 余弦距离

  • 相关系数

  • 马氏距离

  • KL散度

• 数据预处理

  • 数据清理

    • 缺失值处理
    • 噪声处理

  • 数据集成

    • 相关分析

      • 卡方分析

    • 数据压缩

      • 维度压缩

        • PCA降维
        • 特征筛选：信息增益

      • 数据压缩

        • 聚类
        • 直方图
        • 采样

      • 数据变换

        • 最大-最小归一化
        • Z-score归一化

关联规则和挖掘

• 基本概念

  • 频繁项集
  • 什么是关联规则

• Apriori算法

  • 两个先验性质
  • 算法流程
  • 改进方法

• FP_Growth

  • 生成FP树，找频繁模式
  • 候选集产生-测试

• 关联规则评估

  • 置信度
  • 提升度，兴趣因子

分类

• 监督学习vs无监督学习
• 判别模型vs生成模型

• 分类算法

  • 决策树

    • 如何构造决策树
    • 如何对属性进行划分
    • 划分准则：id3,c4.5,cart,选择最具划分能力的feature，使得划分后的数据集越纯越好

    • 如何解决过拟合问题

      • 过拟合的原因

      • 如何避免过拟合

        • 去除噪声

        • 增加样本

        • Train-valid-test

        • 正则项

        • 限制树高

        • 设置最大叶子节点阈值

        • 先剪枝/后剪枝

  • KNN

    • lazy learning
    • 流程
    • 优点，缺点

  • Naive Bayes

    • 概率输出
    • 类条件下特征独立

  • SVM

    • 基本思想：间隔最大化
    • 优点及其原因
      • 支持最小样本
      • 泛化能力强
      • 高维非线性：核技巧

  • ANN

    • 感知机

    • BP算法

    • 优缺点：过拟合，训练慢

  • 集成学习

    • bagging（RF）
    • Boosting
    • stacking

聚类以及离群点检测

• 什么是聚类

• 聚类的功能

• 聚类的分类

  • 基于划分的聚类

    • K-means
      • 流程：初始均值-簇分配-更新均值
      • 缺点：初始值敏感，K是超参数，只能发现类球状簇，离群点敏感

  • 基于密度的聚类

    • DBscan关键概念，密度可达
    • DBscan流程
    • DBscan优缺点：任意球状簇，无需设置K，噪声鲁棒，$\varepsilon$难求，很难找到不同密度的簇

  • 基于层次的聚类：AGES，DJANA

  • 基于网络的聚类：STNG

• 离群点检测

  • 什么是离群点
  • 离群点类型（全局，局部，集体）
  • 方法
    • 基于统计的方法
    • 基于密度的方法
    • LOF算法
    • 基于偏离的方法
    • 基于距离的方法

大数据技术

• hash技术

  • hash作用
  • Shingle文档表征
  • 最小哈希
  • 如何得到签名矩阵
  • 近似计算
  • 局部敏感哈希
    • 基本思想：通过映射函数找到相似的候选集
    • trick：将签名矩阵划分为多个band，对每个band进行hash

• 数据流挖掘

  • 挑战（4个）单程处理，内存限制，时间复杂度，概念漂移
  • 什么是概念漂移
  • 概念漂移的检测方法
    • 基于分布的方法
    • 基于错误率的方法
    • 数据流分类
    • 数据流聚类
      • 框架：线上（微簇MC，簇特征，加减，增量）+线下

• Hadrop/spork

  • 什么是hadrop
  • 设计准则：并行化（自动），容错及恢复，简明接口

  • hadrop生态

    • HDFS（NatureNode,DataNode）
    • Mapreduce（计算）
    • spark（ROD：transformation懒惰，action）
    • spark与Mapreduce比较