聚类

• 性能度量 or 有效性指标

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的值，存在这些特点的数据称稀疏性

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

• 压缩感知

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