流行学习一LLE_机器学习

前言：

流行学习主要用于聚类，分类和回归算法,例如人脸识别（旋转不变性，光照不变性）

流行是几何中一个概念，它是高维空间中的几何结构，即高维空间中点构成的集合。

简单的理解为二维空间的曲线，三维空间的曲面

假设有一个N维空间的流行M，流行学习降维要实现如下映射

$M \in R^N$ , 映射到（k<N) $M \in R^k$

早期想把LLE,LE,LPP,ISOmap, MDS 写在一篇，后来实现的时候发现篇幅过大，就分开来写了。

应用
算法思想
算法推导
算法流程
算法实现

一 LLE 应用

LLE（Locally Linear Embedding) 将高维数据投影到低维空间中，并保持局部线性关系。

应用于人脸图像，手写数字图像，自然语言处理。

二算法思想

高维空间的样本点xi,可由近邻的样本点线性重构出来，如上图

$x_i = W_{ij}x_j+W_{ik}x_k+W_{il}x_l$

$x_i$ ：为行向量，是样本

$W_{i}=[W_{ij},W_{ik},W_{il}]^T$ ：为列向量

上面式子也可以改为矩阵形式：

$x_i = W_i^T[x_j,x_k,x_l]^T$

LLE算法希望在低维空间中保持如此的线性重构关系

三原理推导：

预置条件：

$Q_j$ : $x_i$ 的k个近邻下标集合

$W_i$ : 重构系数,为列向量 , $\sum_{Q} W_{ij}=1$ ,为k行1列的向量

$C_i=(x_i-x_j)(x_i-x_j)^T$ , $j \in Q_i$ ,k*k的矩阵

$X_i$ : 为行向量，代表样本

k: $Q_j$ 的长度

$W_{i}^{T}1_{k}^{T}=1$

$1_k^T=[1,1...,1]^T$

3.1 定义高维空间的损失函数：

$J(W)=\sum_{i=1}^{m}||x_i -\sum_{Q}W_{ij}x_j||_2^2$

$=\sum_{i=1}^{m}||\sum W_{ij}x_i- \sum W_{ij}x_j||_2^2$

$=\sum_{i=1}^{m}|| \sum_{j \in Q}W_{ij}(x_i-x_j)||_2^2$

$=\sum W_i^T(x_i-x_j)(x_i-x_j)^TW_i$

根据预置条件：

$J(W)=\sum_{k=1}^{K}w_{i}^TZ_iw_i$

因为有约束，作拉格朗日对偶求极值

$L(W)=\sum W_i^Tz_iW_i +\lambda(W_i^T1_K-1)$ , 其中 $1_k$ ,为k行1列的矩阵

求偏导数:

$2Z_iW_i+\lambda1_k=0$

$W_i=\frac{-\lambda}{2}Z_{i}^{-1}1_{K}$

设 $\lambda=\frac{-\lambda}{2}$

$W_i=\lambda Z_{i}^{-1}1_{k}$ ..........................式1

根据约束条件 $W_i^T*1_k=1$ , 对上式进行归一化，求出 $\lambda$

$1_k^T \lambda Z_i^{-1}1_k=1$

求出 $\lambda$ , 带入式1 可以得到高维重构系数

3.2 映射到d维

低维度空间映射模型

$min_{y_i} \sum_{i=1}^{m}||y_i -\sum_{j=1}^{m}w_{ij}y_j||^2$

$st :\bigl(\begin{smallmatrix} \sum_{i=1}^{m}y_i=0\\ \sum y_i *y_i^T = m I_{d*d} \end{smallmatrix}\bigr)$

$Y=[y_1, y_2,...y_m]$ ,

$J(Y)=\sum_{i=1}^{m}||y_i -\sum w_{ij}y_j||^2$

其中 : $y_i = YI_i$

$I =\begin{bmatrix} 1 & 0 & ...&0 \\ 0 & 1.& ...&0\\ ... & ...& ...\\ 0 & 0& ... &1 \end{bmatrix}$

$I_i$ 代表取对应的列，例如

$I_2= \begin{bmatrix} 0\\1 \\..\\0 \end{bmatrix}$

$\sum W_ij y_j = YW_i$

W：是 $[w_1, w_2,..,w_m]$ 低维度的稀疏矩阵，每一列代表一个xi的邻值权值分布情况 Wi 代表取对应的列

则：

$J(Y)=min_{y_i}\sum ||YI_i -YW_i||^2$

$= min tr(Y(I-W)(I-W)^TY^T)$

令 $M = (I-W)(I-W)^T$

$J(Y)=min_{y_i} tr(YMY^T)$

加上约束条件，拉格朗日对偶变换后，求极小值

$L= tr(YMY^T +\lambda(YY^T-mI))$

求偏导数

$2MY^T+2\lambda Y^T=0$

可以看出来Y就是特征向量。

注意：

1：跟PCA 降维相反，这里特征值要去从小到大的排序对应的d个特征向量

2：零特征值对应的特征向量为e，所以要去非零特征值对应的特征向量

证明：

e：代表1列全为1的列矩阵

$Me = \lambda e$

左式：

$(I-W)(I-W)^Te = (I-W)(Ie -W^Te)$

$=(I-W)(e-W^Te)=0$

因为e 非0，所以特征向量为0的特征值对应特征向量为e

其中

$W^Te = [\sum w_1 , \sum w_2, ..,\sum w_m]^T =e$

四：算法主要流程：

1：计算每个样本的k个最临近

2：计算对应Wi

3: 重构低维度稀疏矩阵W

4: 计算低维度矩阵M：

5: 获取M矩阵对应的特征值，特征值向量

排序后，选择最大的d个非零特征值对应的特征向量

注意事项：

1：计算Wi的时候，要计算可逆矩阵，这里面有不同的求法，一般都会遇到奇异矩阵。

不同的求法，误差也主要产生在这里面

2：非零特征值定义不同，也会导致不同的结果

3： k 的取值影响也很大

4：每次Wi重构后，可以计算一下重构的误差大小

五算法实现：

1：直接调用sklearn库函数方式：

LLE 后效果

Code:

# -*- coding: utf-8 -*-
"""
Created on Thu Oct 10 16:50:58 2019@author: chengxf2
"""from time import timeimport matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from matplotlib.ticker import NullFormatterfrom sklearn import manifold, datasets
import picklefile = "d:\\1.txt""""
保存的数据集格式
Argsdata: 训练样本color: 样本点对应的color
"""
class Data:def __init__(self, data, color):self.trainData = dataself.dataColor = color"""
绘制点
Args:Argsdata: 训练样本color: 样本点对应的color"""
def Draw(data, color):fig = plt.figure(figsize=(6, 5))ax = fig.add_subplot(111, projection='3d')ax.scatter(data[:, 0], data[:, 1], data[:, 2], c=color, cmap=plt.cm.hot)ax.view_init(10, -70)ax.set_xlabel("$x_1$", fontsize=18)ax.set_ylabel("$x_2$", fontsize=18)ax.set_zlabel("$x_3$", fontsize=18)plt.show()"""
从文件中读取数据
Argsfile: 文件路劲
returntrainData: 训练样本color: 样本点对应的color
"""
def LoadFile(file):f = open(file, 'rb')data = pickle.load(f)f.close()trainData = data.trainDatacolor = data.dataColorDraw(trainData, color)return trainData, color"""
保存文件
Argsfile: 文件名data: 样本color: 颜色
returnNone
"""
def SaveData(file, data ,color):DataInfo = Data(data,color)f = open("d:\\1.txt",'wb')pickle.dump(DataInfo, f,0)f.close()"""
生成保存流行数据
ArgsNone
return None
"""
def SWData():n_points = 500data, color = datasets.samples_generator.make_s_curve(n_points, random_state=0)Draw(data, color)SaveData(file, data,color)"""
局部线性嵌入降维
Argsdata: 数据集color: 颜色
"""def LLE(data,color):n_components = 2 ##降低后的维度n_neighbors = 15  ##邻近的个数t0 = time()  #计时开始lle =  manifold.LocallyLinearEmbedding(n_neighbors, n_components,max_iter=1)X_reduced =lle.fit_transform(data)print(" reconstruction_error:\t ", lle.reconstruction_error_)print(" \n lle.hessian_tol:\t ", lle.hessian_tol)print(" neighbors_algorithm:\t ", lle.method)#print(" embedding_:\t ", lle.embedding_)plt.title("Unrolled swiss roll using LLE", fontsize=14)print("x_reduced ",np.shape(X_reduced), "x_reduced[0",X_reduced[0:2])plt.scatter(X_reduced[:, 0], X_reduced[:, 1], c=color, cmap=plt.cm.hot)plt.xlabel("$z_1$", fontsize=18)plt.ylabel("$z_2$", fontsize=18)plt.grid(True)#save_fig("lle_unrolling_plot")plt.show()SWData()
data, color = LoadFile(file)
x =data.tolist()
LLE(x, color)

二自己实现方法：

# -*- coding: utf-8 -*-
"""
Created on Thu Oct 10 16:50:58 2019@author: chengxf2
"""
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import proj3d
from sklearn.datasets import make_swiss_roll
from sklearn.manifold import LocallyLinearEmbedding
import pickle
import copy"""
保存的数据集格式
Argsdata: 训练样本color: 样本点对应的color
"""
class Data:def __init__(self, data, color):self.trainData = dataself.dataColor = color"""
绘制点
Args:Argsdata: 训练样本color: 样本点对应的color"""
def Draw(data, color, D3):if True ==D3:fig = plt.figure(figsize=(6, 5))ax = fig.add_subplot(111, projection='3d')ax.scatter(data[:, 0], data[:, 1], data[:, 2], c=color, cmap=plt.cm.hot)ax.view_init(10, -70)ax.set_xlabel("$x_1$", fontsize=18)ax.set_ylabel("$x_2$", fontsize=18)ax.set_zlabel("$x_3$", fontsize=18)else:plt.title("Unrolled swiss roll using LLE", fontsize=14)plt.scatter(data[:, 0], data[:, 1], c=color, cmap=plt.cm.hot)plt.xlabel("$z_1$", fontsize=18)plt.ylabel("$z_2$", fontsize=18)plt.grid(True)#save_fig("lle_unrolling_plot")plt.show()"""
从文件中读取数据
Argsfile: 文件路劲
returntrainData: 训练样本color: 样本点对应的color
"""
def LoadFile(file):f = open(file, 'rb')data = pickle.load(f)f.close()trainData = data.trainDatacolor = data.dataColorDraw(trainData, color,True)print("shape ", np.shape(trainData))print("tp :",type(trainData))return trainData, color"""
获取k邻近点
Argsdata: 数据集x_i: 样本点i: 当前样本点indexk: 近邻点取值个数m: 样本个数
"""
def GetNk(data,x_i, i,k,m):#mXDict ={}for j in range(m):if i ==j:continuex_j = data[j]X = x_i-x_jdist = np.linalg.norm(X)XDict[j]=distjDict = sorted(XDict.items(), key=lambda d:d[1])jList =[item[0] for item in jDict]# print("\n i ",i, "\t  NearJ: ",jList[0:k])  return jList[0:k]"""
通过奇异分解求解逆矩阵
ArgsZi
"""
def SvdInv(Z):m,n = np.shape(Z)U,V,T = np.linalg.svd(Z)invV = np.zeros((n,n))#tol=1E-8  ##防止特征值为0alpha = 1e-3for i in range(n):if np.abs(V[i]<alpha):invV[i,i] = alphaelse:a=  V[i]invV[i,i] = 1.0/ainvZ = T.T*invV*U.Treturn invZdef GetLoss(xi, xj, wi):xiNew = wi.T*xja =xi-xiNewloss = np.linalg.norm(a)return loss"""
"""
def GetwL(wNear, wH,m,K):wL = np.zeros((m,m))for i in range(m):QJ = wNear[i] ##邻近矩阵的左边for j in QJ:##QJindex = QJ.index(j)# print("wi ",wH[i], "\t ",j)wij = wH[i][index]wL[j,i]=wij ##列矩阵return wL"""
低维线性嵌入
Argsdata: 数据集color: 标签k: 邻近点取的个数
"""
def LLE(data, color, k):#zero =6.113835700142957e-07zero = 3.5508457154521093e-07n_components = 2m,n = np.shape(data)onek = np.ones((k,1))wNear =[]wH=[]###step1 计算k 邻近####print("\n  step1 计算邻近:")for i in range(m):xi = data[i]# print("\n xi : ",xi)QJ =  GetNk(data, xi, i, k, m)wNear.append(QJ)##计算Zixj =[]for j in QJ:x_j = data[j]xj.append(x_j.tolist()[0])A = xi -xj  ##MatrixZi =A*A.T##10*10InvZ = SvdInv(Zi)a = InvZ*onekb = onek.T*awi = a/b#loss =  GetLoss(xi, xj, wi)wH.append(wi.T.tolist()[0])#print("\n i:  ",wi.T.tolist()[0])##求解低维度稀疏矩阵wL = GetwL(wNear, wH, m,k)  # print("\n 低维度稀疏矩阵: \n ",wL)I = np.mat(np.eye(m,m))matA = I-wL##计算Mprint("\n step3 : M 计算完毕")M = np.dot(matA,  matA.T)# for col in range(m):# print("\n  step2: 计算稀疏矩阵%d \n "%col,M[:,col])#print("\n sp M: ", np.shape(M), "\t tyep ", type(M))#print("\n 低维度稀疏矩阵: \n ",M)##求解特征值特征向量 a 特征值， b特征向量print("\n step4 : 计算特征值特征向量")a, b = np.linalg.eig(M)lista = list(a)Y =np.zeros((m,n_components))a1 = copy.deepcopy(a)a1.sort()print("m: ",m)print("shape Y:::::::::: ", np.shape(Y))col = 0for lamb in a1:  ##从小到大排序if np.abs(lamb)>zero and col<n_components:j = lista.index(lamb)Y[:,col]= b[:,j].reshape(1,m)col = col+1print("\n step5 : 取Y")return Y#reverse = True 降序 ， reverse = False 升序（默认）
def Test():matA = np.mat([[1,2],[2,2]])matB = np.mat([[1,2],[2,2]])a, b = np.linalg.eig(matA)#print("\n a: \n ",a)#print("\n b: \n ",b)for i in range(len(a)):lamb = a[i]x = b[:,i]y = lamb*xy1 = matA*xprint("\n ================\n")print("\n left  :\n ",y.T, "\n   right: \n",y1.T)def Train():file = "d:\\1.txt"data,color = LoadFile(file)dataMat = np.mat(data)Y= LLE(dataMat,color,15)data2 = np.array(Y)Draw(data2, color, False)#Test()
Train()

参考文档

https://www.cnblogs.com/pinard/p/6266408.html?utm_source=itdadao&utm_medium=referral

https://wenku.baidu.com/view/674e73ab647d27284a735143.html?from=search

https://www.cnblogs.com/jiangxinyang/p/9314256.html

https://blog.csdn.net/elma_tww/article/details/88143633