模式识别

也叫作机器学习或数据挖掘。主要包含了绪论、数据预处理、聚类分析、贝叶斯分类、近邻法等。

模式识别

• 绪论
  • 模式识别的基本概念
    • 模式识别
      • 用计算机来实现人的模式识别能力，即用计算机实现人对各种事物或现象的分析、描述、判断、识别，将待识别的事物分配到各个模式类中的技术
      • 模式识别可以看成是从模式向类别所作的映射
    • 模式
      • 物质或现象的相关信息
      • 广义地说，存在于时间，空间中可观察的物体，如果可以区别是否相同或相似，都可以称为模式
      • 模式是通过信息采集，形成的对一个对象的描述，这种描述应该具备规范化、可理解、可识别的特点
      • 说明
        • 模式不是事物本身，而是从事物获得的信息。比如人的照片、个人资料
        • 可以区分模式之间是否相似（与问题有关）
        • 模式一般用向量来表示，下标可以反映时间特性、空间特性或者其他标识
    • 模式向量
      • 通过对具体的个别事物进行观测所得到的具有时间和空间分布的信息（有人称样本或样本向量）
    • 模式类
      • 模式所属的类别或同一类中模式的总体（简称类）
  • 模式识别系统
    • 由设计和实现两个过程
      • 模式所属的类别或同一类中模式的总体（简称类）
      • 设计（训练、学习）
        • 指用一定数量的样本（称为训练集或学习集）进行分类器的设计
      • 实现（决策、分类、判决）
        • 指用所设计的分类器对待识别的样本进行分类决策
    • 系统组成
      • 数据采集（数据获取）
        • 方式
          • 通过各种传感器，将光或声音等信息转化为电信息，或者将文字信息输入计算机
        • 分类
          • 一维波形：声波，心电图，脑电图等
          • 二维图象：文字，图象等
          • 三维图像：人脸等
          • 物理量：人的身高，体重，商品的重量，质量级别等
          • 逻辑量（0/1）：有无，男女等
      • 预处理
        • 目的
          • 去除噪声，增强有用的信息
        • 常用技术
          • 一维信号滤波去噪、图象的平滑、增强、恢复、滤波等
      • 特征提取和选择
        • 目的
          • 从原始数据中，得到最能反映分类本质的特征
        • 特征形成
          • 通过各种手段从原始数据中得出反映分类问题的若干特征（有时需进行数据标准化）
        • 特征选择
          • 从特征中选取若干最能有利于分类的若干特征
        • 特征提取
          • 通过某些数学变换，降低特征数目
      • 分类决策或模型匹配
        • 在特征空间中用判决规则将被识别对象归属为某一类别
    • 说明
      • 这一系统构造适合于统计模式识别、模糊模式识别、人工神经网络中有监督方法
      • 对于结构模式识别方法，只需用基元提取代替特征提取与选择
      • 对于聚类分析，分类器设计与决策合二为一，一步完成
    • 图像特征
      • 颜色
      • 纹理
      • 形状
      • 空间关系
    • 四个空间
    • 三大任务
      • 模式采集
      • 特征提取和特征选择
      • 类型判别
    • 相关问题
      • 性能评价
        • 测试错误率或者误差率
      • 计算复杂性
    • 划分
      • 分类依据
        • 问题或样本性质
          • 有监督模式识别
            • 先有一批带类别标签的样本，根据样本集设计分类器，再判断新的样本类别
          • 无监督模式识别
            • 只有一批样本，根据样本之间的相似性直接将样本集划分成若干类别
        • 主要方法
          • 统计模式识别
            • 分类
              • 非监督分类
                • 聚类分析
              • 监督分类
                • 集合分类
                • 概率分类
            • 描述方法
              • 特征向量
              • 模式判定
                • 用条件概率分布P（X/i）表示，m类就有m个分布，然后判定未知模式属于哪一个分布。
            • 理论基础
              • 概率论
              • 数理统计
            • 优点
              • 比较成熟
              • 能够考虑干扰噪声的影响
              • 识别模式基元能力强
            • 缺点
              • 对结构复杂的模式抽取特征困难
              • 不能反应模式的结构特征，难以描述模式性质
              • 难以从整体角度考虑识别问题
          • 结构模式识别
          • 模糊模式识别
          • 神经网络法
            • 理论基础
              • 神经生理学
              • 心理学
            • 模式描述方法
              • 以不同活跃度表示的输入节点集
            • 模式判定
              • 非线性动态系统
            • 主要方法
              • BP模型、HOPField模型
            • 优点
              • 有效解决复杂的非线性问题
              • 允许样本有较大的缺损、畸变
            • 缺点
              • 缺少有效的学习理论
              • 时间长
        • 应用领域
          • 图像、人脸、文字、数字、指纹、语音...
  • 基本问题
    • 模式（样本）表示方法
      • n维列向量
      • x= （x1 , x2 , …, xn）T
    • 模式类的紧致性
      • 临界点（样本）
        • 在多类样本集中，当一些样本的特征值发生微小变化后，就变成另一类样本，这样的样本称为临界样本（点）
      • 紧致集
        • 定义
          • 同一模式类样本的分布比较集中，没有或临界样本很少，这样的模式类称紧致集
        • 性质
          • 临界点很少
          • 集合内的任意两点的连线，在线上的点属于同 一集合
          • 集合内的每一个点都有足够大的邻域，在邻域内只包含同一集合的点
        • 要求
          • 满足紧致性
      • 相似性
        • 用各种距离表示相似性
        • 常用距离
          • 明考夫斯基（Minkowski） 距离
          • 绝对值距离或城区距离或曼哈顿（Manhattan）距离（q=1）
          • 欧几里德（Euclidean）距离（q=2）
          • 棋盘距离或切比雪夫（Chebyshev）距离（q=∞）
          • 马哈拉诺比斯（Mahalanobis）距离
            • 其中协方差矩阵和均值为
      • 数据的标准化
        • 目的
          • 消除各个分量之间数值范围大小对算法的影响
        • 方法
          • 标准化成[0,1]或者[-1,+1]、方差标准化
        • 公式
          • 特征标准化
          • 方差标准化
• 数据预处理
  • 为什么进行数据预处理
    • 不好
      • 不完整
        • 数据收集的时候就缺乏合适的值
        • 数据收集时和数据分析时的不同考虑因素
        • 人为/硬件/软件 问题
      • 有噪声
        • 数据收集工具的问题
        • 数据输入时的 人为/计算机 错误
        • 数据传输中产生的错误
      • 数据类型不一致
        • 不同的数据源
        • 违反了函数依赖性
    • 好
      • 正确性：如是否正确，精确与否等
      • 完整性：如是否有数据遗漏或无法取得
      • 一致性：如一些数据被修改了而另一些则没有
      • 可靠性：描述数据的正确性的可信程度
    • 任务
      • 数据清理
        • 填写缺失的值，光滑噪声数据，识别、删除离群点，解决不一致性
      • 数据集成
        • 集成多个数据库、数据立方体或文件
      • 数据变换和离散化
        • 规范化
        • 概念分层生成
      • 数据归约
        • 维归约
        • 数量归约
        • 数据压缩
      • 特征提取与特征选择
  • 数据清理
    • ❑ 填写缺失值
      • 原因
        • ❑ 设备异常
        • ❑ 与其他已有数据不一致而被删除
        • ❑ 因为误解而没有被输入的数据
        • ❑ 在输入时有些数据因没有得到重视而未输入
        • ❑ 对数据的改变没有进行日志记录
      • 处理
        • ◼ 忽略元组：当类标号缺少时通常这么做（假定挖掘任务设计分类或描述），当每个属性缺少值的百分比变务设计分类或描述），当每个属性缺少值的百分比变化很大时，它的效果非常差。
          • "类标号"（Class Label 或 Target Label）通常指的是数据集中「用于表示样本所属的类别或组的标记」。
        • ◼ 人工填写缺失值：工作量大，可行性低
        • ◼ 自动填写缺失值
          • ❑ 使用一个全局变量：比如unknown或-∞
          • ❑ 使用属性平均值
          • ❑ 使用与给定元组属同一类的所有样本的均值或中位数
          • ❑ 使用最可能的值填充空缺值：使用像Bayesian公式或决策树这样的基于推理的方法
    • ❑ 光滑噪声数据
      • 原因
        • ❑ 数据收集工具的问题
        • ❑ 数据输入错误
        • ❑ 数据传输错误
        • ❑ 技术限制
        • ❑ 命名规则的不一致
      • 处理
        • 分箱
          • 首先排序数据，并将他们分到等深的箱中，然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等等
          • 操作
            • 等深分箱
              • 边界值平滑：把所有值都变成最大值或者最小值
            • 等宽分箱
              • [110,155)，左闭右开
        • 聚类
          • 通过聚类来检测并删除离群点
        • 回归
          • 过让数据适应回归函数来平滑数据
    • ❑ 识别或删除离群点
    • ❑ 解决数据中的不一致性
  • 数据集成
    • ◼ 数据集成：
      • ❑ 将多个数据源中的数据整合到一个一致的存储中
    • ◼ 模式集成：
      • ❑ 整合不同数据源中的元数据
      • ◼ e.g. A.cust_id = B.customer_no
    • ◼ 实体识别问题：
      • ❑ 匹配来自不同数据源的现实世界的实体
      • ◼ e.g. Bill Clinton = William Clinton
    • ◼ 检测并解决数据值的冲突
      • ❑ 对现实世界中的同一实体，来自不同数据源的属性值可能是不同的
      • ❑ 可能的原因：不同的数据表示，不同的度量等等
  • 数据归约
    • 目的
      • ◆对大规模数据库内容进行复杂的数据分析常需要消耗大量的时间，使得对原始数据分析变得不现实和不可行；
      • ◆数据归约（data reduction）：数据消减或约简，是在不影响最终挖掘结果的前提下，缩小所挖掘数据的规模。
      • ◆数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持原数据的完整性。
      • ◆对归约后的数据集进行挖掘可提高挖掘的效率，并产生相同（或几乎相同）的结果。
    • 标准
      • ◆用于数据归约的时间不应当超过或“抵消”在归约后的数据集上挖掘节省的时间。
      • ◆归约得到的数据比原数据小得多，但可以产生相同或几乎相同的分析结果。
    • 方法
      • ◆数据立方体聚集；
        • 将n维数据立方体聚集为n-1维的数据立方体。
      • ◆维归约（属性归约）；
        • 找出最小属性集，确保新数据集的概率分布尽可能接近原数据集的概率分布。
        • PCA
      • ◆数据压缩；
        • 无损压缩
        • 有损压缩
      • ◆数值归约；
        • 通过选择替代的、较小的数据表示形式来减少数据量。
        • 类型
          • 直方图
          • 聚类
          • 取样
      • ◆离散化和概念分层生成。
        • 规范化
          • 最小—最大规范化
            • 肯定是正的
          • z-score规范化（零均值规范化）
            • 可能为负数
        • 离散化
          • 目的
            • 数据离散化是将连续数据的值划分为若干个区间，以简化原始数据集的复杂性。
          • 类型
            • 无序集合中的值；e.g. 颜色、职业
            • 有序集合中的值； e.g. 军衔、职称
            • 连续值；e.g. 实数
        • 概念分层
• 聚类分析
  • 概念
    • 思想
      • 基于某种相似性度量的方法讲各个带分类的模型进行归类
      • 相似的归为一类
    • 算法
      • 根据相似性阈值和最小距离原则的简单聚类方法
      • 按最小距离原则不断两类合并的方法
      • 依据准则函数动态聚类法
    • 应用
      • 聚类分析可以作为其它算法的预处理步骤
      • 可以作为一个独立的工具来获得数据的分布情况
      • 聚类分析可以完成孤立点挖掘
  • 基于划分的聚类方法
    • 划分方法是将数据对象划分成不重叠的子集（簇），使得每个数据对象恰在一个子集中。
    • 分类
      • 距离类型
        • 欧式距离
        • 曼哈顿距离
        • 闵可夫斯基距离
          • 闵氏距离不是一种距离，而是一组距离的定义。
      • 算法类型
        • k-means（K-均值）算法
          • 输入：簇的数目k和包含n个对象的数据库D
          • 输出：k个簇，使平方误差准则最小。
          • 算法步骤
            • 1．为每个聚类确定一个初始聚类中心，这样就有K个初始聚类中心。 2．将样本集中的样本按照最小距离原则分配到最邻近聚类。 3．使用每个聚类中的样本均值作为新的聚类中心。 4．重复步骤2，3直到聚类中心不再变化。 5．结束，得到K个聚类。
          • 特点
            • 优点
              • 简单快速
              • 可伸缩、效率高
              • 当结果集是密集的时，效果比较好
            • 缺点
              • 簇的平均值被定义的情况下才能使用
              • 必须事先给出k
              • 对初值很敏感，直接影响迭代次数
              • 不适用于发现非凸面形状的簇或者大小差别很大的簇
              • 对于“躁声”和孤立点数据是敏感
          • 改进
            • k-mode 算法：实现对离散数据的快速聚类，保留了k-means算法的效率同时将k-means的应用范围扩大到离散数据。
            • k-prototype算法：可以对离散与数值属性两种混合的数据进行聚类，在k-prototype中定义了一个对数值与离散属性都计算的相异性度量标准。
            • k-中心点算法( K-Mediods )：k -means算法对于孤立点是敏感的。为了解决这个问题，不采用簇中的平均值作为参照点，可以选用簇中位置最中心的对象，即中心点作为参照点。这样划分方法仍然是基于最小化所有对象与其参照点之间的相异度之和的原则来执行的。
        • k-medoids（K-中心点）算法
          • 输入：簇的数目k和包含n个对象的数据库。
          • 输出：k个簇
          • 算法步骤
            • 1.为每个聚类确定一个初始聚类中心，这样就有k个初始聚类中心。 2.计算其余所有点到k个中心点的距离，并把每个点到k个中心点最短的聚簇作为自己所属的聚簇。 3.在每个聚簇中按照顺序依次选取点，计算该点到当前聚簇中所有点距离之和，最终距离之和最小的点，则视为新的中心点。 4.重复2，3步骤，直到各个聚簇的中心点不再改变。 5.结束，得到k个聚类。
          • 特点
            • 优点
              • K-medoids算法计算的是某点到其它所有点的距离之和最小的点，通过距离之和最小的计算方式可以减少某些孤立数据对聚类过程的影响。从而使得最终效果更接近真实划分。
            • 缺点
              • 相对于K-means算法大约会增加O（n）的计算量，因此一般情况下K-medoids算法更加适用于小规模数据运算。
  • 基于层次的聚类算法
    • 定义
      • 将数据对象创建成一颗聚类的树。根据层次分解是自底向上还是自顶向下形成，可进一步分为凝聚式层次聚类和分裂式层次聚类。
    • 核心
      • 如何度量两个簇之间的距离，其中每个簇一般都是一个对象集。
    • 分类
      • 距离类型（簇间距离度量方法）
      • 算法类型
        • AGNES(凝聚式层次聚类)
          • 定义
            • AGNES(凝聚的层次聚类)是一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。
          • 相似度
            • 两个簇间的相似度由这两个不同簇中距离最近的数据点对的相似度来确定。
          • 步骤
            • 1、将每个对象当成一个初始簇； 2、REPEAT； 3、根据两个簇中最近的数据点找到最近的两个簇； 4、合并两个簇，生成新的簇的集合； 5、UNTIL达到定义的簇的数目；
        • DIANA(分裂式层次聚类)
        • BIRCH（利用层次方法的平衡迭代规约和聚类）
  • 密度聚类方法
    • 核心
      • 只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。
    • 分类
      • DBSCAN
        • 核心
          • 与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。
        • 定义
          • 对象的ε-临域：给定对象在半径ε内的区域。
          • 核心对象（核心点）：如果一个对象的ε-临域至少包含最小数目MinPts个对象，则称该对象为核心对象。
          • 直接密度可达：给定一个对象集合D，如果p是在q的ε-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。
          • 密度可达：如果存在核心点P2，P3，……，Pn，且P1到P2密度直达，P2到P3密度直达，……，P(n-1)到Pn密度直达，Pn到Q密度直达，则P1到Q密度可达。密度可达也不具有对称性。
          • 密度相连：如果存在核心点S，使得S到P和Q都密度可达，则P和Q密度相连。密度相连具有对称性，如果P和Q密度相连，那么Q和P也一定密度相连。密度相连的两个点属于同一个聚类簇。
          • 噪声: 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。
        • 步骤
          • 1）如果该点的邻域包含的点多于MinPts个，则其为核心点，否则该点暂时被记为噪声点 2）找出所有从该点密度可达的对象，形成一个簇
        • 特点
          • 优点
            • 聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类。
          • 缺点
            • （1）当数据量增大时，要求较大的内存支持I/O消耗也很大； （2）当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差。 （3）有两个初始参数ε（邻域半径）和minPts(ε邻域最小点数)需要用户手动设置输入，并且聚类的类簇结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果。
      • OPTICS
      • DENCLUE
• 贝叶斯分类
  • 朴素贝叶斯
    • Bayes法是一种在已知先验概率与类条件概率的情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体
    • 朴素贝叶斯假设所有特征属性都是互相独立的，这也正是算法名称中“朴素(naive)”一词的由来
    • 现实中属性之间往往存在依赖，但有意思的是，即使是在朴素贝叶斯算法的独立性假设明显不成立的情况下，它也仍然能得到非常好的分类结果
    • 贝叶斯公式
    • 最小错误率
      • • 特征是给出来的信息
        • 类别是最终要求的
      • 有多个特征属性时
      • 含义
        • 后验概率P(cj |x)
          • 即给定数据样本x时cj成立的概率,而这正是我们所感兴趣的(要计算的)
        • • 每个P(xk|Ci)可以通过先验知识 或者通过样本集进行统计
        • 先验概率P(cj)
          • 先验概率P(Ci)可以通过先验知识 或者通过样本集进行统计
        • P(x)可以约去或套公式
      • 化简
    • 最小风险
      • 决策表
      • 计算方法
        • 对于每种决策α，分别计算
        • 取条件风险最小的决策
• 近邻法
  • 最近邻法/K近邻法
    • 目的
      • 确定一个点的分类
    • 思路
      • 在训练数据集中找出与这个新实例最近的k 个训练实例，然后统计最近的k 个训练实例中所属类别计数最多的那个类，就是新实例的类。
    • 流程
      • 计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）
      • 对上面所有的距离值进行排序
      • 选前k 个最小距离的样本
      • 根据这k 个样本的标签进行投票，得到最后的分类类别
    • k值的选择
      • k值越小表明模型越复杂，更加容易过拟合 但是k值越大，模型越简单，如果k=N的时候就表明无论什么点都是训练集中类别最多的那个类 所以一般k会取一个较小的值，然后用过交叉验证来确定 这里所谓的交叉验证就是将样本划分一部分出来为预测样本，比如95%训练，5%预测，然后k分别取1，2，3，4，5之类的，进行预测，计算最后的分类误差，选择误差最小的k
  • 区别
    • K-Means
      • 目的是为了将一系列点集分成k类
      • K-Means是聚类算法
      • 非监督学习，将相似数据归到一起从而得到分类，没有外部分类
      • 训练数据集无label，是杂乱无章的，经过聚类后才变得有点顺序，先无序，后有序
    • 最近邻法/K近邻法
      • 目的是为了确定一个点的分类
      • KNN是分类算法
      • 监督学习，分类目标事先已知
      • 训练数据集有label，已经是完全正确的数据
• 关联规则
  • 定义
    • 基本概念
      • 项目（item）：例如可乐，薯片，面包，啤酒，尿布都称作item。
      • 设I={i1, i2,…,im}是所有项(Item)的集合。
      • 事务T是购买记录，且对于每一个事务T具有唯一的标识，记作Tid。
      • D是所有事务(Transaction)的集合。
      • 项集（itemset）是我们想研究的集合
        • 项集中item的个数称为项集的长度，含有k个item的项集称为K-itemset。
    • 关联规则
      • 形如A->B的逻辑蕴含式，其中A,B都不为空，且A⸦I， B⸦I，并且(A交B=空)。
    • 支持度Support
      • 描述项集A和B在所有事务D中同时出现的概率
      • S(A->B)=P(AB)=|AB|/|D|
      • 支持度是对关联规则重要性的衡量
    • 置信度Confidence
      • 在出现了项集A的事物T中，项集B也同时出现的概率。
      • C(A->B)=P(B|A)=|AB|/|A|
      • 置信度是对关联规则的准确度的衡量
    • 强关联规则
      • D 在 I 上满足最小支持度和最小可信度的关联规则称为强关联规则。
    • 提升度Lift
      • 提升度表示A项集的出现，对B项集的出现有多大影响。
      • L(A->B)=P(AB)/(P(A)*P(B))
        • 大于1
          • 正相关
        • 等于1
          • 相互独立
        • 小于1
          • 负相关
    • 频繁项集
      • 满足最小支持度的项集称为频繁项集。频繁k-项集的集合通常记作Lk
  • 目的
    • 根据用户指定的最小支持度和最小置信度来寻找强关联规则
    • 步骤
      • 通过用户给定最小支持度，寻找所有频繁项目集或者最大频繁项目集
      • 通过用户给定最小可信度，在频繁项目集中，寻找关联规则
  • 算法
    • Apriori算法
      • 第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；
        • 频繁项目：数数，算S
      • 第二步利用频繁项集构造出满足用户最小信任度的规则。
        • 关联规则：算C
    • FP-Growth