K均值聚类---K-mean

对无监督学习对象进行分类的常用方法之一。

因为比较简单，所以就简单说下

 

一开始先输入K(就是cluster的个数)还有training set。 

 

从training set中随机选取K的点作为初始的cluster centroid。

然后for loop：

① min(每个training set的点到cluster centroid的距离)，因为是根据这个点到cluster centroid的距离来判断，这个点是否属于这个cluster centroid。E.g c(5) = 4 代表 第五个样本点是属于第四个cluster centroid。

② 等到所有点都找到了自己的cluster centroid后，再找出每个cluster新的中心点，具体就是将属于同一个cluster的所有点加起来，再取平均值，得到的就是新的cluster centroid的坐标。E.g c(76) = 4, c(24) = 4,c(5) = 4，就是将这三个的横纵坐标加起来然后除以3得出新点坐标。

在将所有新的cluster centroid算出来后，如果新点跟旧点相比，差距不大，则可以结束，否则就继续循环①②(带着新点循环)。

如图，K-mean的目的是让costFunction J达到最小，就是training set中每个点到其cluster centroid的距离的和最小。

然而，随机初始化centroid可能会带来不好的影响，看图

 如上图，如果运气差的话，初始点的位置不好，会出现以上现象。明显的3个cluster可能最后结果只有2个cluster。

解决方法：多次循环K-mean，然后去J的最小值时的K

 

循环算K-mean后，会有这么两种结果第一种称为Elbow method，就是斜率问题。如图选择K=3，因为斜率在这里骤变。

然后对于图二，很难选

这里post上一题目。K=5时>K=3

有时候，对于K-mean要根据需求了来选择K，如下图，不同衣服size

Dimensionality Reduction---维度约简

两个motivation ： 1. Data compression 数据压缩，可以提高运算速度和减少存储空间。

                               2. Data Visualization 更直观的视图

Data Compression

从2D->1D

在这个例子里，2D坐标系中所有点可以由一条大概的直线贯穿，点到直线上的映射(注意，这里是点到直线的距离，并不是点的纵坐标到直线的距离) 如下图那一条线就是点的映射，那么整个2D数据就可以由原来的(x,y)--->z用z来表达

3D->2D同理，只不过用（z1,z2)来代替原本的(x,y,z) 

 

 Data Visualization

 

 

 上面三图所表达的东西可以最终由GDP和人均GDP或类似的东西来表达。从原本的好多D降到了2D

Principal Component Analysis Problem Formulation(PCA)

PCA的目的就是降维，具体怎么做呢，就是找到一个向量(就是那条线)，使得所有training 点映射在这向量上面的projection error最小。啥是projection error，就是下图，点到直线的距离（是距离，不是纵坐标距离）

 

 这就是上面所说的距离。左图是linear regression，其目的是预测y和原本真实的y的差距，所以用的是纵坐标上的距离。

而右图则是PCA，求得是降维过程中的最佳向量。

那咋用呢

第一步：处理数据，feature scaling啊 mean normalization啊什么的保证取值范围在一个合理的范围内，不然容易因为某一个的取值范围过大或过小而影响了最终结果（参考那个房子面积和房间数）

 第二步：计算协方差矩阵 和特征向量

 这个协方差(covariance matrix)符号和求和符号很像，然后这里用sigma表示协方差矩阵

接下来就是算特征向量

svd()唤作single value decomposition奇异值分解。这里U,S,V我们只取U来玩。

具体原理，咱不知道，咱也不敢问。

看到上面的U没有，我们取前K个(这里的K就是降维后的维数)，作为K个向量μ，(啥意思呢，就是如果2D->1D, 就只用一条向量能表达嘛，这个μ就等于那条直线，同理 3D->2D，μ1，μ2)。。然后z就是我们降维后用来代替原本维度东东。z = Ureduce * X，这个Ureduce就是取了前K个后的U。

Reconstruction

有降维肯定就有还原啦。

 

这是第一种方法，projection error 的平均值误差 / 那个总变量得到的结果小于某个数，这里是小于0.01，换句话说，99%的变量都被保留了 

第二种方法就简单的多， 咱取U,S,V中的S，这是一个对角线有元素，其他为0的矩阵，然后按照公式，要多少k取多少k然后除总数，搞定

最后补充： 

  

PCA只是用来降维，不能用来解决over'fit 

 

PCA不应该是作为首先考虑的手段，应该用别的方法算过后不行才用。

这里只放两段代码