搜索
Lecture1IntroductiontoSupervisedLearning（1）ExpectatinMaximization(EM)Algorithm(期望值最大)（2）LinearRegressionAlgorithm(线性回归)（3）LocalWeightedRegression(局部加权回归)（4）k-NearestNeighborAlgorithmforRegression(回归k近邻)（5）LinearClassifier(线性分类)（6）PerceptronAlgorithm(线性分类)（7）FisherDiscriminantAnalysisorLinearDiscriminantAnalysis(LDA)（8）k-NNAlgorithmforClassifier(分类k近邻)（9）BayesianDecisionMethod(贝叶斯决策方法)Lecture2Feed-forwardNeuralNetworksandBPAlgorithm（1）MultilayerPerceptron(多层感知器)（2）BPAlgorithmLecture3RudimentsofSupportVectorMachine（1）SupportVectorMachine(支持向量机)（此算法是重点，必考题）此处有一道必考题Lecture4IntroductiontoDecisionRuleMining（1）DecisionTreeAlgorithm（2）ID3Algorithm（3）C4.5Algorithm（4）粗糙集……Lecture5ClassifierAssessmentandEnsembleMethods（1）Bagging（2）Booting（3）AdaboostingLecture6IntroductiontoAssociationRuleMining（1）AprioriAlgorithms（2）FP-treeAlgorithmsLecture7IntroductiontoCusteringAnalysis（1）k-meansAlgorithms（2）fuzzyc-meansAlgorithms（3）k-modeAlgorithms（4）DBSCANAlgorithmsLecture8BasicsofFeatureSelection（1）ReliefAlgorithms（2）ReliefFAlgorithms1（3）mRMRAlgorithms最小冗余最大相关算法（4）attributereductionAlgorithms比较了几种分类算法性质。（以下两个表格来自两篇该领域经典论文）2Lecture1IntroductiontoSupervisedLearning（1）ExpectatinMaximization(EM)Algorithm(期望值最大)①算法思想：EM算法又称期望最大化算法，是对参数极大似然估计的一种迭代优化策略，它是一种可以从非完整的数据集中对参数进行极大似然估计的算法,应用于缺损数据，截尾数据，带有噪声的非完整数据。最大期望算法经过两个步骤交替进行计算：第一步计算期望（E）：也就是将隐藏的变量对象能够观察到的一样包含在内，从而计算最大似然的期望值；另外一步是最大化（M），也就是最大化在E步上找到的最大似然期望值，从而计算参数的似然估计。M步上找到的参数然后用于另一个E步计算。重复上面2步直至收敛。②优点：1）Ｍ步仅涉及完全数据极大似然，通常计算比较简单2）收敛是稳定的，因为每次迭代的似然函数是不断增加的。③缺点：1）表现在对缺失数据较多或是多维高斯分布的情形下，计算量大，收敛速度较慢。2）对于某些特殊的模型，要计算算法中的M步，即完成对似然函数的估计是比较困难的。3）在某些情况下，要获得EM算法中E步的期望显式是非常困难的。4）EM算法的收敛速度，非常依赖初始值的设置，设置不当，计算代价相当大。5）EM算法中的M-Step依然是采用求导函数的方法,所以它找到的是极值点,即局部最优解,而不一定是全局最优解。3④改进：针对1）改进：扩大参数空间来加快收敛针对2）改进：ECM算法，该算法通过在Ｍ步构建计算比较简单的小循环对EM算法进行了改进，从而使期望函数极大化更加容易和有效，从而解决这一问题。针对3）改进：MCEM算法，将E步积分求期望用蒙特卡洛模拟方法来实现，使得E步求期望更容易实现。针对4）初始值的获取可以通过k-means算法，层次聚类算法或是数据数据进行随机分割，然后重复EM效果进行初始点选择。针对5）结合遗传算法的全局搜索能力，扩大EM算法的搜索空间，有效降低EM算法对初始值的依赖度，改善局部最优值的缺陷。（2）LinearRegressionAlgorithm(线性回归)①算法思想：线性回归(LinearRegression)是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参数的线性组合。只有一个自变量的情况称为简单回归,大于一个自变量情况的叫做多元回归。回归模型：其中和C是未知参数，对于每个训练样本(xi，yi)可得到)(xih，用来预测真实值yi。损失函数：即误差值的平方。1：对于训练集，求取θ，使得损失函数最小。（使用最小二乘法，梯度下降法）2：对于新输入x，其预测输出为θTx②优点：结果易于理解，实现简单，计算简单③缺点：1）对于非线性的数据拟合效果不好（原因：因为线性回归将数据视为线性的，可能出现欠拟合现象，导致结果不能取得最好的预测效果）2）如果训练数据如果有些数据偏差特别大，这回造成最后训练的模型可能对整体数据都不具备很好的准确性④改进：针对2）改进：局部加权回归（3）LocalWeightedRegression(局部加权回归)①算法思想：给每个待预测点周围的点赋予一定的权重,越近的点权重越高,以此来选出该预测点对应的数据子集,然后在此数据子集上基于最小均方差进行普通的回归.局部加权回归实质上是对于需要预测的点，只是根据其附近的点进行训练，其他的没有改变。对于局部线性加权算法：1：对于输入x，找到训练集中与x邻域的训练样本2：对于其邻域的训练样本，求取θ，使得其∈x的邻域）最小。其中w(i)为权重值。3.预测输出为θTx4.对于新输入，重复1-3过程。其中τ为带宽(bandwidth)常量，距离输入越远，权重越小，反之越大。②优点：1）局部加权回归还是对训练数据拟合的比较好2）不太依赖特征的选择，而且只需要用线性模型就能够训练出不错的拟合模型、③缺点：1）计算量较大。（因为局部加权回归的损失数随着预测值的不同而不同，这样θ4就无法事先确定，每次预测时都需要扫描所有的数据并重新计算θ）2）局部加权回归容易出现过拟合现象，过拟合现象很明显3）关注局部的训练数据，忽略了全局数据，如果预测点在出现偏差的训练数据附近，那么预测值会偏差很大。④改进：（4）k-NearestNeighborAlgorithmforRegression(回归k近邻)①算法思想：通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成反比。②优点：1）简单、有效。2）重新训练的代价较低（类别体系的变化和训练集的变化，在Web环境和电子商务应用中是很常见的）。3）计算时间和空间线性于训练集的规模（在一些场合不算太大）。4）由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。5）该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。③缺点：（1）KNN在对属性较多的训练样本进行分类时，由于计算量大而使其效率大大降低，效果不是很理想。（2）当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。（3）对数据的局部结构比较敏感。如果查询点是位于训练集较密集的区域，那预测相对比其他稀疏集来说更准确。（4）对k值敏感。（5）维数灾难：临近距离可能被不相干属性主导（因此特征选择问题）④改进：（1）分类效率：事先对样本属性进行约简，删除对分类结果影响较小的属性，快速的得出待分类样本的类别。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。（2）分类效果：采用权值的方法（和该样本距离小的邻居权值大）来改进，Han等人于2002年尝试利用贪心法，针对文件分类实做可调整权重的k最近邻居法WAkNN(weightedadjustedknearestneighbor)，以促进分类效果；而Li等人于2004年提出由于不同分类的文件本身有数量上有差异，因此也应该依照训练集合中各种分类的文件数量，选取不同数目的最近邻居，来参与分类。（3）该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进。（4）K值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用，但容易发生过拟合；如果K值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，是预测发生错误。在实际应用中，K值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的K值。随着训练实例数目趋向于无穷和K=1时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。（5）该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。5该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。（5）LinearClassifier(线性分类器)①算法思想：线性分类器使用线性判别函数，实现线性判别函数分类的方法有感知器算法、LMSE分类算法和Fisher分类。在分类问题中，因变量Y可以看做是数据的label，属于分类变量。所谓分类问题，就是能够在数据的自变量X空间内找到一些决策边界，把label不同的数据分开，如果某种方法所找出的这些决策边界在自变量X空间内是线性的，这时就说这种方法是一种线性分类器。C1和C2是要区分的两个类别，在二维平面中它们的样本如上图所示。中间的直线就是一个分类函数，它可以将两类样本完全分开。线性分类器在数学上被理解为线性判别函数(LinearDiscriminantFunctions)，在几何上可以理解为决策超平面(DecisionHyperplanes)。②优点：算法简单③缺点：只能处理线性问题④改进：要处理其他非线性问题，可以向高维转化，例如用SVM方法。线性分类器是分类方法，不是具体算法。（6）PerceptronAlgorithm(感知器算法)①算法思想：感知机（Perceptron）是二类分