ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据发掘学习条记 [打印本页]

---

作者: 瑞星    时间: 2025-1-12 11:21
标题: 数据发掘学习条记


第一章 绪论

• 数据期间
  

• 数据发掘发展的动力
  
  
  
  • 数据爆炸：数据收罗工具和成熟的数据存储技能使大量的数据被收集和存储。
    
  • 我们拥有丰富的数据，但是缺乏有用的信息
    
  • 迫切需要将传统的数据分析方法与用于处置惩罚大量数据的复杂算法相连合。
    
  
  
• 数据发掘的的价值
  
  
  
  • 电子商务领域，金融领域，医疗健康领域，交通运输领域，交际媒体领域，制造业领域，教导领域，政府和公共服务领域，农业领域
    
  
  

• 数据发掘概念
  

• 数据发掘是在大型数据库中自动发现有用信息的过程
  
  
  
  • 
    
    
    
    • 探查大型数据库、发现先前未知的有用模式 (pattern)
      
    
    
  • 可以预测未来的观测效果，并非所有的信息发现任务都被视为数据发掘（如数据库的查询任务）
    
  • 数据发掘是数据库中知识发现（KDD）不可缺少的一部分
    
    
    
    • KDD是识别数据中有用的、新颖的、潜在有用的和易于理解的模式的非平常过程
      
    
    
  
  
• 预处置惩罚是将原始输入数据转换为适当的格式，以便后续分析
  
  
  
  • 
    
    
    
    • 融合多个数据源的数据，数据洗濯（消除噪声和重复值），选择与任务相干的记录和特征
      
    
    
  
  
• 后处置惩罚确保只将有用和有用的效果集成到决定支持系统（DSS）中
  
  
  
  • 
    
    
    
    • 可视化：使得数据分析者从差别的视角探查数据和发掘效果
      
    • 使用统计度量或假设检验，删除虚假发掘效果
      
    
    
  
  

• 数据发掘要办理的问题
  

• 可伸缩性/可扩展性
  
  
  
  • 代表一种弹性，随着数据量的快速增长，能够包管茂盛的生命力，通过很少的改动甚至只是硬件设备的添置，就能实现处置惩罚本事的线性增长，实现高吞吐量和高性能
    
    
    
    • 采样技能：随机采样、均匀采样、水库采样
      
    • 并行（分布式）盘算：Map/Reduce盘算框架
      
    • 在线/增量学习方法：连续学习（Continual Learning）
      
    
    
  
  
• 高维性
  
  
  
  • 维度（Dimension）通常是形貌数据的属性或特征，比如地理位置、时间、类别、性别、职业等，它们是用来分别数据的类别或属性。
    
  • 为低维数据开辟的传统分析技能通常不能很好地处置惩罚高维数据
    
  • 某些分析算法，随着维度（特征数）的增长，盘算复杂度会迅速增长。
    
  
  
• 异构和复杂
  
  
  
  • 传统分析方法只处置惩罚包罗雷同类型属性的数据集。
    
  • 现在的数据类型更复杂：文本、图像、音频和视频
    
  • 为发掘复杂对象，需要思量数据中的联系
    
    
    
    • 时间和空间的自相干性
      
    • 图的连通性
      
    • 半布局化数据与XML文档的关系
      
    
    
  
  
• 所有权和分布
  
  
  
  • 针对在物理上分布式存储的数据需要面临一系列挑战
    
    
    
    • 如何低落分布式盘算所带来的额外通信开销
      
    • 如何有用地从多个数据源获得发掘效果
      
    • 如何办理数据安全和隐私问题
      
    
    
  
  

• 数据发掘的起源
  

   1989年8月于美国底特律市召开的第十一届国际连合人工智能学术集会上首次提到“知识发现”这一概念；
    到1993年，美国电气电子工程师学会（IEEE）的知识与数据工程（Knowledge and Data Engineering）汇刊出版了KDD技能专刊，发表的论文和摘要体现了其时KDD的最新研究效果和动态；
    1995年在加拿大蒙特利尔召开的首届“知识发现与数据发掘”国际学术集会上，首次提出了“数据发掘”这一学科的名称，并把数据发掘技能分为科研领域的知识发现与工程领域的数据发掘。
  

• 多学科的交织：设计数据库技能、人工智能、数理统计、呆板学习、模式识别、高性能盘算、知识工程、神经网络、信息检索、信息的可视化等领域
  

• 数据发掘任务
  

• 两大根本任务：预测和形貌
  
  
  
  • 预测任务：根据其他属性的值预测特定属性的值
    
    
    
    • 被预测的属性：目标变量/因变量
      
    • 用于预测的属性：表明变量/自变量
      
    
    
  • 形貌任务：导出数据中潜在联系的模式
    
    
    
    • 相干、趋势、聚类、轨迹和异常
      
    • 探查性的，需要加以验证息争释
      
    
    
  
  
• 预测建模
  
  
  
  • 为目标变量建立模型，将其作为表明变量的函数
    
    
    
    • 分类：用于预测离散的目标变量
      
    • 回归：用于预测连续的目标变量
      
    
    
  • 任务目标：使目标变量的预测值与实际值之间的误差最小
    
  
  
• 关联分析
  
  
  
  • 用来发现形貌数据中强关联特征的模式
    
    
    
    • 所发现的模式通常用蕴含规则或特征子集的形式表示变量
      
    
    
  • 任务目标：以最有用的方式提取最有趣的模式
    
  
  
• 聚类分析
  
  
  
  • 旨在发现紧密相干的观测值组群，使得与属于差别簇的观测值相比，属于同一簇的观测值之间尽大概雷同模式。
    
  
  
• 保举算法
  
  
  
  • 通过一些数学算法，推测出用户大概喜欢的东西
    
  • 任务目标：帮助用户找到真正想要的+低落信息过载
    
  
  
• 异常检测
  
  
  
  • 识别特征显著差别于其他数据的观测值，如许的观测值称为异常点或离群点。
    
  • 任务目标：具有高检测率和低误报率。
    
  
  
• 图数据分析
  
  
  
  • 图（Graph）是一种数据布局，用于模拟物理、生物、社会和信息系统中的许多类型的关系和过程。
    
  • 图由节点或极点（表示系统中的实体）构成，这些节点或极点由边（表示这些实体之间的关系）链接。
    
  • 任务目标：使用特定于图的算法来实现节点级、边级和图级的分析任务。
    
  
  

第二章 数据基础

• 数据类型
  

• 属性
  
  
  
  • 属性：对象的性子或特性，因对象而异，或随时间而变化（也称为变量、特性、字段、特征或维）
    
  • 一组属性用于形貌对象（对象也称记录、点、事例、示例、实体或实例）
    
  • 数据集：数据对象的集合
    
  
  
• 属性值
  
  
  
  • 属性值是指定给特定对象属性的数值或符号（数值可以具有无穷多个值，符号具有少量的值）
    
  • 属性和属性值之间的区别（雷同的属性可以映射到差别的属性值，差别的属性值可以映射到同一组值）
    
  • 属性的性子可以差别于表示属性值的性子（年龄属性有最大值，而整数没有）
    
  
  
• 属性类型
  
  
  
  • 可以界说四种属性类型：标称、序数、区间、比率
    
    
    
    • 标称（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)
    
  
  
• 准确率
  
  
  
  • 准确率：被测量的测量值与实际值之间的接近度
    
  • 一个重要方面是有用数字的使用
    
    
    
    • 目标是只使用与数据精度符合的数字来测量或盘算效果
      
    
    
  • 缺乏对数据和效果准确率的分析，分析者将大概出现严峻的数据分析错误
    
  
  
• 离群点
  
  
  
  • 离群点：具有差别于数据会合其他大部分数据对象的特征的数据对象，或是相对于该属性的典型值来说不寻常的属性值。我们也称其为异常对象或异常值。
    
  • 留意区分噪声和离群点：离群点是合法的数据对象或值
    
  
  
• 遗漏值
  
  
  
  • 一个对象遗漏一个或多个属性值的环境并不少见
    
  • 应对策略：
    
    
    
    • 删除数据对象或属性：删除具有遗漏值的数据对象，然而偶然即便不完整的数据对象也大概包罗一些有用的信息
      
    • 估计遗漏值：可以接纳插值方法、相近点的属性（平均）值、近邻中最常出现的属性值进行可靠估计。
      
    • 在分析时忽略遗漏值：接纳没有遗漏值的属性来盘算相似性。
      
    
    
  
  
• 不一致的值
  
  
  
  • 数据大概包罗不一致的值
    
  • 无论原因是什么，重要的是能检测出来而且假如大概的话，改正这种错误，比如基于“校验”信息
    
  • 检测到不一致后，有事可以对数据进行更正
    
  
  
• 重复数据
  
  
  
  • 数据集可以包罗重复或险些重复的数据对象
    
  • 去重复
    
    
    
    • 对于雷同的对象，假如存在属性值差别，要一致化
      
    • 制止意外地将两个相似但并非重复的数据对象合并
      
    
    
  • 在某些环境下，两个或多个对象在数据库的属性度量上是雷同的，但是仍然代表差别的对象
    
  
  

• 数据预处置惩罚
  

• 预处置惩罚方法：选择分析所需要的数据对象和属性，以及创建/改变属性
  
• 聚集：将两个或多个对象合并成单个对象
  
  
  
  • 删除属性/压缩特定属性差别值个数的过程，常用于联机分析处置惩罚OLAP
    
  • 定量属性通常通过求和和求平均值进行聚集
    
  • 定性属性可以忽略也可以用更高层次的类别来概括
    
  • 动机：1️⃣ 数据归约导致的较小的数据集需要较少的内存和处置惩罚时间； 2️⃣ 通过高层而不是低层数据视图，聚集起到了范围或标度转换的作用； 3️⃣ 对象或属性群的行为通常比单个对象或属性的行为更加稳固（平均值、总数等聚集量具有较小的变异性）
    
  • 聚集的缺点是大概丢失有趣的细节
    
  
  
• 抽样：选择数据子集进行分析的常用方法
  
  
  
  • 使用抽样的算法可以压缩数据量，以便可以使用更好但开销较大的数据发掘算法
    
  • 若样本近似地具有与原数据集雷同的（感爱好的）性子，则称标本是有代表性的
    
  • 假如样本是有代表性的，则使用样本与使用整个数据集的效果险些一样
    
  • 选择一个抽样方案，确保以很高的概率得到有代表性的样本
    
    
    
    • 简单随机抽样：选取任何特定项的概率相称
      
      
      
      • 无放回抽样/有放回抽样
        
      
      
    • 分层抽样：总体由差别类型的对象构成而且每种类型的对象数量差别很大时，简单随机抽样不能充分地代表不太频繁出现的对象类型。
      
      
      
      • 需要提供具有差别频率的感爱好的项的抽样方案
        
      • 也叫类型抽样，可以每个类型取雷同对象，也可以每一组抽的量正比于组大小
        
      
      
    • 蓄水池采样：给定一串很长的数据流，对该数据流中数据只能访问一次，使得数据流中所有数据被选中的概率相称
      
      
      
      • 假设需要采样的数量为k，起首构建一个k个元素的数组，将序列的前k个元素放入数组中
        
      • 对于从第j个元素(j>k)，以\frac{k}{j}的概率来决定该元素是否被替换到数组中，数组中的k个元素被替换的概率是雷同的
        
      • 当遍历完所有元素之后，数组中剩下的元素即为采样样本
        
      
      
    
    
  • 选择样本容量：太大跟没抽样一样，太小容易丢失模式
    
    
    
    • 由于大概很难确定符合的样本容量，因此偶然需使用自顺应或渐近抽样方法
      
      
      
      • 从一个小样本开始，然后增长样本容量直至得到充足容量的样本
        
      • 预测模型的准确率随样本容量的增长而增长，但在某一点准确率的增长趋于稳固
        
      • 掌握模型准确率随样本逐渐增大的变化环境，估计出当前容量与稳固点的接近程度
        
      
      
    
    
  
  
• 维归约（降维）
  
  
  
  • 维灾难：随着数据维度的增长，许多数据分析变得非常困难；特殊是随着维度增长，数据在它所占据的空间中越来越稀疏；
    
    
    
    • 对于分类，这大概意味着没有充足的数据对象来创建模型，将所有大概的对象可靠地指派到一个类（准确率低落）；
      
    • 对于聚类，点之间的密度和间隔的界说（对聚类时至关重要的）失去了意义（聚类质量下降）
      
    
    
  • 通过创建新属性或将一些旧属性合并在一起以低落数据集的维度，使得低维表示生存原始数据的一些有意义的特性
    
    
    
    • 删除不相干的特征并低落噪声，许多数据发掘算法的效果就会更好
      
    • 可以使模型只涉及较少的属性、更容易理解，更容易让数据可视化；低落了数据发掘算法的时间和内存需求
      
    
    
  • 最常用的方法是使用线性代数技能，将数据由高维空间投影到低维空间，特殊是对于连续数据
    
  • 主身分分析PCA是一种用于它找出新的属性（主身分），这些属性是原属性的线性组合，是相互正交的，而且捕获了数据的最大变差
    
  • 奇异值分解SVD是一种线性代数技能，它与PCA有关，而且也用于维归约
    
  
  
• 特征子集选择
  
  
  
  • 冗余特征：重复地包罗在一或多个其他属性中的许多或所有信息
    
  • 不相干特征：包罗对于当前的数据发掘任务险些完全没用的信息
    
  • 冗余和不相干的特征大概低落分类的准确率，影响聚类的质量
    
  • 选择方法
    
    
    
    • 理想选择方法：将所有大概的特征子集作为感爱好的数据发掘算法的输入，然后选取能产生最好效果的子集（涉及n个属性的自己多达2^n个，行不通）
      
    • 嵌入方法：特征选择作为数据发掘算法的一部分，在数据发掘算法运行期间，算法本身决定使用哪些属性和忽略哪些属性。
      
    • 过滤方法：使用某种独立于数据发掘任务的方法，在数据发掘算法运行前进行特征选择
      
    • 包装方法：直接把最终将要使用的数据发掘算法的性能作为特征子集的评价准则，但通常并不罗列所有大概的子集来找出最佳属性子集
      
    
    
  • 可以将过滤和包装方法放到一个共同的体系布局中，特征选择过程可以看作由四部分构成：控制新的特征子集产生的搜索策略、子集评估度量、停止搜索判断和验证过程。
    
  • 过滤：差别于目标数据发掘算法；包装：使用目标数据发掘算法
    
  • 特征子集搜索策略的盘算花费应当较低，而且应当找到最近或近似最优的特征子集（很难同时满足，要折中）
    
  • 评估步调需要一种评估度量，确定属性特征子集的质量
    
    
    
    • 过滤方法：预测实际数据发掘算法在给定的属性集上实行的效果如何
      
    • 包装方法：运行目标数据发掘算法，评估函数就是通常用于度量数据发掘效果的评判标准
      
    
    
  • 因为子集的数量大概很大，考察所有的子集大概不实际，所以需要某种停止准则
    
  • 策略通常基于如下一个或多个条件：
    
    
    
    • 迭代次数
      
    • 子集评估的度量值是否最优或高出给定的阈值
      
    • 一个特定大小的子集是否已经得到
      
    • 使用搜索策略得到的选择是否可以实现改进
      
    
    
  • 一旦选定特征子集，就要验证目标数据发掘算法在选定子集上的效果
    
    
    
    • 方法1: 将使用全部特征得到的效果与使用该特征子集得到的效果进行比力
      
    • 方法2: 使用一些差别的特征选择算法得到多个特征子集，然后比力数据发掘算法在每个子集上的运行效果
      
    
    
  • 特征加权是另一种生存或删除特征的办法
    
    
    
    • 特征越重要，赋予它的权值越大，而对于不太重要的特征，赋予它的权值较小
      
    • 这些权值可以根据特征的相对重要性的领域知识确定，也可以自动确定
      
    
    
  
  
• 特征创建：可以由原来的属性创建新的属性集，以更有用地捕获数据会合的重要信息
  
  
  
  • 新属性的数量大概比原属性少，使得我们可以获得前面先容的维归约带来的所有好处
    
  • 两种方法：特征提取、映射数据到新的空间
    
    
    
    • 特征提取：由原始数据创建新的特征集
      
      
      
      • 将数据发掘用于一个相对较新的领域，一个关键任务就是开辟新的特征和特征提取方法
        
      
      
    • 映射数据到新空间：使用一种完全差别的视角去发掘数据
      
      
      
      • 比如通过对时间序列实行傅里叶变更，将它转换成频率信息明显的表示，就能检测到这些模式
        
      
      
    
    
  
  
• 离散化和二元化
  
  
  
  • 某些分类算法，要求数据是分类属性形式
    
  • 发现关联模式的算法要求数据是二元属性形式
    
  • 离散化：将连续属性变更成分类属性，而且连续和离散属性大概都需要变更成一个或多个二元属性（二元化）
    
    
    
    • 若一个离散属性有m个分类值[0,m-1]，则需n=\lceil log_2m \rceil个二元属性
      
    • 关联分析需要非对称的二元属性，其中只有属性的值为1才是重要的。因此，对于关联问题需要为每一个分类值引入一个二元属性
      
    • 连续属性变更身分类属性涉及两个子任务：1️⃣ 决定需要多少个分类值n 2️⃣ 确定如何将连续属性值映射到这些分类值
      
    • 具体步调：1️⃣ 将连续属性值排序后，通过指定n-1个分割点把它们分成n个区间；2️⃣ 将一个区间中的所有值映射到雷同的分类值
      
    • 离散化问题就是决定选择多少个分割点和确定分割点位置的问题
      
    • 两种形式：
      
      
      
      • 无监督离散化：不使用类信息进行离散化（等宽法、等频率或等深）
        
      • 监督离散化：根据类标对数据进行离散化（极大化区间纯度的方式确定分割点）
        
      
      
    • 基于熵（纯度的度量）的方法是重要的离散化方法之一。
      
      
      
      • 熵：设k是不同的类标号数，m_i是某分别的区间i中值的个数，m_{ij}是区间i中类j的值的个数，第i个区间的熵是e_i=-\sum_{j=1}^{k}p_{ij}log_2p_{ij},\space p_{ij}=\frac{m_{ij}}{m_i}第i个区间中类j的概率
        
      • 分别的总熵e是每个区间的熵的加权平均：e=\sum_{i=1}^{n}w_i \times e_i, \space wi=\frac{m_i}{m}第i个区间的值的比例
        
      • 假如一个区间只包罗一个类的值（该区间非常纯）则其熵为0；假如一个区间中的值类出现的频率相称（该区间非常不纯），则其熵最大。
        
      
      
    
    
  • 分类属性偶然大概具有太多的值
    
  • 假如分类属性是序数属性，则可以使用雷同于处置惩罚连续属性的技能，以淘汰分类值的个数
    
  • 假如分类属性是标称的，就需要使用属性值之间联系的知识，将其合并成较大的组（仅当分组效果能进步分类准确率或达到某种其他数据发掘目标时，才将至聚集到一起）
    
  
  
• 变量变更：用于变量的所有值的变更
  
  
  
  • 一个函数，它将给定属性的整个值集映射到一组新的替换值，如许每个旧值都可以用一个新的值来标识（简单函数变更、规范化或标准化）
    
  • 简单函数变更：一个简单的数学函数分别作用于每一个值
    
  • 在统计学中，变量变更（特殊是平方根、对数和倒数变更）常用来将不具有高斯（正态）分布的数据变更成具有高斯（正态）分布的数据
    
  • 假如变量具有很大的值域，常用对数变更将其进行压缩
    
  • 使用变量变更时需要小心，因为它们改变了数据的特性（新数据特性，是否保序，是否可作用于0或负值，对0-1间的值有何影响）
    
  • 规范化和标准化：使整个值的集合具有特定的性子
    
    
    
    • 最小-最大规范化：对原始数据进行线性变更。假如min_A和max_A分别是属性A地最小值和最大值。最小-最大规范化通过如下盘算：v_i'=\frac{v_i-min_A}{max_A-min_A}(new\_max-new\_min_A)+new\_min_A把A的值映射到区间[new\_min-A,new\_max_A]中。
      
      
      
      • z分数：也叫标准分数，是一个数与平均数的差再除以标准差的过程。
        
      • x'=\frac{x-\bar x}{s_x},\bar x是属性值的均值（平均值），而s_x是它们的标准差，它具有均值0和标准差1
        
      • 均值和标准差受离群点的影响很大，可以用中位数代替均值，用均值绝对毛病代替标准差\bar d=\frac{|x_1-\bar x|+|x_2-\bar x|+\cdots+|x_n-\bar x|}{n}=\frac{\sum_{i=1}^{n}|x_i-\bar x|}{n}
        
      
      
    • 小数定标规范化：通过移动属性A的值的小数点位置进行规范化。小数点的移动位数依赖于A的最大绝对值。A的值v_i被规范化为v_i'，由下式盘算：v_i'=\frac{v_i}{10^j}，其中j是使得max(|v_i'|)<1的最小整数。
      
    
    
  
  

• 相似性和相异性的度量
  

• 基础
  
  
  
  • 相似度：两个对象相似程度的数值度量（非负，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=\begin{align} \begin{cases} 0, \space if\space x=y\\ 1, \space if\space x\ne y \end{cases} \end{align}	s= \begin{align} \begin{cases} 1, \space if\space x=y\\ 0, \space if\space x\ne y \end{cases} \end{align}
序数	d=\frac{|x-y|}{(n-1)}，值映射到整数0到n-1，其中n是值的个数	s=1-d
区间或比率	d=|x-y|	s=-d,\space s=\frac{1}{1+d}, \space s=e^{-d} s=1-\frac{(d-min\_d)}{(max\_d-min\_d)}

• 数据对象之间的相异度
  
  
  
  • 间隔具有一些众所周知的性子
    
  • 假如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，则在盘算对象相似度时忽略它们
      
    
    
  
  

• 当某些属性对相近度的界说比其他属性更重要时，可以通过对每个属性的贡献加权来修改相近度公式，属性权重为w_k时，similarity(x,y)=\frac {\sum_{k=1}^{n}w_k*\delta_k*s_k(x,y)} {\sum_{k=1}^{n}w_k*\delta_k}，闵可夫斯基间隔的界说也可修改为d(x,y)=(\sum_{k=1}^{n}w_k*|x_k-y_k|^r)^{1/r}
  

• 数据可视化
  

• 数据可视化：旨在通过图形表示清晰有用地表达数据
  
  
  
  • 通过将数据映射到图形图元上，深入了解信息空间
    
  • 提供大型数据集的定性概述
    
  • 搜索模式、趋势、布局、不规则性、数据之间的关系
    
  • 帮助找到有趣的区域和符合的参数，以便进行进一步的定量分析
    
  • 提供盘算机表示的视觉证实
    
  
  
• 基于像素的可视化技能
  
  
  
  • 一种可视化一维值的简单方法是使用像素，其中像素的颜色反映该维的值
    
  • 对于一个m维数据集，基于像素的技能在屏幕上创建m个窗口，每维一个
    
  • 记录m个维值映射到这些窗口中对应位置上的m个像素
    
  • 窗口不必是矩形的，圆弓分割技能使用圆弓形窗口
    
  
  
• 多少投影可视化技能
  
  
  
  • 像素对于我们理解多维空间的数据分布帮助不大
    
  • 多少投影技能帮助用户发现多维数据集的有趣投影
    
  • 多少投影技能的首要挑战是设法办理如何在二维显示上可视化高维空间
    
  • 散点图使用笛卡尔坐标显示二维数据点，使用差别的颜色/外形表示差别的数据点，可以增长第三维。
    
  • 维数高出4散点图一般不太有用，散点图矩阵是散点图的一种有用扩充，散点图矩阵是二维散点图的n\times n网格，提供每个维与所有其他维的可视化
    
  
  
• 可视化复杂对象和关系
  
  
  
  • 越来越多的非数值数据，标签云是用户产生的标签的统计量的可视化
    
  
  

第三章 分类

• 根本概念
  

• 总体思路
  
  
  
  • 分类任务的数据由元组(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}}
      
    • 大多数分类计数的学习算法旨在学习在应用于测试集时达到最高准确度或等效最低错误率的模型
      
    
    
  
  

• 决定树分类器
  

• 根本概念
  
  
  
  • 从根结点开始，应用其属性测试实例，并根据测试效果按照适当的分支进行操纵；一旦到达叶结点，将于该结点关联的类别标签分配给测试实例。
    
  
  
• 构建决定树的根本算法（Hunt）
  
  
  
  • 搜索空间随数据集规模指数级上升，寻找最佳数的代价是昂贵的
    
  • 需要在公道的时间内归纳出具有公道准确率的决定树，尽管不是最优的
    
  • 贪婪策略：以自顶向下的方式生成决定树，对分别训练数据时要使用的属性进行一系列局部最优决定
    
  • 决定树是递归方式生长，最初包罗与所有训练实例关联的单个根结点；
    
  • 假如某个结点与来自多个类的实例相干联，则会使用由拆分标准确定的属性测试条件进行扩展。为每个属性测试条件的每个效果创建一个子结点，并将与父结点关联的实例分发给子结点，可以递归应用于每个子结点（只要它具有多个类的标签），假如某个叶结点相干所有实例都具有雷同的类别标签则不会进一步扩展
    
  • 两个关键问题：拆分标准、停止标准
    
    
    
    • 拆分标准：决定选择哪个属性作为测试条件以及如何将训练实例分配给子结点
      
    • 停止标准：确定何时应该停止扩展结点的条件
      
    
    
  
  
• 表示属性测试条件的方法
  
  
  
  • 二元属性的测试条件产生两个大概的输出
    
  • 标称属性可以有多个属性值，因此多路分别和二元分别(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
  
  
  
  • 线性SVM是寻找具有最大边沿的分离超平面的分类器，因此它也经常被称为最大边沿分类器
    
  • 令w^Tx+b=0是一个分离超平面的方程，它通过将两个类放置在超平面相反的两侧来分离这两个类\left\{ \begin{array}{ll} w^Tx_i+b>0 & y_i=+1 \\ w^Tx_i+b<0 & y_i=-1 \end{array} \right.
    
  • 任意线x到超平面的间隔D(x)=\frac{|w^Tx+b|}{||w||}
    
  
  
• 非线性SVM
  
  
  
  • 需要一个非线性变更\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\{ \begin{array}{ll} e^{-\alpha_i} & \text{if } C_i(x_j)=y_j \\ e^{\alpha_i} & \text{if } C_i(x_j)\ne y_j \end{array} \right.
      
    • \alpha_i称为基分类器C_i的重要性，界说为\alpha_i=\frac{1}{2}ln(\frac{1-\epsilon_i}{\epsilon_i})
      
    
    
  
  
• 随机森林
  
  
  
  • 随机森林试图通过构建去相干决定树组合分类器来进步泛化性能。
    
  • 基于装袋的思想，使用差别训练数据集的自助样本来学习决定树；与装袋的关键区别在于在一小组随机选择的属性中选择分别标准
    
    
    
    • 随机森林不但通过操纵训练实例，还通过操纵输入属性来构建决定树的集合。
      
    • 有放回随机抽样实例 ➡️ 随机抽样一组p个属性 ➡️ 选择一个属性
      
    
    
  
  

• 模型的过拟合
  

• 根本概念
  
  
  
  • 模型没有很好地捕获到数据特征，不能够很好地拟合数据，这种环境称为模型欠拟合。
    
  • 有的模型即使能够很好地覆盖训练数据，但它仍然大概表现出较差的泛化性能，过拟合。
    
  • 模型过拟合：在寻求训练错误率最小化的过程中，选择了一种过于复杂的模型，这种模型捕获到了训练数据中的特定模式，但没能获取到整体数据中属性和类别标签之间的本质关系
    
  
  
• 过拟合的原因
  
  
  
  • 有限的训练规模：增大训练数据可以淘汰过拟合影响
    
  • 高模型复杂度
    
  
  

• 模型评估
  

• 根本概念
  
  
  
  • 模型评估：估计模型泛化性能的方法
    
  • 精确方法：在有标签的测试集上，对学习模型的性能进行评估，测试集从未被使用
    
    
    
    • D.train用于模型选择，D.test用于盘算测试错误率err_{test}
      
    
    
  
  
• 留出法（Holdout）
  
  
  
  • 多次重复，随机子采样/重复留出法
    
  
  
• 交织验证（Cross-Validation）
  
  
  
  • 随机分别，差别子集测试，末了求均值
    
  • 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回归。然而，它的表达本事仅限于学习线性决定边界。
    
  • 因为每个属性都有差别的权重（参数），因此可以分析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）
      
    
    
  
  
• 先验原理
  
  
  
  • 假如一个项集是频繁的，那么它的所有自己肯定也是频繁的。
    
  • 一个项集的支持度永远不会高出其子集的支持度，也称为反单调性
    
  
  
• Apriori算法的频繁项集产生
  
  
  
  • 使用基于支持度的剪枝技能，系统地控制候选项集的指数增长
    
  • 两个重要特点：
    
    
    
    • 逐层算法：每次遍历项集格中的一层
      
    • 产生-测试策略：新的候选项集由前一次迭代发现的频繁项集产生然后计数，总迭代次数是频繁项集的最大长度+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的子集
    
  
  
• Apriori算法中规则的产生
  
  
  
  • 逐层方法产生关联规则，每层对应于规则效果中的项数
    
  • \{acd\} \rightarrow \{b\} ,\space \{abd\} \rightarrow \{c\}，可以合并为\{ad\}\rightarrow\{bc\}
    
  
  

• 关联模式的评估
  

• 根本概念
  
  
  
  • 第一套标准：数据驱动方法界说客观爱好度度量，用来对规则进行排序
    
  • 第二组标准：主观论据，需要大量先验信息
    
  
  
• 爱好度的客观度量
  
  
  
  • 不依赖于领域，只需要用户设置阈值来过滤低质量的模式。
    
  • 基于列联表中列出的频度技能来盘算
    
  
  

• 
  
  
  
  • 爱好因子/提拔度：爱好因子度量了模式s(A, B)的支持度与在统计独立性假设下盘算出的基准支持度S_{indep}(A,B)的比值
    
    
    
    • I(A,B)=\frac{N\times f_{11}}{f_{1+}\times f_{+1}}，等于1相互独立，大于1正相干，小于1负相干
      
    • 分析变量之间统计独立性的符合度量方法
      
    
    
  • 相干度分析：皮尔森相干系数
    
    
    
    • 二元变量：\phi=\frac{f_{11}f_{00}-f_{01}f_{10}}{\sqrt {f_{1+}f_{+1}f_{0+}f_{+0}}}, 0没关联，+1完全正相干，-1完全负相干
      
    • \phi= \frac{ s(A,B)-s(A)\times s(B) }{ \sqrt{ s(A)\times (1-s(A))\times s(B)\times (1-s(B)) } }
      
    • 用于评估变量之间统计独立性的强度
      
    
    
  
  

第六章 聚类分析

• 概述
  

• 什么是聚类分析
  
  
  
  • 聚类分析仅根据在数据中发现的形貌对象及其关系的信息，将数据对象分组（称为簇）。其目标是，组内的对象是相似的（相干的），而差别组中的对象是差别的（不相干的）。组内的相似性（同质性）越大，组间差别越大，聚类就越好。
    
  • 分类是有监督分类，即使用由类别标签已知的对象开辟的模型，对新的、无标志的对象赋予类别标签。而聚类分析被视为无监督分类。
    
  
  
• 聚类的差别类型
  
  
  
  • 层次的与分别的
    
    
    
    • 分别聚类简单地把数据对象分别成不重叠的子集（簇），使得每个数据对象恰在一个子会合。
      
    • 层次聚类是嵌套簇的集合，构造成一棵树；除叶结点，每一个结点（簇）都是其后代（子簇）的并集，而树根是包罗所有对象的簇。通常树叶是单个数据对象的单元素。
      
    
    
  • 互斥的、重叠的与模糊的
    
    
    
    • 互斥的：每个对象都被指派到单个簇。
      
    • 重叠的/非互斥的：一个对象同时属于多个组（类）
      
    • 模糊聚类：每个对象以0（绝对不属于）和1（绝对属于）之间的隶属权值归属于每个簇。差别簇权值之和必须等于1，通常指派到具有最大隶属权值的簇，转化成互斥聚类。
      
    
    
  • 完全的与部分的
    
    
    
    • 完全聚类：将每个对象指派到一个簇。
      
    • 部分聚类：数据会合的某些对象大概不属于明确界说的组。
      
    
    
  
  
• 簇的差别类型
  
  
  
  • 明显分离的：不必球形，阈值
    
  • 基于原型的：质心/均值为中心，趋于呈球形
    
  • 基于图的：连通分支
    
  • 基于密度的：稠密区域
    
  
  

• K均值
  

• K均值算法
  
  
  
  • 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均值
  
  
  
  • 将所有点集合分裂成两个簇，选一个继续分裂知道产生K个簇
    
  • 可以选最大、最大SSE等，局部使用不代表最终总SSE最小
    
  
  
• K均值和差别的簇类型
  
  
  
  • 具有范围性，非球外形或尺寸密度差别，K均值很难检测到“自然簇”
    
  • 一种办理方案：找到大量的簇，小簇再进行组合
    
  
  

• 凝聚层次聚类
  

• 根本概念
  
  
  
  • 两种产生层次聚类的根本方法：
    
    
    
    • 凝聚的：从点作为个体簇开始，每一步合并两个最接近的簇。这需要界说簇的相近度概念。
      
    • 分裂的：从包罗所有点的某个簇开始，每一步分裂一个簇，直到仅剩下单点簇。在这种环境下，我们需要确定每一步分裂哪个簇，以及如何分裂。
      
    • 最常见的是凝聚层次聚类技能。
      
    
    
  • 树状图显示簇-子簇联系和簇合并（凝聚）或分裂的次序。二维点使用嵌套簇图。
    
  
  
• 根本凝聚层次聚类算法
  
  
  
  • 从个体点作为簇开始，相继合并两个最接近的簇，直到只剩下一个簇。
    
  • MIN（单链）界说簇的相近度为差别簇的两个最近的点之间的相近度（最短边）
    
  • MAX（全链）取差别簇中两个最远的点之间的相近度作为簇的相近度（最长边）
    
  • 组平均技能：差别簇的所有点对相近值的均值（平均边长）界说为簇的相近度。
    
  • 质心间间隔：簇的相近度界说为簇质心之间的相近度。
    
  
  

• DBSCAN
  

• 根本概念
  
  
  
  • 基于密度的聚类寻找被低密度区域分离的高密度区域。
    
  
  
• 传统的密度：基于中心的方法
  
  
  
  • 特定点指定半径(Eps)内的点的数量来估计
    
  • 点可以分为：稠密区域内部；稠密区域边沿；稀疏区域
    
  • 三个重要的点：核心点、边界点、噪声点
    
  
  
• DBSCAN算法
  
  
  
  • 任意两个充足靠近（相互之间的间隔在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
      
    
    
  
  

第七章 异常检测

• 概述
  

• 异常检测的目标是发现一些不符合正通例律和行为的对象。
  
  
  
  • 异常对象被称为离群点（outlier），因为在数据的散点图中，它们的分布远离其他的数据点。
    
  • 异常检测也称为毛病检测，因为异常对象的某些属性值明显偏离该属性的盼望值或典型的属性值
    
  • 异常检测也称为例外发掘，因为异常在某种意义上是例外的。
    
  
  
• 应用场景：欺诈检测、入侵检测、医疗和公共卫生、航空安全
  

• 异常检测问题的特性
  

• 异常的界说
  
  
  
  • 异常是指不符合正常实例分布的观测，比如与某种分布下大多数实例不相似。
    
    
    
    • 这个界说没有假设这种分布是可以用已知统治分布术语容易表达的。毕竟上，这种困难正式许多异常检测方法使用非统计学方法的原因。
      
    • 可以按照看到一个对象的概率或某种更极度的方法来对数据对象排序。出现的概率越低，这个对象越大概是一个异常数据。
      
    • 造成异常现象的原因有很多：噪声，对象来自差别的分布，对象仅仅是这个分布中少少出现的。
      
    
    
  
  
• 数据的性子
  
  
  
  • 输入数据的性子在决定选择符合的异常检测技能中起偏重要的作用。
    
  • 输入数据的一些共有特性包括属性的数量和类型，以及形貌每个数据实例的表示方式
    
  • 单变量或多变量
    
    
    
    • 假如单一属性，该对象是否异常只依赖于这个对象的属性值是否是异常的
      
    • 假如多个属性，大概某些属性上有异常的数值，其他属性表现正常
      
    • 一个对象即使每个单独属性都不异常，整体而言也有大概是异常对象
      
    
    
  • 记录数据或相近度矩阵
    
    
    
    • 表示一个数据集合最常见的方式是使用记录数据或它的变体，比如数据矩阵，在矩阵中每个数据实例都使用雷同的属性进行形貌。
      
    • 一些异常检测方法顺应相近度矩阵，矩阵中的每一个数值表示两个实例间的接近程度（相似或不相似）
      
    
    
  • 标签的可用性
    
    
    
    • 一个数据实例的标签标明这个实例是正常的还是异常的。
      
    • 假如有一个每个数据实例都带有标签的训练数据集，那么异常检测的问题就可以转化为监督学习（分类）问题。
      
    • 因为异常数据非常稀疏，获得异常类的类标是非常具有挑战性的
      
    • 本质上大多数异常检测问题是无监督的
      
    • 给定一个输入数据集，从正常实例中区分出异常实例是非常具有挑战性的
      
    
    
  • 异常的两个重要性子
    
    
    
    • 数量相对较少
      
      
      
      • 正常实例占绝大多数，输入数据集作为正常类的不完美展示，指定输入数据中异常值盼望数量的机制可以处置惩罚具有大量异常的数据。
        
      
      
    • 稀疏分布
      
      
      
      • 异常数据分布稀疏，有一些异常检测方法专门用来找聚类异常，通常假设这些异常数据的数量很小或者离其他实例的间隔很远。
        
      
      
    
    
  
  
• 如何使用异常检测
  
  
  
  • 方法一：给定的输入数据中既包罗正常实例又包罗异常实例，我们要找到异常实例，本章所有异常检测方法都可以在这种设定中使用
    
  • 方法二：获得识别为异常的测试实例（每次出现一个），大多数异常检测方法都能够使用输入数据集来提供测试实例的输出。
    
  
  

• 统计方法
  

• 根本概念
  
  
  
  • 统计方法使用概率分布对正常类进行建模。
    
  • 这些分布的一个重要特征是它们把每一个数据实例和一个概率值进行关联，表示这个实例从分布中生成的大概性有多大。
    
  • 异常数据被认为是那些不太大概从正常类的概率分布中生成的实例。
    
  • 有两种类型的模型可以用来表示正常类的概率分布：
    
    
    
    • 参数模型：使用那些熟知的统计分布族，这些分布需要从数据中进行参数估计
      
    • 非参数模型：非常机动，直接从得到的数据中学习正常类的分布
      
    
    
  
  
• 使用参数模型
  
  
  
  • 一些常用的参数模型被广泛用于形貌许多类型的数据集，这些模型包括高斯分布、泊松分布和二项分布。其中涉及的参数需要从数据中学习，例如，高斯模型需要从数据中确定均值和方差这两个参数
    
  • 参数模型能够非常有用的表示正常类的行为，尤其当知道正常类服从某个特定分布时。通过参数模型盘算的异常分数具有较强的理论性子，可以用于分析异常分数并评估其统计显著性。
    
  • 将在一元和多元环境下讨论用高斯分布对正常类进行建模
    
    
    
    • 一元高斯分布
      
      
      
      • 两个参数：均值\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)
    
  
  

density(x,k)=\frac{1}{(x,k)}
avg.density(x,k)=\frac{1}{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)}
      
    • 相对间隔是该点与质心的间隔跟该簇中所有点与质心的中位间隔之比
      
    
    
  
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4