分类算法小结
分类算法小结
学号：12013120116 李余芳
分类是数据挖掘中比较重要的一类，它的算法也有很多。在此，我将一些常用的算法做一个简单的小结。
一、决策树
决策树技术是用于分类和预测的主要技术，决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理除决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支，然后进行剪枝，最后在决策树的叶节点得到结论。所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规则。树的每一个结点上使用信息增益度量选择测试属性。可以从生成的决策树中提取规则。。
优点：
1、易于理解和解释.人们在通过解释后有能力去理解决策树所表达的意义。
2、能够同时处理数据型和常规型属性。其他技术往往要求数据属性的单一。
3、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。
4、在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
5、可以对有许多属性的数据集构造决策树。
6、决策树可很好地扩展到大型数据库中，它的大小独立于数据库的大小。
缺点：
1、对于各类别样本数量不一致的数据，在决策树中,信息增益的结果偏向于那些具有更多数值的特征。
2、决策树处理缺失数据时的困难。
3、过度拟合问题的出现。
4、忽略数据集中属性之间的相关性。
应用
1、决策树是用二叉树形图来表示处理逻辑的一种工具。可以直观、清晰地表
达加工的逻辑要求。特别适合于判断因素比较少、逻辑组合关系不复杂的情况。
2、决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。比如，在贷款申请中，要对申请的风险大小做出判断。
3、决策树很擅长处理非数值型数据，这与神经网络只能处理数值型数据比起来，就免去了很多数据预处理工作等等。
二、K最近邻法(KNN）
KNN法即K最近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法。该方法的思路非常简单直观：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
优点：
1、简单、有效。
2、K最近邻算法是一种非参数的分类技术，在基于统计的模式识别中非常有效，并对未知和非正态分布可取得较高的分类准确率。
3、在类别决策时，只与极少量的相邻样本有关，可以较好地避免样本的不平衡问题。
4、该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。
缺点：
1、KNN算法是建立在VSM模型上的，其样本距离测度使用欧式距离。若各维权值相同，即认定各维对于分类的贡献度相同，显然这不符合实际情况。
2、KNN是懒散的分类算法，对于分类所需的计算均推迟至分类进行，故在其分
类器中存储有大量的样本向量。在大样本集和高维样本分类时所需要的时间和空间的复杂度均较高。
3、计算量较大。因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。
应用
KNN在快速文本分类，快速分形图像编码，在药材的识别和查询、搜索等诸多方面都有应用。
三、人工神经网络(ANN)
神经网络的学习规则就是修改神经网络的权值和偏置值的方法和过程（也称这种过程为训练算法）。神经网络分类算法的重点是构造阈值逻辑单元，一个值逻辑单元是一个对象，它可以输入一组加权系数的量，对它们进行求和，如果这个和达到或者超过了某个阈值，输出一个量。
优点：
1、神经网络可以任意精度逼近任意函数
2、神经网络方法本身属于非线形模型，能够适应各种复杂的数据关系。
3、神经网络具备很强的学习能力，使它能够比很多分类算法更好地适应数据空间的变化。
4、神经网络借鉴人脑的物理结构和机理，能够模拟人脑的某些功能，具备“智能”的特点。
缺点：
1、神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值。
2、不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度。
3、学习时间过长,甚至可能达不到学习的目的。
应用
ANN作为人工智能的一个分支，在暖通空调（HAVC)领域、中药领域、水文领域、
电力系统中、经济学、网络故障诊断以及疾病诊断等等有广泛的应用。
四、贝叶斯（Bayes）
Bayes法是统计学分类方法，它利用统计学中的贝叶斯定理，来预测类成员的概率，即给定一个样本，计算该样本属于一个特定的类的概率。朴素贝叶斯分类需假设每个属性之间都是相互独立的，并且每个属性对非类问题产生的影响都是一样的。贝叶斯算法是一种在已知先验概率与类条件概率的情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体。利用Bayes定理来预测一个未知类别的样本的可能属性，可选择其可能性最大的类别作为该样本的类别。
优点：
1、朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。
2、它是一种在已知先验概率与类条件概率的情况下的模式分类方法，待分样本的分类结果取决于各类域中样本的全体。
缺点：
1、贝叶斯定理假设一个属性对给定类的影响独立于其他属性，但此假设在实际情况中经常不成立，因此影响了其分类的准确率。
2、实际情况下，类别总体的概率分布和各类样本的概率分布函数(或密度函数)常常是不知道的。为了获得它们，就要求样本足够大。
应用
Bayes在智能信息处理、医疗、网络检测和统计推断等诸多方面得到了充分的应用。
五、支持向量机（VSM）
该方法是建立在统计学习理论基础上的机器学习方法。通过学习算法，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器可以最大化类与类的间隔，因而有较好的适应能力和较高的分辨率。该方法只需要由各类域的边界样本的类别来决定最后的分类结果。
优点：
1、可以避免神经网络结构选择和局部极小点问题。
2、可以解决高维问题。
3、可以解决非线性问题。
4、待分样本集中的大部分样本不是支持向量，移去或者减少这些样本对分类结果没有影响，SVM法对小样本情况下的自动分类有着较好的分类结果。
缺点：
1、对缺失数据敏感。
2、对非线性问题没有通用解决方案，必须谨慎选择Kernel function来处理。
六、基于规则的分类
该算法的构造分类器分为两步：第一步用关联规则挖掘算法从训练数据集中挖掘出所有满足指定支持度和置信度的类关联规则；第二步选择高优先度的规则来覆盖训练集，即选择具有最高置信度的规则作为可能规则。
优点：
1、可以产生清晰有用的结果。
2、可以处理变长的数据。
3、计算的消耗量是可以预见的。
4、基于关联规则的分类技术在总体上分类准确度高。
缺点：
1、资源消耗大。
2、规则剪枝难。
3、分类模型较复杂。
目标跟踪算法的分类
主要基于两种思路： a)不依赖于先验知识，直接从图像序列中检测到运动目标，并进行目标识别，最终跟踪感兴趣的运动目标； b)依赖于目标的先验知识，首先为运动目标建模，然后在图像序列中实时找到相匹配的运动目标。 一．运动目标检测 对于不依赖先验知识的目标跟踪来讲，运动检测是实现跟踪的第一步。运动检测即为从序列图像中将变化区域从背景图像中提取出来。运动目标检测的算法依照目标与摄像机之间的关系可以分为静态背景下运动检测和动态背景下运动检测 （一）静态背景 1.背景差 2.帧差 3.GMM 4.光流 背景减算法可以对背景的光照变化、噪声干扰以及周期性运动等进行建模，在各种不同情况下它都可以准确地检测出运动目标。因此对于固定
个关键技术： a)匹配法则，如最大相关、最小误差等 b)搜索方法，如三步搜索法、交叉搜索法等。 c) 块大小的确定，如分级、自适应等。 光流法 光流估计的方法都是基于以下假设：图像灰度分布的变化完全是目标或者场景的运动引起的，也就是说，目标与场景的灰度不随时间变化。这使得光流方法抗噪声能力较差，其应用范围一般局限于目标与场景的灰度保持不变这个假设条件下。另外，大多数的光流计算方法相当复杂，如果没有特别的硬件装置，其处理速度相当慢，达不到实时处理的要求。 二．目标跟踪 运动目标的跟踪，即通过目标的有效表达，在图像序列中寻找与目标模板最相似候选目标区位置的过程。简单说，就是在序列图像中为目标定位。运动目标的有效表达除了对运动目标建模外，目标跟踪中常用到的目标特性表达主要包括视觉特征 (图像边缘、轮廓、形状、纹理、区域)、统计特征 (直方图、各种矩特征)、变换系数特
预测方法的分类 郑XX 预测方法的分类 由于预测的对象、目标、内容和期限不同，形成了多种多样的预测方法。据不完全统计，目前世界上共有近千种预测方法，其中较为成熟的有150多种，常用的有30多种，用得最为普遍的有10多种。 1-1预测方法的分类体系 1）按预测技术的差异性分类 可分为定性预测技术、定量预测技术、定时预测技术、定比预测技术和评价预测 技术，共五类。 2）按预测方法的客观性分类 可分为主观预测方法和客观预测方法两类。前者主要依靠经验判断，后者主要借 助数学模型。 3）按预测分析的途径分类 可分为直观型预测方法、时间序列预测方法、计量经济模型预测方法、因果分析 预测方法等。 4）按采用模型的特点分类 可分为经验预测模型和正规的预测模型。后者包括时间关系模型、因果关系模 型、结构关系模型等。 1-2 常用的方法分类 1)定性分析预测法 定性分析预测法是指预测者根据历史与现实的观察资料，依赖个人或集体的经验与智慧，对未来的发展状态和变化趋势作出判断的预测方法。 定性预测优缺点 定性预测的优点在于： 注重于事物发展在性质方面的预测，具有较大的灵活性，易于充分发挥人的主观能动作用，且简单的迅速，省时省费用。
定性预测的缺点是： 易受主观因素的影响，比较注重于人的经验和主观判断能力，从而易受人的知识、经验和能力的多少大小的束缚和限制，尤其是缺乏对事物发展作数量上的精确描述。 2)定量分析预测法 定量分析预测法是依据调查研究所得的数据资料，运用统计方法和数学模型，近似地揭示预测对象及其影响因素的数量变动关系，建立对应的预测模型，据此对预测目标作出定量测算的预测方法。通常有时间序列分析预测法和因果分析预测法。 ⅰ时间序列分析预测法 时间序列分析预测法是以连续性预测原理作指导，利用历史观察值形成的时间数列，对预测目标未来状态和发展趋势作出定量判断的预测方法。
第8章?机器学习基础算法建模
目录 1.机器学习 2.分类算法 3.回归算法 4.集成学习算法 5.聚类算法 6.关联规则算法 7.智能推荐算法
l 在机器学习的有监督学习算法中，目标是学习出一个稳定的且在各个方面表现都较好的模型，但实际情况往往达不到理想状态，有时只能得到多个有偏好的模型（弱分类器，在某些方面表现较好）。 ?集成学习是组合多个弱分类器，得到一个更好且更全面的强分类器，即将多个分 类器聚集在一起，以提高分类的准确率。 ?这些分类器可以是不同的算法，也可以是相同的算法。如果把单个分类器比作一 个决策者，那么集成学习的方法就相当于多个决策者共同进行一项决策。 集成学习
l集成学习的作用 将多个弱分类器合并，实现更好的效果。 l分类器间存在一定的差异性，会导致分类的边界不同，可以理解为分类器是一个比较专精的专家，它有它自己一定的适用范围和特长。 l通过一定的策略将多个弱分类器合并后，即可拓展模型的适用范围，减少整体 的错误率，实现更好的效果。
l 数据过大时会导致训练一个模型太慢，而集成学习可以分别对数据集进行划分和有放回的操作，从而产生不同的数据子集，再使用数据子集训练不同的分类器， 最终再将不同的分类器合并成为一个大的分类器。 l 数据过小时则会导致训练不充分，而集成学习可以利用Bootstrap 方法进行抽样，得到多个数据集，分别训练多个模型后再进行组合。如此便可提高训练的准确度 和速度，使得之前很难利用的数据得到充分的利用。集成学习在各个规模的数据集上都有很好的策略。
将多个模型进行融合。 l对于存在多个异构的特征集的时候，很难进行融合，可以考虑使用集成学习的方式，将每个数据集构建一个分类模型，然后将多个模型进行融合。
JAVA常用的高级数据类型——集合类型 一、JAVA语言中的集合类型主要有三种形式：Set（集）、List（列表）、Map（映射），每种类型的集合都包括三部分：接口、实现和算法。 a)集合接口实现集合的操作和集合的具体功能实现细节的相互分离—— Set接口、List接口、Map接口 b)集合的具体功能实现类实质上是各种可重用的数据结构的具体表示 List接口的实现类有ArrayList、LinkedList、Stack和Vector等 集合类，Vector 类提供了实现可增长数组的功能，随着更多元素加 入其中，数组变的更大。在删除一些元素之后，数组变小。 Set接口的实现类有HashSet、LinkedHashSet和TreeSet等集合类 Map接口的实现类有HashMap、Hashtable、LinkedHashMap、Properties和TreeMap等集合类。 c)集合的算法指可以对实现集合接口的各个集合的功能实现类提供如排 序、查找、交换和置换等方面的功能实现。 二、List接口 1.List接口代表有序的集合，可以对List接口代表的有序集合中每个元素 的插入位置进行精确地控制，并利用元素的整数索引（代表元素在集合中的位置）访问元素中的各个成员，List接口代表的集合是允许出现重复元素的。 2.List接口主要成员方法： 1）void add（int index,E element）在列表指定位置插入指定元素 2）E get(int index) 返回结合中指定位置的元素 3）E remove(int index) 移除集合中指定位置的元素 4）E set(int index,E elment) 用指定元素替换集合中指定位置的元素 5）boolean add(E o) 向列表的尾部追加指定的元素 6）boolean contains(Object o) 如果列表包含指定的元素，则返回true。 7）boolean isEmpty() 如果列表不包含元素，则返回 true。 8）int size() 返回列表中的元素数 9）Iterator iterator()返回以正确顺序在列表的元素上进行迭代的迭代器。 3.List的实现类 List在数据结构中分别表现为数组（ArrayList）、向量（Vector）、链表（LinkedList）、堆栈（Stack）和队列等形式。 Vector集合和ArrayList集合都是采用数组形式来保存对象，区别在于ArrayList集合本身不具有线程同步的特性，不能用在多线程的环境下，可以使用ArrayList集合能够节省由于同步而产生的系统性能的开销。而Vector集合实现了对线程同步的支持，因此在多线程并发访问的应用环境下，该集合本身能够保证自身具有线程安全性。在多线程的并发访问中，可以将Vector集合的对象实例设计为类中的成员属性，而应该将ArrayList 集合的对象实例设计为局部对象。 public class UserInfo{ List oneVector=new Vector(); public void execute(){
树模型 决策树：从根节点开始一步步走到叶子节点（决策） 所有的数据最终都会落到叶子节点，既可以做分类也可以做回归
树的组成 根节点：第一个选择点 非叶子节点与分支：中间过程叶子节点：最终的决策结果
决策树的训练与测试 训练阶段：从给定的训练集构造出来一棵树（从跟节点开始选择特征，如何进行特征切分） 测试阶段：根据构造出来的树模型从上到下去走一遍就好了 一旦构造好了决策树，那么分类或者预测任务就很简单了，只需要走一遍就可以了，那么难点就在于如何构造出来一颗树，这就没那么容易了，需要考虑的问题还有很多的！
如何切分特征（选择节点） 问题：根节点的选择该用哪个特征呢？接下来呢？如何切分呢？ 想象一下：我们的目标应该是根节点就像一个老大似的能更好的切分数据（分类的效果更好），根节点下面的节点自然就是二当家了。 目标：通过一种衡量标准，来计算通过不同特征进行分支选择后的分类情况，找出来最好的那个当成根节点，以此类推。
衡量标准-熵 熵：熵是表示随机变量不确定性的度量 （解释：说白了就是物体内部的混乱程度，比如杂货市场里面什么都有那肯定混乱呀，专卖店里面只卖一个牌子的那就稳定多啦） 公式：H(X)=-∑ pi * logpi, i=1,2, ... , n 一个栗子：A集合[1,1,1,1,1,1,1,1,2,2] B集合[1,2,3,4,5,6,7,8,9,1] 显然A集合的熵值要低，因为A里面只有两种类别，相对稳定一些 而B中类别太多了，熵值就会大很多。（在分类任务中我们希望通过节点分支后数据类别的熵值大还是小呢？）
衡量标准-熵 熵：不确定性越大，得到的熵值也就越大 当p=0或p=1时，H(p)=0,随机变量完全没有不确定性当p=0.5时，H(p)=1,此时随机变量的不确定性最大 如何决策一个节点的选择呢？ 信息增益：表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果是同类在一起）
数据挖掘分类算法比较 分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。通过对当前数据挖掘中具有代表性的优秀分类算法进行分析和比较，总结出了各种算法的特性，为使用者选择算法或研究者改进算法提供了依据。 一、决策树（Decision Trees） 决策树的优点： 1、决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。 2、对于决策树，数据的准备往往是简单或者是不必要的.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。 3、能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。 4、决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。 5、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。 6、在相对短的时间内能够对大型数据源做出可行且效果良好的结果。 7、可以对有许多属性的数据集构造决策树。 8、决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。 决策树的缺点： 1、对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。 2、决策树处理缺失数据时的困难。 3、过度拟合问题的出现。 4、忽略数据集中属性之间的相关性。 二、人工神经网络 人工神经网络的优点：分类的准确度高,并行分布处理能力强,分布存储及学习能力强，对噪声神经有较强的鲁棒性和容错能力，能充分逼近复杂的非线性关系，具备联想记忆的功能等。 人工神经网络的缺点：神经网络需要大量的参数，如网络拓扑结构、权值和阈值的初始值；不能观察之间的学习过程，输出结果难以解释，会影响到结果的可信度和可接受程度；学习时间过长,甚至可能达不到学习的目的。
iSIGHT中优化方法种类 iSIGHT里面的优化方法大致可分为三类： 1 数值优化方法 数值优化方法通常假设设计空间是单峰值的，凸性的，连续的。iSIGHT中有以下几种： （1）外点罚函数法（EP）： 外点罚函数法被广泛应用于约束优化问题。此方法非常很可靠，通常能够在有最小值的情况下，相对容易地找到真正的目标值。外点罚函数法可以通过使罚函数的值达到无穷值，把设计变量从不可行域拉回到可行域里，从而达到目标值。 （2）广义简约梯度法（LSGRG2）： 通常用广义简约梯度算法来解决非线性约束问题。此算法同其他有效约束优化一样，可以在某方向微小位移下保持约束的有效性。 （3）广义虎克定律直接搜索法： 此方法适用于在初始设计点周围的设计空间进行局部寻优。它不要求目标函数的连续性。因为算法不必求导，函数不需要是可微的。另外，还提供收敛系数（rho），用来预计目标函数方程的数目，从而确保收敛性。 （4）可行方向法（CONMIN）： 可行方向法是一个直接数值优化方法，它可以直接在非线性的设计空间进行搜索。它可以在搜索空间的某个方向上不断寻求最优解。用数学方程描述如下： Design i = Design i-1 + A * Search Direction i方程中，i表示循环变量，A表示在某个空间搜索时决定的常数。它的优点就是在保持解的可行性下降低了目标函数值。这种方法可以快速地达到目标值并可以处理不等式约束。缺点是目前还不能解决包含等式约束的优化问题。 （5）混合整型优化法（MOST）： 混合整型优化法首先假定优化问题的设计变量是连续的，并用序列二次规划法得到一个初始的优化解。如果所有的设计变量是实型的，则优化过程停止。否则，如果一些设计变量为整型或是离散型，那么这个初始优化解不能满足这些限制条件，需要对每一个非实型参数寻找一个设计点，该点满足非实型参数的限制条件。这些限制条件被作为新的约束条件加入优化过程，重新优化产生一个新的优化解，迭代依次进行。在优化过程中，非实型变量为重点考虑的对象，直到所有的限制条件都得到满足，优化过程结束，得到最优解。 （6）序列线性规划法（SLP）：序列线性规划法利用一系列的子优化方法来解决约束优化问题。此方法非常好实现，适用于许多工程实例问题。 （7）序列二次规划法（DONLP）： 此方法对拉各朗日法的海森矩阵进行了微小的改动，进行变量的缩放，并且改善了armijo型步长算法。这种算法在设计空间中通过梯度投影法进行搜索。 （8）序列二次规划法（NLPQL）： 这种算法假设目标函数是连续可微的。基本思想是将目标函数以二阶拉氏方程展开，并把约束条件线性化，使得转化为一个二次规划问题。二阶方程通过quasi－Newton公式得到了改进，而且加入了直线搜索提高了算法的稳定性。 （9）逐次逼近法（SAM）： 逐次逼近法把非线性问题当做线性问题来处理。使用了稀疏矩阵法和单纯形法求解线性问题。如果某个变量被声明成整型，单纯形法通过重复大量的矩阵运算来达到预期的最优值。逐次逼近法是在M. Berkalaar和J.J. Dirks提出的二次线性算法。 2 探索优化方法 探索优化法避免了在局部出现最优解的情况。这种方法通常在整个设计空间中搜索全局最优值。iSIGHT中有以下两种： （1）多岛遗传算法（MIGA）： 在多岛遗传算法中，和其他的遗传算法一样每个设计点都有一个适应度值,这个值是建立在目标函
C语言常用算法集合
1.定积分近似计算： /*梯形法*/ double integral(double a,double b,long n) { long i;double s,h,x; h=(b-a)/n; s=h*(f(a)+f(b))/2; x=a; for(i=1;i if(n==1||n==2) *s=1; else{ fib(n-1,&f1); fib(n-2,&f2); *s=f1+f2; } } 3.素数的判断： /*方法一*/ for (t=1,i=2;i 分类算法小结 分类算法小结 学号：12013120116 李余芳 分类是数据挖掘中比较重要的一类，它的算法也有很多。在此，我将一些常用的算法做一个简单的小结。 一、决策树 决策树技术是用于分类和预测的主要技术，决策树学习是以实例为基础的归纳学习算法。它着眼于从一组无次序、无规则的事例中推理除决策树表示形式的分类规则。它采用自顶向下的递归方式，在决策树的内部节点进行属性值的比较并根据不同属性判断从该节点向下的分支，然后进行剪枝，最后在决策树的叶节点得到结论。所以从根到叶节点就对应着一条合取规则，整棵树就对应着一组析取表达式规则。树的每一个结点上使用信息增益度量选择测试属性。可以从生成的决策树中提取规则。。 优点： 1、易于理解和解释.人们在通过解释后有能力去理解决策树所表达的意义。 2、能够同时处理数据型和常规型属性。其他技术往往要求数据属性的单一。 3、易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。 4、在相对短的时间内能够对大型数据源做出可行且效果良好的结果。 5、可以对有许多属性的数据集构造决策树。 6、决策树可很好地扩展到大型数据库中，它的大小独立于数据库的大小。 缺点： 1、对于各类别样本数量不一致的数据，在决策树中,信息增益的结果偏向于那些具有更多数值的特征。 2、决策树处理缺失数据时的困难。 3、过度拟合问题的出现。 4、忽略数据集中属性之间的相关性。 应用 1、决策树是用二叉树形图来表示处理逻辑的一种工具。可以直观、清晰地表 达加工的逻辑要求。特别适合于判断因素比较少、逻辑组合关系不复杂的情况。 2、决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法。比如，在贷款申请中，要对申请的风险大小做出判断。 3、决策树很擅长处理非数值型数据，这与神经网络只能处理数值型数据比起来，就免去了很多数据预处理工作等等。 二、K最近邻法(KNN） KNN法即K最近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法。该方法的思路非常简单直观：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。 优点： 1、简单、有效。 2、K最近邻算法是一种非参数的分类技术，在基于统计的模式识别中非常有效，并对未知和非正态分布可取得较高的分类准确率。 3、在类别决策时，只与极少量的相邻样本有关，可以较好地避免样本的不平衡问题。 4、该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。 缺点： 1、KNN算法是建立在VSM模型上的，其样本距离测度使用欧式距离。若各维权值相同，即认定各维对于分类的贡献度相同，显然这不符合实际情况。 2、KNN是懒散的分类算法，对于分类所需的计算均推迟至分类进行，故在其分 机器学习实战之分类算法 第一章机器学习概论 (4) 机器学习基本概念 (4) 机器学习的主要任务以及相应的算法 (4) 如何选择合适的算法？ (4) 机器学习应用的步骤 (5) 第二章 K近邻算法(KNN) (5) 工作原理 (5) 实现步骤 (6) K近邻算法的优缺点 (6) 第三章决策树 (7) 基本思路 (7) 集合无序程度测量 (7) 应用场景 (7) 优缺点 (7) 第四章朴素贝叶斯分类 (8) 基本思路 (8) 基本假设 (8) 条件概率 (8) 词袋模型和词集模型 (9) 优缺点 (10) 标称型和数值型数据的区别 (10) 主要应用及步骤 (10) 第五章逻辑回归 (12) 基本思想 (12) 使用场景 (12) 优缺点 (12) Sigmoid函数 (13) 回归系数 (13) 梯度上升法 (14) 特征缺失处理 (14) 标签缺失处理 (14) 第六章支持向量机SVM (14) 基本思想 (14) SVM第一层理解 (15) 超平面的确定 (15) 函数间隔和几何间隔 (15) 最大间隔分类器 (16) SMO优化算法 (16) 核函数 (19) 应用场景 (19) 第七章 AdaBoost分类 (19) Bagging (20) Boosting (20) Adaboost (20) Adaboost的优点 (20) Adaboost实现步骤 (21) 第八章非均衡分类问题 (23) 分类性能指标 (23) 混淆矩阵 (23) ROC曲线 (24) 处理非均衡问题的数据抽样 (24) 第一章机器学习概论 机器学习基本概念 机器学习就是将无序的数据转化为有用的信息。一个实例有n个特征，由n列组成。机器学习最主要的任务就是分类，另一个就是回归，回归中比较典型的就是线性拟合。分类和回归都属于监督学习，因为这类算法必须知道要预测什么，即已知目标变量的分类信息。与监督学习对应的是无监督学习，此时数据没有类别信息，也不会给定目标值，将数据集合分成由类似的对象组成的多个类的过程叫做聚类。将描述数据统计值的过程称之为密度估计。分类首先要进行训练，训练样本集必须确定目标变量的值，以便发现特征与目标变量之间的关系。特征或者属性通常是训练样本集的列，他们是独立测量得到的结果，多个特征联系在一起共同组成一个训练样本。 机器学习的主要任务以及相应的算法 如何选择合适的算法？ 如果要预测目标变量的值： 运动目标跟踪就是在一段序列图像中的每幅图像中实时地找到所感兴趣的运动目标 (包括位置、速度及加速度等运动参数)。在运动目标跟踪问题的研究上，总体来说有两种思路： a)不依赖于先验知识，直接从图像序列中检测到运动目标，并进行目标识别，最终跟踪感兴趣的运动目标； b)依赖于目标的先验知识，首先为运动目标建模，然后在图像序列中实时找到相匹配的运动目标。 一、运动目标检测 对于不依赖先验知识的目标跟踪来讲，运动检测是实现跟踪的第一步。运动检测即为从序列图像中将变化区域从背景图像中提取出来。运动目标检测的算法依照目标与摄像机之间的关系可以分为静态背景下运动检测和动态背景下运动检测。 静态背景下运动检测就是摄像机在整个监视过程中不发生移动，只有被监视目标在摄像机视场内运动，这个过程只有目标相对于摄像机的运动；动态背景下运动检测就是摄像机在整个监视过程中发生了移动 (如平动、旋转或多自由度运动)，被监视目标在摄像机视场内也发生了运动，这个过程就产生了目标与摄像机之间复杂的相对运动。 1、静态背景 背景差分法 背景差分法是利用当前图像与背景图像的差分来检测运动区域的一种技术。它一般能够提供最完全的特征数据，但对于动态场景的变化，如天气、光照、背景扰动及背景物移入移出等特别敏感，运动目标的阴影也会影响检测结果的准确性及跟踪的精确性。其基本思想就是首先获得一个背景模型，然后将当前帧与背景模型相减，如果像素差值大于某一阈值，则判断此像素属于运动目标，否则属于背景图像。背景模型的建立与更新、阴影的去除等对跟踪结果的好坏至关重要。 帧间差分法 相邻帧间差分法是通过相邻两帧图像的差值计算，获得运动物体位置和形状等信息的运动目标检测方法。其对环境的适应性较强，特别是对于光照的变化适应性强，但由于运动目标上像素的纹理、灰度等信息比较相近，不能检测出完整 预测模型分类及优缺点分析 灰色(系统)预测模型 神经网络预测模型 趋势平均预测法 1 微分方程模型 当我们描述实际对象的某些特性随时间(或空间)而演变的过程、分析它的变化规律、预测它的未来性态、研究它的控制手段时,通常要建立对象的动态微分方程模型。微分方程大多是物理或几何方面的典型.问题,假设条件已经给出,只需用数学符号将已知规律表示出来,即可列出方程,求解的结果就是问题的答案,答案是唯一的,但是有些问题是非物理领域的实际问题,要分析具体情况或进行类比才能给出假设条件。作出不同的假设,就得到不同的方程。比较典型的有:传染病的预测模型、经济增长预测模型、正规战与游击战的预测模型、药物在体内的分布与排除预测模型、人口的预测模型、烟雾的扩散与消失预测模型以及相应的同类型的预测模型。其基本规律随着时间的增长趋势是指数的形式,根据变量的个数建立初等微分模型。微分方程模型的建立基于相关原理的因果预测法。该法的优点:短、中、长期的预测都适合,而.既能反映内部规律,反映事物的内在关系,也能分析两个因素的相关关系,精度相应的比较高,另外对初等模型的改进也比较容易理解和实现。该法的缺点:虽然反映的是内部规律,但是由于方程的建立是以局部规律:的独立性假定为基础,故做中长期预测时,偏差有点大,而且微分方程的解比较难以得到。 2 时间序列法 将预测对象按照时问顺序排列起来,构成一个所谓的时间序列,从所构成的这一组时间序列过去的变化规律,推断今后变化的可能性及变化趋势、变化规律,就是时间序列预测法。时间序列预测一般反映三种实际变化规律:趋势变化、周期性变 化、随机性变化。考虑一组给定的随时间变化的观察值,t=1,2,3,?,n},如何选取合适模型预报,t=n+1,n+3, n+k}的值。 上面的模型统称ARMA模型,是时间序列建模中最重要和最常用的预测手段。 事实上,对实际中发生的平稳时间序列做恰当的描述,往往能够得到自回归、滑动平均或混合的模型,其阶数通常不超过2。时间序列模型其实也是一种回归模型,属于定量预测,其基于的原理是,一方面承认事物发展的延续性,运用过去时间序列的数据进行统计分析就能推测事物的发展趋势;另一方面又充分考虑到偶然因素影响而产生的随机性,为了消除随机波动的影响,利用历史数据,进行统计分析,并对数据进行适当的处理,进行趋势预测。优点是简单易行,便于掌握,能够充分运用原时间序列的各项数据,计算速度快,对模型参数有动态确定的能力,精度较好,采用组合的时间序列或者把时间序列和其他模型组合效果更好。缺点是不能反映事物的内在联系,不能分析两个因素的相关关系,常数的选择对数据修匀程度影响较大,不宜取得太小,只适用于短期预测 3 灰色预测理论模型 灰色预测的基本思路是将已知的数据序列按照某种规则构成动态或非动态的 白色模块,再按照某种变化、解法来求解未来的灰色模型。它的主要特点是模型使用的不是原始数据序列,而是生成的数据序列。其核心体系是灰色模型(GM),即对原始数据作累加生成(或其他方法生成)得到近似的指数规律再进行建模的模型方法。优点是不需要很多的数据,一般只需要4个数据就够,能解决历史数据少、序列的完整性及可靠性低的问题;能利用微分方程来充分挖掘系统的本质,精度高;能将无规律的原始数据进行生成得到规律性较强的生成数列,运算简便,易于检验,具有不考虑分布规律,不考虑变化趋势。缺点是只适用于中长期的预测,只适合指数增长的预测,对波动性不好的时间序列预测结果较差。 4 BP神经网络模型 首都师范大学 硕士学位论文 数据挖掘分类算法的研究与应用 姓名：刘振岩 申请学位级别：硕士 专业：计算机应用技术 指导教师：王万森 2003.4.1 首都师范入学硕．卜学位论Ｚ数据挖掘分类算法的研究与应用 摘要 ， ｆ随着数据库技术的成熟应用和Ｉｎｔｅｒｎｅｔ的迅速发展，人类积累的数据量正在以指数速度增长。科于这些数据，人｛｝ｊ已经不满足于传统的查询、统计分析手段，而需要发现更深层次的规律，对决策或科研工作提供更有效的决策支持。正是为了满足这种要求，从大量数据中提取出隐藏在其中的有用信息，将机器学习应用于大型数据库的数据挖掘（ＤａｔａＭｉｎｉｎｇ）技术得到了长足的发展。 所谓数据挖掘（ＤａｔａＭｉｎｉｎｇ，ＤＭ），也可以称为数据库中的知识发现（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒＤａｔ曲鹅ｅ，ＫＤＤ），就是从大量的、不完全的、有噪声的、模糊的、随机的数据ｒ｝，，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数据挖掘是数据库研究中的一个很有应用价值的新领域，它又是一门广义的交叉学科，融合了数据库、人工智能、机器学习、统计学等多个领域的理论和技术。 分类在数据挖掘中是一项非常重要的任务，目前在商业上应用最多。分类的目的是学会一个分类函数或分类模型，该模型能把数据库中的数据项映射到给定类别中的某一个。｛乍多分类的方法已被机器学习、专家系统、统计学和神经生物学方面的研究者提｝Ｈ。本论文主要侧重数据挖掘中分类算法的研究，并将分类算法划分为急切分类和懒散分类，全部研究内容基本围绕着这种划分方法展开。．１本文的主要研究内容：， ｌ，讨论了数掂挖掘中分类的基本技术，包括数据分类的过程，分类数据所需的数据预处理技术，以及分类方法的比较和评估标准；比较了几种典 型的分类算法，包括决策树、ｋ．最近邻分类、神经网络算法：接着，引 出本文的研究重点，即将分类算法划分为急切分类和懒散分类，并基于 这种划分展歼对数据挖掘分类算法的研究。 ２．结合对决簸树方法的研究，重点研究并实现了一个“懒散的基于模型的分类”思想的“懒散的决策树算法”。在决策树方法的研究中，阐述了决 策树的基本概念以及决策树的优缺点，决策树方法的应用状况，分析了 决策树算法的迸一步的研究重点。伪了更好地满足网络环境下的应用需 求，结合传统的决策树方法，基于Ⅶ懒散的基于模型的分类”的思想， 实现了一个网络环境下基于Ｂ／Ｓ模式的“懒散的决策树算法”。实践表明： 在ＷＥＢ应ｆＨ程序叶ｉ采用此算法取得了很好的效果。、 ≯ ３．选取神经Ｈ络分类算法作为急切分类算法的代表进行深入的研究。在神经网络中，重点分析研究了感知器基本模型，包括感知器基本模型的构 造及其学习算法，模型的几何意义及其局限性。并针对该模型只有在线 性可分的情况一Ｆ彳‘能用感知器的学习算法进行分类的这一固有局限性， 研究并推广了感知器模型。 集合概念、表示方法、分类以及集合之间的关系 一般地，我们把研究对象统称为元素，一些元素组成的总体叫集 合，也简称集。 通常用大括号{ }或大写的拉丁字母A,B,C…表示，而元素用小写的拉丁字母a,b,c…表示。 元素与集合的关系有“属于∈”及“不属于?两种) ⑴若a是集合A中的元素，则称a属于集合A，记作a∈A； ⑵若a不是集合A的元素，则称a不属于集合A，记作a?A。 非负整数集（或自然数集），记作N； ；N内排除0的集. 正整数集，记作N*或N + 整数集，记作Z；有理数集，记作Q；实数集，记作R； ⑴确定性：⑵互异性：⑶无序性： 1：判断以下元素的全体是否组成集合，并说明理由： ⑴某班个子较高的同学⑵长寿的人 ⑷倒数等于它本身的数 ⑸某校2011级新生；⑹血压很高的人； ⑺著名的数学家；⑻平面直角坐标系内所有第三象限的点 7.元素与集合的关系：(元素与集合的关系有“属于∈”及“不属于?”) ⑴若a是集合A中的元素，则称a属于集合A，记作a∈A； ⑵若a不是集合A的元素，则称a不属于集合A，记作a?A。 例如，我们A 表示“1~20以内的所有质数”组成的集合，则有3∈A ，4 ?A ，等等。 练：A={2，4，8，16}，则4A ，8 A ，32 A. 巩固练习分析： 练1．已知集合P 的元素为21,,3m m m --, 若2∈P 且-1?P ，求实 数m 的值。 练2下面有四个命题: ①若-a ?Ν,则a ∈Ν ②若a ∈Ν,b ∈Ν,则a +b 的最小值是2 ③集合N 中最小元素是1 ④ x 2+4=4x 的解集可表示为{2,2} 其中正确命题的个数是( ) 3求集合{2a ,a 2+a }中元素应满足的条件? 4若 t 1t 1+-∈{t},求t 的值. ⒈列举法：把集合中的元素一一列举出来, 并用花括号“{ }”括起来表 示 2．用列举法表示下列集合： (1) 小于5的正奇数组成的集合； (2) 能被3整除而且大于4小于15的自然数组成的集合； ⒉描述法：用集合所含元素的共同特征表示集合的方法，称为描述法。。 一般格式：{}()x A p x ∈ 现代六爻预测的十种分类预测方法 预测求财做生意 在市场经济中，每个人的经济活动都离不开经济效益。广义上讲，看我们自己所做的一切工作有没有经济效益。这就是求财。 在求财预测中，必须先搞清楚各个卦爻在预测财运中各自代表什么人什么物，然后依据人和物的旺衰、相生相克、空亡入墓等等情况，才可做出综合判断，看能否得到财。因而，知道卦爻在求财中代表什么，能派上什么用场，是积极因素还是消极因素，才能最后达到预测准确的目的。所以，取准用神是至关重要的第一步，然后再去考虑忌原仇及各自的旺衰。 财爻代表所求的经济效益，是求财中的主用神，因而，财爻的旺与衰，直接关系到能否得到财。 首先，财爻必须与世爻(代表求财人)构成一种关系，这种关系就是财爻持世并合关系，财爻生世克世的关系，财爻被世爻生和克的关系。这几种关系，在卦中是相生相克的关系，在实际求财中，是求财人与经济效益的关系。因而，测求财时，如果卦中无财(财爻不上卦)，或伏藏不得出，或子孙爻也不上卦，一般情况下是求财无望。这是因为，卦中无财，无法与世爻构成这种关系，既无这种人与经济效益的关系，或财无来源，又怎能谈发财呢! 按五行论，无论世爻是何种五行，必然与其他五行构成并列、相生、相克三种关系。有了这三种关系，不等于说世爻同财爻就构成了这种联系。因为在实际断卦中，虽然财爻可以生世爻，但财爻衰弱，或空亡，或入墓或因合忘生等等情况，实际上财爻并不能生世爻。这种实际不能生的情况，就等于财爻与世爻暂时无必然联系，无相互关系。既然无联系和无关系，又怎能谈发财呢!财爻可以因种种原因不能生世爻，世爻也可以因其衰弱或入墓空而不受生。这种不受生的表现形式，也等于割断了财爻与世爻的联系。至于世爻克财爻，世爻生财爻，都可以因自己或对方旺衰强弱的具体情况，而不能克对方生对方，或不受生不受克，因而暂时都没有了联系。没有了联系，就不会得财。 财爻生世克世，或世爻生财爻克财爻，都是得财之象。在遇到暂时不能生克对方而被切断这种联系的情况时，也可以因为年月日令即旺衰的来源的改变而又恢复这种联系，使财爻可以生世克世，世爻可以克财生财的时候，也就是求财的应期到了。 不论你是为公私营企业求利，或以自己技能求利，以及得奖、接受馈赠、借贷、继承遗产等等，都是求财求利，希望自己能得到财力。在预测时，均以财爻为用来代表。 《数据挖掘》 数据挖掘分类算法综述 专业：计算机科学与技术专业学号：S2******* 姓名：张靖 指导教师：陈俊杰 时间：2011年08月21日 数据挖掘分类算法综述 数据挖掘出现于20世纪80年代后期，是数据库研究中最有应用价值的新领域之一。它最早是以从数据中发现知识(KDD，Knowledge Discovery in Database)研究起步，所谓的数据挖掘(Data Mining，简称为DM)，就从大量的、不完全的、有噪声的、模糊的、随机的、实际应用的数据中提取隐含在其中的、人们不知道的但又有用的信息和知识的过程。 分类是一种重要的数据挖掘技术。分类的目的是根据数据集的特点构造一个分类函数或分类模型(也常常称作分类器)。该模型能把未知类别的样本映射到给定类别中的一种技术。 1. 分类的基本步骤 数据分类过程主要包含两个步骤： 第一步，建立一个描述已知数据集类别或概念的模型。如图1所示，该模型是通过对数据库中各数据行内容的分析而获得的。每一数据行都可认为是属于一个确定的数据类别，其类别值是由一个属性描述(被称为类别属性)。分类学习方法所使用的数据集称为训练样本集合，因此分类学习又可以称为有指导学习(learning by example)。它是在已知训练样本类别情况下，通过学习建立相应模型，而无指导学习则是在训练样本的类别与类别个数均未知的情况下进行的。 通常分类学习所获得的模型可以表示为分类规则形式、决策树形式或数学公式形式。例如，给定一个顾客信用信息数据库，通过学习所获得的分类规则可用于识别顾客是否是具有良好的信用等级或一般的信用等级。分类规则也可用于对今后未知所属类别的数据进行识别判断，同时也可以帮助用户更好的了解数据库中的内容。 图1 数据分类过程中的学习建模 第二步，利用所获得的模型进行分类操作。首先对模型分类准确率进行估计，例如使用保持(holdout)方法。如果一个学习所获模型的准确率经测试被认为是可以接受的，那么就可以使用这一模型对未来数据行或对象(其类别未知)进行分类。例如，在图2中利用学习获得的分类规则(模型)。对已知测试数据进行模型 #include q=p; p=(LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data.n); } q->next=NULL; } void add(polymail &pa,polymail &pb) { polymail ha,hb,qa,qb; ElemType a; ha=pa; hb=pb; qa=ha->next; qb=hb->next; while(qb) { a=qb->data; switch(comp(pa,a)) { case 0:hb=qb->next;qb->next=ha->next;ha->next=qb;qb=hb;break; case 1:hb=qb->next;free(qb);qb=hb;break; } } free(hb); } int comp(polymail &p,ElemType b) { int n; n=0; polymail q; q=p->next; if(q!=NULL) do { if(b.n==q->data.n) { n=1; break; } q=q->next; }while(q!=NULL); return n; } void print(polymail &p) 分类算法综述 1 分类算法分类是数据挖掘中的一个重要课题。分类的目的是学会一个分类函数或分类模型（也常常称作分类器），该模型能把数据库中的数据项映射到给定类别中的某一个。分类可用于提取描述重要数据类的模型或预测未来的数据趋势。分类可描述如下：输入数据，或称训练集（Training Set），是一条条的数据库记录（Record）组成的。每一条记录包含若干个属性（Attribute），组成一个特征向量。训练集的每条记录还有一个特定的类标签（Class Label）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量：（v1,v2,…, vn ;c）。在这里vi表示字段值，c表示类别。分类的目的是：分析输入数据，通过在训练集中的数据表现出来的特性,为每一个类找到一种准确的描述或者模型。这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新 数据所属的类。注意是预测，而不能肯定，因为分类的准确率不能达到百分之百。我们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个类的知识。 2 典型分类算法介绍解决分类问题的方法很多，下面介绍一些经典的分类方法，分析 各自的优缺点。 2.1 决策树分类算法决策树（Decision Tree）是一种有向无环图（Directed Acyclic Graphics,DAG）。决策树方法是利用信息论中 的信息增益寻找数据库中具有最大信息量的属性字段，建立决策树的一个结点，在根据该属性字段的 不同取值建立树的分支，在每个子分支子集中重复 建立树的下层结点和分支的一个过程。构造决策树 的具体过程为：首先寻找初始分裂，整个训练集作 为产生决策树的集合，训练集每个记录必须是已经 分好类的，以决定哪个属性域（Field）作为目前最 好的分类指标。一般的做法是穷尽所有的属性域， 对每个属性域分裂的好坏做出量化，计算出最好的 一个分裂。量化的标准是计算每个分裂的多样性（Diversity）指标。其次，重复第一步，直至每个叶 节点内的记录都属于同一类且增长到一棵完整的树。分类算法小结
机器学习实战之分类算法
目标跟踪算法的分类
预测模型分类
数据挖掘分类算法的研究与应用
集合概念、表示方法、分类以及集合之间的关系
现代六爻预测的十种分类预测方法
分类算法综述
两个集合合并算法
分类算法综述
相关主题
文本预览