数据挖掘学习笔记

* **数据爆炸** ：数据采集工具和成熟的数据存储技术使大量的数据被收集和存储。
* 我们拥有 _丰富的_ 数据，但是缺乏 _有用的_ 信息
* 迫切需要将 _传统的数据分析方法_ 与 _用于处理大量数据的复杂算法_ 相结合。

* 电子商务领域，金融领域，医疗健康领域，交通运输领域，社交媒体领域，制造业领域，教育领域，政府和公共服务领域，农业领域

* 代表一种**弹性** ，随着数据量的快速增长，能够保证旺盛的生命力，通过很少的改动甚至只是硬件设备的添置，就能实现处理能力的线性增长，实现高吞吐量和高性能 
  * 采样技术：随机采样、均匀采样、水库采样
  * 并行（分布式）计算：Map/Reduce计算框架
  * 在线/增量学习方法：持续学习（Continual Learning）

* **维度（Dimension）** 通常是描述数据的 _属性或特征_ ，比如地理位置、时间、类别、性别、职业等，它们是用来 _划分数据的类别或属性_ 。
* 为**低维** 数据开发的传统分析技术通常**不能** 很好地处理**高维** 数据
* 某些分析算法，随着**维度** （特征数）的**增加** ，计算复杂度会迅速**增加** 。

* 传统分析方法只处理包含**相同类型属性** 的数据集。
* 现在的**数据类型更复杂** ：文本、图像、音频和视频
* 为挖掘复杂对象，需要考虑**数据中的联系** * 时间和空间的自相关性
  * 图的连通性
  * 半结构化数据与XML文档的关系

* 针对在** _物理上分布式存储_** 的数据需要面临一系列挑战 
  * 如何降低分布式计算所带来的额外 _通信开销_
  * 如何有效地从 _多个数据源_ 获得挖掘结果
  * 如何解决数据 _安全和隐私_ 问题

* **属性** ：对象的性质或特性，因对象而异，或随时间而变化（也称为变量、特性、字段、特征或维）
* 一组属性用于描述对象（对象也称记录、点、事例、示例、实体或实例）
* 数据集：数据对象的集合

* 属性值是指定给特定对象属性的**数值** 或**符号** （数值可以具有无穷多个值，符号具有少量的值）
* 属性和属性值之间的区别（相同的属性可以映射到不同的属性值，不同的属性值可以映射到同一组值）
* 属性的性质可以不同于表示属性值的性质（年龄属性有最大值，而整数没有）

* 可以定义四种属性类型：**标称、序数、区间、比率** * **标称（Nominal）** ：标称属性的值是一些符号或实物的 _名称_ ，每个值代表某种 _类别、编码或状态_ 。比如：ID，性别
  * **序数（Ordinal）** ：序数属性可能的取值之间 _具有意义的序_ ，但相继值之间的 _差是未知的_ 。比如：排名，等级
  * **区间（Interval）** ：区间属性可能的 _取值之间是有序的_ ，不同取值之间的 _差异是有意义的_ 。比如：日期，温度
  * **比率（Ratio）** ：具有相等单位 _绝对零点_ 的变量，例如身高、体重等。
* 属性的类型取决于它拥有以下哪些性质/操作 
  * 相异性：=和\ne
  * 序：< 、\leq 、>、\geq
  * 差异：+ 和 -
  * 比率：* 和 /
* 标称：相异性；序数：相异性、序；区间：相异性、序、差异；比率：全具备

* **离散** ：具有 _有限个值_ 或者 _无限可数个值_ ，常用 _整数变量_ 表示 
  * 可以是分类的（如邮政编码或ID号），也可以是数值的（如计数）
  *  _二元_ 属性是 _离散属性的特例_ ，常用 _布尔_ 变量表示
* **连续** ：取 _实数值_ 的属性，常用 _浮点变量_ 表示 
  * 例如：温度、高度、重量
* 通常， _标称和序数_ 属性是 _二元的或离散的_ ， _区间和比率_ 属性是 _连续_ 的

* 只有存在 _非零属性值_ 才被视为重要（文档中出现的单词，客户购买过的商品）
* 非对称的二元属性：只有 _非零值_ 才重要的二元属性（对于关联分析特别重要）
* 也存在离散的/连续的非对称属性（比如文档中单词出现的次数/频率）

* **维度** ：数据对象具有的 _属性数_ 
  * 分析高维数据有时会陷入 _维灾难_ ，主要通过 _降维_ 解决
* **稀疏性** ：稀疏的数据对象 _大多数_ 属性值 _都是0_ 
  * 对于关联分析特别重要
* **分布** ：构成数据对象的属性的各种 _值或值得集合_ 出现的 _频率_ 
  * 很多数据的分布 _并非标准的统计分布_ ，比如高斯分布

* 数据集的分布特征可以从 _集中趋势_ 、 _离散程度_ 及 _分布形态_ 三个方面进行描述
* **集中趋势** * 主要测度： _众数、中位数、均值_ 
* 均值两点特质：各变量值与均值的离差之和等于0；离差平方和最小
* 几何平均值：适用于对比率数据的平均，主要用于计算平均增长率。计算公式G_m=\sqrt[n]{x_1 \times x_2 \times x_3 \times \cdots \times x_n}=\sqrt[n]{\prod_{i=1}^{n}x_i}
* **离散程度** * 反映观测变量各个取值之间的 _差异_ ，包括： _异众比率、四分位差、方差及标准差、标准分数、离散系数_ 等。
  * **异众比率** ：分类数据离散程度的测度，计算公式\frac{\sum_{}^{}{f_i-f_m}}{\sum_{}^{}{f_i}}=1-\frac{f_m}{\sum_{}^{}{f_i}}
  * **四分位数** ：顺序数据离散程度的测度，把数据分布划分成4个相等的部分，使得每部分表示数据的四分之一，这三个数据点就称为四分位数，下四分位数Q1、中位数Q2、上四分位数Q3.
  * **四分位差** ：Q=Q3-Q1，其中：Q1的位置=(n+1)/4，Q3的位置=3(n+1)/4
  * **方差和标准差** ：数据离散程度的最常用测度值；反映了各变量值与均值的平均差异；方差公式为s^2=\frac{1}{n}[(x_1-x)^2+(x_2-x)^2+\cdots+(x_n-x)^2]
  * **标准分数** ：也称标准化值，是对某一个值在一组数据中相对位置的度量，计算公式为z_i=\frac{x_i-\bar{x}}s
  * **离散系数** ：标准差与其相应的均值之比，消除了数据水平高低和计量单位的影响，其计算公式是V_s=\frac{s}{\bar{x}}
* **分布形态** * 分布形状通过 _偏态和峰态_ 衡量
  * **偏态** ：倾斜度（skewness），统计数据分布偏移方向和程度的度量。 
* 根据原始数据计算偏态系数SK=\frac{n\sum(x_i-\bar x)^3}{(n-1)(n-2)s^3}
* SK<0，左偏分布；SK>0，右偏分布；SK=0，对称分布
  * **峰态** ：是反应变量分布 _陡峭程度_ 的指标 
* 三种情况：标准正态分布、尖峰分布、扁平分布
* **分辨率（resolution）** ：经常可以在不同的分辨率下得到数据，并且在不同的分辨率下数据的性质不同。 
  * 数据的模式也依赖于分辨率。如果 _分辨率太高_ ， _模式可能看不出_ ，或者掩埋在噪声中；如果 _分辨率太低_ ， _模式可能不出现_ 。
* **数据集的类型：记录数据、基于图的数据、有序数据** * **记录数据集** ：记录的汇集，每个记录具有 _固定的、相同的属性集_ ，记录之间或属性之间没有明显的联系。 
* 事务数据：一种 _特殊类型的记录数据_ ；每个记录涉及 _一系列项_ ；事务数据是 _项的集合_ ，可以将其视为一组字段为非对称属性的记录
  * **基于图的数据** ：图捕获数据对象之间的联系，数据对象本身用图表示 
* 频繁图挖掘：在图的集合中发现一组频繁出现的子结构
  * **有序数据** * **时序事务数据** ： _事务数据的扩充_ ，每个事务包含一个与之相关联的时间
* **时间序列数据** ：在不同时间上收集到的数据，用于所描述现象随时间变化的情况（重要考虑 _时间自相关性_ ，即如果两个测量的 _时间很近_ ，则它们的 _值很相似_ ）
* **序列数据** ：一个数据集合，包含各个实体的序列，如词或字母的序列
* **空间和时空数据** ：具有空间属性的数据对象（重要考虑 _空间自相关性_ ，即 _物理上靠近_ 的对象趋于在 _其他方面也相似_ ；空间自相关类似于时间自相关）

* 人类的 _错误_ 、测量设备的 _限制_ 或数据收集过程中的 _漏洞_ 都可能导致 _不真实或重复的对象_ ， _也会存在不一致_
* **数据挖掘着眼于两个方面** * 数据质量问题的 _检测与纠正_ ——**数据清理** * 使用可以 _容忍低质量_ 数据的算法——**鲁棒算法**

* **测量误差** ：测量过程中产生的问题——记录值与实际值不同 
  * 误差：对于连续属性，测量值与真实值的差
* **数据搜集错误** ： _遗漏_ 数据对象或属性值，或者不当地包含了其他数据对象等错误
* 这两种问题可能是 _系统的_ ，也可能是 _随机的_

* 噪声：测量误差的 _随机部分_ ，通常涉及值被扭曲或加入了谬误对象（既有时间上的也有空间上的）
* 使用信号或图像处理技术 _降低噪声_ ，从而帮助发现可能“淹没在噪声中”的模式（信号）
* 鲁棒算法：在噪声干扰下也能产生可以接受的结果。
* 数据错误可能是 _更确定性现象_ 的结果，伪像就是数据的 _确定性失真_

* 测量过程和结果数据用精度和偏置度量
* 精度：（同一个量的） _重复测量_ 值之间的 _接近程度_ （用值集合的标准差度量S=\sqrt{\frac{\sum_{i=1}^{n}{(x_i-\bar x)^2}}{n-1}}）
* 偏置：测量值与被测值之间的 _系统的变化_ ）（用值集合的均值与被测量的已知值之间的差度量bias^2(x)=(\bar f(x)-y)^2)

* **准确率** ：被测量的测量值与实际值之间的接近度
* 一个重要方面是** _有效数字_** 的使用 
  * 目标是只使用与数据精度相符的数字来测量或计算结果
* 缺乏对数据和结果准确率的分析，分析者将可能出现严重的数据分析错误

* 离群点：具有 _不同于_ 数据集中其他 _大部分数据对象_ 的特征的数据对象，或是相对于该属性的典型值来说 _不寻常_ 的属性值。我们也称其为异常对象或异常值。
* **注意区分噪声和离群点** ：离群点是 _合法的_ 数据对象或值

* 一个对象 _遗漏_ 一个或多个属性值的情况 _并不少见_
* **应对策略** ： 
  * _删除_ 数据对象或属性：删除具有遗漏值的数据对象，然而有时即便不完整的数据对象也可能包含一些有用的信息
  *  _估计_ 遗漏值：可以采用 _插值方法、邻近点的属性（平均）值、近邻中最常出现的属性值_ 进行可靠估计。
  * 在分析时忽略遗漏值：采用没有遗漏值的属性来计算相似性。

* 数据可能包含不一致的值
* 无论原因是什么，重要的是 _能检测出来_ 并且如果可能的话， _纠正_ 这种错误，比如基于“ _校验_ ”信息
* 检测到不一致后，有事可以对数据 _进行更正_

* 数据集可以包含重复或几乎重复的数据对象
* **去重复** * 对于相同的对象，如果存在属性值不同，要 _一致化_
  * 避免意外地将两个相似但并非重复的数据对象合并
* 在某些情况下，两个或多个对象在数据库的属性度量上是相同的，但是仍然代表不同的对象

* **相似度** ：两个对象相似程度的数值度量（非负，0不相似，1完全相似） 
  * 区间变换：s'=\frac{(s-min\_s)}{(max\_s-min\_s)}，和min\_s分别是相似度的最大值和最小值
* **相异度** ：两个对象差异程度的数值度量（越类似相异度越低，[0,1]或[0,∞]取值） 
  * 区间变化：d'=\frac{(d-min\_d)}{(max\_d-min\_d)}
  * 如果相似度/相异度落在[0,1]区间，则相异度/相似度可以定义为d=1-s或s=1-d
* **邻近度** 表示相似性或相异性

* 下表显示了两个对象x和y在单个简单属性方面的相似性和不相似性

* 距离具有一些众所周知的性质
* 如果d(x,y)是两个点x和y之间的距离，则如下性质成立： 
  * 非负性d(x,y)\geq 0、同一性x=y,d(x,y)=0
  * 对称性d(x,y)=d(y,x)、三角不等式d(x,z) \leq d(x,y)+d(y,z)
  * 满足以上四个性质的测度称为度量
* **欧几里得距离**d(x,y)= \sqrt{\sum_{k=1}^{n}(x_k-y_k)^2}, n是维度，x_k和y_k分别是x和y的第k个属性
* **闵可夫斯基距离**d(x,y)=(\sum_{k-1}^{n}|x_k-y_k|^r)^{1/r} 
  * 三个特例 
* r=1，城市街区、曼哈顿、出租车距离d(x,y)=\sum_{k=1}^{n}|x_k-y_k|
* r=2，欧几里得距离（L2范数）
* r=∞，上确界距离、切比雪夫距离d(x,y)=\max_{k}{(|x_k-y_k|)}

* 对于相似度，三角不等式（或类似的性质）通常不成立，但是 _对称性_ 和 _非负性通常成立_
* 如果s(x,y)是两个点x和y之间的相似度，则如下性质成立 
  * 非负性0\leq s \leq 1;仅当x=y时，s(x,y)=1
  * 对称性 对于所有x和y，s(x,y)=s(y,x)

* 两个仅包含 _二元属性_ 的对象之间的相似性度量也称为相似系数，并且通常在0和1之间取值， _值为1表明两个对象完全相似_ ， _0表明对象完全不相似_
* 设x和y是两个对象，都由n个二元属性组成。这样的两个对象（即两个二元向量）D额比较可生成如下四个量： 
  * f_{00}：x取0并且y取0的属性个数
  * f_{01}：x取0并且y取1的属性个数
  * f_{10}：x取1并且y取0的属性个数
  * f_{11}：x取1并且y取1的属性个数
* **简单匹配系数SMC** SMC=\frac{值匹配的属性个数}{属性个数}=\frac{f_{00}+f_{11}}{f_{00}+f_{01}+f_{10}+f_{11}}
* **Jaccard系数** ：J=\frac{f_{11}}{f_{01}+f_{10}+f_{11}}，用来处理仅包含 _非对称的二元属性_ 的对象
* **文档** 用向量表示，向量的每个分量（属性）代表一个特定的词（术语）在文档中出现的频率；每个文档向量都是 _稀疏_ 的，因为它具有 _相对较少的非零属性值_ ；文档的相似性度量不仅影响Jaccard度量一样 _需要忽略0-0匹配_ ，而且还必须 _能够处理非二元向量_ 。
* **余弦相似度** cos(x,y)=\frac{x \cdot y}{||x||\space||y||}=\frac{\sum_{k=1}^{n}x_ky_k}{\sqrt{\sum_{k=1}^{n}x_k^2}\sqrt {\sum_{k=1}^{n}y_k^2}} 
  * 两个向量的内积(x \cdot y)适用于 _非对称属性_ ，只依赖于两个向量中 _非零的分量_
  * 两个文档之间的相似性只取决于它们中出现的单词
  * 余弦相似度实际上是x和y之间 _夹角（余弦）的度量_
  * 余弦相似度 _不考虑两个数据对象的量值_
* **广义Jaccard系数（Tanimoto系数）**T(x,y)= \frac {x \cdot y} { ||x||^2 + ||y||^2 - x\cdot y} = \frac {\sum_{k=1}^{n}x_ky_k} { \sum_{k=1}^{n}x_k^2 + \sum_{k=1}^{n}y_k^2- \sum_{k=1}^{n}x_ky_k } 
  * 在 _二元属性_ 情况下归约为Jaccard系数T(x,y)= \frac {x \cdot y} { ||x||^2 + ||y||^2 - x\cdot y} = \frac {f_{11}} { (f_{10}+f_{11})+ (f_{01}+f_{11})- f_{11} }
* **相关性** * 相关性经常被用来测量两组被观察到的值之间的 _线性关系_
  * 相关性可以测量两个变量（高度和重量）之间或两个对象（一对温度时间序列）之间的线性关系
  * 如果两个数据对象中的值 _来自不同的属性_ ，可以使用 _相关性_ 来度量属性之间的 _相似度_
  * 统计学中的 _三大相关性系数_ ： _Pearson Spearman Kendall_
  * **协方差** ：用来衡量两个变量的总体误差 
* **_变化趋势一致，正值，正相关；变化趋势相反，负值，负相关_** * ** _相互独立协方差为0，不相关_** * cov(X,Y)=\frac{\sum_{i=1}^{n}(X_i-\bar X)(Y_i - \bar Y)}{n-1}
* 方差是协方差的特殊情况，其中两个属性相同（属性与自身的协方差）
  * **皮尔森相关系数** 是协方差于标准差的比值 
* corr(x,y)=\frac{covariance(x,y)}{standard_{deviation(x)} \times standard_{deviation(y)} }=\frac{S_{xy}}{S_xS_y}
* S_{xy}=\frac{1}{n-1}\sum_{k=1}^{n}(x_k-\bar x)(y_k-\bar y), S_x=\sqrt{\frac{1}{n-1}\sum_{k=1}^{n}(x_k-\bar x)^2}, S_y=\sqrt { \frac{1}{n-1} \sum _{k=1} ^{n} (y_k-\bar y)^2 }
* 相关度总是在-1到1之间取值： _1（-1）意味着x和y具有完全正（负）线性关系_ ；相关度为0，则两个数据对象的属性 _不存在线性关系_ ，仍然 _可能存在非线性关系_ 。
  * 数据变换发现邻近度度量值不变，则该邻近度度量方法被认为 _对数据变换具有不变性_
  * 相关性度量对于缩放和平移都有不变性，而余弦度量只对缩放具有不变性
  *  _闵可夫斯基度量_ 对 _缩放和平移都是敏感的_

* 当属性具有 _不同的值域_ 通常称作变量具有 _不同的尺度_ 。
* 当 _属性相关_ 时、具有 _不同的值域（不同的方差）_ ，并且数据分布 _近似于高斯（正态）分布_ 时，**马氏距离** 是有用的M(x,y)=\sqrt{(x-y)^T \Sigma^{-1}(x-y)} 
  * \Sigma^{-1}是 _数据协方差矩阵的逆_ ，协方差矩阵的第ij个元素是第i个和第j个属性的协方差
* 当属性具有 _不同类型_ 时，直截了当的方法是 _分别计算_ 出每个属性之间的相似度，然后使用一种 _输出为0和1之间相似度_ 的方法 _组合这些相似度_ 。 
  * 将总相似度定义为所有属性相似度的平均值；当某些属性是 _非对称属性_ ，如果两个对象在这些属性上的 _值都是0_ ，则在计算对象相似度时 _忽略它们_

* 分类任务的数据由元组(x,y)组成，其中x是描述实例的 _属性值集合_ ，y是实例的 _类别标签_ 。属性集x可以包含 _任何类型的属性_ ，而 _类别标签y必须是可分类的_ 。
* 分类模型是 _属性集和类别标签之间关系_ 的抽象表示，在数学表达上作为一个** _目标函数f_** ，它将 _属性值x作为输入_ 并产生 _一个对应于预测类别标签的输出_ ，如果f(x)=y，则该模型可正确地对实例(x,y)进行分类
* 分类模型在数据挖掘中担当 _两个重要角色_ ： 
  * **预测模型** ：对先前未标记的实例进行分类（一个好的分类模型必须以 _快速的响应时间_ 提供 _准确的预测_ ）
  * **描述性模型** ： _识别_ 不同类别实例的 _特征_
*  _类别标签_ 必须是 _标称类型_ ，可能 _并非所有属性_ 都与分类任务 _相关_ ，寻找区分不同类别实例的 _最佳属性组合_ 是构建最优分类模型的 _关键挑战_ 。

* 二分类器将每个数据实例分配给两种可能的标签中的一种，通常表示为 _+1（正类）和-1（负类）_ 。 _正类通常指的是我们对正确预测更感兴趣的类别_ 。
* **多分类器** ：有 _两个以上的可用标签_
* **确定性分类器** ：对每个它分类的数据实例产生一个 _离散值标签_
* **概率性分类器** ：分配一个 _在0-1之间的连续的分数_ 来表示特定标签的 _可能性_ ，各 _分类下概率总和1_ （提供了更多分配到类时的 _置信度信息_ ，实例通常分配给 _概率得分最高的类_ ）
* **线性分类器** ：用一个 _线性分离超平面_ 来区分不同类别中的实例
* **非线性分类器** ：能够构造 _更复杂的_ 、 _非线性的_ 决策表面（ _拟合复杂数据不太灵活_ ，但不容易过拟合）
* **全局分类器** ：用 _单个模型拟合整个数据集_
* **局部分类器** ：将输入空间划分为 _更小的区域_ ，并将 _不同的模型拟合于每个区域_ 的训练实例（K近邻分类器是一个经典例子， _更具灵活性_ ，但更容易过拟合）
* **生成分类器** ：在预测类别标签的过程中， _学习每个类的生成模型_
* **判别分类器** ：在没有明确描述每个类别分布的情况下， _直接预测类别标签_ （不用对生成机制进行深入研究）
* **基分类器** ：基于决策树的方法、基于规则的方法、最近邻方法、朴素贝叶斯和贝叶斯信念网络、支持向量机、神经网络、深度神经网络
* **集成分类器** ：提升、装袋、随机森林

* 分类模型是 _使用给定的一组实例创建_ 的，这组实例称为 _训练集_ ，其中包含每个实例的属性值以及类别标签
* **学习算法** ：用于学习给定训练集的分类模型的系统方法
* **归纳** ：使用学习算法 _从训练数据建立分类模型_ 的过程
* **演绎** ：在 _未知的测试实例_ 上应用分类模型来 _预测它们的类别标签_ 的过程
* 训练集和测试集应该是 _相互独立的_ ，以确保归纳模型能够准确 _预测以前从未遇到过_ 的实例的类别标签——** _具有良好的泛化性能_** * 模型（分类器）的性能可以通过 _比较实例的预测标签和真实标签_ 来评估，这些信息可以在 _混淆矩阵_ 中总结出来。
* 评估度量：准确率，错误率 
  * 对于二分类问题，准确率=\frac{正确预测的数量}{总预测数量}=\frac{f_{00}+f_{11}}{f_{00}+f_{01}+f_{10}+f_{11}}
  * 对于二分类问题，错误率=\frac{错误预测的数量}{总预测数量}=\frac{f_{01}+f_{01}}{f_{00}+f_{01}+f_{10}+f_{11}}
  * 大多数分类计数的学习算法旨在学习 _在应用于测试集_ 时达到 _最高准确度_ 或 _等效最低错误率_ 的模型

* 从根结点开始，应用其属性测试实例，并根据测试结果按照适当的分支进行操作；一旦到达叶结点，将于该结点关联的类别标签分配给测试实例。

* _搜索空间_ 随数据集规模 _指数级上升_ ， _寻找最佳数的代价是昂贵的_
* 需要在 _合理的时间内_ 归纳 _出具有合理准确率的决策树_ ， _尽管不是最优的_
* ** _贪心策略_** ：以 _自顶向下_ 的方式生成决策树，对 _划分训练数据时要使用的属性_ 进行一系列 _局部最优_ 决策
* 决策树是 _递归方式_ 生长，最初包含 _与所有训练实例关联的单个根结点_ ；
* 如果某个结点 _与来自多个类的实例相关联_ ，则会使用由** _拆分标准_** 确定的 _属性测试条件_ 进行扩展。为每个属性测试条件的每个结果 _创建一个子结点_ ，并将与父结点关联的实例 _分发给子结点_ ，可以 _递归应用于每个子结点_ （只要它具有多个类的标签），如果某个叶结点相关 _所有实例都具有相同的类别标签_ 则不会进一步扩展
* **两个关键问题：拆分标准、终止标准** * **拆分标准** ：决定选择哪个属性作为测试条件以及如何将训练实例分配给子结点
  * **终止标准** ：确定何时应该终止扩展结点的条件

* **二元属性** 的测试条件产生** _两个可能_** 的输出
* **标称属性** 可以 _有多个属性值_ ，因此** _多路划分和二元划分_**(2^{k-1}-1种)
* **序数属性** 也可以产生二元或多路划分，只要分组 _不违反有序性_ 就能分组
* **连续属性** 的测试条件可以表示为产生二元划分的比较测试或表示用于产生多路划分的形的范围查询

* **贪心算法** ：优先考虑更纯净的子集的属性测试条件 
  * 基尼指数：Gini\space Index=1-\sum_{i=0}^{c-1}p_i(t)^2
  * 熵：Entropy=-\sum_{i=0}^{c-1}p_i(t)log_2p_i(t)
  * 分类误差：Classification\space error=1-max[p_i(t)]
* **子结点的不纯性度量** ：I(子结点)=\sum_{j=1}^{k}\frac{N(v_j)}{N}I(v_j) 
  * 差异越大条件越好，差异也叫**纯度增益**\Delta=I(父结点)-I(子结点)
  * I(v_j)是该结点子结点的 _熵_ 时，通常称为** _信息增益_**\Delta_{info}

* 熵和基尼指数等不纯性度量存在一个 _潜在的局限_ ，即它们更容易选择 _具有大量不同值的定性属性_
*  _单一的低不纯性结点_ 不足以找到良好的属性测试条件
*  _子结点越多_ ， _决策树越复杂_ ，更容易出现 _过拟合_
* 在决定最佳属性测试条件时，考虑划分属性产生的子结点数量（一种方法是 _仅生成二元决策树_ ，从而避免使用不同数量的划分来处理属性；另一种方法是修改划分标准以 _考虑属性生成的划分数量_ ）
* Gain\space Ratio=\frac{\Delta_{info}}{Split\space Info}, Split \space Info=-\sum_{i=1}^{k}\frac{n_i}{n}log_2\frac{n_i}{n} 
  * 划分信息（Split Info)测量将结点 _划分成子结点的熵_ ，并评估划分 _是否会导致大量相同大小的子结点_
  * 如果属性 _产生大量的划分_ ，则其划分信息也很大，从而 _降低了增益率_

  * 非参数化，不需要先验假设因此适用于各种各样的数据集（连续可分类、多分类），易于理解，简单数据集准确率也与其它分类技术相当

  * 离散值函数通用表示，可以编码任何离散值属性的函数；每个离散值函数表示为一个赋值表，其中每个离散属性的唯一组合都被赋予一个类别标签，由于每个属性组合可以表示为一个叶结点所以总能找到

  * 数量可能非常大因此采用基于启发式的方法来指导搜索，自顶向下的贪心递归划分策略，最坏情况下复杂度为O(\omega)，\omega是树的最大深度

  * 信息增益的计算式推广为Gain(D,a)=\rho\times Gain(\tilde{D},a)=\rho \times (Ent(\tilde D)-\sum_{v=1}^{V}\tilde r_v Eny(\tilde D^v)
  * 其中，Ent(\tilde D)=-\sum_{k=1}^{|y|}\tilde p_klog_2\tilde p_k
  * C4.5使用概率划分，CART使用替代划分，CHAID使用独立类

  * 相互作用：一起使用能区分类别，单独使用提供很少或不提供信息
  * 存在相互作用时决策树可能表现不佳

  * 属性对分类任务无用就利用特征选择技术消除

  * 属性间强相关说明有属性冗余，选一个作为属性测试条件

  * 边界称为 _决策边界_ ，一次只涉及 _单个属性_ ，边界是直线 _平行于坐标轴_ ；限制了决策树在表示具有 _连续属性_ 数据集的决策边界时的表达能力； _倾斜决策树_ 可以通过允许 _使用多个属性_ 指定测试条件来克服这个限制

* 决策树分类器是 _渴望学习器_ ， _懒惰学习器_ 是 _延迟建模过程直到需要对测试实例进行分类_
* **最近邻** ：找到与测试实例的属性 _相对形似的_ 所有训练实例，用来 _确定测试实例的类别标签_ 
  * 最近邻分类器将 _每个样本_ 表示为 _d维空间_ 中的数据点，其中d为属性数目
  * 给定一个 _测试实例_ ，计算它与训练实例的 _接近程度_
  * 在邻居有多个标签的情况下，将测试实例分配给其最近邻居的类

* 在 _多数表决_ 方法中， _每个邻居_ 对分类 _具有相同的影响_
* 为了 _减少k的影响_ 的方法之一是， _根据距离权衡_ 每个最近邻的影响
* 使用距离加权w_i=\frac{1}{d(x',x_i)^2}投票方案，距离z较远的训练实例对分类的影响要小于距离z较近的

* 最近邻分类器是以 _实例学习_ 而闻名的一种通用技术
* 需要用 _邻近度量_ 来确定 _实例之间的相似性或距离_ ，以及基于测试实例与其他实例的 _邻近度_ 返回其预测类别的分类函数
* 基于 _局部信息预测_ ，具有较小的k值， _对噪声非常敏感_
* 难以处理缺失值，因为通常 _需要所有属性存在_
* 如果 _有高度相关的冗余属性_ ，可能 _过度偏向_ 导致错误
* 除非 _采取适当的邻近度量_ 和 _数据预处理步骤_ ，否则可能出错

* 不确定性，所以需要置信度的度量
* **概率分类模型** ：利用概率论来表示属性和类别之间的关系

* **边缘化** ：对随机变量Y的联合概率求和，我们得到观察剩余变量Y的概率
* **贝叶斯定理** ：P(Y|X)=\frac{P(X,Y)}{P(X)}=\frac{P(X|Y)P(Y)}{P(X)} 
  * **全概率公式** ：P(X)=\sum_{i=1}^{k}P(X,y_i)=\sum_{i=1}^{k}P(X|y_i)\times P(y_i)
  * P(Y)是 _类先验概率_ ，P(Y|X)是 _后验概率_ ，P(X|Y)是 _类条件概率_ （生成分类模型），P(X)不依赖于类别标签可被视为 _归一化常数_

* **条件独立** ：独立P(X_1,X_2|Y)=P(X_1|Y)\times P(X_2|Y),假设P(X|Y)=\prod_{i=1}^{d}P(x_i|Y)
* **工作机制** ：P(y|x)\propto P(x)\prod_{i=1}^{d}P(x_i|y),选择能够 _最大化后者_ 的类，可以自然地 _处理缺失值_ ，没有极端情况仍然可以 _使用先验概率作为后验概率的估计_
* **高斯分布**P(X_i=x_i|Y=y_j)=\frac{1}{\sqrt{2\pi}\sigma_{ij}}exp[-\frac{(x_i-\mu_{ij})^2}{2\sigma_{ij}^2}]，可以用样本均值估计期望值\mu_{ij}，可以用样本方差S^2来估计方差\sigma_{ij}
* 对噪声/不相关属性具有 _鲁棒性_

* **支持向量机SVM** 是一种 _二分类_ 模型，用于 _学习属性空间中的线性或非线性决策便捷来分离类_
* 提供 _正则化能力_ ，控制复杂度确保良好 _泛化性能_ ， _学习高度表达模型而不过拟合_
* 仅使用 _最难分类的一个子集_ 来表示 _决策边界_ （也即支持向量）
*  _判别模型_ ，只受两类边界附近的训练实例的影响，而不是学习每个类的生成分布

* **_通用方程_**w^Tx+b=0
* x代表参数，(w,b)代表超平面的参数。x可以属于超平面 _任一侧_ ，取决于w^Tx+b的符号
* 存在能够完全分离数据集中的类的超平面，则数据集是 _线性可分_ 。
* **边缘超平面** （分离超平面的平行超平面且接触到两个类最近的实例的超平面），间距称为超平面的边缘 
  * **支持向量** ：距离超平面最近的几个样本点
  * 较大边缘泛化性能更好（边缘大有余地处理鲁棒性）；边缘小容易受干扰和过拟合

* 线性SVM是寻找具有最大边缘的分离超平面的分类器，因此它也经常被称为最大边缘分类器
* 令w^Tx+b=0是一个分离超平面的方程，它通过将两个类放置在超平面相反的两侧来分离这两个类\left\{  \right.
* 任意线x到超平面的距离D(x)=\frac{|w^Tx+b|}{||w||}

* 需要一个非线性变换\varphi，将数据从其原始属性空间映射到一个新的空间，以便线性超平面可以分离这些类。新空间可以构建一个线性超平面。w^T\varphi(x)+b=0

* **SVM的优化问题** ：\min_{w,b}\frac{||w||^2}{2} \\  
  * s.t \space\space\space\space\space\space y_i(w^Tx_i+b)\geq1
  * 拉格朗日乘子\lambda，**对偶优化问题** ，仅受最接近SVM的决策边界的支持向量影响
  * **最大边缘超平面** 可以表示为f(x)=(\sum_{i=1}^{n}\lambda_iy_ix_i^Tx_j)+b=0

* **组合或分类器组合** ：通过 _聚集多个分类器的预测_ 来 _提高分类准确率_ 的技术。 
  * 构建一组几分类器，并通过对每个基分类器的预测 _进行投票_ 来分类
*  _组合分类器的性能优于单个分类器_ 必须满足两个必要条件： 
  * _基分类器应该相互独立_
  *  _基分类器应该好于随机猜测分类器（_ _\epsilon小于0.5）_

* **基本思想** ：在 _原始数据上构建多个分类器_ ，然后在 _分类未知样本_ 时 _聚集_ 它们的预测结果
* **通过处理训练数据集** ：抽样得到多个数据集，装袋、提升
* **通过处理输入特征** ：选择输入特征的子集，随机森林（决策树）
* **通过处理类标签** ：适合类数足够多，类标签随机划分两个子集变换为二分类问题，重新标记数据得到新的一组基分类器，统计选票，例如ECOC错误-纠错编码
* **通过处理学习算法** ：相同的训练数据上多次执行算法

* **装袋/自助聚集** ：根据 _均匀概率分布_ 从数据集中 _有放回的重复抽样技术_ 。每个自助样本集都和原始数据集一样大。
* **决策树桩** ：仅包含一层的二叉决策树

* 提升是一个 _迭代的过程_ ，用于 _自适应地改变训练样本的分布_ ，使得基分类器聚焦那些 _难以分类的样本_ 。
* 不同于装袋，提升给每个训练样本 _赋一个权重_ ，而且可以在每一轮提升过程结束时 _自动地调整权重_ 。可以用来 _抽样分布_ 或者 _学习偏向于更高权重示例的模型_ 。
* 初始时权重都相同\frac{1}{N}，每一轮提升结束更新权重，增加错误样本权重，减少正确分类样本权重。
* **AdaBoost算法** ：错误率\epsilon=\frac{1}{N}[\Sigma_jw_j\delta(C_i(x_j)\ne y_j] 
  * C_i是基分类器，\delta判断谓词真则为1否则为0
  * w_j^{(i)}表示第i轮迭代分配的权重，更新方式w_j^{(i+1)}=\frac{w_j^{(i)}}{Z_i}\times \left\{  \right.
  * \alpha_i称为基分类器C_i的重要性，定义为\alpha_i=\frac{1}{2}ln(\frac{1-\epsilon_i}{\epsilon_i})

* 随机森林试图通过构建 _去相关决策树组合分类器_ 来提高 _泛化性能_ 。
* 基于 _装袋_ 的思想，使用不同训练数据集的自助样本来学习决策树；与装袋的关键区别在于 _在一小组随机选择的属性中选择划分标准_ 
  * 随机森林不仅通过 _操纵训练实例_ ，还通过 _操纵输入属性_ 来构建决策树的集合。
  * 有放回随机抽样实例 ➡️ 随机抽样一组p个属性 ➡️ 选择一个属性

* 模型 _没有_ 很好地捕捉到数据特征， _不能够_ 很好地拟合数据，这种情况称为 _模型欠拟合_ 。
* 有的模型即使 _能够很好地覆盖训练数据_ ，但它仍然可能表现出 _较差的泛化性能_ ， _过拟合_ 。
* **模型过拟合** ：在 _追求训练错误率最小化的过程_ 中，选择了一种 _过于复杂的模型_ ，这种模型捕捉到了 _训练数据中的特定模式_ ，但没能获取到 _整体数据中属性和类别标签之间的本质关系_

* 有限的训练规模：增大训练数据可以减少过拟合影响
* 高模型复杂度

* 模型评估：估计模型泛化性能的方法
* 正确方法：在有标签的测试集上，对学习模型的性能进行评估，测试集从未被使用 
  * D.train用于模型选择，D.test用于计算测试错误率err_{test}

* 多次重复，随机子采样/重复留出法

* 随机划分，不同子集测试，最后求均值
* **k折交叉验证方法** ：分成k相等大小的分区或子类，重复k次 
  * 特殊情况：留一法，每次运行只使用一个数据实例进行测试

* 超参数不会出现在最终分类模型
* 取值在模型选择期间被确定，模型评估期间也要考虑超参数

* D.train分为三个部分，其中一折D.val用于验证，其余两折D.tr用于训练
* 求和计算，选择验证错误率最低的超参数p^*，并使用它习得模型m^*

* **倾斜/类不平衡** ：不同类别的实例数量不接近
* 带来**两个挑战** ： 
  * 很难找到 _充足的稀有类别的样本_
  *  _准确率_ 不适合在 _类不平衡的测试数据_ 中评估模型

* **考虑因素** ： 
  * 既能充分表示多数类，也能表示少数类（过采样、欠采样）
  * 调整分类决策，匹配不平衡测试集的要求，分类模型输出转换为实数分数然后选择合适的阈值
* **平衡数据集** ：欠采样（降低多数类）、过采样（生成少数类SMOTE）

* **回归分析** ：确定 _两种或两种以上变量间相互依赖的定量关系_ 的一种统计分析方法
* 作为一种 _预测模型_ ，它基于 _观测数据_ 建立变量间 _适当的依赖关系_ ，以便分析数据间的内在规律，并应用于 _预测、控制_ 等问题

* 回归与分类均为 _有监督学习_ 问题，其中 _输入x_ 和 _输出y_ 的数值是 _给定_ 的，任务是 _学习_ 从输入到输出的映射 
  * 按照问题所 _涉及变量的多少_ ，可将回归分析分为 _一元回归分析_ 和 _多元回归分析_
  * 按照自变量和因变量之间 _是否存在线性关系_ ，分为 _线性回归分析_ 和 _非线性回归分析_

* **线性回归** ：因变量y和一个或多个自变量x之间建立一种** _线性方程关系_** * 线性回归是常用的建模技术之一，也通常是人们在学习预测模型时首选的技术之一
  * 在这种技术中， _因变量是连续的_ ， _自变量可以是连续的也可以是离散的_
*  _只有两个变量_ ，一个因变量和一个自变量，且自变量与因变量之间的函数关系能够 _用一条直线来近似表示_ ，那么称其为 _一元线性回归分析_ 。

* E(y)=\beta_0+\beta_1x
* 这个方程对应的图像时一条直线，称作回归线，其中\beta_0是回归线的截距，\beta_1是回归线的斜率，E(y)是给定x值下y的期望值（均值）
* **最小二乘法** * 出发点是使实际测量数据y_i与拟合直线上的估计值\hat{y_i}的差（残差）的平方和为最小，即min\sum(y_i-\hat{y_i})^2
  * 让总的误差的平方最小的y就是真值，这是基于“如果误差是随机的，应该围绕真值上下波动”
  * \beta_o=\frac { \sum x_i^2\sum y_i-\sum x_i\sum x_iy_i } { n\sum x_i^2-(\sum x_i)^2 }, \beta_1=\frac { n\sum x_iy_i-\sum x_i\sum y_i } { n\sum x_i^2-(\sum x_i)^2 }

* 线性模型试图学得一个通过 _属性的线性组合_ 来进行预测的函数，即f(X)=\beta_0+\beta_1X1+\beta_2X2+\cdots+\beta_dX_d
* \beta_1,\beta_2,\cdots,\beta_d称为 _偏回归系数_ ，\beta_i的意义是当 _其他自变量X_j(j\ne i)都固定_时， _自变量X_i每变化一个单位_而使 _因变量平均改变_ 的数值
* 参数的最小二乘估计量为\beta=(X^TX)^{-1}X^TY

* 两个现象变量之间的相关关系 _并非二元关系_ ，而呈现 _某种非线性的曲线关系_
* 对于非线性回归问题，常采用适当的 _变量代换_ ，把问题 _转化为线性回归问题_ ， _求出线性回归模型_ 后代回，得到非线性回归方程。

* 样本点分布在某幂函数曲线y=c_1x^{c_2}的周围，其中c_1,c_2是待定参数。
* 变量代换：令m=ln\space y,\space n=ln \space x，变换后样本点应该分布在直线m=an+b的周围，其中a=c_2,\space b=ln\space c_1

* 样本点分布在某一条指数函数曲线y=c_3e^{c_4x}的周围，其中c_3,\space c_4是待定参数
* 变量代换：令z=ln\space y，变换后样本点应该分布在直线z=ax+b的周围，其中a=c_4, \space b=ln\space c_3

* 进行多项式回归分析，首先要 _确定多项式的次数_ ，一般是 _根据经验和实验_
* 假设确定了用一个一元k次多项式来拟合训练样本集，多项式函数表示为\hat y=\beta_0+\beta_1x+\beta_2x^2+\cdots+\beta_kx^k，令x_1=x,\space x_2=x^2,\space \dots,\space x_k=x^k，则该式可化为\hat y=\beta_0+\beta_1x+\beta_2x_2+\cdots+\beta_kx_k，后续采用 _类似于多元线性回归_ 的方法求解各\beta值。
* 多项式回归的优势在于它可以拟合处各种形状的曲线。然而，随着 _多项式阶数的增加_ ，模型的 _复杂度也会增加_ ，可能会导致 _过拟合的问题_ 。

* **logistic回归** ：一种 _概率判别类型_ ，它直接 _利用其属性值来估计数据实例x的概率_
* logistic回归的基本思想是使用 _线性预测器_z=w^Tx+b表示x的 _概率_ ：比率值\Rightarrow \frac{P(y=1|x)}{P(y=0|x)}=e^z=e^{w^Tx +b }
* 如果w^Tx+b >0，那么x属于第1类，因为它的比率值大于1；否则，x属于第0类
* 由于P(y=0|x)+P(y=1|x)=1，可以重写\frac{P(y=1|x)}{1-P(y=1|x)}=e^z，进一步简化，将P(y=1|x)表示为z的函数P(y=1|x)=\frac{1}{1+e^{-z}}=\sigma(z) 
  * \sigma(\cdot )称为logistic或者S形函数
  * P(y=0|x)可以表示为P(y=0|x)=1-\sigma(z)=\frac{1}{1+e^{z}}
  * 如果知道了参数w和b的合适值，可以用上式来估计任何数据实例x的后验概率，并确定其类别标签

* 参数(w,b)是在训练过程中使用最大似然估计法来估计的：需要观察训练数据可能性，然后确定最大似然估计下的模型参数

* logistic回归是一种用来 _直接计算概率的判别类型_ ，它不做任何关于条件概率的假设。因此，它是相当通用的，可以应用于不同的应用程序。它也可以 _轻松地扩展到多分类_ ，那是，它被称为多项式logistic回归。然而，它的表达能力 _仅限于学习线性决策边界_ 。
* 因为每个属性都有不同的权重（参数），因此可以分析logistic回归的学习参数来理解属性和类别标签之间的关系

* **关联分析** ：用于发现隐藏在大型数据集汇总有意义的联系 
  * 大型事务数据集代价高，发现的模式可能是偶然的虚假的 ➡️ 有效、评估
* **频繁项集** ：用出现在许多事务中的项集来表示所发现的联系
* **关联规则** ：表示两个项集之间的关系

* **二元表示** ：每行一个事务，每列对应一个项，项用二元变量表示（非对称二元变量）
* I是所有项的集合，T是所有事务的集合，每个事务包含的项集都是I的子集。
* **支持度计数/包含某特定项集的事务个数** ：\sigma(X)=|\{t_i|X\subseteq t_i,\space t_i\in T \}|
* **支持度** ：某一项集出现的比率s(X)=\frac{\sigma(X)}{N} 
  * 如果s(X)比阈值大则称项集X是频繁的；关联规则的强度可以用支持度/置信度度量
  * 置信度度量是通过规则进行推理的可靠性，也可以估计条件概率
  * 拆分支持度和置信度要求
* 关联规则挖掘任务**两个主要子任务** ： 
  * **频繁项集产生** ：发现满足最小支持度阈值的所有项集/频繁项集（开销大）
  * **规则的产生** ：提取所有高置信度的规则/强规则

* **格结构** ：用于枚举所有可能的项集
*  _降低产生频繁项集的计算复杂度_ 3种方法： 
  * _减少候选项集的数目（M）_ ：先验原理，不用计算支持度删除某些候选项集
  *  _减少比较次数（MN）_ ：选用更高级的数据结构来存储
  *  _减少事务数目（N）_

* 如果一个项集是频繁的，那么它的所有自己一定也是频繁的。
* 一个项集的支持度永远不会超过其子集的支持度，也称为反单调性

* 使用 _基于支持度的剪枝技术_ ，系统地控制候选项集的指数增长
* 两个重要特点： 
  * **逐层算法** ：每次遍历项集格中的一层
  * **产生-测试策略** ：新的候选项集由前一次迭代发现的频繁项集产生然后计数，总迭代次数是频繁项集的最大长度+1

* **产生** ：新的候选项集由前一次迭代发现的频繁项集产生 
  * 未遗漏则是完备的，候选项集的集合必须包含所有频繁项集的集合
  * 产生不超过一次是无冗余的
  * F_{k-1}\times F_{k-1}方法：两个候选项集除了最大的都一样就可以合并，完备无冗余
* **剪枝** ：基于支持度的剪枝技术，子集非频繁直接删除，不需要计算实际支持度 
  * 真子集中有任何一个是非频繁的会被立即剪枝

* **作用** ：确定在候选剪枝步骤中保留下来的每个候选项集出现的频繁程度
* 枚举每个事务包含的项集，并利用其更新对应的候选项集的支持度 
  * 先枚举，再用Hash树（候选项集划分为不同的桶放在Hash树中）

* 忽略前因或后果为空的规则，每个频繁k-项集Y最多可以产生(2^k-2)个关联规则——等于Y的非空真子集的个数
* 将项集Y划分为两个非空的子集X和Y-X，使X\rightarrow Y-X满足置信度阈值，必然满足支持度阈值因为就是频繁项集产生的。

* 令Y是一个项集，X是Y的一个子集。如果X\rightarrow Y-X不满足置信度阈值，则形如\tilde X \rightarrow Y- \tilde X的规则也一定不满足置信度阈值，其中\tilde X是X的子集

* 逐层方法产生关联规则，每层对应于规则后果中的项数
* \{acd\} \rightarrow \{b\} ,\space \{abd\} \rightarrow \{c\}，可以合并为\{ad\}\rightarrow\{bc\}

* 第一套标准：数据驱动方法定义客观兴趣度度量，用来对规则进行排序
* 第二组标准：主观论据，需要大量先验信息

* 不依赖于领域，只需要用户设置阈值来过滤低质量的模式。
* 基于列联表中列出的频度技术来计算

* **聚类分析** _仅根据_ 在数据中发现的 _描述对象及其关系的信息_ ， _将数据对象分组（称为簇）_ 。其目标是， _组内的对象是相似的_ （相关的），而 _不同组中的对象是不同的_ （不相关的）。 _组内的相似性（同质性）越大，组间差别越大，聚类就越好。_
* 分类是 _有监督分类_ ，即使用由类别标签已知的对象开发的模型，对新的、无标记的对象赋予类别标签。 _而聚类分析被视为无监督分类。_

  * **划分聚类** 简单地把数据对象划分成 _不重叠的子集（簇）_ ，使得每个数据对象恰在一个子集中。
  * **层次聚类** 是 _嵌套簇的集合_ ，组织成一棵树；除叶结点， _每一个结点（簇）都是其子女（子簇）的并集_ ，而 _树根是包含所有对象的簇_ 。通常树叶是 _单个数据对象_ 的单元素。

  * **互斥的** ：每个对象都被指派到单个簇。
  * **重叠的/非互斥的** ：一个对象同时属于多个组（类）
  * **模糊聚类** ：每个对象以0（绝对不属于）和1（绝对属于）之间的隶属权值归属于每个簇。不同簇权值之和必须等于1，通常指派到具有最大隶属权值的簇，转化成互斥聚类。

  * **完全聚类** ：将每个对象指派到一个簇。
  * **部分聚类** ：数据集中的某些对象可能不属于明确定义的组。

* **明显分离的** ：不必球形，阈值
* **基于原型的** ：质心/均值为中心，趋于呈球形
* **基于图的** ：连通分支
* **基于密度的** ：稠密区域

* K个初始质心，每个点指派到 _最近的质心_ ，更新质心，重复 _指派更新_ 直到质心不变
* **邻近度度量** ： _欧几里得距离/余弦相似性_
* 质心可能随 _数据邻近度度量_ 和 _聚类目标_ 的不同而改变
* 聚类目标用一个 _目标函数_ 表示，该函数依赖于 _点之间或点到簇的质心的邻近度_
* **误差的平方和SSE/散布** ：度量聚类质量的目标函数SSE=\sum_{i=1}^{K}\sum_{x\in C_i}dist(c_i,x)^2，其中dist是欧几里得空间中两个对象之间的标准欧几里得距离，第i个簇的质心（均值）c_i=\frac{1}{m_i}\sum_{x\in C_i}x，局部最优
* **文档** ：目标是 _最大化簇中文档与簇的质心的相似性_ ，该量称为簇的 _凝聚度_ 。总凝聚度总凝聚度=\sum_{i=1}^{K}\sum_{x\in C_i}cosine(c_i,x)
* **K均值++** : 一种初始化K均值的新方法，保证Olog(k)内可以找到一个最优K均值聚类的解决方案

* 将所有点集合分裂成两个簇，选一个继续分裂知道产生K个簇
* 可以选最大、最大SSE等，局部使用不代表最终总SSE最小

* 具有 _局限性_ ， _非球形状或尺寸密度不同_ ，K均值很难检测到“自然簇”
* 一种解决方案：找到大量的簇，小簇再进行组合

* 两种产生层次聚类的基本方法： 
  * **凝聚的** ：从 _点作为个体簇开始_ ，每一步 _合并两个最接近的簇_ 。这需要定义簇的 _邻近度_ 概念。
  * **分裂的** ：从包含 _所有点的某个簇开始_ ，每一步 _分裂_ 一个簇，直到 _仅剩下单点簇_ 。在这种情况下，我们需要确定每一步分裂哪个簇，以及 _如何_ 分裂。
  * 最常见的是 _凝聚层次聚类技术_ 。
* 树状图显示 _簇-子簇联系_ 和 _簇合并（凝聚）或分裂的次序_ 。二维点使用 _嵌套簇图_ 。

* 从 _个体点_ 作为簇开始，相继合并两个 _最接近_ 的簇，直到只剩下一个簇。
* **MIN（单链）** 定义簇的邻近度为 _不同簇_ 的 _两个最近的点之间的邻近度_ （ _最短边_ ）
* **MAX（全链）** 取不同簇中两个 _最远的点_ 之间的 _邻近度_ 作为簇的邻近度（ _最长边_ ）
* **组平均技术** ：不同簇的所 _有点对邻近值的均值（平均边长）_ 定义为簇的邻近度。
* **质心间距离** ：簇的邻近度定义为簇 _质心之间的邻近度_ 。

* 基于密度的聚类寻找 _被低密度区域_ 分离的 _高密度区域_ 。

* 特定点指定半径(Eps)内的点的数量来估计
* 点可以分为：稠密区域内部；稠密区域边缘；稀疏区域
* 三个重要的点：核心点、边界点、噪声点

* 任意 _两个足够靠近_ （相互之间的距离在Eps之内）的 _核心点_ 将 _放在同一个簇中_ 。同样，任何 _与核心点足够靠近_ 的 _边界点_ 也放到与核心点相同的簇中。如果一个边界点靠近不同簇的核心点，则可能需要 _解决平局_ 问题。 _噪声点被丢弃_ 。

* **基本时间复杂度** 是O(m\times找出Eps邻域中的点所需要的时间)，m是点的个数，最坏情况下时间复杂度O(m^2)
* 低维空间（尤其二维）平均时间复杂度可以降低到O(mlogm)
* 即便对于高维数据，**空间复杂度** 也是O(m)

* 基于 _密度定义簇_ ，所以 _能抗噪声_ ，能处理 _任意形状和大小的簇_
*  _密度变化太大_ 时候、对于 _高维数据难以定义密度_ 的，会出现问题
* 计算所有点的时候 _开销可能很大_

* **簇验证的重要任务** ： 
  * 确定数据集的 _聚类趋势_ （是否存在 _非随机结构_ ）
  * 确定 _正确的簇个数_
  *  _不引用_ 附加的信息，评估聚类分析结果 _对数据拟合的情况_
  * 将聚类分析结果 _与已知的客观结果比较_
  * 比较 _两个簇集_ ，确定哪个更好
* **度量或指标分为三类** ： 
  * **无监督的** ：不考虑外部信息， _内部指标_ ，如SSE，进一步分成凝聚、分离
  * **有监督的** ：发现的聚类结构与某种 _外部结构的匹配程度_ ， _外部指标_
  * **相对的** ：比较 _不同的聚类或簇_

* **簇凝聚度** ：衡量簇中对象的紧密关系，SSE越小聚类效果越好SSE=\sum_i\sum_{x\in C_i}(x-m_i)^2
* **簇分离度** ：测量簇与其他簇的区别或分离程度，SSB越高分离性越好SSB=\sum_i|C_i|(m-m_i)^2, |C_i|表示簇i的大小

* 结合了 _凝聚度_ 和 _分离度_
* 计算过程： 
  * 1️⃣ 计算第i个对象到簇中所有其他对象的平均距离a_i
  * 2️⃣ 计算第i个对象到包含该对象的任意簇中对象的平均距离b_i
  * 3️⃣ 轮廓系数s_i=\frac{b_i-a_i}{max(a_i,b_i)}，-1～1之间，越接近1说明聚类效果越好

* **理想的簇** ：点与簇内所有点相似度为1，与其他簇内所有点相似度为0 
  * 矩阵排序： _块对角结构_
  * 块内部相似度非0，其他为0

* 统计方法使用概率分布对正常类进行建模。
* 这些分布的一个重要特征是它们把每一个数据实例和一个概率值进行关联，表示这个实例从分布中生成的可能性有多大。
* 异常数据被认为是那些不太可能从正常类的概率分布中生成的实例。
* **有两种类型的模型可以用来表示正常类的概率分布：** * 参数模型：使用那些熟知的统计分布族，这些分布需要从数据中进行参数估计
  * 非参数模型：非常灵活，直接从得到的数据中学习正常类的分布

* 一些常用的参数模型被广泛用于描述许多类型的数据集，这些模型包括** _高斯分布、泊松分布和二项分布_** 。其中涉及的 _参数需要从数据中学习_ ，例如，高斯模型需要从数据中确定均值和方差这两个参数
* 参数模型能够非常有效的 _表示正常类的行为_ ，尤其当知道正常类服从某个特定分布时。通过参数模型计算的异常分数具有较强的理论性质，可以用于 _分析异常分数_ 并评估其 _统计显著性_ 。
* 将在一元和多元环境下讨论用 _高斯分布_ 对正常类进行建模 
  * **一元高斯分布** * 两个参数： _均值\mu=\frac{1}{m}\sum_{i=1}^{m}{x_i}_和 _标准差_\sigma^2=\frac{1}{m}\sum_{i=1}^{m}{(x_i-\mu)^2}
* 概率密度函数f(x)表示为：f(x)=\frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}
* x离分布中心越远，f(x)的值越小，因此可以使用点x到原点的的距离作为异常分数
* 这个距离值有一个概率解释，可以用来评定x是一个异常点的置信度
  * **多元高斯分布** * 对于由两个或多个连续属性组成的数据集，可以使用多元高斯分布对正常类建模
* 多元高斯分布N(\mu,\Sigma)包括两个参数： _均值向量\mu和协方差矩阵\Sigma_，它们需要从数据中估计得到
* 点x的概率密度函数N(\mu,\Sigma)表示为f(x)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}}e^{-\frac{(x-\mu)^T\Sigma^{-1}(x-\mu)}{2}}
* n是x的维数，|\Sigma|表示协方差矩阵的行列式

* 简单的对正常类建模的**非参数方法** 是 _建立正常数据的直方图_ 。
* 如果数据包含单一连续的属性，那么可以使用 _等宽离散技术_ 来构造属性的不同范围的容器。
* 之后，可以检查一个新的实例是否落在了直方图的容器中。如果它没有落在任何一个容器中，则可以认为它是一个异常实例
* 否则，可以使用实例所在 _容器频率的倒数_ 作为它的 _异常分数_ 。这个方法称为 _基于频率的_ 或 _基于计数的_ 异常检测方法。

* 基于邻近度的方法把那些 _远离其他对象_ 的实例认定为** _离群点_** 。
* 该方法依赖的假设是， _正常实例_ 是 _相关的并且彼此接近_ ，而异常的实例与其他实例不同，因此 _与其他实例的距离相对较远_ 。
* 因为许多基于邻近度的技术都 _基于距离变量_ ，因此也称为 _基于距离的异常检测技术_ 。
* 基于邻近度的方法都是 _无模型异常检测技术_ ，因为它们** _没有_** 构建一个 _明确的正常类模型_ 用于计算异常分数。
* 它们利用每个数据的** _局部视角_** _计算其异常分数_
* 它们比统计方法 _更加通用_ ，因为确定一个对数据集 _有意义的邻近度度量_ 往往比确定其他统计分布更容易。

* 定义数据实例x的 _基于_** _邻近度_** _的异常分数_ 的最简单方法之一是使用 _它到第k个最近邻的距离_dist(x,k) 
  * 如果一个 _实例x_ 有 _许多其他实例位于它的附近（_ 正常类的特性）， _dist(x,k)的值将会很小_
  * 一个 _异常实例x_ 将会和它的 _k-近邻实例由非常远的距离_ ，因此 _dist(x,k)的值也会比较大_。
  * dist(x,k)对k的取值非常敏感，k太小少量离群点的异常分数也会较低；k太大所有对象都有可能变成异常。
* 另一种基于距离的异常分数是 _取前k个最近邻距离的平均值_avg.dist(x,k)，其对k的选择 _更具有_** _鲁棒性_** 。 
  * 事实上，avg.dist(x,k)作为一种可靠的基于邻近度的异常分数被广泛应用在多个应用中。

* 一个实例周围的** _密度_** 可以定义为\frac{n}{V(d)}，其中 _n是指距离它在一个特定距离d内的实例数_ ， _V(d)是邻域的体积_ 。
* 由于V(d)对于给定的d是恒定的，所以实例周围的密度通常用 _固定距离d内的实例数量_ 来表示。此定义类似于DBSCAN聚类算法所使用的定义。
* 从基于密度的观点来看， _异常是_** _低密度_** _区域中的实例_ 。因此，一个异常在距离d内具有的实例个数 _比正常的实例更少_ 。
* 在基于密度的度量中选择参数d是具有挑战性的。 
  * 如果** _d太小_** ，那么许多 _正常实例_ 会 _错误地_ 显示 _低密度值_
  * 如果** _d太大_** ，那么许多 _异常_ 可能具有类似于 _正常实例的密度_
*  _基于距离_ 和 _基于密度_ 的异常分数是 _相反的关系_ 。这可以用来定义如下的密度度量，其基于两个距离度量dist(x,k)和avg.dist(x,k)

* 上述基于邻近度的方法只考虑 _单个实例_ 的** _局部性_** 来计算其异常分数
* 在数据包含 _不同密度_ 的区域的情况下，这样的方法无法正确地识别异常，因为 _正常位置_ 的概念会 _随着区域的变化而变化_ 。（有的区域松一点异常标准应该低一点）
* 为了正确地识别上述数据集中的异常点，需要一个与相邻实例的密度相关的密度概念
* 对于一个点x，有一种方法就是计算它的k-近邻（y1到yk）平均密度和x的密度的比率，如下：相对密度(x,k)=\frac{\frac{1}{k}\sum_{i=1}^{k}density(y,k)}{density(x,k)}
* 当 _点附近的平均密度_ 明显 _高_ 于点的密度时，它的 _相对密度就会很高_

* 基于聚类的异常检测方法 _使用簇_ 来表示 _正常类_
* 这依赖于这样的假设： _正常实例彼此接近_ ，因此可以 _被分组成簇_
* 异常点则为 _不符合正常类的簇的实例_ ，或者出现在与 _正常类的簇相距很远_ 的小簇中的实例。
* 基于聚类的方法可以分为** _两种类型_** ： 
  * 将 _小簇_ 视为 _异常_
  * 一个点如果 _没有很好地符合聚类_ 将被定义为异常，通常由该点到簇心的距离来度量

* 这种方法假定在数据中存在簇异常，其中异常以 _小规模的紧密组_ 出现。
* 当异常从同一异常类中产生时，就会出现聚类异常。
* 异常类通常为 _小簇_ ，因为异常在自然界中是 _罕见的_ 。
* 由于异常 _不符合正常_ 的模式或行为，所以异常也被期望会 _远离正常类的簇_ 。
* 检测异常簇的一种基本方法是对 _总体数据进行聚类_ ，并 _标记大小太小_ 或与其他簇 _相距太远的簇_ 。

* 从聚类的角度看，另一种描述一个异常的方式是该实例 _不能被任何正常簇解释_
* 一个异常检测的基本方法是，首先 _聚类所有数据_ （主要包括正常实例），然后 _评估每个实例属于其各自簇的程度_ 。
* 因此， _远离_ 它们各自簇的 _质心的实例_ 可以被识别为 _异常_ 。
* **评估一个对象属于一个簇的程度** * 对于基于原型的簇，有几种方法来评估一个实例属于一个簇的程度。
  * 一种方法是度量实例与其簇原型之间的距离，并将其视为该实例的异常分数。
  * 如果这些簇的密度不同，那么我们可以构造一个异常分数，该分数可以就实例到簇中其余实例的距离而言， _度量实例到簇原型的相对距离_ 。
  * 另一种可能是 _假设簇_ 可以用 _高斯分布_ 精确地建模，那就使用 _马氏距离_ 作为度量方式M(x,y)=\sqrt{(x-y)^T\Sigma^{-1}(x-y)}
  * 相对距离是 _该点与质心的距离_ 跟 _该簇中所有点与质心的中位距离_ 之比