聚类

  • 性能度量 or 有效性指标
两样本在同一个参考模型类中 两样本不在同一个参考模型中
两样本在同一个聚类类中 a=|SS| c=|DS|
两样本步子同一个聚类类中 b=|SD| d=|DD|

avg(C) 样本间平均距离,diam(C) 样本内最大距离,d_{min}(C_i,C_j) 两个簇间样本最近距离,d_{max}最远距离

  • 常用聚类性能度量
    • Jaccard系数 JC=\\frac{a}{a+b+c}
    • FM系数 FMI=\sqrt{\\frac{a}{a+b}*\\frac{a}{a+c}}
    • Rand指数 RI=\\frac{2(a+d)}{m(m-1)}
    • DB指数 DBI=\\frac{1}{k} \\sum^k_{i=1} \\max_{j \\rlap{\\,/}{=} i}(\\frac{avg(C_i)+avg(C_j)}{d_{cen}(u_i,u_j)})
    • Dunn指数 DI=\\min_{k\\geq i\\geq 1}(\\min_{{j \\rlap{\\,/}{=} i}}(\\frac{d_{min}(C_i,C_j)}{max_{k\\geq i\\geq 1} diam(C_l)}))
  • 距离计算
    • 闵可夫斯基距离 dist_{mk}(x_i,x_j) = (\\sum^n_{u=1}|x_{iu}-x_{ju}|^p)^\\frac{1}{p}

      当P=2是及欧式距离,P=1时为曼哈顿距离

    • VDM 用于无序属性

    • 加权距离

需满足 非负性,同一性,对称性,直递性

  • 原型聚类
    • K均值算法(k-means)随机选择k起始点,囊括所有距离最近的点,重新计算类中心,迭代直到收敛
    • 学习向量量化(LVQ)通过样本的标记对原型向量进行更新
    • 高斯混合聚类 采用概率模型表达聚类原型
    • 密度聚类 (DBSCAN等) 以任意样本为起点寻找所有密度可达的样本
    • 层次聚类 (AGNES等) 每次迭代找出距离最近的两个样本合并,直到成为一颗树

降维与度量学习(略)

  • K近邻学习

对于一个样本,找出数据集中k个与其最相近的样本,通过这些样本的标签来对其进行预测

  • 低维嵌入

高维情况下出现的样本稀疏,距离计算困难等称为维数灾难

MDS 多维缩放

原始空间中样本间距离在低维空间中保持(一般认为尽可能接近而不是相等)。

对原始高维控件进行线性变换的方法 称为线性降维方法

  • PCA 主成份分析
    • 最近重构性:样本点到这个超平面的距离都足够近
    • 最大可分性:样本点在这个超平面上的投影都尽可能分开
  • 核化线性降维

同前核方法,在线性降维中使用核方法使其能处理非线性降维

  • 流形学习

等度量映射 Isomap

认为低维流形潜入到高维空间之后,直接在高维空间中计算直线距离有误导性,利用“流形在局部上与欧氏空间同胚”性质,对每个点基于欧式距离找出近邻点。

局部线性嵌入

企图保持邻域样本之间的关系。假定样本点能通过多个领域样本的坐标通过线性组合重构,这个关系在低维关系中需要保持

  • 度量学习

学习出一个合适的距离度量

特征选择与稀疏学习

  • 子集搜索与评价

从属性集合中搜索子集并评价

  • 过滤式选择

Relief

通过相关统计量来度量特征重要性。先从同类样本中寻找最近近邻x_{i,nh},再从异类样本中寻找最近近邻x_{i,nm}

相关统计两 \\sigma^j=\\sum_i -diff(x_i^j,x^j_{i,nh})^2+diff(x_i^j,x^j_{i,nm})^2

其中diff函数 当其中两参数相同时取0,否则为1

  • 包裹式选择

把通过属性子集得出的学习器性能用于评价属性集合

  • 嵌入式选择与L1正则化

在学习器训练的过程中同时优化特征选择

L1范数正则化比L2更容易带来稀疏解

  • 稀疏表示与字典学习

举例:文档分词后一定存在属性中存在实际为0的值,存在这些特点的数据称稀疏性

通过学习一个字典来将原本稠密的数据学习成为稀疏数据。

  • 压缩感知

关注如何基于稀疏性从少量观测数据中恢复原信号