精华内容
下载资源
问答
  • 对算法的评价包括多个方面
    千次阅读
    2019-09-23 08:05:25

    一种数据结构的优劣是由实现其各种运算的算法具体体现的,对数据结构的分析实质上就是实现运算算法的分析,除了要验证算法是否正确解决该问题之外,还需要对算法的效率作性能评价。在计算机程序设计中,算法分析是十分重要的。

    算法分析是每个程序设计人员应该掌握的技术。评价算法性能的标准主要从算法执行时间与占用内存空间两方面考虑,即算法执行所需的时间和存储空间来判断一个算法的优劣。

    1.性能评价

    对问题规模与该算法在运行时所占用空间与所耗费时间给出一个数量关系的评价。

    数量关系评价体现在时间上,即算法经编程实现后在计算机中运行所耗费的时间。

    数量关系评价体现在空间上,即算法经编程实现后再计算机中运行所占用的存储量。

    2.问题规模

    算法性能与问题规模相关。问题规模是问题大小的本质表示,对不同的问题其表现形式不同,算法求解问题的输入量称为问题的规模,一般用整数表示。一个图论问题的规模则是图中的顶点数或边数,对矩阵而言是其阶数,对多项式运算而言是多项式项数,对集合运算而言是集合中的元素个数,可以说算法效率应是问题规模的函数。

    算法的时间性能分析

    1.算法耗费的时间

    一个算法的执行时间是指算法中所有语句执行时间的总和。每条语句的执行时间等于该条语句的执行次数乘以执行一次所需实际时间。

    由于语句的执行要由源程序经编译程序翻译成目标代码,目标代码经装配后再执行,语句执行一次实际所需的具体时间是与计算机的软、硬件环境(计算机速度、编译程序质量、输入数据量等)密切相关的,故难以精确估计。

    2.语句频度

    质量一个算法的效率应当抛弃具体计算机条件,仅仅考虑算法本身的效率高低。算法时间分析质量的标准并不是针对实际执行时间精确算法执行的时间,而是根据算法中语句的执行次数做出估计,从中得到算法执行时间的信息。

    语句频度是指该语句在一个算法中重复执行的次数。一个算法的时间耗费就是该算法中所有语句频度之和。

    例1.   求两个n阶方阵的乘积C=A*B。

    #define n 100      /*n可根据需求定义,这里假定为100*/

    void MatrixMulti(int a[n][n],int b [n][n],int c[n][n])

    {                                                                                             该算法每一语句的语句频度为

    (1)for(i=0;i<n;i++)                                                                   n+1

    (2)  for(j=0;j<n;j++)                                                                 n(n+1)

    (3)    {   c[i][j]=0;                                                                      n^2

    (4)        for(k=0;k<n;k++)                                                        n^2(n+1)

    (5)           c[i][j]=c[i][j]+a[i][k]*b[k][j];                                         n^3

                 }

    }

    【分析】语句(1)的循环控制变量i从0增加到n,测试条件i=n成立才会终止,故它的语句频度是n+1,但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次,但语句(2)作为语句(1)循环体内的语句应该执行n次,但语句(2)本身要执行n+1次,所以语句(2)的频度是n(n+1).同理可得语句(3)、(4)和(5)的频度分别是n^2、n^2(n+1)和n^3.

    该算法中所有语句的频度之和(即算法的时间耗费)为

    f(n)=2n^3+3n^2+2n+1

    也就是说、该矩阵乘积算法的问题规模是矩阵的阶数n,时间耗费是矩阵阶数n的函数。

    3.算法的时间复杂度

    为便于比较解决同一问题的不同算法,通常以算法中基本操作重复执行的频度作为度量标准。基本操作是指算法中选取一种对所研究问题是基本运算的操作,用随着问题规模增加的函数来表征,以此作为时间量度。

    对于算法分析,关心的是算法中语句总的执行次数f(n)是问题规模n的函数,进而分析f(n)随n的变化情况并确定T(n)的数量级(Order of Magnitude)。这里用“O”来表示数量级,给出算法的时间复杂度概念。算法的时间复杂度T(n)是该算法的时间度量,记作

    T(n)=O(f(n))

    它表示随问题规模n的增大,算法的执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称时间复杂度。

    在例1中算法MatrixMulti中,当n充分大时,f(n)和n^3之比是一个不等于零的常数,即f(n)和n^3是同阶的,或者说f(n)和n^3的数量级相同,O(n^3)是算法MatrixMulti的渐进时间复杂度。

    数学符号“O”的严格数学定义为:

    若T(n)和f(n)是定义在正整数集合上的两个函数,则T(n)=O(f(n))表示存在正的常数C和n0,使得当n>=n0时都满足0<=T(n)<=Cf(n).

    4.渐进时间复杂度

    由于算法执行的实际机器时间难以精确统计,因此主要考虑用算法时间复杂度的数量级(即算法的渐进时间复杂度)来评价一个算法的时间性能。

    例如,由两个算法A1和A2求解同一问题,时间复杂度分别是T1(n)=100n^2,T2(n)=5n^3.

    ①当输入量n<20时,有T1(n)>T2(n),后者花费的时间较少。

    ②随着问题规模的增大,两个算法的时间开销之比5n^3/100n^2=n/20亦随着增大。即当问题规模较大时,算法A1比算法A2有效的多。

    它们的渐进时间复杂度O(n^2)和O(n^3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时,往往对算法的时间复杂度渐进时间复杂度不予区分,而经常是讲渐进时间复杂度T(n)=O(f(n))简称为时间复杂度,其中的f(n)一般是算法中频度最大的语句频度。例1中的算法MatrixMulti的时间复杂度为T(n)=O(n^3),f(n)=n^3是该算法中语句(5)的频度。

    下面在举例说明如何求算法的时间复杂度。

    例1.4   常数阶实例

    temp=i;

    i=j;

    j=temp;

    以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。如果算法执行的时间不随着问题规模n的增大而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

    例1.5  线性阶实例

    for(i=1;i<=n;i++)

    x=x+1;

    其时间复杂度为O(n),称为线性阶。

    例1.6  平方阶实例

    (1)x=0;y=0;

    (2)for(k=1;k<=n;k++)

    (3)x++;

    (4)for(i=1;i<=n;i++)

    (5)for(j=1;j<=n;j++)

    (6)y++;

    一般情况下,对步进循环语句只需考虑循环体中语句的执行次数,忽略该语句中步长加1、终值判断、控制转移等成分。因此,以上程序段中频度最大的是语句(6),其频度为f(n)=n^2,所以该程序段的时间复杂度为T(n)=O(n^2).

    当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

    例1.7给出源操作x=x+1;语句频度及程序的时间复杂度分析。

    (1)x=1;

    (2)for(i=1;i<=n;i++)

    (3)for(j=1;j<=i;j++)

    (4)x=x+1

    该程序段中频度最大的是语句(4),内循环的执行次数虽然与问题规模n没有直接关系,但是却与外层循环的变量取值有关,而最外层循环的次数直接与n有关,因此可以从内层循环向外层分析语句(4)的执行次数:当i=1时,j取值范围是1~1,原操作执行次数为1;当i=2时,j取值范围是1~2;当i=3时,j取值范围是1~3,执行次数为3,以此类推,故原操作x=x+1;执行的总次数为

    f(n)=(1+2+3+...+n)=n(n+1)/2=n^2/2+n/2

    则该程序段的时间复杂度为T(n)=O(n^2/2+n/2)=O(n^2).

    5.常用算法时间复杂度

    数据结构中常用的时间复杂度频率计数有以下7种:

    O(1)常数型,O(n)线性型,O(n^2)平方型,O(n^3)立方型,O(2^n)指数型,O(log2n)对数型(ps:以2为底n的对数),O(nlog2n)二维型(ps:同上)

    按时间复杂度由小到大递增排列如下所示。一般来说,前三种可实现,后三种虽理论上是可实现的,但实际上只有当n限制在很小的范围时才有意义,当n较大时实现困难。

                                                                           常用的时间复杂度频率表

    log2n                n                      nlog2n                     n^2                                 n^3                              2^n

    0                       1                         0                             1                                     1                                2

    1                       2                         2                             4                                     8                                4

    2                       4                         8                             16                                   64                              14

    3                       8                        24                            64                                  512                            256

    4                      16                       64                            256                                5096                         65536

    5                      32                      160                          1024                               32768                       2147483648

     

    6.最坏时间复杂度和平均时间复杂度

    算法的时间复杂度不仅仅依赖于问题的规模,还输入实例的初始状态有关。

    例1.8  在数值A[0..n-1]中查找给定值k的算法大致如下,分析其时间复杂度。

    (1)i=n-1;

    (2)while(i>=0&&(a[i]!=k))

    (3)i--;

    (4)return i;

    此算法中,语句(3)的频度不仅与问题规模n有关,还与A的各元素值及k的取值有关。

    ①最坏情况:若A中没有与k相等的元素,则语句(3)的频度f(n)=n。

    ②最好情况:若A的最后一个元素等于k,则语句(3)的频度f(n)是常数0.

    最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比这一上界更长。由此可知,上述算法的时间复杂度为T(n)=O(n)。

    平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下,算法的期望运行时间。

    算法的空间性能分析

    一般情况下,一个程序在机器执行时,除了需要存储本身所用的指令、常数、变量和输入数据以外,还需要一些对数据进行操作的辅助存储空间。其中,对于输入数据所占用的具体存储量取决于问题本身,与算法无关,这样只需分析该算法在实现时所需要的辅助空间个数即可。

    1.算法耗费的空间

    一个算法的占用空间是指算法实际占用的辅助空间总和。

    由于实际占用空间与计算机的软件(编译系统)、硬件(字长等)环境密切相关,以整形为例,可能在一种系统中需要2字节,在另一个系统中需要4字节,实际占用空间的多少难以相互类比。算法空间分析度量的标准并不是计算实际占用空间,而是计算整个算法的辅助空间单元个数。

    2.算法的空间复杂度

    算法的空间复杂度S(n)定义为该算法所耗费的存储空间数量级,它是问题规模n的函数。记作

    S(n)=O(f(n))

    若算法执行时所需的辅助空间相对于输入数据量而言是一个常数,则称这个算法为原地工作。辅助空间为O(1)。

    例1.9  将一维数组a中的n个数据逆序存放到原数组中,给出实现该问题的两种算法。

    【算法1】

    for (i=0;<n;i++)

      b[i]=a[n-i-1];

    for(i=0;<n;i++)

      a[i]=b[i];

    【算法2】

    for(i=0;i<n/2;i++)

    {

      t=a[i];

      a[i]=a[n-i-1];

      a[n-i-1]=t;

      }

    算法1的空间复杂度为O(n),需要一个大小为n的辅助数组b。

    算法2的空间复杂度为O(1),仅需要一个变量t,与问题规模没有关系。

    算法的时间复杂度和空间复杂度合称为算法的复杂度。

    算法性能选择

    要想使一个算法即占用存储空间少,又运行时间短,而且其他性能也好,这是很难做到的。原因是上述要求有时相互抵触:要节约算法的执行时间往往要以牺牲更多的空间为代价,而为了节约空间可能要耗费更多的计算时间。因此,只要根据具体的情况进行取舍。

    ①若程序使用次数少,则力求算法简明易懂

    ②对于反复使用的程序,应尽可能选用快速的算法。

    ③若待解决的问题数据量较大,计算机存储空间较小,则相应算法主要考虑如何节省空间。

    更多相关内容
  • 目标优化算法的性能评价

    一、多目标进化算法

    多目标进化算法 (MOEA )是一类模拟生物进化机制而形成的全局性概率优化搜索方法 ,在 20世纪 90年代中期开始迅速发展 ,其发展可以分为两个阶段。

    第一阶段主要有两种方法即不基于 Pareto优化的方法和基于 Pareto优化的方法 ;第二个阶段就是在此基础上提出了外部集这个概念 ,外部集存放的是当前代的所有非支配个体 ,从而使解集保持较好的分布度。这个时期提出的多目标进化算法更多地强调算法的效率和有效性。在这两个阶段中 , 比较典型的多目标进化算法有 NS2 GA2[ 3 ]、PESA2和 SPEA2。
    对于这三种算法而言 ,其优点较多但是其缺点也比较明显的。如 NSGA2的优点在于运行效率高、解集有良好的分布性 ,特别对于低维优化问题具有较好的表现 ;其缺点在于在高维问题中解集过程具有缺陷 ,解集的多样性不理想。PESA2的优点在于其解的收敛性很好 ,比较容易接近最优面 ,特别是在高维问题情况下 ;但其不足之处在于选择操作一次只能选取一个个体 ,时间消耗很大 ,而且阶级的多样性不佳。SPEA2的优点在于可以取得一个分布度很好的解集 ,特别是在高维问题的求解上 ,但是其聚类过程保持多样性耗时较长 ,运行效率不高。

    多目标进化算法的基本原理描述如下 : 多目标进化算法从一组随机生成的种群出发 ,通过对种群执行选择、交叉和变异等进化操作 ,经过多代进化 ,种群中个体的适应度不断提高 , 从而逐步逼近多目标优化问题的 Pareto最优解集。与单目标进化算法不同 ,多目标进化算法具有特殊的适应度评价机制。为了充分发挥进化算法的群体搜索优势 ,大多数 MOEA均采用基于 Pareto排序的适应度评价方法。在实际应用中 ,为使算法更好地收敛到多目标优化问题的 Pareto最优解 ,现有的MOEA通常还采用了精英策略、小生境和设置外部集等关键技术。

    MOEA一般框架所描述的算法思想如下 : MOEA通过对种群 X ( t)执行选择、交叉和变异等操作产生下一代种群 X ( t + 1) 。在每一代进化过程中 ,首先将种群 X ( t)中的所有非劣解个体都复制到外部集 A ( t)中 ,然后运用小生境截断算子剔除A ( t)中的劣解和一些距离较近的非劣解个体 ,以得到个体分布更为均匀的下一代外部集 A ( t + 1) ,并且按照概率 pe从 A ( t + 1)中选择一定数量的优秀个体进入下代种群。在进化结束时 ,将外部集中的非劣解个体作为最优解输出 , 目前 , MOEA研究取得了大量成果 ,已被应用于许多领域 ,如工程领域、工业领域和科学领域。其中 ,工程领域的应用最多 ,如电子工程、水利工程、风电工程和控制等。

    二、指标的常见分类方法

    1.考虑指标同时能评估的解集数目(1个或2个解集),可将指标分为一元和二元指标。
    一元指标:接受一个解集作为参数进行评估。
    二元指标:接受两个解集作为参数,通过比较两个解集的支配关系或其他方面,给出哪个解集更好的判断。

    2.多目标进化算法解集的性能评价指标主要分为三个方面:
    1)解集的收敛性评价(convergence), 反映解集与真实Pareto前沿之间的逼近程度(距离)。一般我们希望所得解集距离PF尽可能近。
    2)解集的均匀性评价(uniformity / evenness), 体现解集中个体分布的均匀程度。一般我们希望所得解集在PF上分布尽可能均匀。
    3)解集的广泛性评价(spread), 反映整个解集在目标空间中分布的广泛程度。一般我们希望所得解集在PF上分布尽可能广、尽可能完整地表达PF。

    也有一些学者,不这样分类,分为基数指标,收敛性指标,和多样性/分布性指标,认为多样性包括均匀性(evenness)和广泛性/范围(spread),具体如下:
    1)基数指标:评估解集中存在的解的个数。
    2)收敛性指标(精确度指标):评估解集到理论帕累托最优前沿的距离(逼近程度)。
    3)多样性指标:包括评估解集分布的均匀性(evenness)和广泛性/范围(spread)。均匀性体现解集中个体分布的均匀程度;广泛性反映整个解集在目标空间中分布的广泛程度。

    二、常用性能评价指标回顾

    *1.GD:解集P中的每个点到参考集P 中的平均最小距离表示。GD值越小,表示收敛性越好。

    在这里插入图片描述

    其中P是算法求得的解集,P 是从PF上采样的一组均匀分布的参考点,而dis(x,y)表示解集P中的点y和参考集P中的点x之间的欧式距离。

    优点:相比HV,计算代价是轻量级的。
    缺点:1)仅度量解集的收敛性,无法评估多样性;
    2)需要参考集,使得这个测度很容易不客观;

    *2.convergence metric γ:解集P中的每个点到参考集P 中的最小距离的平均值。(类似GD)

    在这里插入图片描述

    其中P是算法求得的解集,P 是从PF上采样的均匀分布的参考点集,而dis(x,y)表示参考集P中的点x和解集P中的点y之间的欧式距离。

    3.Spacing:度量每个解到其他解的最小距离的标准差。Spacing值越小,说明解集越均匀。

    在这里插入图片描述

    其中表示第di个解到P中其他解的最小距离,d-表示所有di的均值。

    缺点:仅度量解集的均匀性,而不考虑它的广泛性。

    4.diversity metric △:衡量所获得的解集的广泛程度。

    在这里插入图片描述

    参数df和dl是极端解与所获得的非支配集的边界解之间的欧几里德距;di 是所获得的非支配解集中的连续解之间的欧几里德距离;
    d是di 的平均值。
    假设最佳非支配前沿有N个解。使用N个解,有N-1个连续距离。当只有一个解,即N=1时,分母=分子。值得注意的是,这不是解可能的最坏情况。我们可以有一个场景,其中di 存在很大的差异。在这种情况下,度量可能大于1。因此,上述度量的最大值可以大于1.然而,良好的分布将使所有距离di 等于d并且将使得df=dl = 0(在非支配集合中存在极端解)。因此,对于最广泛和均匀展开的非支配解集,△的分子将为零,使得度量值为零。对于任何其他分布,度量的值将大于零。
    对于具有相同df和dl值的两个分布,度量△在极端解中具有更高的值和更差的解的分布。

    5.超体积指标(HV,Hypervolume):算法获得的非支配解集与参照点围成的目标空间中区域的体积。HV值越大,说明算法的综合性能越好。

    在这里插入图片描述

    代表δ表示 Lebesgue 测度,用来测量体积。 |S| 表示非支配解集的数目, vi表示参照点与解集中第 i 个解构成的超体积。
    优点:1)同时评价收敛性和多样性;
    2)无需知道PF或参考集;
    缺点:1)计算复杂度高,尤其是高维多目标优化问题;
    2)参考点的选择在一定程度上决定超体积指标值的准确性;

    6.反转世代距离(IGD,Inverted Generational Distance):每个参考点到最近的解的距离的平均值。IGD值越小,说明算法综合性能越好。

    在这里插入图片描述

    其中P是算法求得的解集,P 是从PF上采样的一组均匀分布的参考点,而dis(x,y)表示参考集P中的点x到解集P中的点y之间的欧式距离。

    优点:1)可同时评价收敛性和多样性;
    2)计算代价小;
    缺点:2)需要参考集;

    7.C-metric解集覆盖率:

    在这里插入图片描述

    分子表示B中被A中至少一个解支配的解的数目;分母表示B中包含的解的总数。
    C(A,B)=1表示B中所有解都被A中的一些解所支配;C(A,B)=0表示B中没有解被A中的任一解所支配。

    8.IGD-NS 注:为什么要识别非贡献解呢?因为非贡献解影响收敛

    在这里插入图片描述

    P是PF上均匀采样的参考点集,P是算法获得的解集,P’是P中的非贡献解集。
    公式的前一部分和IGD很相似,控制P的收敛性和多样性;
    第二部分是每个非贡献解到参考集P的点的最小距离之和。
    因此,IGD-NS值越小,说明收敛和多样性越好,且解集的非贡献解尽可能少。

    9.KD:衡量是否每个解集都至少包含一个与拐点相近的解或该解集是否包括全部拐点。

    在这里插入图片描述

    其中d(vi,G)是K中的第i个真实拐点vi到G中最接近解之间的欧几里得距离。
    KD值越小,说明检测拐点的能力越完整;
    当所获的解集覆盖到所有的拐点时,KD=0。

    三、参考集的缺陷

    不少指标在计算时都需要参考集,因为有参考集的存在,指标的客观型就值得怀疑,如下图所示。

    在这里插入图片描述

    解集B肯定比A要好,可是因为选用了图中的参考集。而且,绝大多数实际问题都没参考集。

    四、支配关系的缺陷

    在高维多目标里,很多解集或解都相互不支配,这时候支配关系这种东西就很鸡肋了。

    展开全文
  • 点击上方“小白学视觉”,选择加"星标"或“置顶”重磅干货,第一时间送达 本文转自:磐创AI1. 典型聚类算法1.1 基于划分的方法代表:kmeans算法·指定k聚类中心...

    点击上方“小白学视觉”,选择加"星标"或“置顶

    重磅干货,第一时间送达
    
    

    本文转自:磐创AI

    1. 典型聚类算法

    1.1 基于划分的方法

    代表:kmeans算法

    ·指定k个聚类中心
    ·(计算数据点与初始聚类中心的距离)
    ·(对于数据点,找到最近的{i}ci(聚类中心),将分配到{i}ci中)
    ·(更新聚类中心点,是新类别数值的均值点)
    ·(计算每一类的偏差)
    ·返回
    返回第二步

    1.2 基于层次的方法

    代表:CURE算法

    ·每个样本作为单独的一个类别
    ·
    ·合并,
    ·遍历完本次样本,合并成新的类别后,若存在多个类别,则返回第二步
    ·遍历完本次样本,合并成新的类别后,若所有样本为同一类别,跳出循环,输出每层类别

    1.3 基于网格的方法

    代表:STING算法

    ·将数据集合X划分多层网格结构,从某一层开始计算
    ·查询该层网格间的属性值,计算属性值与阈值的关系,判定网格间的相关情况,不相关的网格不作考虑
    ·如果网格相关,则进入下一层的相关区域继续第二步,直到下一层为最底层
    ·返回相关网格结果

    1.4 基于密度的方法

    代表:DBSCAN算法

    ·输入数据集合X,随机选取一点,并找出这个点的所有高密度可达点
    ·遍历此点的所有邻域内的点,并寻找这些密度可达点,判定某点邻域内的点,并寻找这些点密度可达点,判定某点的邻域内的点数是否超过阈值点数,超过则构成核心点
    ·扫描数据集,寻找没有被聚类的数据点,重复第二步
    ·输出划分的类,并输出异常值点(不和其他密度相连)

    1.5 神经网络的方法

    代表:SOM算法

    ·数据集合,权重向量为,归一化处理
    ·寻找获胜的神经元,找到最小距离,对于每一个输入数据,找到与之最相匹配的节点
    的距离,更新权重:
    ·更新临近节点,,其中代表学习率

    1.6 基于图的聚类方法

    代表:谱聚类算法

    ·计算邻接矩阵,度矩阵
    ·计算拉普拉及矩阵
    ·计算归一化拉普拉斯矩阵
    ·计算的特征值和特征向量
    ·对Q矩阵进行聚类,得到聚类结果

    2. 聚类算法的评价指标

    一个好的聚类方法可以产生高品质簇,是的簇内相似度高,簇间相似度低。一般来说,评估聚类质量有两个标准,内部质量评价指标和外部评价指标。

    2.1 内部质量评价标准

    内部评价指标是利用数据集的属性特征来评价聚类算法的优劣。通过计算总体的相似度,簇间平均相似度或簇内平均相似度来评价聚类质量。评价聚类效果的高低通常使用聚类的有效性指标,所以目前的检验聚类的有效性指标主要是通过簇间距离和簇内距离来衡量。这类指标常用的有CH(Calinski-Harabasz)指标等

    CH指标

    CH指标定义为:

    其中表示类间距离差矩阵的迹,表示类内离差矩阵的迹,是整个数据集的均值,是第个簇的均值,代表聚类个数,代表当前的类。值越大,聚类效果越好,主要计算簇间距离与簇内距离的比值

    簇的凝聚度

    簇内点对的平均距离反映了簇的凝聚度,一般使用组内误差平方(SSE)表示:

    簇的邻近度

    簇的邻近度用组间平方和(SSB)表示,即簇的质心到簇内所有数据点的总平均值的距离的平方和

    2.2 外部质量评价标准

    外部质量评价指标是基于已知分类标签数据集进行评价的,这样可以将原有标签数据与聚类输出结果进行对比。外部质量评价指标的理想聚类结果是:具有不同类标签的数据聚合到不同的簇中,具有相同类标签的数据聚合相同的簇中。外部质量评价准则通常使用熵,纯度等指标进行度量。

    熵:

    簇内包含单个类对象的一种度量。对于每一个簇,首先计算数据的类分布,即对于簇,计算簇的成员属于类的概率

    其中表示簇中所有对象的个数,而是簇中类的对象个数。使用类分布,用标准公式:

    计算每个簇的熵,其中K是类个数。簇集合的总熵用每个簇的熵的加权和计算即:

    其中是簇的个数,而是簇内数据点的总和

    纯度:

    簇内包含单个类对象的另外一种度量。簇的纯度为,而聚类总纯度为:

    下载1:OpenCV-Contrib扩展模块中文版教程

    在「小白学视觉」公众号后台回复:扩展模块中文教程即可下载全网第一份OpenCV扩展模块教程中文版,涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。

    下载2:Python视觉实战项目52讲

    在「小白学视觉」公众号后台回复:Python视觉实战项目即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目,助力快速学校计算机视觉。

    下载3:OpenCV实战项目20讲

    在「小白学视觉」公众号后台回复:OpenCV实战项目20讲即可下载含有20个基于OpenCV实现20个实战项目,实现OpenCV学习进阶。

    交流群

    欢迎加入公众号读者群一起和同行交流,目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群(以后会逐渐细分),请扫描下面微信号加群,备注:”昵称+学校/公司+研究方向“,例如:”张三 + 上海交大 + 视觉SLAM“。请按照格式备注,否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告,否则会请出群,谢谢理解~

    展开全文
  • 从机器人个体的自私利益出发,以经费和报酬的驱动,通过包含环境知识、历史经验、信用3个方面的综合评价值进行选举和谈判,自发地建立联合协作,完成复杂任务。算法通过调整权值,能够适应于不同的全局最优目标。该...
  • 评价算法的优劣标准有什么?

    千次阅读 2021-03-22 11:45:17
    想要去评价个算法的优劣,我们可以借助时间维度,即时间复杂度就是用来估计算法运行时间的一式子(单位)。时间的单位为时、分、秒。算法的单位就是O(1),O(n),O(nk)等,例如: 循环语句循环1次、2次、3次…...

    一、评价算法的优劣标准有什么?

    1.1什么是算法?

    算法就是一个解决问题的方法,一种计算过程。补充:一个程序就是算法与数据结构的组合(数据结构可以直白的理解为研究数据存储的方式)

    1.2时间复杂度

    想要去评价一个算法的优劣,我们可以借助时间维度,即时间复杂度就是用来估计算法运行时间的一个式子(单位)。时间的单位为时、分、秒。算法的单位就是O(1),O(n),O(nk)等,例如:
    循环语句循环1次、2次、3次…(比较少),时间复杂度就是O(1)
    循环语句循环n次,则时间复杂度为O(n)
    循环语句循环n次,语句内嵌套n次,则时间复杂度为O(n2)
    循环语句循环n次,每一次循环次数减半,则时间复杂度为O(logn)

    当然时间复杂度越低,算法运行时间越少
    复杂问题时间的复杂度:
    O(n!),O(2n),O(nn)…

    1.3空间复杂度

    用来评估算法内存占用大小的式子
    例如:
    算法使用了一个变量 空间复杂度为 O(1)
    长度为n的一维列表 、、、、、、、 O(n)
    m行n列的二维列表、、、、、、、、O(mn)
    随着内存的不断更新,目前时间远远比空间要重要的多,往往会牺牲空间来换取时间

    1.4汉诺塔问题

    汉诺塔的算法思想可以深思,将最大盘子看作一类,其他n-1个盘子看作一类,过程看着确实不难,但思想确实很神奇。
    汉诺塔问题注意解决问题的思想

    def hanio(n, a, b, c):#代表把n个盘子从a经过b移动到c
        if n > 0:
            hanio(n-1,a,c,b)#代表把n-1个盘子从a经过c移动到b
            print('moving from %s to %s'%(a,c))
            hanio(n-1,b,a,c)#代表把n-1个盘子从b经过a移动到c
    
    展开全文
  • 如何评价个算法的好坏

    万次阅读 2019-04-27 21:38:39
    首先,这个算法必须是正确的 其次,好的算法应该是友好的,便于人们理解和交流,并且是机器可执行的。 这个算法还需要足够健壮,即当输入的数据非法或不合理时,也能适当的做出正确的反应或进行相应的处理 最后它还...
  • 介绍论文名: “classification, ranking, and top-k ...与常规准确率比较的方式不同, 本文从另一角度, 即推荐算法稳定性方面进行比较.详细参与比较的推荐算法包括: baseline 传统基于用户 传统基于物品 oneSlope s
  • 文章目录那么我们过去是怎么评价的?客观评价-基于指标客观评价-基于模型R&S®UPV音频分析仪小结那么我们现在用哪些评价方法呢?基于深度学习的方法:AutoMOS, QualityNe, NISQA, MOSNetMOSNet(`absolute....
  • 目标检测算法评价指标之mAP

    千次阅读 2021-12-04 16:19:38
    随着计算机技术的发展和计算机视觉原理的广泛应用,利用计算机图像处理技术目标进行实时跟踪研究越来越热门,目标进行动态实时跟踪...在目标检测问题中,给定一图像,找到它所包含的物体,找到它们的位置并...
  • 针对目前冲突数据源的质量评价模型仅考虑准确度与精确度2个方面,没有考虑数据源提供错误描述与提供空值数据源质量会产生不同影响的情况,通过将数据源提供的错误描述定义为主动错误,并将数据源没有为实体提供...
  • 算法算法的评估

    千次阅读 2020-08-18 17:22:38
    1、算法评价标准 (1)正确性 • 不含语法错误; • 输入数据能够得出满足要求的结果; • 一切合法输入,都可以得到...• 每个问题有多个算法存在,每个算法的计算量都会不同。 • 在保证运算效率的前提下,力
  • 数据挖掘十大算法之分类算法(分类介绍及评价指标) 接上篇文章,接下来学习挖掘算法中的分类算法: 首先我们应该知道数据挖掘十大算法中可以简单的进行分类,分为分类算法,聚类算法和关联规则三大类 算法分类 连接...
  • 算法的性能评价一般来说考虑一下四个方面: 完备性:当问题有解时,这个算法是否能够保证找到解 最优性:当问题的解存在时,这个算法是否能够找到最优解 时间复杂度:找到解花费的时间 空间复杂:在执行算法的...
  • 综合评价算法的对比分析

    千次阅读 2021-04-02 14:01:25
    近来,看了一些综合评价算法的资料,这里面包含熵值法、TOPSIS法、层次分析法、模糊综合评价法。综合评价,顾名思义,就是一些已有的评价结果进一步综合评价,进而得出具有决策意义结果的算法。 首先,说一下熵值...
  • 评价组播路由算法的重要指标包括组播树代价(cost)、时延(delay)和可扩展性(sealability )等。移动IP出现后,原有的组播路由算法受到了严重的挑战,不再适合于新的移动Internet环境。因此研究移 动环境下的...
  • 任务进化优化算法(一)——因子进化算法(MFEA)

    万次阅读 多人点赞 2019-10-25 19:09:21
    最近看了很关于任务优化的文章,觉得这是一蛮有意思的方向,想把里面最经典的两方法介绍给大家,今天先介绍第一MFEA,这方向有一平台,这里面有原作者的代码及最新的出版物,感兴...
  • 一、算法简介 白鲨优化算法(White Shark Optimizer,WSO)由Malik Braik等人于2022年提出,该算法受大白鲨导航和觅食时具有的非凡听觉和嗅觉启发。该算法思路新颖,策略高效。 大白鲨体呈纺锤型,躯干较粗壮。头...
  • 目标进化算法的性能评价指标总结(一)

    万次阅读 多人点赞 2019-04-04 16:59:25
    考虑评估近似解集的三个方面可将指标分为三类: 1.基数指标:指解集中存在的解的个数。 2.收敛性指标(精确度指标):评估解集到理论帕累托最优前沿的距离(贴近程度)。 3.多样性指标:评估解集分布的均匀度...
  • 目标进化算法的性能指标总结 (一) 觉得有用的话,欢迎一起讨论相互学习~ 转载自: https://blog.csdn.net/qq_40458671/article/details/88601195 注:此次总结的只是目标性能评价指标中很少的一部分。 一、指标...
  • 第7-6课:遗传算法的两应用实例

    千次阅读 2020-09-22 12:16:54
    所谓的确定性是指以上这些算法都是建立在确定性基础上的搜索算法,在搜索过程中遇到一决策点时,对于选 a 还是选 b,其结果是确定的。比如贪婪法,就是按照贪婪策略选择,同样的条件下,每决策选 1000 次结果都...
  • 目标优化算法的性能指标_简介

    千次阅读 多人点赞 2020-05-06 12:45:59
      在对多目标优化算法的性能进行评价时,主要有两个评价标准:多样性和收敛性。由于单一的性能指标不能很好地同时反映这两个评价标准,本文使用了三种性能指标来衡量目标优化算法的性能。三性能指标分别为超...
  • 【你了解什么是算法设计与分析吗?】

    千次阅读 多人点赞 2022-04-25 14:52:44
    这篇文章对算法设计与分析基础做了一较为详细的介绍,有什么不足请大家指正!
  • 0、优化算法 优化算法是一种根据概率按照固定步骤寻求问题的最优解的过程。常见的优化算法有最传统的梯度下降法(Gradient Descent),在自然特性的基础上模拟个体种群的适应性的遗传算法(Genetic Algorithm,GA)和...
  • 本文主要分析皆来自其他资料,借用较为权威的总结来我已经学习的这些经典算法做一极为精简的概述(根据自身经验有一定修改),另外同时附上机器学习实战中作者各种算法评价。另外机器学习实战这本书是本人看...
  • 完整代码已上传我的资源:【目标优化求解】基于matlab粒子群算法求解目标优化问题【含Matlab源码 441期】 点击上面蓝色字体,直接付费下载,即可。获取代码方式2: 付费专栏优化求解(Matlab)备注: 点击上面...
  • 带约束的目标优化进化算法综述

    千次阅读 多人点赞 2020-12-16 16:26:09
    约束优化进化算法综述 ...同时,基于约束处理机制,将这些方法分为罚函数法、可行性法则、随机排序法、ᴈ-约束处理法、目标优化法、混合法等 6 类,并从约束处理方法的角度约束优化进化算法的最新研究进展进行综述;
  • 推荐算法面试集锦--算法模型

    千次阅读 2022-03-12 14:11:15
    推荐算法面试题集锦--算法模型
  • 欢迎大家来到“Python从零到壹”,在这里我将分享约200篇Python系列文章,带大家一起去学习和玩耍,看看Python这有趣的世界。所有文章都将结合案例、代码和作者的经验讲解,真心想把自己近十年的编程经验分享给...
  • 推荐算法架构4:重排

    千次阅读 2022-02-23 17:56:36
    重排的技术点也十分,总结下来,个人认为重排主要是为了解决三大方面的问题:用户体验、算法效率、流量调控。下图是重排总体架构 2 用户体验 重排模块是推荐系统最后一模块(可能还会有混排),离用户最近...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 64,687
精华内容 25,874
热门标签
关键字:

对算法的评价包括多个方面