【降维】

P1->降维?why;降维的分类;几何角度分析数据稀疏性;

降维方法
降维方法分为线性和非线性降维，非线性降维又分为基于核函数和基于特征值的方法。
1、线性降维方法：PCA 、ICA LDA、LFA、LPP(LE的线性表示)
2、非线性降维方法：
（1）基于核函数的非线性降维方法：KPCA 、KICA、KDA
（2）基于特征值的非线性降维方法（流型学习）：ISOMAP、LLE、LE、LPP、LTSA、MVU
降维概念：通过单幅图像数据的高维化，将单幅图像转化为高维空间中的数据集合，对其进行非线性降维。寻求其高维数据流形本征结构的一维表示向量，将其作为图像数据的特征表达向量。
目的：若原特征空间是D维的,现希望降至D-1维的，用来进行特征选择和特征提取。
①特征选择：选择重要的特征子集，删除其余特征；
②特征提取：由原始特征形成的较少的新特征。
在特征提取中，我们要找到k个新的维度的集合，这些维度是原来k个维度的组合，这个方法可以是监督的，也可以是非监督的，如PCA是非监督的，LDA是监督的。
作用：
（1）降低时间的复杂度和空间复杂度
（2）节省了提取不必要特征的开销
（3）去掉数据集中夹杂的噪音
（4）较简单的模型在小数据集上有更强的鲁棒性
（5）当数据能有较少的特征进行解释，我们可以更好地解释数据，是的我们可以提取知识
（6）实现数据的可视化
运用：通过单幅图像数据的高维化,将单幅图像转化为高维空间中的数据集合,对其进行非线性降维,寻求其高维数据流形本征结构的一维表示向量,将其作为图像数据的特征表达向量。从而将高维图像识别问题转化为特征表达向量的识别问题,大大降低了计算的复杂程度,减少了冗余信息所造成的识别误差,提高了识别的精度。通过指纹图像的实例说明,将非线性降维方法(如Laplacian Eigenmap方法)应用于图像数据识别问题,在实际中是可行的,在计算上是简单的,可大大改善常用方法(如K-近邻方法)的效能,获得更好的识别效果。此外,该方法对于图像数据是否配准是不敏感的,可对不同大小的图像进行识别,这大大简化了识别的过程。
子集选择:对于n个属性，有2n个可能的子集。穷举搜索找出属性的最佳子集可能是不现实的，特别是当n和数据类的数目增加时。通常使用压缩搜索空间的启发式算法，通常这些方法是典型的贪心算法，在搜索属性空间时，总是做看上去是最佳的选择。他们的策略是局部最优选择，期望由此导致全局最优解。在实践中，这种贪心方法是有效的，并可以逼近最优解。
子集选择的缺点：
案例：假设对一张100*100像素的图片做人脸识别，每个像素是一个特征，那么会有10000个特征，而对应的类别标签y仅仅是0/1值，1代表是人脸。这么多特征不仅训练复杂，而且不必要特征对结果会带来不可预知的影响，但我们想得到降维后的一些最佳特征（与y关系最密切的）。
主要思想：将一个高维空间中的数据投影到一个较低维的空间中，且投影后要保证各个类别的类内方差小而类间均值差别大，这意味着同一类的高维数据投影到低维空间后相同类别的聚在一起，而不同类别之间相距较远。
假设有一个D维的边长a=1的超正方体，里面有一个D维的半径为0.5的超球体。则

V超正方体=1
V超球体=K0.5^D当D—>+∞时，
出现一个惊人的发现，当D的值足够大，发现中间的超球体的竟然趋近于零。

这样扩展到数据来说，随着数据维度的增大，数据的量也会相对稀疏的多。这就是维度灾难。实际上在许多领域的研究与应用中，为了反映事物的多个变量对结果的影响，需要进行大量数据收集以便进行分析寻找规律。多变量、大样本虽然会为研究和应用提供了丰富的信息，但也遇到了以下问题：
1.一定程度上增加了数据采集的工作量
2.更重要的是在多数情况下，许多变量之间可能存在相关性，从而增加了问题分析的复杂性，同时对分析带来不便。
3.如果分别对每个指标进行分析，分析往往是孤立的，而不是综合的。盲目减少指标会损失很多信息，容易产生错误的结论。
因此需要找到一个合理的方法，在减少需要分析的指标同时，尽量减少原指标包含信息的损失，以达到对所收集数据进行全面分析的目的，由于各变量间存在一定的相关关系，因此有可能用较少的综合指标分别综合存在于各变量中的各类信息。主成分分析就属于这类降维的方法。

P2->预备知识;

数据data特征矩阵表示；样本均值(Sample Mean)；样本协方差(Sample Covariance)；H为中心矩阵(centering matrix)，中心矩阵将X每一维都减去均值，实现归一化。
p3->经典PCA
一个中心：原始特征空间的重构，线性相关特征–>线性无关特征（主成分），
两个基本点：
最大投影方差：样本点投影到某方向上分布尽量分散（投影方差最大），该方向就是主成分。
最小重构距离：样本点投影后重构回去所花的代价要最小，投影分布越分散（投影方差最大），则重构所需的代价越小。所以，这两个方法其实是等价的。
最大投影方差：找到一个方向，使得数据在这些投影方向上的方差最大。计算原始数据在这些正交基上投影的方差，方差越大，就说明在对应正交基上包含了更多的信息量。这个方向就是主成分。
方法：（把n维的降维成k维）

1.去掉均值
2.计算协方差矩阵的特征值和特征向量；特征值代表重要程度。
3.保留最大的k个特征值对应的特征向量
4.把数据转化到上述特征向量构建的新空间

def pca(dataMat, topNfeat=999999):
    meanVals = mean(dataMat)
    meanRemoved = dataMat - meanVals #去均值
    covMat = cov(meanRemoved, rowvar=0) #协方差矩阵
    eigVals,eigVects = linalg.eig(mat(covMat))
    # numpy内建函数，一次性求出特征值和特征向量
    eigValInd = argsort(eigVals)
    eigValInd = eigValInd[:-(topNfeat+1):-1]
    redEigVects = eigVects[:,eigValInd]
    # 对特征值从小到大排序
    lowDDataMat = meanRemoved * redEigVects
    # 将数据集投影到新的空间，结果是一个低维数据
    reconMat = (lowDDataMat * redEigVects.T) + meanVals
    return lowDDataMat, reconMat

P4->最小重构距离角度

最大投影方差基本点如P4，将样本投影到u1和u2上的距离D1>D2，则u1这个特征相对于u2来说就是主成分。最大投影方向就是主成分。首先要对数据进行中心化处理，为什么要进行中心化处理呢？因为主成分变换对正交向量的尺度敏感。数据在变换前需要进行归一化处理。然后计算投影方差，接着可以将上一步的待求内容转化为最优化问题吹，最后通过拉格朗日函数，将约束项放到最优化问题中，通过极大似然求得最优解。
最小重构距离：在P4中，如果把样本点投影到u1和u2后，再将样本点还原原来的数据，这样的代价，显然u1比u2小的多。（因为u1相对稀疏比较好还原，u2甚至有些点都已经重合了，不容易还原）
有了上面最小重构代价的思想，接下来直接可以给出运算过程，如P4所示。

P5->SVD角度
去主成分的方法实现是太麻烦了，有没有更简单的方法呢？答案是肯定的，那就是奇异值分解SVD！
首先得知道特征值和特征向量。Sx=λx,其中S是一个n×n的实对称矩阵，x是一个n维向量，则我们说λ是矩阵S的一个特征值，而x是矩阵S的特征值λ所对应的特征向量。
求出特征值和特征向量有什么好处呢？就是我们可以将矩阵A特征分解。如果我们求出了矩阵A的n个特征值λ1≤λ2≤…≤λn,以及这n个特征值所对应的特征向量{w1,w2,…wn}，，如果这n个特征向量线性无关，那么矩阵S就可以特征分解,其中G是这n个特征向量所张成的n×n维矩阵，而Σ为这n个特征值为主对角线的n×n维矩阵。注意到要进行特征分解，矩阵S必须为方阵。那么如果S不是方阵，即行和列不相同时，我们还可以对矩阵进行分解吗？答案是可以，此时就要用到奇异值分解SVD。
SVD也是对矩阵进行分解，但是和特征分解不同，SVD并不要求要分解的矩阵为方阵。假设矩阵S是一个m×n的矩阵，那么定义矩阵S的SVD为Hx,其中U是一个m×m的列正交矩阵；Σ是一个m×n的对角矩阵，除了主对角线上的元素以外全为0，主对角线上的每个元素都称为奇异值；V是一个n×n的正交矩阵。U和V都是酉矩阵，即满足：UTU=I,VTV=I。
这样可以求出每个奇异值，进而求出奇异值矩阵Σ。

P6->主成分分析(PCA)
主成分分析(PCA)
将样本投影到某一维上，新的坐标的选择方式：找到第一个坐标，数据集在该坐标的方差最大（方差最大也就是我们在这个数据维度上能更好地区分不同类型的数据），然后找到第二个坐标，该坐标与原来的坐标正交。该过程会一直的重复，直到新坐标的数目和原来的特征个数相同，这时候我们会发现数据的大部分方差都在前面几个坐标上表示，这些新的维度就是我们所说的主成分。
（1）PCA的基本思想：寻找数据的主轴方向，由主轴构成一个新的坐标系，这里的维数可以比原维数低，然后数据由原坐标系向新坐标系投影，这个投影的过程就是降维的过程。
（2）PCA算法的过程
①将原始数据中的每一个样本都用向量表示，把所有样本组合起来构成样本矩阵，通常对样本矩阵进行中心化处理，得到中心化样本矩阵。
②求中心化后的样本矩阵的协方差；
③求协方差矩阵的特征值和特征向量；
④将求出的特征值按从大到小的顺序排列，并将其对应的特征向量按照此顺序组合成一个映射矩阵，根据指定的PCA保留的特征个数取出映射矩阵的前n行或者前n列作为最终的映射矩阵；
⑤用映射矩阵对数据进行映射，达到数据降维的目的。
（3）PCA实例中的小插曲：TF-IDF
TF-IDF：term freuency-inverse document frequency,它是一种用于信息检索与文本挖掘的常用加权技术，是一种统计方法，用以评估一字词对于一个文本集或一个语料库中其中一份文件的重要程度。包括两部分，词频和逆向文件频率。
（4）协方差矩阵的对角上是方差，非对角线上是协方差。协方差是衡量两个变量同时变化的变化程度。协方差大于0表示x和y中若一个增，另一个也增；小于0表示一个增一个减。
（5）PCA推导—最大方差理论
在信号处理中认为信号具有较大的方差，噪音具有较小的方差，信噪比越大越好。PCA遵循投影后的样本点间方差最大原则。

线性分类

线性分类

线性分类
LDA（Linear discriminant analysis)
线性判别式分析，也叫fisher线性判别，是模式识别中的经典算法。
是一种监督学习的降维技术，它的数据集的每个样本是有类别输出的。
思想：投影后类内距离最小，类间距离最大。
1、线性判别：将高维的模式样本投影到最佳鉴别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，这是一种有效的特征提取方法，使用这个方法，能使得投影后模式样本的类间散布矩阵最大，且同时类内散布矩阵最小。
2、与PCA相比较：
（1）共同点：①都属于线性方法；
②在降维时都采用矩阵分解的方法；
③都假设数据符合高斯分布；
（2）不同点：
①LDA是有监督的；
②不能保证投影到的坐标系是正交的（根据类别的标注，关注分类能力）；
③降维直接与类别的个数有关，与数据本身的维度无关（原始数据是n维的，有c个类别，降维后一般是到c-1维）
④可以用于降维，还可用于分类；
⑤选择分类性能最好的投影方向。
LLE
1、属于流形学习的一种，和传统的PCA、LDA相比，不再是关注样本方差的降维方法，而是一种关注降维时保持样本局部的线性特征。
LLE是将高维流形分成很多小块，每一小块可以用平面代替，然后再在低维中重新拼合起来，且要求保留各点之间的拓扑关系不变。
2、LLE思想：
首先假设数据在较小的局部是线性的，即某一个数据能够用它邻域中的几个样本来线性表示，可以通过k-近邻的思想来找到它的近邻点。在降维之后，希望样本点对应的投影尽量保持同样的线性关系。即投影前后线性关系的权重参数不变或者改变很小。
3、LLE算法推导：
（1）首先确定邻域大小的选择;
（2）需要找到某个样本Xi和这k个最近邻之间的线性关系（找线性关系是一个回归问题）;
（3）由该样本点的局部重建权值矩阵和其近邻点计算出该样本点的输出值;
（4）定义一个误差函数;
ISOMAP（等距特征映射）
1、以线性流形学习方法MDS为理论基础，将经典MDS方法中的欧式距离替换为
*tSNE *
TSNE是由SNE衍生出的一张算法，SNE最早出现在2002年，改变了MDN和ISOMAP中基于距离不变的思想，将高维映射到低维的同时，尽量保证相互之间的分布概率不变，SNE将高维和低维中的样本分布都看作高斯分布，而TSNE将低维中的坐标当作T分布，这样的好处是为了让距离大的簇之间距离拉大，从而解决了拥挤问题。

PCA的Python实现

选用Python内置的iris数据集，通过PCA降维，对数据分类：

from __future__ import print_function
from sklearn import datasets
import matplotlib.pyplot as plt
from pylab import *
plt.rcParams['font.sans-serif']=['SimHei']
plt.rcParams['axes.unicode_minus']=False
import numpy as np

def shuffle_data(X, y, seed=None):
    if seed:
        np.random.seed(seed)
    idx = np.arange(X.shape[0])
    np.random.shuffle(idx)
    return X[idx], y[idx]

# 正规化数据集 X
def normalize(X, axis=-1, p=2):
    lp_norm = np.atleast_1d(np.linalg.norm(X, p, axis))
    lp_norm[lp_norm == 0] = 1
    return X / np.expand_dims(lp_norm, axis)

# 标准化数据集 X
def standardize(X):
    X_std = np.zeros(X.shape)
    mean = X.mean(axis=0)
    std = X.std(axis=0)
    # 做除法运算排除分母不能等于0的情形
    for col in range(np.shape(X)[1]):
        if std[col]:
            X_std[:, col] = (X_std[:, col] - mean[col]) / std[col]
    return X_std

# 划分数据集为训练集和测试集
def train_test_split(X, y, test_size=0.2, shuffle=True, seed=None):
    if shuffle:
        X, y = shuffle_data(X, y, seed)

    n_train_samples = int(X.shape[0] * (1-test_size))
    x_train, x_test = X[:n_train_samples], X[n_train_samples:]
    y_train, y_test = y[:n_train_samples], y[n_train_samples:]
    return x_train, x_test, y_train, y_test

# 计算矩阵X的协方差矩阵
def calculate_covariance_matrix(X, Y=np.empty((0,0))):
    if not Y.any():
        Y = X
    n_samples = np.shape(X)[0]
    covariance_matrix = (1 / (n_samples-1)) * (X - X.mean(axis=0)).T.dot(Y - Y.mean(axis=0))
    return np.array(covariance_matrix, dtype=float)

# 计算数据集X每列的方差
def calculate_variance(X):
    n_samples = np.shape(X)[0]
    variance = (1 / n_samples) * np.diag((X - X.mean(axis=0)).T.dot(X - X.mean(axis=0)))
    return variance

# 计算数据集X每列的标准差
def calculate_std_dev(X):
    std_dev = np.sqrt(calculate_variance(X))
    return std_dev

# 计算相关系数矩阵
def calculate_correlation_matrix(X, Y=np.empty([0])):
    # 先计算协方差矩阵
    covariance_matrix = calculate_covariance_matrix(X, Y)
    # 计算X, Y的标准差
    std_dev_X = np.expand_dims(calculate_std_dev(X), 1)
    std_dev_y = np.expand_dims(calculate_std_dev(Y), 1)
    correlation_matrix = np.divide(covariance_matrix, std_dev_X.dot(std_dev_y.T))

    return np.array(correlation_matrix, dtype=float)

class PCA():
    """
    主成份分析算法PCA，非监督学习算法.
    """
    def __init__(self):
        self.eigen_values = None
        self.eigen_vectors = None
        self.k = 2

    def transform(self, X):
        """ 
        将原始数据集X通过PCA进行降维
        """
        covariance = calculate_covariance_matrix(X)

        # 求解特征值和特征向量
        self.eigen_values, self.eigen_vectors = np.linalg.eig(covariance)

        # 将特征值从大到小进行排序，注意特征向量是按列排的，即self.eigen_vectors第k列是self.eigen_values中第k个特征值对应的特征向量
        idx = self.eigen_values.argsort()[::-1]
        eigenvalues = self.eigen_values[idx][:self.k]
        eigenvectors = self.eigen_vectors[:, idx][:, :self.k]

        # 将原始数据集X映射到低维空间
        X_transformed = X.dot(eigenvectors)

        return X_transformed

if __name__ == "__main__":
    #使用燕尾花数据集
    data = datasets.load_iris()
    X = data.data
    y = data.target

    # 将数据集X映射到低维空间
    X_trans = PCA().transform(X)

    x1 = X_trans[:, 0]
    x2 = X_trans[:, 1]

    cmap = plt.get_cmap('viridis')
    colors = [cmap(i) for i in np.linspace(0, 1, len(np.unique(y)))]

    class_distr = []
    # 展示不同类别数据的分布
    for i, l in enumerate(np.unique(y)):
        _x1 = x1[y == l]
        _x2 = x2[y == l]
        _y = y[y == l]
        class_distr.append(plt.scatter(_x1, _x2, color=colors[i]))

    # Add a legend
    plt.legend(class_distr, y, loc=1)

    # Axis labels
    plt.xlabel('主成分1')
    plt.ylabel('主成分2')
    plt.show()

PCA优缺点并存：

优点：

1.它是无监督学习，完全无参数限制的。在PCA的计算过程中完全不需要人为的设定参数或是根据任何经验模型对计算进行干预，最后的结果只与数据相关，与用户是独立的。
2.用PCA技术可以对数据进行降维，同时对新求出的“主元”向量的重要性进行排序，根据需要取前面最重要的部分，将后面的维数省去，可以达到降维从而简化模型或是对数据进行压缩的效果。同时最大程度的保持了原有数据的信息。
3.各主成分之间正交，可消除原始数据成分间的相互影响。
4.计算方法简单，易于在计算机上实现。

缺点：

1.如果用户对观测对象有一定的先验知识，掌握了数据的一些特征，却无法通过参数化等方法对处理过程进行干预，可能会得不到预期的效果，效率也不高。
2.贡献率小的主成分往往可能含有对样本差异的重要信息。
3.特征值矩阵的正交向量空间是否唯一有待讨论。
4.在非高斯分布的情况下，PCA方法得出的主元可能并不是最优的，此时在寻找主元时不能将方差作为衡量重要性的标准。

总结

首先通过几何概念引出维度爆炸带来的问题，接下来通过PCA数据降维来解决之。在讲PCA内容时主要介绍了：经典主成分分析、最大投影方差、最小重构距离，SVD奇异值分解。最后通过Python实现PCA。

MachineLearning05

2020-03-27

MachineLearning05

【降维】

P1->降维?why;降维的分类;几何角度分析数据稀疏性;

P2->预备知识;

p3->经典PCA

P4->最小重构距离角度

P5->SVD角度

P6->主成分分析(PCA)

PCA的Python实现

PCA优缺点并存：

总结

MachineLearning05

【降维】

P1->降维?why;降维的分类;几何角度分析数据稀疏性;

P2->预备知识;

p3->经典PCA

P4->最小重构距离角度

P5->SVD角度

P6->主成分分析(PCA)

PCA的Python实现

PCA优缺点并存：

总结

Thanks~