非线性特征降维——聚类

聚类

聚类就是按照某个特定标准（如距离准则）把一个数据集分割成不同的类和簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同的数据尽量分开。

聚类与降维的区别与联系

区别

降维是在数据预处理时为了防止过拟合和避免维度灾难时常用的方法，聚类时在数据集是在整个数据集上按照一个定义的拓扑距离进行分组的过程。

联系

聚类可以看作是对类别变量做降维，而降维也常常为聚类服务。

降维的目的主要有两个。首先，是为了更好的适应模型。特别是在样本较少的数据集上，如果维度过高导致样本在空间上分布稀疏，很容易造成过拟合（当然有SVM等算法来解决这一问题）；其次，是避免维度灾难的问题。在维度过高的时候，如果采用常见的距离度量方法（如欧式距离等）度量空间样本上的距离，就会陷入维度灾难，也即大部分样本间的距离会被压缩到很小的范围内，以致无法区分。

聚类的思路主要有两种。一种是常规的聚类（需要定义距离的聚类），另一种为图上的聚类（基于连通关系的）。对于第一种聚类而言，距离的定义很关键，而我们的数据通常是高维的，而修改距离度量算法的普适性又不强。这时候，常常会采用降维的方法论来解决。

几种常见的聚类算法
k-means聚类算法

k-means是划分方法中较经典的聚类算法之一。由于该算法的效率高，所以在对大规模数据进行聚类时被广泛应用。目前，许多算法均围绕着该算法进行扩展和改进。

k-means算法以k为参数，把n个对象分成k个簇，使簇内具有较高的相似度，而簇间的相似度较低。k-means算法的处理过程如下：首先，随机地 选择k个对象，每个对象初始地代表了一个簇的平均值或中心；对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇;然后重新计算每个簇的平均值。 这个过程不断重复，直到准则函数收敛。通常，采用平方误差准则，其定义如下：

​

这里E是数据库中所有对象的平方误差的总和，p是空间中的点，mi是簇Ci的平均值。该目标函数使生成的簇尽可能紧凑独立，使用的距离度量是欧几里得距离,当然也可以用其他距离度量。k-means聚类算法的算法流程如下：

输入：包含n个对象的数据库和簇的数目k； 输出：k个簇，使平方误差准则最小。

步骤：

  1. 任意选择k个对象作为初始的簇中心；
  2. 根据簇中对象的平均值，将每个对象(重新)赋予最类似的簇；
  3. 更新簇的平均值，即计算每个簇中对象的平均值；
  4. 重复2、3，直到k个簇中心不再发生变化。

k-means的python实现

>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
...               [4, 2], [4, 4], [4, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([0, 0, 0, 1, 1, 1], dtype=int32)
>>> kmeans.predict([[0, 0], [4, 4]])
array([0, 1], dtype=int32)
>>> kmeans.cluster_centers_
array([[ 1.,  2.],
       [ 4.,  2.]])
层次聚类算法

根据层次分解的顺序是自底向上的还是自上向下的，层次聚类算法分为凝聚的层次聚类算法和分裂的层次聚类算法。

凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。四种广泛采用的簇间距离度量方法如下：

最小距离：

最大距离：

平均值距离：

平均距离：

这里， 是两个对象和之间的距离， 是簇 的平均值 是簇中对象的数目。

这里给出采用最小距离的凝聚层次聚类算法流程：

  1. 将每个对象看作一类，计算两两之间的最小距离；
  2. 将距离最小的两个类合并成一个新类；
  3. 重新计算新类与所有类之间的距离；
  4. 重复2、3，直到所有类的数量为k。
    SOM聚类算法

SOM神经网络是由芬兰神经网络专家Kohonen教授提出的，该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。

SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。 学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。

算法流程：

  1. 网络初始化，对输出层每个节点权重赋初值；
  2. 将输入样本中随机选取输入向量，找到与输入向量距离最小的权重向量；
  3. 定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢；
  4. 提供新样本、进行训练；
  5. 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类结果。

参考资料

  1. 特征哈希(Feature Hashing)
  2. Trevor Hastie et al. The Elements of Statistical Learning, 2001.
  3. Kilian Weinberger et al. Feature Hashing for Large Scale Multitask Learning, 2010.
  4. Joshua Attenberg et al. Collaborative Email-Spam Filtering with the Hashing-Trick, 2009.
  5. https://www.zhihu.com/question/264165760/answer/277634591
  6. sklearn.feature_extraction.FeatureHasher
  7. sklearn学习笔记2 Feature_extraction库
  8. 特征选择和稀疏学习
  9. 《西瓜书》笔记11：特征选择与稀疏表示（三）
  10. 特征选择与稀疏学习
  11. https://www.zhihu.com/question/24124122/answer/50403932
  12. https://blog.csdn.net/u014595019/article/details/52433754
  13. PCA算法详解
  14. 主成分分析（PCA）原理详解
  15. 主成分分析PCA算法：为什么去均值以后的高维矩阵乘以其协方差矩阵的特征向量矩阵就是“投影”？
  16. 用Python的sklearn库进行PCA(主成分分析)
  17. 用scikit-learn学习主成分分析(PCA)
  18. 独立成分分析（Independent Component Analysis）
  19. 独立成分分析 ( ICA ) 与主成分分析 ( PCA ) 的区别在哪里？
  20. 独立成分分析ICA系列4:ICA的最优估计方法综述
  21. ICA-独立成分分析
  22. 独立成分分析Independent component analysis(ICA)
  23. 线性判别分析LDA原理总结
  24. 一文读懂特征工程
  25. 线性判别分析LDA详解
  26. LinearDiscriminantAnalysis
  27. 用scikit-learn进行LDA降维
  28. https://blog.csdn.net/u010705209/article/details/53518772
  29. https://blog.csdn.net/u012162613/article/details/42214205
  30. https://blog.csdn.net/qianhen123/article/details/40077873
  31. https://github.com/ceys/jdml/wiki/ALS
  32. 美团点评技术团队之深入FFM原理与实践
  33. [深度学习笔记（一）稀疏自编码器] (https://blog.csdn.net/u010278305/article/details/46881443)
  34. Field-aware Factorization Machines for CTR Prediction ,Yuchin Juan et al.
  35. Factorization Machines, Steffen Rendle et al.[2010]
  36. http://deeplearning.stanford.edu/wiki/index.php/UFLDL_Tutorial
  37. 局部线性嵌入(LLE)原理总结
  38. Locally linear embedding(LLE)局部线性嵌入-降维
  39. LocallyLinearEmbedding
  40. 用scikit-learn研究局部线性嵌入(LLE)
  41. 聚类和降维的区别与联系
  42. 聚类算法
  43. 受限玻尔兹曼机（RBM）学习笔记
  44. 受限制玻尔兹曼机RBM原理简介
  45. 从SNE到t-SNE
  46. t-SNE完整笔记
  47. SNE降维与可视化
  48. 比PCA降维更高级 —— t-SNE聚类算法实现指南

results matching ""

    No results matching ""