精华内容
下载资源
问答
  • 之前以下三种排序算法属于三篇文章,由于都属于基本排序算法,就合并到了一篇,便于对比。 1、冒泡排序 冒泡排序算法简介: 冒泡排序算法,它是最慢的排序算法之一,但也是一种最容易实现的排序算法。之所以叫...

    之前以下三种排序算法属于三篇文章,由于都属于基本排序算法,就合并到了一篇,便于对比。

    1、冒泡排序

    冒泡排序算法简介:

                 冒泡排序算法,它是最慢的排序算法之一,但也是一种最容易实现的排序算法。 之所以叫冒泡排序是因为使用这种排序算法排序时,数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列,较大的值会浮动到数组的右侧,而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动,比较相邻的数据,当左侧值大于右侧值时将它们进行互换。 

    观察规律:以下是数组[72,  54, 58, 30, 31, 78,  2, 77, 82, 72]在进行小到大排序时的各次排序的结果,第一行为数组初始值。

    注意观察72和2的是如何移动到右边、左边的,之后会以完整代码举例深入剖析。

    解释:在第一次排序中,72与54比较,54移到前面,随后72与58比较,58移到前面......72与78比较时,72小,于是顺序不变,接而78与2对比,2移到前面,接下来78与77比较,77移到前面...于是第一次排序后结果是:54 58 30 31 72 2 77 78 72 82。根据这规律,不难解释接下来的几次排序。

    冒泡排序演练:使用冒泡排序算法对数组[10,1,8,6,7,5,3,4,2,9]进行升序排序。

    实现代码:

    <script>
        function bubbleSort(array) {
            var length = array.length;
            var temp;
            // i可以理解为每次参与排序的项有几个
            // 第一次排序之后,最后一个肯定比前一个大,所以下一次不用再对比最后两个数字
            // 所以i--,减少参与排序的数字的个数,即第二次参与排序的项只有[1,8,6,7,5,3,4,2,9]共9个。
            // 以此类推,最后参与对比的项只有两个,即最后i==2。
            for (var i = length; i >= 2; i--) {
                // 开始循环对比需要对比的项
                for (var j = 0; j <= i - 1; j++) {
                    if (array[j] > array[j + 1]) {
                        // 前面的比后面的大,交换位置
                        temp = array[j];
                        array[j] = array[j + 1];
                        array[j+1] = temp;
                    }
                }
                console.log("第"+(length-i+1)+"次排序结果:"+array.toString()+"--此次参与排序的项为=>"+i); // 用于观察每次排序的结果
            }
            console.log("最终结果:"+array.toString()); // 最终结果
        }
        var array = [10,1,8,6,7,5,3,4,2,9];
        bubbleSort(array);
    </script>

     

    运行结果如图:


     

    总结:

           实现方法几乎每行代码都加以解释,帮助理解;结合每次排序的结果我们可以更加容易地看出小的值是如何移到数组开头的,

    大的值又是如何移到数组末尾的,每次参与排序的项有多少个,冒泡排序神秘的面纱就此揭开。
    

    实现降序排序:实现数组降序排序只需要修改内层循环中的条件判断即可,相信各位能轻易实现。

    if (array[j] < array[j + 1]) {
        // 后面的比前面的大,交换位置
        temp = array[j];
        array[j] = array[j+1];
        array[j+1] = temp;
    }

    降序排序运行结果:

     

    2、选择排序

    升序原理:使用寻找最小值的方法去遍历剩余数组,记录最小值得下标index,然后跟首位交换位置。 
    比如对4 3 6 8 2 9 10进行排序 
    第一次排序后的结果为: 
    2 3 6 8 4 9 10 
    第二次: 
    2 3 6 8 4 9 10 
    因为剩余的数字中3最小,位置不用变化 
    第三次: 
    2 3 4 8 6 9 10 
    第四次 
    …….. 
    按照以上推算,可得到以下实现代码:

    function selectionSort (arr) {
      for (var i = 0; i < arr.length - 1; i++) {
        var min = i
        for (var j = min + 1; j < arr.length; j++) {
          if (arr[j] < arr[min]) {
            min = j;
          }
        }
        if (min !== i) {
          var temp = arr[i];
          arr[i] = arr[min];
          arr[min] = temp;
        }
      }
      return arr
    }
    var array = [4, 3, 6, 8, 2, 9, 10]
    var result = selectionSort(array)
    console.log(result.toString())

    进入控制台,使用node运行此js文件,可见结果为: 
    这里写图片描述

    3、插入排序

    //    插入排序-原理解释:从数组第二项开始循环,每次循环取当前项与前边的项对比,符合条件则交换位置。  
        function insertSort(array) {  
    //        从第二个元素开始循环  
            for (var i = 1; i < array.length; i++) {  
    //          从当前项开始往前对比  
                for (var j = i; j > 0; j--) {  
    //                前面的比后面的大,交换位置  
                    if (array[j-1] > array[j]) {  
                        var temp = array[j];  
                        array[j] = array[j - 1];  
                        array[j - 1] = temp;  
                    }  
                }  
            }  
            console.log(array.toString());  
        }  
        insertSort([1,4,5,7,2,9,8]);  

    运行结果:

    4、快速排序

      function quickSort (arr) {
        let length = arr.length
        if (length <= 1) {
          return arr
        }
        let base = arr[length - 1]
        let left = [], right = []
        for (let i = 0; i < length - 1; i++) {
          if(arr[i] > base) {
            right.push(arr[i])
          } else {
            left.push(arr[i])
          }
        }
        return [...quickSort(left), base, ...quickSort(right)]
      }
      console.log(quickSort([3,23,66,32,2,77,45,87,64,34,33]))

    运行结果:

    展开全文
  • Day3 算法基本要素

    千次阅读 2021-01-22 19:59:13
    Day3 算法基本要素


    算法目录

    既然我要学算法,那我就得知道,到底算法是什么?今天我们来聊一下,什么是一个算法(Algorithm)?难道程序就等于算法么?
    首先我们可以看一下下面两张图对算法的定义

    算法(Algorithm)

    在这里插入图片描述
    算法是解决问题的明确指令序列,满足以下要求
    (1) Input: O个或多个有效的输入值(2)输出:至少产生一个值明确的:每条指令/每一步都清楚、准确、明确地规定了(4)有限性:指令有限,每条指令的执行时间有限,每条指令的运行时间有限
    (1)输入: 0个或多个有效的输入值
    (2)输出:至少输出一个有效值
    (3)明确:每条指令/每一步都清楚、准确
    (4)有穷性:指令有限,每条指令的执行时间有限,每条指令的运行时间有限

    程序(Program)

    在这里插入图片描述
    程序

    • 基于该算法的问题解决方案的实现编码
    • 可以无限执行
    • 如操作系统:不是一个算法,而是一个根据具体算法无限循环运行的程序
    • 可以将每个任务视为子程序

    总结

    总是有很多人说要学算法,但是他们总是无法弄清楚算法到底是什么,只知道这是一个很不错的东西,但是不明白,只知道去写,认为自己能打程序就说明自己很懂算法了
    这里我想借用一句话和两个公式大概可以回答什么是算法以及程序和算法的区别

    Computer science should be called computing science, for the same reason why surgery is not called knife science.

    我理解的算法本质是计算机模型

    Algorithms + Data Structures = Programs
    算法 + 数据结构 = 程序
    (Algorithms + Data Structures) * Efficiency = Computation

    数据结构是一种存储和组织数据的方式,旨在便于访问和修改。

    我们常见会见到一个问题,如果将一个大学放进冰箱里,其实很简单,只需要三步即可
    1.打开冰箱
    2.把大象放进冰箱
    3.关上冰箱
    这也是一个简单的算法哦
    在这里插入图片描述

    补充

    根据清华大学邓俊辉老师的解释,算法的特质包括但不限于这些:
    在这里插入图片描述

    每日一句
    Those who turn back never reach the summit.(回头的人永远到不了最高峰!)

    展开全文
  • 算法

    万次阅读 2018-02-08 00:13:09
    1.算法定义 ...如果一个算法有缺陷,或适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

    1.算法定义

    算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

    一个算法应该具有以下七个重要的特征:
    ①有穷性(Finiteness):算法的有穷性是指算法必须能在执行有限个步骤之后终止;
    ②确切性(Definiteness):算法的每一步骤必须有确切的定义;
    ③输入项(Input):一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输 入是指算法本身定出了初始条件;
    ④输出项(Output):一个算法有一个或多个输出,以反映对输入数据加工后的结果。没 有输出的算法是毫无意义的;
    ⑤可行性(Effectiveness):算法中执行的任何计算步骤都是可以被分解为基本的可执行 的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性);
    ⑥高效性(High efficiency):执行速度快,占用资源少;
    ⑦健壮性(Robustness):对数据响应正确。

    2. 时间复杂度

    计算机科学中,算法的时间复杂度是

    展开全文
  • 机器学习之基本算法总结

    千次阅读 2015-10-30 15:10:27
    机器学习方法越来越得到关注与学习,很多人在研读机器学习相关文章和算法时,对一些概念不慎明确,容易走进坑里花费太多的时间才弄明白,有作者将一些并不是很简单的基础知识算法做了一定的总结。本文在原博文的基础...

    机器学习方法越来越得到关注与学习,很多人在研读机器学习相关文章和算法时,对一些概念不慎明确,容易走进坑里花费太多的时间才弄明白,有作者将一些并不是很简单的基础知识算法做了一定的总结。本文在原博文的基础上根据自己的阅读和理解,做了一些补充,对概念和算法的总结如下。


    1.基础概念:

    以下这些基础概念基本上是在所有的机器学习算法中都会遇到。这些概念的背后是一系列数据处理的思想,它们包含了数据的降维去噪,验证处理,分布监测等等

    (1) 10折交叉验证:英文名是10-fold cross-validation,用来测试算法的准确性。是常用的测试方法。将数据集分成10份。轮流将其中的9份作为训练数据,1分作为测试数据,进行试验。每次试验都会得出相应的正确率(或差错率)。10次的结果的正确率(或差错率)的平均值作为对算法精度的估计,一般还需要进行多次10折交叉验证,在求其平均值,对算法的准确性进行估计。

    (2) 极大似然估计:极大似然估计,只是一种概率论在统计学中的应用,它是参数评估的方法之一。如果已知某个随机样本满足某种概率分布,但是其中具体的参数不清楚,参数估计通过若干次实验,观察其结果,利用结果推出参数的大概值。极大似然估计是建立在这样的思想上的:已知某个参数能使这个样本出现的概率最大。我们当然不会再去选择其他其他小概率的样本,所以干脆就把这个参数作为估计的真实值。

    (3) 熵:在信息论中,熵表示的是不确定性的量度。信息论的创始人香农在其著作《通信的数学理论》中提出了建立在概率统计模型上的信息度量。他把信息定义为”用来消除不确定性的东西“。熵的定义为信息的期望值,具体到机器学校里可以表示数据的离散程度。

    ps:熵指的是体系的混乱程度,它在控制论,概率论,数论,天体物理,生命科学等领域都有重要的应用,在不同的学科中也有引申出更为具体的定义,是各个领域十分重要的参量。熵由鲁道夫.克劳修斯提出,并应用在热力学中。后来在,克劳德.埃尔伍德.香农 第一次将熵的概念引入到信息论中来。

    (4) 后验概率:信息论的基本概念之一,指的是在一个通信系统中,在收到某个消息之后,接收端所了解到的该消息发送的概率称为后验证概率。后验概率是指在得到”结果“的信息后重新修正的概率,如贝叶斯公式中的,是执果寻因的问题。后验概率和先验概率有着不可分割的联系,后验的计算要以先验概率为基础,其实说白了后验概率其实就是条件概率。

    (5) PCA 主成分分析:
    优点:降低数据的复杂性,识别最重要的多个特征。
    缺点:不一定需要,且可能损失有用信息。
    适用适用类型:数值型数据。
    技术类型:降维技术。

    简述:在PCA中,数据从原来的坐标系转换到了新的坐标系,新坐标系的选择是由数据本身决定的。第一个新坐标轴选择时原始数据中方差最大的方向,第二个新坐标轴的选择和第一个坐标轴正交且具有最大方差的方向。该过程一直重复,重复次数为原始数据中特征的数目。会发现大部分方差都包含在最前面的几个新坐标轴中。因此,可以忽略余下的坐标轴,即对数据进行了降维处理。除了PCA主成分分析技术,其他降维技术还有ICA(独立成分分析),因子分析等。

    (6) 将不同的分类器组合起来,而这种组合结果则被称为集成方法(ensemble method)或者元算法(meta-algorithm)。

    (7) 回归算法和分类算法很像,不过回归算法和分类算法输出标称型类别值不同的是,回归方法会预测出一个连续的值,即回归会预测出具体的数据,而分类只能预测类别,具体就是拟合的最终数据形式不同,一个连续,一个离散。

    (8) SVD(singular value decomposition) 奇异值分解:
    优点:简化数据,去除噪声,提高算法的结果。
    缺点:数据转换可能难以理解。
    适用数据类型:数值型数据。
    ps:SVD是矩阵分解的一种类型。

    总结:SVD是一种强大的降维工具,我们可以利用SVD来逼近矩阵并从中提取重要特征。通过保留矩阵80%~90%的能量,就可以得到重要的特征并去掉噪声。SVD已经运用到多个应用中,其中一个成功的应用案例就是推荐引擎。推荐引擎将物品推荐给用户,协同过滤则是一种基于用户喜好和行为数据的推荐和实现方法。协同过滤的核心是相似度计算方法,有很多相似度计算方法都可以用于计算物品或用户之间的相似度。通过在低维空间下计算相似度,SVD提高了推荐引擎的效果。

    (9)共线性:是指线性回归模型中的解释变量之间由于存在精确的相关关系或高度相关关系而使模型估计失真或难以估计。

    2.基本算法

    以下这些算法都是机器学习中一些基本的处理算法,都是核心处理思想简单,但是解决某些问题非常有效。

    2.1 Logistic回归:

    优点:计算代价不高,易于理解和实现。
    缺点:容易欠拟合,分类精度可能不高。
    适用数据类型:数值型和标称型数据。
    类别:分类算法。
    试用场景:解决二分类问题。

    简述:Logistic回归算法基于Sigmoid函数,或者说Sigmoid就是逻辑回归函数。Sigmoid函数定义如下:1/(1+exp(-z))。函数值域范围(0,1)。可以用来做分类器。
    Sigmoid函数的函数曲线如下:


    逻辑回归模型分解如下: 

    (1)首先将不同维度的属性值和对应的一组权重加和,公式如下:

     z = w0+w1*x1+w2*x2+…+wm*xm(其中x1,x2,…,xm是某样本数据的各个特征,维度为m)
    ps:z在这里就是一个线性回归。W权重值就是需要经过训练学习到的数值,具体W向量的求解,就需要用到极大似然估计和将似然估计函数代入到 优化算法来求解。最常用的最后化算法有 梯度上升算法。
    由上面可见:逻辑回归函数虽然是一个非线性的函数,但其实其去除Sigmoid映射函数之后,其他步骤都和线性回归一致。

    (2)然后将上述的线性目标函数 z 代入到sigmond逻辑回归函数,可以得到值域为(0,0.5)和(0.5,1)两类值,等于0.5的怎么处理还以自己定。这样其实就得到了2类数据,也就体现了二分类的概念。

    总结:Logistic回归的目的是寻找一个非线性函数Sigmoid的最佳拟合参数,它的本质是求解概率,根据概率的分布就可以将结果划分为二分类问题,其中最关键的是W的求解,参数的求解过程可以由最优化算法来完成。在最优化算法中,最常用的就是梯度上升算法,而梯度上升算法有可以简化为随机梯度上升算法。随机梯度下降算法具体的方法后续会做详细分析。

    博文《逻辑回归》中给出了非常漂亮的公式推导过程以及梯度求导额逻辑回归的问题分析

    http://blog.csdn.net/pakko/article/details/37878837

    2.2 SVM(Support Vector Machines) 支持向量机

    优点:泛化错误率低,计算开销不大,结果易解释。
    缺点:对参数调节和核函数的选择敏感,原始分类器不加修改仅适用于处理二分类问题。
    适用数据类型:数值型和标称型数据。
    类别:分类算法。
    试用场景:解决二分类问题。

    简述:通俗的讲,SVM是一种二类分类模型,其基本模型定义为特征空间上的间隔最大的线性分类器,即支持向量机的学习策略便是间隔最大化,最终可转化为一个凸二次规划问题的求解。或者简单的可以理解为就是在高维空间中寻找一个合理的超平面将数据点分隔开来,其中涉及到非线性数据到高维的映射以达到数据线性可分的目的。

    支持向量概念:

    5a9c4a22f556c803716815def7fff078

     

    上面样本图是一个特殊的二维情况,真实情况当然可能是很多维。先从低纬度简单理解一下什么是支持向量。从图中可以看到3条线,中间那条红色的线到其他两条先的距离相等。这条红色的就是SVM在二维情况下要寻找的超平面,用于二分类数据。而支撑另外两条线上的点就是所谓的支持向量。从图中可以看到,中间的超平面和另外两条线中间是没有样本的。找到这个超平面后,利用超平面的数据数学表示来对样本数据进行二分类,就是SVM的机制了。

    ps: 《机器学习实战》书中有这么几个概念:

    (1)如果能找到一个直线(或多维的面)将样本点分开,那么这组数据就是线性可分的。将上述数据集分隔开来的直线(或多维的面)称为分隔超平面。分布在超平面一侧的数据属于一个类别,分布在超平面另一侧的数据属于另一个类别
    (2)支持向量(Support vector)就是分离超平面最近的那些点。
    (3)几乎所有分类问题都可以使用SVM,值得一提的是,SVM本身是一个二分类分类器,对多类问题应用SVM需要对代码做一些修改。

    公式:
    SVM有很多实现,但是本章值关注其中最流行的一种实现,及序列最小优化(Sequential Minimal Optimization,SMO)算法。
    其公式如下:

    f0591dcad561e38e06d6fd691a28fe25

    SMO算法的目标是求出一些列的alpha,一旦求出了alpha,就很容易计算出权重向量w并得到分隔超平面。

    SMO算法的工作原理是:每次循环中选择两个alpha进行优化处理。一旦找到一对合适的alpha,那么就增大其中一个同时减小另一个。这里所谓的“合适”就是指两个alpha必须符合一定的条件,条件之一就是这两个alpha必须要在间隔边界之外,而其第二个条件则是这两个alpha还没有进行过区间化处理或者不在边界上。

    核函数将数据从低维度映射到高维:
    SVM是通过寻找超平面将数据进行分类的,但是当数据不是线性可分的时候就需要利用核函数将数据从低维映射到高维使其线性可分后,在应用SVM理论。

    93c1d8bf3bf14c8072c04cb4e1b13827

     

    示例:

    这个二维数据分布不是线性可分的,其方程为:

    20130820145508875

    但是通过核函数维度映射后,其变为:

     

    对应的方程为:

    20130820145544562

    这样映射后的数据就变成了线性可分的,就可以应用SVM理论了。

    总结:支持向量机是一种分类器。之所以成为“机”是因为他会产生一个二值决策结果,即它是一种‘决策’机。核方法或者说核技巧会将数据(有时是非线性数据)从一个低维空间映射到一个高维空间,可以将一个在低维空间中的非线性问题转换为高维空间下的线性问题来求解。

    SVM算法是及其经典的一种算法,此算法有很多种变形,被研究者津津乐道,其中研究者July的博文《 机器学习之支持向量机通俗导论(理解SVM的三层境界)》是非常经典且详细的一篇博文,深入浅出的逐一理解分析支持向量机。源文链接如下:http://www.cnblogs.com/v-July-v/archive/2012/06/01/2539022.html

    2.3 决策树
    决策树归纳是经典的分类算法。它采用自顶向下递归的方式构造决策树。树的每一个结点上使用一种规则将数据特征分为左右两部分,分成的两部分各自再继续进行划分,直到满足一定条件,停止划分,叶子节点保存数据的标签或者数值,节点上保存分裂函数或者特征阈值。决策树主要有ID3,ID45和CART三种,前两者使用信息论中的信息增益率(信息论中的概念,衡量是否是有益划分的量)选择测试属性,CART主要用于回归树,使用的是某一种测试误差作为分别规则,树回归将数据集切分成多份易建模的数据,然后利用线性回归进行建模和拟合。

    优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据。
    缺点:可能会产生匹配过度问题。
    适用数据类型:数值型和标称型。
    数据要求:树的构造只适用于标称型的数据,因此数值型数据必须离散化。

    简述:在构造决策树时,我们需要解决的第一个问题就是,当前数据集上哪个特征在划分数据分类时起决定性作用。以ID3决策树为例,为了找到决定性特征,划分出最好的结果,我们必须评估每个特征。完成测试后,原始数据就被划分为几个数据子集。这些数据的子集分布在第一个决策点的所有分支上,如果某个分支下的数据属于同一个类型,则无需进一步对数据集进行切割。反之则需要进一步切割。

    在可以评测哪种数据划分方式是最好的数据划分之前,我们必须学习如何计算信息增益。集合的信息度量方式称为香农熵或者简称为熵。熵在信息论中定义为信息的期望值。

    信息熵的计算公式为:
    H(信息熵) = -∑ P(xi) log2P(xi) ps:其中p(xi)表示选择该分类的概率。

    下面简述一下生成决策树的步骤:
    (1) 根据给定的训练数据,根据熵最大原则根据每一个维度来划分数据集,找到最关键的维度。
    (2) 当某个分支下所有的数据都数据同一分类则终止划分并返回类标签,否则在此分支上重复实施(1)过程。
    (3) 依次计算就将类标签构建成了一棵抉择树。
    (4) 依靠训练数据构造了决策树之后,我们就可以将它用于实际数据的分类。

    决策树中一个比较严重的问题是过拟合,所以经常需要对决策树进行剪枝。其实就是节点的合并,即将不必要的叶子节点和分裂节点进行合并,减少不必要的计算和复杂度。

    总结决策树分类器就像带有终止块的流程图,终止块表示分类结果。开始处理数据集时,我们首先需要测量集合中数据的不一致性,也就是熵,然后寻找最优的方案划分数据集,直到数据集中的所有数据属于同一个分类。

    决策树单独使用的情况比较少,稍微大一些的数据处理中基本用的都是森林,即将很多棵树组成到一起进行决策,森林中最著名的算法就是随机森林。关于随进森林一篇比价好的文章是

    http://blog.csdn.net/Armily/article/details/8923961

    2.4 朴素贝叶斯
    优点:在数据较少的情况下仍然有效,可以处理多类别问题。
    缺点:对于输入数据的准备方式较为敏感。
    适用的数据类型:标称型数据。
    算法类型:分类算法

    简述:朴素贝叶斯是贝叶斯理论的一部分,贝叶斯决策理论的核心思想,即选择具有高概率的决策。朴素贝叶斯之所以冠以朴素开头,是因为其在贝叶斯理论的基础上做出了两点假设:
    (1)每个特征之间相互独立。
    (2)每个特征同等重要。
    贝叶斯准则是构建在条件概率的基础之上的,其公式如下:

    P(H|X)=P(X|H)P(H)/P(X)

    ps:P(H|X)是根据X参数值判断其属于类别H的概率,称为后验概率。P(H)是直接判断某个样本属于H的概率,称为先验概率。P(X|H)是在类别H中观测到X的概率(后验概率),P(X)是在数据库中观测到X的概率。可见贝叶斯准则是基于条件概率并且和观测到样本的先验概率和后验概率是分不开的。

    总结:对于分类而言,使用概率有事要比使用硬规则更为有效。贝叶斯概率及贝叶斯准则提供了一种利用已知值来估计未知概率的有效方法。可以通过特征之间的条件独立性假设,降低对数据量的需求。尽管条件独立性的假设并不正确,但是朴素贝叶斯仍然是一种有效的分类器。

    2.5 K-近邻算法(KNN)
    优点:精度高、对异常值不敏感、无数据输入假定。
    缺点:计算复杂度高,空间复杂度搞。
    适用数据范围:数值型和标称型。
    算法类型:分类算法。

    简述:算法原理,存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一个数据与所属分类的对应关系。输入没有标签的新数据后,将新数据的每个特征和样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标签。一般来说,我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类,作为新数据的分类。

    kNN算法的具体实现步骤见博文http://blog.csdn.net/zhaofrjx/article/details/47686359

    2.6 线性回归(Linear Regression)
    优点:结果易于理解,计算上不复杂。
    缺点:对非线性数据拟合不好。
    适用数据类型:数值型和标称型数据。
    算法类型:回归算法。
    ps:回归于分类的不同,就在于其目标变量时连续数值型。

    简述:在统计学中,线性回归(Linear Regression)是利用称为线性回归方程的最小平方函数对一个或多个自变量和因变量之间关系进行建模的一种回归分析。这种函数是一个或多个称为回归系数的模型参数的线性组合(自变量都是一次方)。只有一个自变量的情况称为简单回归,大于一个自变量情况的叫做多元回归。

    线性方程的模型函数的向量表示形式为:

    b56cacd2f3f00b7588d2c1c20f45dfc1

    通过训练数据集寻找向量系数的最优解,即为求解模型参数。其中求解模型系数的优化器方法可以用“最小二乘法”、“梯度下降”算法,来求解损失函数:

    b01388e05ff4e2c5cfb0b974c7ad9b0b的最优值。

    附加:岭回归(ridge regression):
    岭回归是一种专用于共线性数据分析的有偏估计回归方法,实质上是一种改良的最小二乘估计法,通过放弃最小二乘法的无偏性,以损失部分信息、降低精度为代价,获得回归系数更为符合实际、更可靠的回归方法,对病态数据的耐受性远远强于最小二乘法。

    岭回归分析法是从根本上消除复共线性影响的统计方法。岭回归模型通过在相关矩阵中引入一个很小的岭参数K(1>K>0),并将它加到主对角线元素上,从而降低参数的最小二乘估计中复共线特征向量的影响,减小复共线变量系数最小二乘估计的方法,以保证参数估计更接近真实情况。岭回归分析将所有的变量引入模型中,比逐步回归分析提供更多的信息。

    总结:与分类一样,回归也是预测目标值的过程。回归与分类的不同点在于,前者预测连续型的变量,而后者预测离散型的变量。回归是统计学中最有力的工具之一。在回归方程里,求得特征对应的最佳回归系统的方法是最小化误差的平方和。

    2.7 K-Means(K 均值算法)
    优点:容易实现。
    缺点:可能收敛到局部最小值,在大规模数据集上收敛较慢。
    适用数据类型:数值型数据。
    算法类型:聚类算法。
    ps:K-Means和上面的分类和回归算法不同,它属于非监督学习算法。类似分类和回归中的目标变量事先并不存在。与前面“对于数据变量X能预测变量Y”不同的是,非监督学习算法要回答的问题是:“从数据X中能发现什么?“,这里需要回答的X方面可能的问题是:”构成X的最佳6个数据簇都是哪些“或者”X中哪三个特征最频繁共现?“。

    K-Means的基本步骤:
    (1) 从数据对象中随机的初始化K个初始点作为质心。然后将数据集中的每个点分配到一个簇中,具体来讲每个点找到距其最近的质心,并将其分配给该质心所对应的簇。
    (2) 计算每个簇中样本点的均值,然后用均值更新掉该簇的质心。然后划分簇结点。
    (3) 迭代重复(2)过程,当簇对象不再发生变化时,或者误差在评测函数预估的范围时,停止迭代。
    算法的时间复杂度上界为O(nkt), 其中t是迭代次数。
    ps:初始的K个质心的选取以及距离计算公式的好坏,将影响到算法的整体性能。
    附加:
    二分K-均值算法:为克服K-均值算法收敛于局部最小值的问题,有人提出了另一个称为二分K-均值(bisecting K-Means)的算法。该算法首先将所有点作为一个簇,然后将簇一分为二。之后选择其中一个簇继续划分,选择哪个一簇进行划分取决于对其划分是否可以最大程度降低SSE(Sum of Squared Error,两个簇的总误差平方和)的值。

     kmeans的算法步骤和具体实现过程见博文http://blog.csdn.net/zhaofrjx/article/details/47829789

    2.8 算法关联分析
    首先了解两个概念:
    频繁项集(frequent item sets):经常出现在一块的物品的集合。
    关联规则(association rules):暗示两种物品间可能存在很强的关系。
    项集的支持度(support):数据集中包含该项集记录所占的比例。
    关联分析的目标包括两项:发现频繁项集合发现关联规则。首先找到频繁项集,然后才能获得关联规则。

    Apriori算法:
    优点:易编码实现。
    缺点:在大型数据集上可能较慢。
    适用数据类型:数值型或标称型数据。
    原理:如果某个项集时频繁的,那么他的所有子集也是频繁的。
    Apriori运用的DEMO示例参见博客:http://blog.csdn.net/lantian0802/article/details/38331463
    简述:
    Apriori算法是发现频繁项集的一种方法。Apriori算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个item的项集列表。然后扫描列表计算每个item的项集支持度,将低于最小支持度的item排除掉,然后将每个item两两组合,然后重新计算整合后的item列表的支持度并且和最小支持度比较。重复这一过程,直至所有项集都被去掉。

    总结:关联分析是用于发现大数据集中元素间有趣关系的一个工具集,可以采用两种方式来量化这些有趣的关系。发现元素间不同的组合是个十分耗时的任务,不可避免需要大量昂贵的计算资源,这就需要一些更智能的方法在合理的时间范围内找到频繁项集。能够实现这一目标的一个方法是Apriori算法,它使用Apriori原理来减少在数据库上进行检查的集合的数目。Apriori原理是说如果一个元素是不频繁的,那么那些包含该元素的超集也是不频繁的。Apriori算法从单元素项集开始,通过组合满足最小支持度要求的项集来形成更大的集合。支持度用来度量一个集合在原始数据中出现的频率。

    2.9 FP-growth算法
    简述:FP-growth也是用于发现频繁项集的算法,他以FP树的结构存储构建元素,其他Apriori算法的性能要好很多。通常性能要好2个数量级以上。其发现频繁项集的过程如下:(1)构建FP树。(2)从FP树中挖掘频繁项集。

    优点:一般要快于Apriori。
    缺点:实现比较困难,在某些数据集上性能会下降。
    适用数据类型:标称型数据。

    总结:FP-growth算法是一种用于发现数据集中频繁模式的有效方法。FP-growth算法利用Apriori原则,执行更快。Apriori算法产生候选项集,然后扫描数据集来检查他们是否频繁。由于只对数据集扫描两次,因此FP-growth算法执行更快。在FP-growth算法中,数据集存储在一个称为FP树的结构中。FP树构建完成后,可以通过查找元素项的条件及FP树来发现频繁项集。该过程不断以更多元素作为条件重复进行,直到FP树只包含一个元素为止。

    3.全文总结

    综上所述,简单的分析了机器学习中的基本概念和基本算法,具体到每个算法,想要详细了解还需要自己亲自调试程序,一步步实现。机器学习需要扎实的基础,只有对基本的数据分析算法有所了解,掌握其中的精妙之处,才能运用自如,如鱼得水。


    原文链接如下:

    http://blog.csdn.net/jdbc/article/details/49491069#0-tsina-1-56080-397232819ff9a47a7b7e80a40613cfe1


    展开全文
  • 图论的各种基本算法

    千次阅读 2018-03-17 00:00:00
    本篇主要涉及到图论的基本算法包含有关最大流的内容。图论的大部分算法都是由性质或推论得出来的,想朴素想出来确实容易。二分图(Is-Bipartite)一个图的所有顶点可以划分成两个子集,使所有的边的入度和出度...
  • 算法基本原理

    千次阅读 2018-12-06 21:15:16
    (2)时间复杂度为一个算法流程中, 常数操作数量的指标。 常用O(读作big O) 来表示。 具体来说, 在常数操作数量的表达式中,只要高阶项, 不要低阶项, 也不要高阶项的系数, 剩下的部分如果记为f(N), 那么时间...
  • 数据挖掘6大类基本算法

    千次阅读 2019-06-12 00:08:30
    算法对空间需求及时间需求均是适度的,另外算法收敛速度很快。算法难以发现非球形簇,且对噪声及孤立点较为敏感 模糊C均值 模糊聚类分析作为无监督机器学习的主要技术之一,是用模糊理论对重要数据分析和建模的...
  • MD5不是加密算法,是散列算法

    千次阅读 2018-03-13 19:33:17
    MD5算是加密算法吗?MD5不是加密算法,是散列算法,或者叫做哈希算法。 加密算法一般指对称加密算法。 MD5哈希函数将任意长度的二进制字符串映射为固定长度的小型二进制字符串。加密哈希函数有这样一个属性:在...
  • 随着互联网技术的发展,特别是web2.0时代的到来,互联网为我们提供了...机器学习的很多算法都是基于以下图1中模型来进行设计。  图1 学习系统模型 我们应对外界环境的刺激输入,在实践的过程中
  • 机器学习实战-基本算法总结1

    万次阅读 2018-01-25 22:27:40
    机器学习基本算法总结 ☞监督学习——分类 代码在这,基于python3(原书代码是python2) 这里只是一个总结,原书已经讲解很清楚了,清楚的直接看代码,或者李航的统计学习方法也有公式推导。 目录1 1....
  • CTC算法基本原理解释

    千次阅读 2018-12-25 22:26:41
    语音识别中的CTC算法基本原理解释 目前主流的语音识别都大致分为特征提取,声学模型,语音模型几个部分。目前结合神经网络的端到端的声学模型训练方法主要CTC和基于Attention两种。 本文主要介绍CTC算法基本...
  • u和v不属于同一个联通分支,但v会成为u的后继 因此该算法不可行。   22.5-5 见 算法导论 22.5-5 O(V+E)求有向图的分支图   22.5-6 待解决,题目的意思不太懂,网上找了个答案,主要是其中的第四步不懂。 令所求图...
  • 基本算法(整数划分)

    千次阅读 2017-11-27 17:16:34
    所谓整数划分,是指把一个正整数n写成为 ...中的最大值超过m,即 ,则称它属于n的一个m划分。 这里我们记n的m划分的个数为 。 例如,当n=4时,有5个划分,即 , , , , 。 注意:
  • 【推荐架构day5】今日头条算法基本原理

    万次阅读 多人点赞 2020-02-22 16:03:37
    本文来自今日头条曹欢欢博士的分享。...今日头条委托资深算法架构师曹欢欢博士,公开今日头条的算法原理,以期推动整个行业问诊算法、建言算法;通过让算法透明,来消除各界对算法的误解,并逐步推动整个行业让算...
  • 如果一个算法有缺陷,或适合于某个问题,执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。 一个...
  • 基于频域的算法是在图像的某种变换域内对图像的变换系数值进行某种修正,是一种间接增强的算法,把图像看成一种二维信号,对其进行基于二维傅里叶变换的信号增强。采用低通滤波(即只让低频信号通过)法,可去掉图中的...
  • 数据平衡imblearn算法汇总

    万次阅读 多人点赞 2018-04-16 19:18:11
    数据平衡,imblearn,算法汇总
  • 图像处理基本算法 动态阈值分割

    万次阅读 多人点赞 2012-02-11 16:18:32
    在图像处理时,受外界光线的干扰一般比较大,假如在阈值分割时采用固 ...图像分割是图像处理与计算机视觉领域低层次视觉中最为基础和重要的领域之一,它是对图像进行视觉分析和模式识别的基本前提.阈
  • 基本算法——深度优先搜索(DFS)和广度优先搜索(BFS) 安然若知 12018.07.13 08:38:53字数 753阅读 101,761 深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方...
  • 基本Kmeans算法介绍及其实现

    万次阅读 多人点赞 2012-11-30 06:26:11
    1.基本Kmeans算法[1] 选择K个点作为初始质心 repeat 将每个点指派到最近的质心,形成K个簇 重新计算每个簇的质心 until 簇发生变化或达到最大迭代次数时间复杂度:O(tKmn),其中,t为迭代次数,K为簇的数目,m...
  • 负载均衡的基本(常用)算法

    千次阅读 2016-06-18 20:49:08
    负载均衡的基本算法
  • K-means 算法基本概念篇】

    万次阅读 多人点赞 2018-11-14 22:57:54
    k-means 算法是一个聚类的算法 也就是clustering 算法。是属于无监督学习算法,也是就样本没有label(标签)的算分,然后根据某种规则进行“分割”, 把相同的或者相近的objects 物体放在一起。 在这里K就是我们想要...
  • Apriori算法是一种找频繁项目集的基本算法。其基本原理是逐层搜索的迭代:
  • 首先我们先代入问题来认识一下贪心算法涉及的问题 找钱问题 给顾客找钱,希望找零的钞票尽可能少,零钱种类和数量限定 找钱问题满足最优子结构 最快找零(贪心):为得到最小的找零次数,每次最大程度低减少零额 ...
  • (图片来自 算法概论 by dasgupta) 有向无环图和拓扑排序 有向图有环当且仅当DFS过程中遇到回边。 有向无环图中每一条边都指向一个finish值更小的顶点。 对于DFS,无环性、可线性化、无回边三者是等价的。 ...
  • 页面置换算法-CLOCK置换算法及其改进版算法

    万次阅读 多人点赞 2018-12-29 13:31:51
    本文主要介绍页面置换算法中的CLOCK置换算法。...1.简单的CLOCK算法是通过给每一个访问的页面关联一个附加位(reference bit),有些地方也叫做使用位(usebit)。他的主要思想是:当某一页装入主存时,将use ...
  • 什么是AES算法

    千次阅读 2020-02-02 20:37:52
    单向加密算法是不可逆的,也就是无法将加密后的数据恢复成原始数据,除非采取碰撞攻击和穷举的方式。像是银行账户密码的存储,一般采用的就是单向加密的方式。 双向加密是可逆的,存在密文的密钥,持有密文的一方...
  • 基于股票交易质量(属于Q500US过滤器)和基本参数(例如roe,roi,ecc)对股票进行整体选择2.在优质公司中,只有那些显示出向上的势头,并且该势头构成了排名值(更好的TODO)。3.市场趋势过滤器:基于通过SPY etf...
  • 演化算法(一) 基本概念

    万次阅读 2012-03-25 13:46:58
    演化算法 1、简介 演化算法,又称为进化算法(Evolutionary Algorithm)、进化计算(EvolutionaryComputing)或遗传算法(Genetic Algorithm),是一种元启发式(metaheuristic)方法(定义见:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 176,872
精华内容 70,748
关键字:

以下不属于基本算法的是