Q：什么是K临近学习？
K临近学习是一种监督学习算法。与以往的监督学习，如线性回归、决策树、支持向量机等不同，K临近学习虽然也需要训练数据，但不需要事先使用训练集做模型训练。
K临近学习的核心思想是“物以类聚，人以群分”。假设一个二分类任务，给定一个样本要求判定该样本是正类还是反类，则仅需以该样本为圆心，找出离该样本最近的k个训练样例，若这k个训练样例中正例多，则判定该样本为正例，否则判定为反例。整个判定只需要设置一个k值，即选择多少个邻居，不需要做其他事情，因此不需要事先使用训练集做模型训练。
举一个可能不怎么恰当的例子：在下课时间内判断一个小学生教室里某个学生a是男是女（下课时段内人们可以自由走动聚集），则可以看看距离学生a最近的k个学生，是男生多还是女生多，如果男生多则判定学生a是男生，否则判定为女生。因为按照常理判断，小学生一般是男生和男生一起玩，女生和女生一起玩的，只有个别例外。
在找出样本附近k个邻居时（实现标记好的训练样例），需要计算样本间的距离。这个距离一般使用欧氏距离，也可以用其他合适的距离做计算。
"""
Simple K nearest neighbors classifier
:file: supervised.py
:author: Richy Zhu
:email: rickyzhu@foxmail.com
"""
import numpy as np
class KNNClissifier:
def __init__(self):
self.X = None
self.y = None
self.k = None
self.func_dist = None
def _top_k_nn(self, centroid, surroundings):
'''
return indices of the top k nearest neighbors of centroid
from surroundings
'''
distances = []
for vec in surroundings:
distances.append(self.func_dist(centroid - vec))
distances = np.array(distances)
top_k = np.argsort(distances)[:self.k]
# print('neightbors and distances:', \
# [(v, d) for v, d in zip(surroundinds, distances)])
return top_k
def fit(self, X, y, k=1, func_dist=None):
'''
Train the K nearest neighbor classifier model
Parameters
----------
X: ndarray of shape (m, n)
sample data where row represent sample and column represent feature
y: ndarray of shape (m,)
labels of sample data
k: int
number of neightbors selected to compare
func_dist: function
distance function, by default Euclidean distance
Returns
-------
self
trained model
'''
self.X = X
self.y = y
self.k = k
if func_dist == None:
self.func_dist = np.linalg.norm # Euclidean distance
else:
self.func_dist = func_dist
def predict(self, X):
'''
Make prediction by the trained model.
Parameters
----------
X: ndarray of shape (m, n)
data to be predicted, the same shape as trainning data
Returns
-------
C: ndarray of shape (m,)
Predicted class label per sample.
'''
if self.X is None:
raise Exception("Model haven't been trained!")
from collections import Counter
C = []
for x in X:
top_k_indices = self._top_k_nn(x, self.X)
top_k_labels = self.y[top_k_indices]
# top_k = self.X[top_k_indices]
# print('top k neightbors:', top_k)
# print('class of top k neightbors:', top_k_labels)
C.append(Counter(top_k_labels).most_common(1)[0][0])
return np.array(C)
测试代码如下
from sklearn.datasets import load_boston, load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error, accuracy_score
print('\nK Nearest Neighbors')
print('---------------------------------------------------------------------')
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target)
kclf = KNNClissifier()
kclf.fit(X_train, y_train, 2)
y_pred = kclf.predict(X_test)
print(y_pred, y_test)
print('My Accuracy:', accuracy_score(y_test, kclf.predict(X_test)))
from sklearn.neighbors import KNeighborsClassifier
clf = KNeighborsClassifier()
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
print('Sk Accuracy:', accuracy_score(y_test, clf.predict(X_test)))
测试结果如下
$ python supervised_example.py
K Nearest Neighbors
---------------------------------------------------------------------
My Accuracy: 0.9473684210526315
Sk Accuracy: 0.9736842105263158
Q：会不会出现训练样例分布太过稀疏，以至于选择的k个邻居其实都不是离该样本很近，导致邻居们不足以代表目标样本？
会，而且样本的维度越高（特征/属性越多），这种情况越容易出现。因为采集只有两个特征的样本数据很简单（西瓜的体积和重量），但采集有十个特征的样本数据就不容易了（西瓜的体积、重量、含水量、密度、甜度、表面积······），而采集五十个甚至一百个特征的样本数据就更难了，即便能做到，成本也会高的惊人。因此高维样本的数的分布，稀疏才是常态，这在机器学习中称作“维数灾难”。另外高维样本的距离计算起来也不容易。
Q：若出现上述情况，可以怎么解决？
一个重要的解决方法是降维。顾名思义，把维度降低，就是讲原始的高维空间中样本映射到低维空间中，同时保持一些对于学习任务来说很重要的信息不丢失。
举个例子，假如我们要训练自己的对于跑车外形的鉴别能力。我们当然不可能把车行里全部三维的样本（真正的实物跑车）弄回家处理，因此我们可以选择降维，把车辆信息从三维空间映射二维空间——给所有跑车拍照，把照片带回家处理。虽说拍照会损失很多车辆的信息，比如车内配置，但对于我们的学习任务：训练自己的对于跑车外形的鉴别能力来说，最重要的信息，车辆外形信息得到了很好的保持。这就是典型的降维。当然这个例子中降维的主要动机不是由于样本稀疏分布，而是由于我们没钱把完整的三维样本带回家而已。
Q：机器学习中对样本数据的降维方法有哪些？
- 维度缩放（MDS）：保持降维后各个样本间的距离不变。
- 主成分分析（PCA）：保持降维后各个样本间的线性关系。
- 核化线性降维：保持高维空间中样本分布的部分结构信息。
- 流型学习：借鉴了拓扑学流型概念（好吧，我也不知道什么东西）的降维方法。
- 度量学习：直接学习出最优的降维后样本间距离。这个涉及的数学知识有点深，看不懂。
Q：什么是 维度缩放（MDS）？
想象左边的三维空间中，样本点全部落在一张弯曲的纸上，而右边的二维空间则是将左边的弯曲的纸拉直了，然后所有点都变成了落在一个平面上。在这个变化过程中，所有点之间的距离是保持不变的。如果左边有两个点：（0,0,0）和（1,1,1），距离为根号3，那么变换后这两个点之间的距离应该也为根号3，比如（0,0）和（1，）。
那么具体算法应该如何？假设D是原样本数据集，里面的每个元素是，Z是降维后的样本数据集，里面每个元素是
。
是原样本集中
和
的距离，也是降维后样本集中
和
的距离。我们可以通过距离
这点，通过降维后矩阵的内积矩阵B来间接确定降维后的矩阵。
嗯，下面是一波数学公式。
这轮计算要求解降维后矩阵Z的内积矩阵B！
这轮计算要求解降维后矩阵Z的内积矩阵B！
这轮计算要求解降维后矩阵Z的内积矩阵B！
首先是dist的计算公式
将dist计算公式两边平方后，用完全平方公式展开，注意看是什么东西，这个
是我们这轮计算要求解的量。
为求解，需要先求解和，那么这两个又怎么求？
先做一些简化，比如数据中心化，也就是说每个样本都减去样本总体的平均值，这样处理后所有样本的加起来等于0。下面公式中矩阵的迹是指一个n×n矩阵A的主对角线（从左上方至右下方的对角线）上各个元素的总和。B是Z的内积矩阵，内积矩阵B的迹就是等于Z中各个列向量的范数的和，因此可以写成下面的形式。
然后为了方便最后计算，定义三个常量。
联立上面各式，求得$b_{ij}，也就是内积矩阵B的每个元素。
求得了内积矩阵B，如何反推出矩阵Z？这一部分我数学不好，不理解，书上直接给出：
由此，求得降维后的矩阵Z。整个过程就是用原矩阵D，求出各个样本和
的距离
，然后利用不变的
，以及Z的内积矩阵B，求解出降维后矩阵Z。也就是
Q：什么是主成分分析（PCA）？
PCA是一种利用了线性变换的降维方式。那么PCA使用的线性变换有什么要求呢，或者说要满足什么条件呢？
想象这种线性变换是把一个高维空间中的样本点投影到一个超平面上（相对低维空间，二维平面的高维推广），按照常识，我们当然希望投影后的点能够尽量分开而不要很密集地堆在一起。翻译成数学语言，就是希望投影后的样本点总体方差最大。这就是我们的优化目标，也就是PCA的线性变换所要满足的条件。
假设原始数据集为X，里面每个元素都是d维向量，变换后的数据集为Z，每个元素都是d’维向量
，使用矩阵W来对X做线性变换：
按照总体方差最大化的优化目标，可以写出下面式子（假设样本经过了中心化，使得均值为0）：
如何求解W？可以使用拉格朗日乗子法
只要把看成一个整体矩阵A（其实就是X的协方差矩阵），就不难看出这是一个求矩阵A的特征值和特征向量的问题，也就是说把A的特征值和特征向量全部求出来去最大的d'个特征值对应的特征向量，就可以构成W了。
得到W（变换矩阵）后，就可以对原样本X做线性变换降维了：
得到的Z就是降维后的样本集（矩阵）。
以上基于“最大可分性”的推导较为简单，容易理解；PCA还可以根据“最近重构性”推导，嫌麻烦，不看了。
"""
Principle Component Analysis
:file: pca.py
:author: Richy Zhu
:email: rickyzhu@foxmail.com
"""
import numpy as np
class MyPCA:
def __init__(self):
self.projector = None
def _covM(self, _X):
'''compute covariance matrix'''
M = np.zeros([_X.shape[1], _X.shape[1]])
for i in range(len(_X)):
col_vec = _X[i].reshape([-1,1]) # the i-th column vector
M += col_vec.T.dot(col_vec)
return M / len(_X)
def fit_transform(self, X, k):
'''
PCA for X using Karhunen-Loeve Transform. Return the top k components.
Parameters
----------
X: ndarray of shape (m, n)
sample data where row represent sample and column represent feature
k: int
how many components to return
Returns
-------
X_transformed
top k component of original data
'''
mean_vector = np.mean(X, axis=0)
Xp = X - mean_vector # non-zero vectors
X_cov = self._covM(Xp)
E, V = np.linalg.eig(X_cov) # eigenvectors and eigenvalues
self.projector = np.array([V.T[np.argsort(-E)[i]] for i in range(k)])
X_transformed = self.projector.dot(Xp.T).reshape(-1, k)
return X_transformed
测试代码如下
import numpy as np
from sklearn.decomposition import PCA
X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
mypca = MyPCA()
print('My k components:\n', mypca.fit_transform(X, 1))
pca = PCA(n_components=1)
print('Sk k components:\n', pca.fit_transform(X))
print('My total varience ', np.var(mypca.fit_transform(X, 1)))
print('Sk total varience ', np.var(pca.fit_transform(X)))
测试结果如下
My k components:
[[-1.41421356]
[-2.12132034]
[-3.53553391]
[ 1.41421356]
[ 2.12132034]
[ 3.53553391]]
Sk k components:
[[ 1.38340578]
[ 2.22189802]
[ 3.6053038 ]
[-1.38340578]
[-2.22189802]
[-3.6053038 ]]
My total varience 6.333333333333333
Sk total varience 6.616285933932036
Q：什么是核化线性降维？
假设我们对现实世界采样，得到了以下的样本总体
如果我们使用线性降维方式，比如最常用的PCA，降维后的数据集如下
从降维结果来看，线性降维丢失了原本样本的空间分布信息，有时候这没关系，但有时候我们希望保留一定的原样本的空间分布信息，那就不能简单的使用线性降维，而需要使用非线性降维，比如最常用的KPCA，核主成分分析，即引入核函数。
假设原始数据集为X，里面每个元素都是d维向量。既然X里的样本不适合做线性变换，我们可以先用一个非线性映射，将X里的样本映射成适合做线性变换的样本Z，每个元素都是向量
，然后······然后当然是使用PCA来降维后者干些别的事啦。
那么我们要怎么计算KPCA的变换矩阵W呢？
先来一波公式。
这波计算是的目标是计算变换矩阵W。
这波计算是的目标是计算变换矩阵W。
这波计算是的目标是计算变换矩阵W。
下面公式是把X非线性映射成Z后，计算PCA使用的变换矩阵W。
从上面(10.19）式可以得到变换矩阵W的表达式
至于使用哪种非线性变换，可以先用Φ来表示。
那么（10.19）和（10.20）式就可以写成下面的形式
引入核函数
联立上面三式可以得到
由此我们可以用特征值与特征向量的处理方法解出矩阵A。
至此为止我们还没有算出变换矩阵W！
至此为止我们还没有算出变换矩阵W！
至此为止我们还没有算出变换矩阵W！
但我们算出了矩阵A，而A与W有着莫大的联系
因此可以利用矩阵A代替变换矩阵W的作用，求解出降维后的样本：
必须说一句，我个人觉得这里的符号使用不太合理，之前把
非线性映射后，用了
来表示，后面求解
来表示，这很容易造成混淆。
Q：什么是流型学习？
流行学习借鉴了拓扑学流型概念，可以用于保持一定的样本分布空间结构信息。
对于上面的例子，我们能否直接用MDS对原始样本集降维？不合适。因为MDS用到距离计算一般是两点间的直线距离（无论是欧式距离还是闵可夫斯基距离）。但是我们可以专门为其分布情况具有一定拓扑结构的样本，比如流型等，定制一种距离。流型中使用的距离就是测地线，以及两点间不穿过曲面的最短路程，可以想象一只蚂蚁从一点爬到另一点的路程。
测地线怎么算？还是要用到化曲为直的思想，从起点开始往终点的方向，基于欧氏距离挑选出临近的点，然后挑选出临近点的临近点，以此类推，知道把终点囊括在内，构成一个包含起点和终点的无向图，然后使用图的最短路径算法求出起点到终点的最短路径，以此近似作为两点间的测地线。
算出测地线后以此作为空间中两点间的距离，然后就可以使用MDS算法了。这套思路总结起来称为 Isomap算法。
LLE算法不作说明。
更多代码请参考https://github.com/qige96/programming-practice/tree/master/machine-learning
本作品首发于简书 和 博客园平台，采用知识共享署名 4.0 国际许可协议进行许可。
