《机器学习-Python实战（微课版）》课件 第十一章 降维技术与关联规则挖掘

第十一章：降维与关联规则学习目标通过本章的学习：掌握降维的基本思想掌握主成分分析（PCA）的步骤。掌握关联规则算法的基本原理和挖掘过程。

1.降维技术2.

PCA降维技术的原理与实现3.LDA降维技术的原理与实现4.关联规则挖掘算法的基本原理5.关联规则挖掘应用算法降维技术背景（1）维数灾难背景现实应用中属性维度成千上万，在高维度情况下会带来很多麻烦，而且当维度大的时候，数据样本一般分布的非常稀疏，这是所有学习算法要面对的问题，降维技术应运而生。数据降维降维是对事物的特征进行压缩和筛选，该项任务相对比较抽象。如果没有特定领域知识，无法预先决定采用哪些数据，比如在人脸识别任务中，如果直接使用图像的原始像素信息，数据的维度会非常高，通常会利用降维技术对图像进行处理，保留下最具有区分度的像素组合。降维技术背景（2）对数据降维还有如下原因：（1）使得数据集更易使用（2）降低算法的计算开销（3）去除噪声（4）使得结果容易理解降维技术-

主成分分析（1）主成分分析（PCA）

在PCA中，数据从原来的坐标系转换到新的坐标系，由数据本身决定。转换坐标系时，以方差最大的方向作为坐标轴方向，因为数据的最大方差给出了数据的最重要的信息。第一个新坐标轴选择的是原始数据中方差最大的方法，第二个新坐标轴选择的是与第一个新坐标轴正交且方差次大的方向。重复该过程，重复次数为原始数据的特征维数。大部分方差都包含在最前面的几个新坐标轴中，因此，可以忽略余下的坐标轴，即对数据进行了降维处理。降维技术

-

线性判别式分析（2）线性判别式分析（LDA）

线性判别式分析是将高维的模式样本投影到最佳判别矢量空间，以达到抽取分类信息和压缩特征空间维数的效果，投影后保证模式样本在新的子空间有最大的类间距离和最小的类内距离，即模式在该空间中有最佳的可分离性，可以达到对数据进行的降维处理。降维方法总体理解(1)样本数据集的理解将数据集考虑成矩阵，每行对应一个样本，每列对应一个特征或者维度。在降维方法中，都是把数据集看作矩阵形式，数学上有非常多关于矩阵的处理技巧和定理，降维的方法证明均源于此。降维方法总体理解(2)机器学习领域中所谓的降维就是指采用某种映射方法，将原高维空间中的数据点映射到低维度的空间。降维的本质是学习一个映射函数f:x->y，其中x是原始数据点的表达，目前最多使用向量表达形式。y是数据点映射后的低维向量表达，通常y的维度小于x的维度（当然也可以提高维度）。映射函数f可能是显式的或隐式的、线性的或非线性的。在很多算法中，降维算法成为了数据预处理的一部分。一些算法如果没有降维预处理，就很难得到很好的效果。1.降维技术2.PCA降维技术的原理与实现3.LDA降维技术的原理与实现4.关联规则挖掘算法的基本原理5.关联规则挖掘应用算法PCA降维技术(1)PCA（PrincipalComponentAnalysis，主成分分析）在高维向量空间中，随着维度的增加，数据呈现出越来越稀疏的分布特点，增加后续算法的复杂度，而很多时候虽然数据维度较高，但是很多维度之间存在相关性，他们表达的信息有重叠。PCA的思想是将n维特征映射到k维上(k<n)，这k维是全新的正交特征。这k维特征称为主成分，是重新构造出来的k维特征，而不是简单地从n维特征中去除其余n-k维特征（这也是与特征选择特征子集的方法的区别）。PCA降维技术(2)PCA的目的是在高维数据中找到最大方差的方向，接着映射它到比最初维数小或相等的新的子空间。PCA降维技术的原理（1）PCA应用本身是基于一定假设的：1.线性即特征的变换是线性变换，作用有限，目前也有非线性的特征变换kernelPCA。2.处理的数据分布式服从指数族概率密度函数，即能通过均值和协方差来表征数据的分布，因为只有在这个情况下信噪比和协方差矩阵才能表示噪声和数据冗余。（好在实际应用中常见的数据是服从高斯分布或近似高斯分布）。PCA降维技术的原理（2）主成分分析（PCA）的基本原理

在一组多变量的数据中，很多变量常常是一起变动的。一个原因是很多变量是同一个驱动影响的的结果。在很多系统中，只有少数几个这样的驱动，但是多余的仪器使我们测量了很多的系统变量。当这种情况发生的时候，你需要处理的就是冗余的信息。而你可以通过用一个简单的新变量代替这组变量来简化此问题。PCA降维技术的原理（3）

第一主成分是数据空间的一个轴。当你把各观察值投影到这个轴时，结果会形成一个新变量，这个变量的方差是所有可选的轴中最大的。第二主成分是空间的另一个轴，它垂直于第一个轴。投影数据到这个轴上将得到另一组变量，此变量的方差是所有可选的轴中最大的。PCA降维技术的原理（4）特征向量（eigenvector）是一个矩阵的满足如下公式的非零向量：

特征向量和特征值只能由方阵得出，且并非所有方阵都有特征向量和特征值。如果一个矩阵有特征向量和特征值，那么它的每个维度都有一对特征向量和特征值。矩阵的主成分是其协方差矩阵的特征向量，按照对应的特征值大小排序。PCA降维技术的原理（5）

最大的特征值就是第一主成分，第二大的特征值就是第二主成分，以此类推。把数据映射到主成分上，第一主成分是最大特征值对应的特征向量，因此我们要建一个转换矩阵，它的每一列都是主成分的特征向量。如果我们要把5维数据降成3维，那么我们就要用一个3维矩阵做转换矩阵，用特征向量中的前三个主成分作为转换矩阵。若把我们的2维数据映射成1维，那么我们就要用一个1维矩阵做转换矩阵，用特征向量中的第一主成分作为转换矩阵。最后，我们用数据矩阵右乘转换矩阵。PCA算法流程输入：n维特征的样本数据集𝑫输出：降到p维后的样本集𝑫’对所有样本构成的矩阵X进行去中心化；求出X的协方差矩阵C；利用特征值分解，求出协方差矩阵C的特征值及对应的特征向量；将特征向量按对应特征值大小从上到下按行排列成矩阵，根据实际业务场景，取前p列组成新的坐标矩阵W。令原始数据集与新坐标举证W相乘，得到的新的数据集（矩阵）即为降到p维后的坐标。PCA优缺点优点：以方差衡量信息的无监督学习，不受样本标签限制。各主成分之间正交，可消除原始数据成分间的相互影响。计算方法简单，主要运算是奇异值分解，易于在计算机上实现。可减少指标选择的工作量。缺点：主成分解释其含义往往具有一定的模糊性，不如原始样本特征的解释性强。方差小的非主成分也可能含有对样本差异的重要信息，因降维丢弃可能对后续数据处理有影响。PCA降维的Python实现

#Python实现PCAimportnumpyasnpdefpca(X,k):#kisthecomponentsyouwant#每个特征的平均值n_samples,n_features=X.shapemean=np.array([np.mean(X[:,i])foriinrange(n_features)])#规范化norm_X=X-mean#散射矩阵scatter_matrix=np.dot(np.transpose(norm_X),norm_X)#计算特征向量和特征值eig_val,eig_vec=np.linalg.eig(scatter_matrix)eig_pairs=[(np.abs(eig_val[i]),eig_vec[:,i])foriinrange(n_features)]PCA降维的Python实现

#根据eig_val从最高到最低对eig_vec进行排序eig_pairs.sort(reverse=True)#选择最上面的keig_vecfeature=np.array([ele[1]foreleineig_pairs[:k]])#获取新数据data=np.dot(norm_X,np.transpose(feature))returndataX=np.array([[-1,1],[-2,-1],[-3,-2],[1,1],[2,1],[3,2]])print(pca(X,1))PCA算法使用方法(1)在sklearn库中，可以使用sklearn.decomposition.PCA加载PCA进行降维。具体方法：PCA(n_components=None,copy=True,whiten=False,svd_solver=‘auto’)主要参数有：n_components：指定主成分的个数，即降维后数据的维度。copy：在运行算法时，是否将原始训练数据复制一份。等于True表示在原始数据的副本上进行运算，原始训练数据的值不会有任何改变；等于False在原始数据上进行降维计算，原始训练数据的值会改。Whiten：白化，使得每个特征具有相同的方差。svd_solver：可选项为{‘auto’,‘full’,‘arpack’,‘randomized’}，表示解析器计算SVD的策略。PCA算法使用方法(2)在sklearn库中，可以使用sklearn.decomposition.PCA加载PCA进行降维。主要属性：components_：降维后各主成分方向，并按照各主成分的方差值大小排序。explained_variance_：降维后各主成分的方差值，方差值越大，越主要。explained_variance_ratio_：降维后的各主成分的方差值占总方差值的比例，比例越大，则越主要。singular_values_：奇异值分解得到的前n_components个中最大的奇异值。1.降维技术2.PCA降维技术的原理与实现3.LDA降维技术的原理与实现4.关联规则挖掘算法的基本原理5.关联规则挖掘应用算法LDA介绍(1)

线性判别式分析（LinearDiscriminantAnalysis），简称为LDA。也称为Fisher线性判别（FisherLinearDiscriminant，FLD），是模式识别的经典算法，在1996年由Belhumeur引入模式识别和人工智能领域。 LDA是一种监督学习的降维技术，将数据在低维度上进行投影，投影后希望每一种类别数据的投影点尽可能的接近，而不同类别的数据的类别中心之间的距离尽可能的大。LDA介绍(2)LDA(LinearDiscriminantAnalysis)线性判别式分析，也叫Fisher线性判别，是模式识别中的经典算法，它的数据集的每个样本是有类别输出的。思想：投影后类内距离最小，类间距离最大。线性判别：LDA的主要思想是将一个高维空间中的数据投影到一个较低维的空间中，且投影后要保证各个类别的类内方差小而类间均值差别大，这意味着同一类的高维数据投影到低维空间后相同类别的聚在一起，而不同类别之间相距较远。判别问题与线性判别函数

1.方法分类：线性判别函数、支持向量机、fisher线性判别函数广义线性判别函数、非线性判别函数、核学习机2.基本思想：步一：给定一个判别函数，且已知该函数的参数形式；步二：采用样本来训练判别函数的参数；判别问题与线性判别函数

步三：对于新样本，采用判别函数对其进行决策，并按照一些准则来完成分类学习判别函数的基本技术路线；假定有n个d维空间中的样本，每个样本的类别标签已知，且一共有c个不同的类别假定判别函数的形式已知，寻找一个判别函数对于给定的新样本x，判定它属于哪个类别LDA算法优缺点LDA算法既可以用来降维，也可以用来分类，主要用于降维，尤其在进行图像识别相关的数据分析时，LDA是一个有力的工具。优点：在降维过程中可以使用类别的先验经验。LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优。缺点：LDA不适合对非高斯分布样本进行降维，PCA也有这个问题。LDA降维最多降到类别数k-1的维数，如果我们降维的维度大于k-1，则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题。LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好。LDA可能过度拟合数据。LDAVSPCA(1)为什么有了PCA之后还需要LDA？LDAVSPCA(2)共同点：都属于线性方法。在降维时都采用矩阵分解的方法。假设数据符合正态分布。不同点：LDA是有监督的，不能保证投影到新空间的坐标系是正交的，选择分类性能最好的投影方向。LDA降维保留个数与其对应类别的个数有关，与数据本身的维度无关。原始数据是n维的，有c个类别，降维后一般是到c-1维。LDA可以用于降维，还可用于分类。LDAVSPCA实验演示(1)实例：根据红酒13种成分数据对红酒进行3分类[class_1,class_2,class_3]，分类之前需要对13种红酒成分的维度进行压缩。数据是对意大利同一地区生长但来自三种不同品种的葡萄酒进行化学分析的结果。该分析确定了三种葡萄酒中每种葡萄酒中含有的13种成分的数量（13种成分如下图）。LDAVSPCA实验演示(2)实例：根据红酒成分数据对红酒进行分类，分类之前对红酒成分的不同维度进行压缩。利用3d可视化制图查看红酒3种分类在任意3种成分上的分布。LDAVSPCA实验演示(3)有监督在LDA降维中用到了标签（本数据集即三种葡萄酒的类型）。与PCA相比，LDA能够将三类样本完全分开，且同类样本之间更为密集，在有标签的分类问题，对数据降维，建议优先有监督的LDA，结果一般会更加准确。1.降维技术2.PCA降维技术的原理与实现3.LDA降维技术的原理与实现4.关联规则挖掘算法的基本原理5.关联规则挖掘应用算法关联规则不同类型的事件可能同时发生。关联规则主要在于发现不同事物背后的联系。关联规则-基本概念(1)基本概念：假设两个不相交的非空集合X、Y（物品集），N为数据记录总数。项集：项的集合，包含𝑘个项的项集称为𝑘项集。频繁项集：满足规定的最小支持度的项集。支持度：𝑠𝑢𝑝𝑝𝑜𝑟𝑡(𝑋→𝑌)=|𝑋交𝑌|/𝑁，表示物品集X和Y同时出现的次数占总记录数的比例。置信度：𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒(𝑋→𝑌)=|𝑋交𝑌|/|𝑋|，集合X与集合Y同时出现的总次数/集合X出现的记录数。提升度：𝑙𝑖𝑓𝑡(𝑋→𝑌)=𝑐𝑜𝑛𝑓𝑖𝑑𝑒𝑛𝑐𝑒(𝑋→𝑌)/𝑃(𝑌)，表示含有X的条件下，同时含有Y的概率，与Y总体发生的概率之比。关联规则-基本概念(2)最小支持度：专家定义的衡量支持度的阈值，表示项目集在统计意义上的最低重要性。最小置信度：专家定义的衡量置信度的阈值，表示关联规则的最低可靠性。强关联规则：同时满足最小支持度阈值和最小置信度阈值的规则。利用提升度体现了X和Y之间的关联关系:提升度大于1则𝑋→𝑌是有效的强关联规则；提升度小于等于1则𝑋→𝑌是无效的强关联规则；如果X和Y独立，则有𝐿𝑖𝑓𝑡(𝑋→𝑌)=1，因为此时P(X|Y)=P(X)。关联规则的挖掘步骤生成频繁项集和生成规则找出强关联规则找到所有满足强关联规则的项集关联规则挖掘的分类（1）（1）基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。

布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。而数值型关联规则可以和关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。关联规则挖掘的分类（2）

例如：类别=“大蓝筹”→涨幅=“弱于大势”，是布尔型关联规则。类别=“大蓝筹”→avg(阿尔法)=-10%，涉及的收入是数值类型，是一个数值型关联规则。关联规则挖掘的分类（3）（2）基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。

在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同层次的。而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例如，央企→分红率高，是一个细节数据上的单层关联规则；国企→分红率高，是一个较高层次和细节层次之间的多层关联规则。关联规则挖掘的分类（4）（3）基于规则中涉及的数据的维数，关联规则可以分为单维的和的。

在单维的关联规则中，我们只涉及数据的一个维，如投资者购买的股票，而在的关联规则中，要处理的数据将会涉及多个维。换句话说，单维关联规则是处理单个属性中的一些关系；关联规则是处理各个属性之间的某些关系。例如，大蓝筹涨→小盘股跌，这条规则只涉及投资者购买的股票类别；类别=“大蓝筹”→涨幅=“弱于大势”，这条规则就涉及两个字段的信息，是两个维上的一条关联规则。1.降维技术2.PCA降维技术的原理与实现3.LDA降维技术的原理与实现4.关联规则挖掘算法的基本原理5.关联规则挖掘应用算法Apriori算法简介Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过频繁项集生成和关联规则生成两个阶段来挖掘频繁项集。它的主要任务就是设法发现事物之间的内在联系。比如在常见的超市购物数据集，或者电商的网购数据集中，如果我们找到了频繁出现的数据集，那么对于超市，我们可以优化产品的位置摆放，对于电商，我们可以优化商品所在的仓库位置，达到节约成本，增加经济效益的目的。算法已经被广泛的应用到商业、网络安全，移动通信等各个领域。Apriori算法举例(1)Apriori算法举例(2)Apriori算法利用先验知识Apriori算法优缺点优点：（1）使用先验原理，大大提高了频繁项集逐层产生的效率；（2）简单易理解；数据集要求低。缺点：（1）每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;（2）每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求更好性能的算法。Apriori算法应用python最常用的机器学习库sklearn中并没有频繁集挖掘相关的算法类库；

python的工具库mlxtend目前提供实践Apriori算法的方法;mlxtend(machinelearningextensions)是一个用于日常数据科学任务的Python库工具库。通过mlxtend子模块frequent_patterns调用方法Apriori。方法描述：Apriori(df,min_support=0.5,use_colnames=False,max_len=None,n_jobs=1)，其中df代表数据框数据集，min_support表示指定的最小支持度，use_colnames=True表示使用元素名字，默认的False使用列名代表元素，max_len表示生成的项目集的最大长度。如果为None，则评估所有可能的项集长度。Apriori算法使用方法python最常用的机器学习库sklearn中并没有频繁集挖掘相关的算法类库；python的工具库mlxtend目前提供实践Apriori算法的方法;mlxtend(machinelearningextensions)是一个用于日常数据科学任务的Python库工具库。通过mlxtend子模块frequent_patterns调用方法Apriori。方法描述：Apriori(df,min_support=0.5,use_colnames=False,max_len=None,n_jobs=1)，其中df代表数据框数据集，min_support表示指定的最小支持度，use_colnames=True表示使用元素名字，默认的False使用列名代表元素，max_len表示生成的项目集的最大长度。如果为None，则评估所有可能的项集长度。FP-growth算法简介2000年，HanJiawei等人提出了基于频繁模式树（FrequentPatternTree，简称为FP-tree）的发现频繁模式的算法FP-growth。FP-growth算法建立在Apriori算法的概念之上，不同之处是它采用了更高级的数据结构FP-tree减少扫描数据次数，只需要两次扫描数据库，相比于Apriori减少了I/O操作，克服了Apriori算法需要多次扫描数据库的问题。FP-growth的数据结构为了减少I/O次数，FP-growth算法引入了一些数据结构来临时存储数据。这个数据结构包括三部分：一个项头表里面记录了所有的1项频繁集出现的次数，按照次数降序排列。FP-Tree将原始数据集映射到了内存中的一颗FP树。节点链表所有项头表里的1项频繁集都是一个节点链表的头，它依次指向FP树中该1项频繁集出现的位置。这样做主要是方便项头表和FP-Tree之间的联系查找和更新，也好理解。FP-growth算法流程1）扫描数据，得到所有频繁一项集的的计数。然后删除支持度低于阈值的项，将1项频繁集放入项头表，并按照支持度降序排列。2）扫描数据，将读到的原始数据剔除非频繁1项集，并将每一条再按照支持度降序排列。3）读入排序后的数据集，逐条插入FP树，插入时按照排序后的顺序，插入FP树中，排序靠前的节点是祖先节点，而靠后的是子孙节点。如果有共用的祖先，则对应的公用祖先节点计数加1。插入后，如果有新节点出现，则项头表对应的节点会通过节点链表链接上新节点。直到所有的数据都插入到FP树后，FP树的建立完成。4）从项头表的底部项依次向上找到项头表项对应的条件模式基。从条件模式基递归挖掘得到项头表项项的频繁项集。5）如果不限制频繁项集的项数，则返回步骤4所有的频繁项集，否则只返回满足项数要求的频繁项集。F