无监督、聚类降维
无监督
  降维
    kNN-k近邻
      取相邻的k个点的结果投票
      假设：密采样，任意测试样本附近都有样本
      lazy learning
      k
        Larger K values smooth the decision boundary
      维度灾难
        样本稀疏、距离计算困难
    MDS
      从距离到位置的方法
        使用欧氏距离
      专注于保持数据点之间的“距离关系”，不关心方差
    PCA
      注重保持数据的“方差”，寻找最大变化方向
      优化的目标是重构error
      中心化
      计算协方差矩阵
      特征值分解
      应用变换
      If the data is centralized (zero mean), PCA can be done through SVD
      And the eigenvalues in PCA is the square of the singular values in SVD.
    监督降维
      LDA
        特征空间投影到一个子空间内
          同类投影点尽可能近，异类样例尽可能远
          保留区分类别的信息
        有监督
          找到更合适的分类的空间
        计算步骤
          算出每个类的均值
          算Sw
            within class
          算出Sb
        LDA关心分类
        PCA更关心方差
    核化降维
      先变到高维映射空间，再使用PCA
      获得最后坐标的时候，需要对所有样本求和，开销较大
    流形学习
      ISOMAP
        直线距离不可达，使用测地线（蚂蚁）
        近邻点构建连接图，使用djikstra计算最短距离
          近邻图使用k近邻或者epsilon近邻
        使用MDS方法获取坐标
        训练一个回归模型
      LLE局部线性嵌入
        数据之间的局部关系是很重要的，降维后也要尽量保留这些关系。
        找到邻居
        用线性关系表示
        在低维空间中，重新安排这些点的位置，使得邻居点对中心点的线性关系（权重）不变
    t-SNE
      最小化高维空间和低维空间之间的Kullback-Leibler散度来优化低维表示
    度量学习
      转换维度就是为了寻找更好的距离度量
        直接学习距离度量
      使用半正定对称阵，满足非负对称性质
        子主题 1
      训练方法
        投票法，优化k近邻的留一法正确率
        凸优化问题
          有些点相似要近一点，有些点要离得远一点
    降维的主要目的是减少数据的复杂性和维度，而不一定提高数据的解释性。
  聚类
    MPP
    kmeas
    性能度量
      外部指标
        两两配对
        Jaccard
        FM
        Rand
        越大越好[0,1]
      内部指标
        DBI
          越小越好
        DI
          越大越好
    距离计算
      闵氏距离
      欧式距离
      曼哈顿距离
      VDM
        分布比例的绝对差值
      无序属性
        飞机轮船
      有序属性
        123
    原型聚类
      通过一组代表性点
      Kmeans
        初始化均值向量
        遍历
          加到最近的簇
        更新均值向量
      k-means++
        初始化k个中心的方法不同
        随机选择第一个聚类中心：
        每个点到已选中心的最小距
        每个点被选为聚类中心的概率与其到已选聚类中心的距离平方成正比
          较远的点更有可能被选为新的聚类中心
      学习向量量化
        q个原型向量
          学习率
        有监督
        计算距离，找出最近的原型向量
        原型向量移动
          标签一样就靠拢
          不一样就远离
      高斯混合聚类
        EM算法
        先确定成分
        计算后验概率
        更新均值
        更新方差
        更新混合系数
      谱聚类
        使用拉普拉斯特征映射将为之后
          kmeans
        Constructing a adjacency matrix for large datasets is time-consuming
    密度聚类
      产生任意形状的簇，不需要指定聚类个数k，对噪声鲁棒
      初始化核心对象
      从序列中抽取一个，组成一个密度可达的链，并从序列中扣除
      直到序列为空
      核心点可以扩展形成簇，而边界点是邻近核心点的点，无法直接扩展簇；噪声点则不属于任何簇。
      能有效处理密度不均的数据，但对参数选择较为敏感。
    层次聚类
      AGNES
        簇间距离的计算可以采用单链接（最小距离）、全链接（最大距离）或均链接（平均距离）
        从每个样本开始，将每个样本初始视为一个独立的簇，然后通过迭代过程逐步合并距离最近的两个簇