常见的算法梳理

常见的算法梳理2017年08月18日1、归并排序（Mergesort）归并排序由冯•诺依曼于1945年发明，是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（DivideandConquer）的一个非常典型的应用。特也叫归并操作（merge），或者归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。步骤：（1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；（2）设定两个指针，最初位置分别为两个已经排序序列的起始位置；（3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；（4）重复步骤3直到某一指针达到序列尾；（5）将另一序列剩下的所有元素直接复制到合并序列尾。2、快速排序快速排序可采用原地分割方法，也可采用分而治之算法。这不是一种稳定的排序算法，但对于基于RAM（内存）的数组排序来说非常有效。快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由东尼・霍尔在1962年提出一种排序算法。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。设要排序的数组是X「X2……Xn,首先任意选取一个数据作为“基准”（pivot）数据，然后将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)，在这个分区退出之后，该基准就处于数列的中间位置。我们把这个过程称为分区(partition)操作或者叫做一趟快速排序。最后，递归地(recursive)把小于基准值的子数列和大于基准值的子数列进行排序。因为它的算法是内部循环可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。3、堆排序(HeapSort)1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特•弗洛伊德(RobertW.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法。堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是一个近似完全二叉树结构。并同时满足堆性质：即子结点的键值或索引总是小于(或者大于)它的父节点。例如：大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。推排序采用优先级队列来减少数据中的搜索时间。该算法也是原地算法，并非稳定排序。4、选择排序选择排序(Selectionsort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。选择排序是不稳定的排序方法。选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比如序列［5,5,3］第一次就将第一个［5］与［3］交换，导致第一个5挪动到第二个5后面。5、冒泡排序（BubbleSort）冒泡排序（台湾译为：泡沫排序或气泡排序）是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。步骤：（1）比较相邻的元素，如果第一个比第二个大，就交换他们两个。（2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。（3）针对所有的元素重复以上的步骤，除了最后一个。（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。6、插入排序（InsertionSort）插入排序的算法描述是一种简单直观的排序算法。插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为0（^2）。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到0（1）的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。步骤：（1）从第一个元素开始，该元素可以认为已经被排序；（2）取出下一个元素，在已经排序的元素序列中从后向前扫描；（3）如果该元素（已排序）大于新元素，将该元素移到下一位置；（4）重复步骤3,直到找到已排序的元素小于或者等于新元素的位置；（5）将新元素插入到该位置中；（6）重复步骤2。其基本基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。7、希尔排序（ShellSort）希尔排序是DonaldShell于1959年提出而得名，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序的以下两点性质而提出改进方法的：（1）插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。2、插入排序一般来说也是低效的，因为插入排序每次只能将数据移动一位。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。先取一个小于n的整数d作为第一个增量，把文件的全部记录分组。所有1距离为d的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，1取第二个增量d2Vdi重复上述的分组和排序，直至所取的增量dt=1（dt<dLjYdjq）,即所有记录放在同一组中进行直接插入排序为止。8、傅里叶变换傅立叶变换表示能将满足一定条件的某个函数表示成三角函数（正弦和或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅立叶变换具有多种不同的变体形式，如连续傅立叶变换和离散傅立叶变换。最初傅立叶分析是作为热过程的解析分析的工具被提出的。傅立叶变换是一种分析信号的方法，它可分析信号的成分，也可用这些成分合成信号。许多波形可作为信号的成分，比如正弦波、方波、锯齿波等，傅立叶变换用正弦波作为信号的成分。傅里叶变换在物理学、电子类学科、数论、组合数学、信号处理、概率论、统计学、密码学、声学、光学、海洋学、结构动力学等领域都有着广泛的应用（例如在信号处理中，傅里叶变换的典型用途是将信号分解成频率谱一一显示与频率对应的幅值大小）。9、快速傅里叶变换快速傅里叶变换利用计算机计算离散傅里叶变换（DFT）的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。有限长序列可以通过离散傅里叶变换（DFT）将其频域也离散化有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换。1965年，Cooley和Tukey提出了计算离散傅里叶变换（DFT）的快速算法，将DFT的运算量减少了几个数量级。从此，对快速傅里叶变换GFT）算法的研究便不断深入，数字信号处理这门新兴学科也随FFT的出现和发展而迅速发展。根据对序列分解与选取方法的不同而产生了FFT的多种算法，基本算法是基2DIT和基2DIF。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。快速傅里叶变换的基本思想是把原始的N点序列，依次分解成一系列的短序列。充分利用DFT计算式中指数因子所具有的对称性质和周期性质，进而求出这些短序列相应的DFT并进行适当组合，达到删除重复计算，减少乘法运算和简化结构的目的。此后，在这思想基础上又开发了高基和分裂基等快速算法，随着数字技术的高速发展，1976年出现建立在数论和多项式理论基础上的维诺格勒傅里叶变换算法（WFTA）和素因子傅里叶变换算法。它们的共同特点是，当N是素数时，可以将DFT算转化为求循环卷积，从而更进一步减少乘法次数，提高速度。快速傅里叶变换是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的

理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。10、迪杰斯特拉(Dijkstra)算法Dijkstra是一种图谱搜索算法。许多问题都可以建模为图谱，然后利用Dijkstra寻找两个节点之间的最短路径。如果没有Dijkstra算法，互联网的运营效率必将大大降低。虽然今天我们已经有了更好的寻找最短路径的解决方案，但出于稳定性的要求，Dijkstra算法仍然被很多系统使用。11、RSA算法RSA公钥加密算法是1977年由罗纳德•李维斯特(RonRivest)、阿迪•萨莫尔(AdiShamir)和伦纳德•阿德曼(LeonardAdleman)一起提出的。RSA就是他们三人姓氏开头字母拼在一起组成的。RSA是目前最有影响力和最常用的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。它是第一个既能用于数据加密也能用于数字签名的算法。RSA算法基于一个十分简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。在公开密钥密码体制中，加密密钥(即公开密钥)PK是公开信息，而解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的三十多年里，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。12、MD5算法（MD5）MD5算法（英文名MessageDigestAlgorithm，中文名为消息摘要算法第五版）用于确保信息传输完整一致，是计算机广泛使用的杂凑算法之一（又译摘要算法、哈希算法），主流编程语言普遍已有MD5实现。将数据（如汉字）运算为另一固定长度值，是杂凑算法的基础原理，MD5的前身有MD2、MD3和MD4。MD5算法具有以下特点：1、压缩性：任意长度的数据，算出的MD5值长度都是固定的。2、容易计算：从原数据计算出MD5值很容易。3、抗修改性：对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。4、强抗碰撞：已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。MD5的作用是让大容量信息在用数字签名软件签署私人密钥前被〃压缩〃成一种保密的格式（就是把一个任意长度的字节串变换成一定长的十六进制数字串）。除了MD5以外，其中比较有名的还有sha-1、RIPEMD以及Haval等。一般用于快速查找和加密算法。MD5应用（1）一致性验证MD5的典型应用是对一段信息（Message）产生信息摘要（Message-Digest）,以防止被篡改。比如，在Unix下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如：MD5（tanajiya.tar.gz）=38b8c2c1093dd0fec383a9d9ac940515这就是tanajiya.tar.gz文件的数字签名。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的MD5信息摘要。为了让读者朋友对MD5的应用有个直观的认识，笔者以一个比方和一个实例来简要描述一下其工作过程：大家都知道，地球上任何人都有自己独一无二的指纹，这常常成为司法机关鉴别罪犯身份最值得信赖的方法；与之类似，MD5就可以为任何文件（不管其大小、格式、数量）产生一个同样独一无二的“数字指纹”，如果任何人对文件做了任何改动，其MD5值也就是对应的“数字指纹”都会发生变化。我们常常在某些软件下载站点的某软件信息中看到其MD5值，它的作用就在于我们可以在下载该软件后，对下载回来的文件用专门的软件（如WindowsMD5Check等）做一次MD5校验，以确保我们获得的文件与该站点提供的文件为同一文件。具体来说文件的MD5值就像是这个文件的“数字指纹”。每个文件的MD5值是不同的，如果任何人对文件做了任何改动，其MD5值也就是对应的“数字指纹”就会发生变化。比如下载服务器针对一个文件预先提供一个MD5值，用户下载完该文件后，用我这个算法重新计算下载文件的MD5值，通过比较这两个值是否相同，就能判断下载的文件是否出错，或者说下载的文件是否被篡改了。利用MD5算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。（2）数字签名MD5的典型应用是对一段Message（字节串）产生fingerprint（指纹），以防止被“篡改”。举个例子，你将一段话写在一个叫readme.txt文件中，并对这个readme.txt产生一个MD5的值并记录在案，然后你可以传播这个文件给别人，别人如果修改了文件中的任何内容，你对这个文件重新计算MD5时就会发现（两个MD5值不相同）。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的“抵赖”，这就是所谓的数字签名应用。（3）安全访问认证MD5还广泛用于操作系统的登陆认证上，如Unix、各类BSD系统登录密码、数字签名等诸多方面。如在Unix系统中用户的密码是以MD5（或其它类似的算法）经Hash运算后存储在文件系统中。当用户登录的时候，系统把用户输入的密码进行MD5Hash运算，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。MD5将任意长度的“字节串”映射为一个128bit的大整数，并且是通过该128bit反推原始字符串是困难的，换句话说就是，即使你看到源程序和算法描述，也无法将一个MD5的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个，这有点象不存在反函数的数学函数。所以，要遇到了md5密码的问题，比较好的办法是：你可以用这个系统中的md5（）函数重新设一个密码，如admin，把生成的一串密码的Hash值覆盖原来的Hash值就行了。正是因为这个原因，现在被黑客使用最多的一种破译密码的方法就是一种被称为〃跑字典〃的方法。有两种方法得到字典，一种是日常搜集的用做密码的字符串表，另一种是用排列组合方法生成的，先用MD5程序计算出这些字典项的MD5值，然后再用目标的MD5值在这个字典中检索。我们假设密码的最大长度为8位字节（8Bytes），同时密码只能是字母和数字，共26+26+10=62个字节，排列组合出的字典的项数则是P（62,1）+P（62,2）….+P（62,8），那也已经是一个很天文的数字了，存储这个字典就需要TB级的磁盘阵列，而且这种方法还有一个前提，就是能获得目标账户的密码MD5值的情况下才可以。这种加密技术被广泛的应用于Unix系统中，这也是为什么Unix系统比一般操作系统更为坚固一个重要原因。13、整数因子分解整数分解，又称质因子分解。这是一个在计算领域使用频繁的数学算法。在数学中，整数分解问题是指：给出一个正整数，将其写成几个素数的乘积。根据算术基本定理，这样的分解结果应该是独一无二的。这个问题在代数学、密码学、计算复杂性理论和量子计算机等领域中有重要意义。如果没有这一算法，密码术就会变得不安全得多。整数因子分解是用来将一个合数分解成一系列素因子的一系列步骤。整数因子分解可被视为是FNP问题（FNP是难以解决的典型NP问题的扩展）。许多密码协议均基于难以分解的大型合数或相关问题。比方说前面提到的RSA问题。如果有算法能够有效分解任意数字，那么就会使得基于RSA的公钥密码系统陷入不安全的境地。而量子计算的诞生则令此问题的解决变得容易，从而也打开了一个全新的领域，可利用量子世界的属性来令系统更加安全。14、链接分析链接分析算法首先由GabrielPinski和FrancisNarin在1976年发明。其背后的思路很简单，即把图谱以矩阵的形式表示，从而转为特征值问题，而特征值有助于了解图谱结构及每个节点的相对重要性。链接分析是指源于对Web结构中超链接的多维分析。目前其主要应用体现在网络信息检索、网络计量学、数据挖掘、Web结构建模等方面。搜索引擎是如何进行网页的相关性排序。除了查看网页本身的关键词密度和关键词位置外，还要看一个更重要的要素，就是链接流行度（或称之为链接分析），几个方面结合起来就能让排序更加精确。链接流行度的原理是，一个网页拥有的反向链接越多，就越有可能是高质量网页，不然也不会有更多人愿意为其做链接。因此，在其他因数相同的条件下，反向链接越多的网页排名更靠前。链接流行度分析并不是等于简单的链接数相加，因为链接重要性各不相同，链接向你的网页越权威，效果就会越好。那么搜索引擎又是如何判断是否权威网站呢？被大量高权威值的网站链接着的站点就是权威网站。但仅仅链接本身还不足以让网页获得好的排名，因为这些链接可能并非与用户搜索的关键词相关。于是，链接的相关性便成为链接流行度分析的重要部分，除了网站主题是否相关之外，锚文本（锚文本又称锚文本链接）出现关键词也是非常重要的。在互联网时代，不同实体间关系的分析至关重要。从搜索引擎和社交网络到营销分析工具，每个人都想找出互联网的真正结构。链接分析无疑是公众对算法的最大困惑与迷思之一。其问题在于进行链接分析有不同的方式，而增加一些特征就会令每一算法略有不同(从而使得算法受到专利保护)，但基本上这些算法都是类似的。外链作为seo优化必备的手段，其重要的的地位无可取代，是因为众多搜索引擎都将外链分析列为网站排名的第一关键要素，当然最重要的还是用户体验，其次就是网站的外链。15、比例积分微分算法在工程实际中，应用最为广泛的调节器控制规律为比例、积分、微分控制，简称PID控制，又称PID调节。PID控制器问世至今已有近70年历史，它以其结构简单、稳定性好、工作可靠、调整方便而成为工业控制的主要技术之一。PID是一个闭环控制算法。因此要实现PID算法，必须在硬件上具有闭环控制，就是得有反馈。比如控制一个电机的转速，就得有一个测量转速的传感器，并将结果反馈到控制路线上，下面也将以转速控制为例。PID是比例(P)、积分(I)、微分(D)控制算法。但并不是必须同时具备这三种算法，也可以是PD,PI,甚至只有P算法控制。我以前对于闭环控制的一个最朴素的想法就只有P控制，将当前结果反馈回来，再与目标相减，为正的话，就减速，为负的话就加速。现在知道这只是最简单的闭环控制算法。比例(P)、积分(I)、微分(D)控制算法各有作用：比例，反应系统的基本(当前)偏差e(t)，系数大，可以加快调节，减小误差，但过大的比例使系统稳定性下降，甚至造成系统不稳定；积分，反应系统的累计偏差，使系统消除稳态误差，提高无差度，因为有误差，积分调节就进行，直至无误差；微分，反映系统偏差信号的变化率e(t)-e(t-1)，具有预见性，能预见偏差变化的趋势，产生超前的控制作用，在偏差还没有形成之前，已被微分调节作用消除，因此可以改善系统的动态性能。但是微分对噪声干扰有放大作用，加强微分对系统抗干扰不利。该算法利用了控制回路机制来让期望输出信号与实际输出信号之间的错误降到最小。只要需要信号处理或需要电子系统来控制自动化的机械、水力或热力系统就要用到它。16、数据压缩算法数据压缩是指在不丢失有用信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率，或按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间的一种技术方法。数据压缩包括有损压缩和无损压缩。在计算机科学和信息论中，数据压缩或者源编码是按照特定的编码机制用比未经编码少的数据位元（或者其它信息相关的单位）表示信息的过程。一种流行的压缩实例是许多计算机都在使用的zip文件格式，它不仅仅提供了压缩的功能，而且还作为归档工具（Archiver）使用，能够将许多文件存储到同一个文件中。数据压缩算法无疑是非常重要的，因为几乎在所有的结构中都要用到。除了最明显的压缩文档以外，网页下载时也会压缩，视频游戏、视频、音乐、数据存储、云计算、数据库等等也都要使用压缩算法。可以说几乎所有应用都要使用压缩算法。压缩算法令系统更有效成本更低，但是要想确定哪一个最重要却很困难，因为应用不同，使用的压缩算法从zip到mp3、JPEG或MPEG-2各异。17、随机数生成算法随机变量X的抽样序列X1、X2、X2……Xn称为随机数列。若随机变量X是均匀分布的，则X的抽样序列X1、X2、X2……Xn称为均匀随机数列；如果X是正态分布的随机变量，则称其抽样序列为正态随机数列。用数学方法产生随机数，就是利用计算机能直接进行算术运算或逻辑运算的特点，产生具有均匀总体、简单子样统计性质的随机数。计算机利用数学方法产生随机数速度快，占用内存少，对模拟的问题可以进行复算检查，通常还具有较好的统计性质。另外，计算机上用数学方法产生随机数，是根据确定的算法推算出来的，因此严格说来，用数学方法在计算机上产生的“随机数”不能说是真正的随机数，故一般称之为“伪随机数”。不过对这些伪随机数，只要通过统计检验符合一些统计要求，如均匀性、随机性、独立性等，就可以作为真正的随机数来使用。以后，我们统称这样产生的伪随机数为随机数。首先给出产生均匀随机数的方法，这是产生具有其它分布随机数的基础，而后给出产生其它分布随机数的方法。很多应用都需要随机数。像interlinkconnection,密码系统、视频游戏、人工智能、优化、问题的初始条件，金融等都需要生成随机数。但实际上目前我们并没有“真正”的随机数生成器，尽管有一些伪随机数生成器也是非常有效的。当然，十大算法也可能给有凑数之嫌，审视的角度不同对算法的重要性看法也会很不一样，如果你认为这一榜单有错漏的地方，不妨在评论中贡献你的意见。18、分类算法分类就是把一些新得数据项映射到给定类别的中的某一个类别，一般的过程是根据样本数据利用一定的分类算法得到分类规则，新的数据过来就依据该规则进行类别的划分。分类在数据挖掘中是一项非常重要的任务，有很多用途，比如说预测，即从历史的样本数据推算出未来数据的趋向，有一个比较著名的预测的例子就是大豆学习。再比如说分析用户行为，我们常称之为受众分析，通过这种分类，我们可以得知某一商品的用户群，对销售来说有很大的帮助。分类器的构造方法有统计方法、机器学习方法、神经网络方法等等。统计方法有knn算法，基于事例的学习方法。机器学习方法包括决策树法(受众分析可以使用决策树方法来实现)和归纳法。神经网络方法主要是bp算法。(1)单一的分类方法主要包括：决策树、贝叶斯、人工神经网络、K-近邻、支持向量机和基于关联规则的分类等；①决策树决策树是用于分类和预测的主要技术之一，决策树学习是以实例为基础的归纳学习算法，它着眼于从一组无次序、无规则的实例中推理出以决策树表示的分类规则。构造决策树的目的是找出属性和类别间的关系，用它来预测将来未知类别的记录的类别。它采用自顶向下的递归方式，在决策树的内部节点进行属性的比较，并根据不同属性值判断从该节点向下的分支，在决策树的叶节点得到结论。主要的决策树算法有ID3、C4.5(C5.0)、CART、PUBLIC、SLIQ和SPRINT算法等。它们在选择测试属性采用的技术、生成的决策树的结构、剪枝的方法以及时刻，能否处理大数据集等方面都有各自的不同之处。C4.5决策树在ID3决策树的基础之上稍作改进，C4.5克服了ID3的2个缺点：揖用信息增益选择属性时偏向于选择分枝比较多的属性值，即取值多的属性。b.不能处理连贯属性。②贝叶斯(Bayes)贝叶斯(Bayes)分类算法是一类利用概率统计知识进行分类的算法，如朴素贝叶斯(NaiveBayes)算法，还有一种TAN算法(树增强型朴素贝叶斯算法)也是贝叶斯分类算法中重要算法。这些算法主要利用Bayes定理来预测一个未知类别的样本属于各个类别的可能性，选择其中可能性最大的一个类别作为该样本的最终类别。由于贝叶斯定理的成立本身需要一个很强的条件独立性假设前提，而此假设在实际情况中经常是不成立的，因而其分类准确性就会下降。为此就出现了许多降低独立性假设的贝叶斯分类算法，如TAN(TreeAugmentedBayesnetwork)算法，它是在贝叶斯网络结构的基础上增加属性对之间的关联来实现的。该算法能运用到大型数据库中，而且方法简单、分类准确率高、速度快。朴素贝叶斯算法设每个数据样本用一个n维特征向量来描述n个属性的值，即:X={x1，x2,…，xn}，假定有m个类，分别用C1,",…，Cm表示。给定一个未知的数据样本X(即没有类标号)，若朴素贝叶斯分类法将未知的样本X分配给类Ci,则一定是P(Ci|X)>P(Cj|X)1WjWm,j/i根据贝叶斯定理由于P(X)对于所有类为常数，最大化后验概率P(Ci|X)可转化为最大化先验概率P(X|Ci)P(Ci)。如果训练数据集有许多属性和元组，计算P(X|Ci)的开销可能非常大，为此，通常假设各属性的取值互相独立，这样先验概率P(x1|Ci),P(x2|Ci),…，P(xn|Ci)可以从训练数据集求得。根据此方法，对一个未知类别的样本X,可以先分别计算出X属于每一个类别Ci的概率P(X|Ci)P(Ci),然后选择其中概率最大的类别作为其类别。朴素贝叶斯算法成立的前提是各属性之间互相独立。当数据集满足这种独立性假设时,分类的准确度较高，否则可能较低。另外，该算法没有分类规则输出。[1]TAN算法（树增强型朴素贝叶斯算法）TAN算法通过发现属性对之间的依赖关系来降低NB中任意属性之间独立的假设。它是在NB网络结构的基础上增加属性对之间的关联（边）来实现的。实现方法是：用结点表示属性，用有向边表示属性之间的依赖关系，把类别属性作为根结点，其余所有属性都作为它的子节点。通常，用虚线代表NB所需的边，用实线代表新增的边。属性Ai与％之间的边意味着属性Ai对类别变量C的影响还取决于属性'的取值。这些增加的边需满足下列条件：类别变量没有双亲结点，每个属性有一个类别变量双亲结点和最多另外一个属性作为其双亲结点。找到这组关联边之后，就可以计算一组随机变量的联合概率分布如下：其中nAi代表的是Ai的双亲结点。由于在TAN算法中考虑了n个属性中（n-1）个两两属性之间的关联性，该算法对属性之间独立性的假设有了一定程度的降低，但是属性之间可能存在更多其它的关联性仍没有考虑，因此其适用范围仍然受到限制。③人工神经网络人工神经网络（ArtificialNeuralNetworks，ANN）是一种应用类似于大脑神经突触联接的结构进行信息处理的数学模型。在这种模型中，大量的节点（或称“神经元“，或“单元”）之间相互联接构成网络，即“神经网络”，以达到处理信息的目的。神经网络通常需要进行训练，训练的过程就是网络进行学习的过程。训练改变了网络节点的连接权的值使其具有分类的功能，经过训练的网络就可用于对象的识别。目前，神经网络已有上百种不同的模型，常见的有BP网络、径向基RBF网络、Hopfield网络、随机神经网络（Boltzmann机）、竞争神经网络（Hamming网络，自组织映射网络）等。但是当前的神经网络仍普遍存在收敛速度慢、计算量大、训练时间长和不可解释等缺点。④k-近邻k-近邻（kNN，k-NearestNeighbors）算法是一种基于实例的分类方法。该方法就是找出与未知样本x距离最近的k个训练样本，看这k个样本中多数属于哪一类，就把x归为那一类。k-近邻方法是一种懒惰学习方法，它存放样本，直到需要分类时才进行分类，如果样本集比较复杂，可能会导致很大的计算开销，因此无法应用到实时性很强的场合。⑤支持向量机支持向量机(SVM，SupportVectorMachine)是Vapnik根据统计学习理论提出的一种新的学习方法，它的最大特点是根据结构风险最小化准则，以最大化分类间隔构造最优分类超平面来提高学习机的泛化能力，较好地解决了非线性、高维数、局部极小点等问题。对于分类问题，支持向量机算法根据区域中的样本计算该区域的决策曲面，由此确定该区域中未知样本的类别。⑥基于关联规则的分类关联规则挖掘是数据挖掘中一个重要的研究领域。近年来，对于如何将关联规则挖掘用于分类问题，学者们进行了广泛的研究。关联分类方法挖掘形如condsetfC的规则，其中condset是项(或属性-值对)的集合，而C是类标号，这种形式的规则称为类关联规则(classassociationrul