机器学习经典算法.ppt

经典算法,机器学习十大经典算法,C4.5分类与回归树朴素贝叶斯支持向量机（SVM)K近邻（KNN）AdaBoostK均值（K-means）最大期望（EM）Apriori算法Pagerank,机器学习方法的分类,基于学习方式的分类（1）有监督学习：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。（2）无监督学习：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。（3）强化学习（增强学习）：以环境反馈（奖/惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。,有监督学习（用于分类）,标定的训练数据训练过程：根据目标输出与实际输出的误差信号来调节参数典型方法全局：BN,NN,SVM,DecisionTree局部：KNN、CBR(Case-basereasoning),无监督学习（用于聚类）,不存在标定的训练数据学习机根据外部数据的统计规律（e.g.Cohension2根据类别中心对数据进行类别划分;3重新计算当前类别划分下每类的中心;4在得到类别中心下继续进行类别划分;5如果连续两次的类别划分结果不变则停止算法；否则循环步骤25;,k-means算法的性能分析,主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。当结果簇是密集的而簇间区别是明显的时，它的效果较好。主要缺点必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。不适合于发现非凸面形状的簇或者大小差别很大的簇。对于“躁声”和孤立点数据是敏感的，因为簇的中心是通过计算数据的平均值得到的，这些数据的存在会使聚类的中心发生很大的偏移。,八、EM,九、Apriori算法,Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。Apriori算法使用频繁项集的先验知识，使用一种称作逐层搜索的迭代方法，k项集用于探索(k+1)项集。首先，通过扫描事务（交易）记录，找出所有的频繁1项集，该集合记做L1，然后利用L1找频繁2项集的集合L2，L2找L3，如此下去，直到不能再找到任何频繁k项集。最后再在所有的频繁集中找出强规则，即产生用户感兴趣的关联规则。,步骤1：发现频繁项集,频繁项集发现过程：（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集重复步骤（1）（5）直到不能发现更大频集,步骤2：产生关联规则,根据前面提到的置信度的定义，关联规则的产生如下：（1）对于每个频繁项集L，产生L的所有非空子集；（2）对于L的每个非空子集S，如果则输出规则“SLS”。注：LS表示在项集L中除去S子集的项集。,Apriori算法可以提高数据访问效率，提升发现频繁项集的速度局限性：可能产生大量的候选集可能需要重复扫描数据库,十、Pagerank,基本思想：如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/C(T)其中PR（T）为T的PageRank值，C(T)为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。,优点：是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。不足：人们的