算法学习报告范文

算法学习报告范文（精选9篇）

算法学习报告 第1篇

算法是数学及其应用的重要组成部分, 是计算科学的重要基础。随着现代信息技术的飞速发展, 算法在科学技术、社会发展中发挥着越来越大的作用, 并日益融入社会生活的许多方面, 算法思想已经成为现代人应具备的一种数学素养。对于高职计算机专业的学生来说, 算法的学习尤为重要, 因为它是学习程序设计语言等专业课的基础。可是, 现在的高职数学教材没有这一内容, 并且在实际教学中数学理论与专业课程之间严重脱节, 让学生觉得数学学习学之无用。因此在高职计算机专业的数学教学中加入算法内容, 可以让学生在初步感受算法思想的基础上, 结合对具体数学实例的分析, 撰写算法学习报告, 体验程序框图在解决问题中的作用;通过模仿、操作、探索, 学习设计程序框图表达解决问题的过程;体会算法的基本思想以及算法的重要性和有效性, 发展有条理的思考与表达的能力, 提高逻辑思维能力, 为学习程序设计语言等专业课程打下坚实的基础。

一、根据学生的学习现状, 设计算法学习报告, 通过让学生撰写学习报告来探讨如何通过具体的数学实例让高职学生体会算法的基本思想

算法学习报告包括:学生预习情况、小组讨论、教师点评、学习总结、教师对学习报告的评价和调查问卷六个部分, 下面来具体进行分析:

(一) 学会课前预习是学好任何学科的前提, 数学学习也不例外。可是, 对于职业学校的学生来说, 大多数的学生没有良好的学习习惯, 也比较懒惰。如何让高职学生改变这样的现状已成为新时期高职教师亟待解决的问题。因此, 根据高职学生的这一特点和算法学习的要求, 笔者设计了算法学习报告中的学生预习情况部分, 让学生通过充分课前预习来为课堂学习做好准备。这部分细分为:解题分析、算法分析、画出流程图和写出程序设计的代码 (程序设计代码的编写可根据学生的实际情况进行调整) 。

下面以一个数学实例来具体介绍算法学习报告中的学生预习部分。教师在课前先给出预习内容:任意给定3个正实数, 设计一个算法, 判断分别以这3个数为三边边长的三角形是否存在?学生预习情况:对于这样一道“判断分别以这3个正实数为三边边长的三角形是否存在?”的题, 以往的数学课上讨论的很少。因此, 可能班级中绝大部分的学生没有一点正确的解题思路, 就更谈不上写出解题分析、算法分析、画出流程图和写出程序设计的代码了。那么这时就来看看在课堂上教师如何引导学生进行这个内容的学习。

(二) 在课堂上通过以学生为主体的小组讨论方式, 可以调动他们学习算法的积极性, 同时开拓他们的学习视野。俗话说:“三个臭皮匠, 顶个诸葛亮!”课堂上小组讨论情况:有同学提出利用“两边之和大于第三边”来判断三个正实数为三边边长是否构成三角形。

(三) 教师点评是教师从旁引导, 使学生能够正确理解算法的设计思路, 建构正确的知识体系。教师点评:为学生分析构成三角形的条件, 鼓励学生尝试用“两边之和大于第三边”来判断三个正实数为三边边长是否构成三角形。

(四) 学生经过课堂上的小组讨论和教师点评后, 已经有了大致的解题思路, 但是仍需精加工。因此, 要求学生独立完成学习报告中的学习总结, 写出其中修改后的算法分析、画出流程图和程序设计的代码以及学后记。

学生修改后的算法分析:第一步:输入3个数a、b、c。第二步:利用“两边之和大于第三边”判断a、b、c是否能构成三角形。第三步:如果能构成三角形, 输出结果或者输出“无法构成三角形”的信息。学生修改后的流程图如图1所示。

程序设计代码:略。

学后记:要求学生写出学习这部分内容的学习感受, 找出自己在学习中的优缺点, 为今后的算法学习打好坚实的基础。

同时通过以上这些具体的学习过程让学生通过自我反思, 提高自身解决问题、分析问题的能力, 为以后的算法学习积累丰厚的经验。

(五) 教师评分。教师对学生所做学习报告的评价和成绩评定, 可以让学生了解自己在算法学习上的优势和不足之处, 为今后的学习打下坚实的基础。

(六) 教学反馈情况。学生在新的内容学习结束后, 究竟掌握了多少?在算法学习方面还存在哪些问题呢?笔者在设计算法学习报告的同时还设计了一份调查问卷来了解学生的学习状况。内容如下:

(1) 你在预习时能理解多少研究主题的内容?

A.全部 B.一半左右 C.很少的一部分 D.一点也不懂

(2) 你在预习时能写出多少算法设计的步骤?

A.全部 B.一半左右 C.很少的一部分 D.一点也不懂

(3) 你在预习时能画出多少流程图的结构?

A.全部 B.一半左右 C.很少的一部分 D.一点也不懂

(4) 你在预习时能写出研究主题的程序设计多少行?

A.全部 B.一半左右 C.很少的一部分 D.0行

(5) 在听了小组的讨论后, 你觉得在哪个方面的收获最大?A.算法设计 B.画流程图的结构 C.写出程序设计 D.以上三种都有

(6) 在听了教师的点评后, 你觉得在哪个方面的收获最大?A.算法设计 B.画流程图的结构 C.写出程序设计 D.以上三种都有

(7) 你觉得填写学习报告中的预习情况对你的算法学习是否有帮助?A.有很大帮助 B.有一点帮助 C.没有帮助 D.可有可无。

(8) 你觉得小组讨论有必要进行下去吗?A.很有必要 B.有些必要 C.没有必要 D.可有可无

(9) 在学习了这个研究主题后, 你觉得目前你最薄弱的是哪一个环节?A.算法设计 B.画流程图的结构 C.写出程序设计 D.以上三种都有

(10) ①教师给出的最佳程序设计写了行, ②你写出的正确的程序设计是行, ③最佳程序设计的行数:你写出正确的程序设计的行数=。

让学生每做一份算法学习报告就做一份调查问卷, 可以让数学教师和专业课教师及时明确地掌握学生学习情况的第一手资料。教师可以通过这些数据, 对全班学生学习情况进行横向的对比, 随时调整教学设计方案, 找到适合高职计算机专业学生数学教学的模式;在撰写多个算法学习报告后, 也可以对某位学生调查问卷的数据进行纵向的对比, 从中可以看出这位学生的算法学习是否有进步, 还存在哪些方面的问题亟待解决。教师可以及时给学生进行有针对性的辅导, 提高他们的算法学习成绩。

二、撰写算法学习报告可以加强算法的核心内容——程序框图的学习

由于算法的概念并没有一个统一的定义, 在教学过程中应从实例出发, 通过让学生撰写算法学习报告可以加强学生对解决具体问题过程与步骤的分析, 体会算法的思想, 了解算法的含义, 力求使学生能够对算法本质有所认识。自然语言、程序框图和算法语言是表达算法的三种形式, 其中程序框图最为重要, 它是算法的核心内容。教师在教学中要重点抓住它, 而不必一味地追求程序设计的完整。算法案例配合学习报告的使用, 可以使学生进一步理解程序框图, 领会算法的本质。

三、算法学习报告对高职计算机专业数学教学的重要性和有效性

(一) 算法学习报告的撰写将数学学习与程序设计语言学习进行了有机的结合。算法是实践性很强的内容, 只有通过学生自己的亲身实践, 让学生亲自去解决几个算法设计的问题, 才能使学生体会算法的基本思想, 学会一些基本逻辑结构和语句。算法内容是将数学中的算法与计算机技术建立联系, 形式化地表示算法。为了有条理地、清晰地表达算法, 往往需要将解决问题的过程整理成程序框图;为了能在计算机上实现, 又要将自然语言或程序框图翻译成计算机语言。因此, 如果能让学生上机, 算法设计的整个过程就可以得到完整的体现, 学生可以及时看到自己设计的算法的可行性、有效性, 这不但可以很好地激发学生的兴趣, 而且还能提高学习效果。但是有些学校教学条件不允许或者还没有开设程序设计语言的课程, 算法学习报告的撰写正好弥补了这一不足, 方便了学生进行算法的学习。

(二) 算法内容的学习最好安排在高职计算机专业的学生已经开始学习VB、C语言等程序设计语言课程后, 这样能够直接与专业课的学习进行互动, 学习成效会更加显著。如果算法内容可以让高职计算机专业的学生用数学学习报告的方式进行学习, 那么不仅能提高学生数学学习的兴趣, 也能为专业课的学习打下了坚实的基础。

目前, 算法教学刚刚起步, 还有很多不完善的地方, 但是笔者相信经过一段时间的摸索, 一定会找到一个适合高职计算机专业学生的数学教学模式。高职数学教学改革任重而道远!

参考文献

[1].郭慧清.普通高中标准实验教科书·数学3[M].北京:人民教育出版社, 2004

算法学习报告 第2篇

1004012033 陈孝婕 10计本3 “数据结构与算法”这门课程对于计算机科学与技术系的学生来说是非常重要的课程。这门课程主要包括十个章节。

一．每章主要知识点总结和个人掌握情况

第一章主要要求学生掌握数据、数据类型、数据结构、算法及算法分析等基本概念和基础知识。另外，第一章结合课程学习要求，复习和掌握算法描述工具--C语言中的指针类型与指针变量、结构类型与结构变量、函数与参数、递归定义和递归函数、动态存储分配、文件操作、程序测试和测试集、测试数据的设计和程序调试等问题。

从这一章中我不仅学到了数据结构的基本概念和基础知识，了解到什么是数据结构，我们为什么要学习数据结构这门课程。而且复习了大一下学期所学的C语言程序课程设计中的算基本法语句。有利于数据结构与算法后面课程的学习。

第二章主要学习顺序表（包括顺序串）数据类型、数据结构、基本算法及相关应用。知识点包括顺序表的概念、数据结构定义、数据类型描述、基本算法的实现及其性能的分析等知识；还有“查找”和“排序”的概念，“查找”包括3种查找方式：简单顺序查找、二分查找、分块查找；“排序”包括直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序和归并排序（重点为二路归并排序）6种排序方式；掌握应用顺序表来进行查找和排序的各类算法以及不同的查找和排序算法间的性能差异。在此基础上，理解顺序串的相关应用。

从这一章中我学习到各种不同的查找方法和排序方式，其中二分查找作为重点查找方法我进行了重点学习，熟悉并熟练地运用二分查找并且了解到各种排序方法适合于不同的顺序表。对于顺序串的学习，我主要掌握了字符串的基本运算，包括：求串长strlen(S)、连接stract(ST1,ST2)、求子串substr(S,i,j)、比较串的大小strcmp(S,T)、插入insert(S1,i,S2)、删除delete(S,i,j)、子串定位index(S1,S2)、置换(replace(S1,i,j,S2)、replace(S,T,V)两种)。

第三章主要学习链表（单聊表、循环链表）的概念、数据结构、数据类型描述、基本算法以及链表相关应用。需要掌握各种链表的概念、数据结构定义、基本算法实现以及算法的性能分析等知识，掌握链表的相关应用方法，在此基础上掌握链串的相关知识。

通过这一章我学习了另一种数据结构——链表，在逻辑结构上，链表与顺序表一样，也是线性逻辑结构；单链表借助“地址”的概念，使用了链式存储结构，产生了一种新的数据结构——链表，链表的基本操作是地址运算，在此基础上构成的链表基本算法的特点也就不同，从链表算法的功能看，链表的基本运算与顺序表基本相同，但实现方法和过程与顺序表是不同的，链表可分为静态链表和动态链表两种。这一章我学习到的实际应用是链表的创建、插入和删除等基本操作。循环链表的建立和查询方法。

第四章主要知识点是在两种不同的存储结构下设计的堆栈，即顺序栈和链栈。主要内容是顺序栈和链栈的概念、数据类型、数据结构定义和基本运算算法及其性能分析。通过对本章的学习，要求掌握顺序栈及链栈的数据类型描述、数据结构、基本算法及其性能分析等知识。在此基础上，了解堆栈的相关应用，掌握应用堆栈解决实际问题的思想及方法。

通过对这一章的学习，我了解了堆栈的概念，堆栈的原理、创建方法以及使用方式。“后进先出”是其基本原则。利用堆栈可以轻松方便的解决对称问题以及括号匹配等问题。堆栈与顺序表、链表不同的是，堆栈只能对一端的数据元素进行操作，即只在栈顶进行元素的插入和删除。掌握顺序栈和链表的存储结构是学习堆栈的要素之一。堆栈是一类常用的数据结构，被广泛应用于各种程序设计中。

第五章的重点知识是在顺序存储和链接存储下的两种队列——顺序（循环）队列和链队

列的数据结构、基本运算及其性能分析以及应用。通过本章的学习，要求掌握顺序队列（重点是循环队列）及链队列的概念、数据类型描述、数据结构、基本算法及其性能分析等知识。在此基础上，了解队列的相关应用，掌握应用队列来解决实际问题的思想及方法。

通过这一章的学习，我掌握了队列的定义，概念，创建以及“对头删除”，“队尾插入”的原则。重点了解了判断循环队列空和满的判断条件。同堆栈一样，队列也是一种具有线性逻辑结构、运算受限制的数据结构。与堆栈只在一端（栈顶）进行元素的插入和删除运算不同的是，队列是在对头进行插入，而在队尾完成数据元素的删除，所以队列的算法和适用的应用问题与堆栈有很大的区别。队列作为一类常用的数据结构，被广泛应用于各种程序设计中。

第六章主要学习数组、系数矩阵和广义表的基本概念、集中特殊矩阵的存储结构及基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。通过本章的学习，要求掌握特殊矩阵的压缩存储结构，在该存储结构下元素的定位方法，理解稀疏矩阵的计算和广义表的存储结构及其基本运算。了解矩阵与广义表的相关应用。

通过这章的学习和前几章的比较，我了解到前几章的线性结构中的数据元素都是非结构的原子类型，即每一个元素都是不可再分解的。本章讨论的数组和广义表等数据结构可以看成是在前几章线性结构基础上的一个扩展：组成该数据结构的数据元素本身也是一个数据结构。矩阵计算应该数值计算方面的问题，由于矩阵和数组的关系以及特殊矩阵存储结构的复杂性，进而使得特殊矩阵的存储结构和算法也表现出其特殊性，所以数据机构课程应该解决其计算问题。

第七章的学习重点是二叉树的概念、数据类型、数据结构定义和各种基本算法，在此基础上介绍二叉树的一些应用问题。通过本章的学习，我掌握了二叉树概念及其性质、二叉树的逻辑结构和存储结构等知识，掌握二叉树的建立、遍历、线索化等基本概念和算法及性能分析，能熟练应用二叉树这章结构来解决一些实际问题，如哈夫曼树及哈夫曼编码、查找与排序（二叉树排序）等问题。了解堆栈排序及其算法等知识。二叉树是非线性数据结构，是树形结构的一种特殊形式。在现实生活有许多数据关系可抽象为树或二叉树的形式。本章中的二叉树的概念及其性质、二叉排序树、存储结构、遍线索（化）、基本算法为重点内容，二叉排序树的应用为难点内容。

第八章的学习重点是树和森林的数据结构、基本算法及其性能分析，树和森林与二叉树间的转化算法等，在此基础上介绍树的应用——B-树。通过本章的学习，我掌握了树和森林的概念和性质、数据结构、树的基本算法及性能分析、树与二叉树间的转换及其算法，并能应用B-树来实现数据元素的动态查找。舒适一种非线性结构，它在二叉树的基础上做了更为一般化的扩展，而森林是树的集合。在树结构中，每一个元素最多只有一个前驱，但可能有多个后继。现实生活中的家族关系、单位的组成结构等，均可抽象为树的形式。

第九章学习重点是散列结构的相关知识，学习常用的散列函数和冲突处理方法，散列表的常用算法及其性能分析，通过本章的学习，我掌握了散列结构和散列函数的相关概念，掌握散列结构的存储（散列表）的相关概念，要求掌握散列冲突处理方法（散列法）的相关知识，并能灵活运用散列法解决应用问题。

散列结构是使用散列函数建立数据结点关键字与存储地址之间的对应关系并提供多种当数据节点存储地址发生“冲突”时的处理方法而建立的一种数据结构。散列结构的查找等运算效率是很高的，本章中的散列函数、散列结构、散列表、散列法的基本概念和基本算法是重点，线性探测散列算法、链地址法散列算法和散列法的应用是难点。

第十章的学习重点是图的定义及性质，图的四种存储结构，图的两种遍历算法以及图的典型应用，包括最小生成树、最短路径、拓扑排序和关键路径等。通过本章学习，我掌握了图的概念和基本性质，图的存储结构（邻接矩阵和邻接表）及其基本算法、图的遍历及算法、图的最小生成树普利姆算法或者克鲁斯卡尔算法、图的最短路径迪杰斯特拉算法和弗洛伊德算法、有向无环图拓扑排序算法。了解了图的逆邻接表、十字链表、邻接多重表存储结构及其基本算法、关键路径求解算法，并能灵活运用图的不同的数据结构和遍历算法解决复杂的应用问题。

二．课程学习体会

在学习开始的时候，老师就明确提出它不是一种计算机语言，不会介绍C语言的变成语言，而是通过学习可以设计出良好的算法，高效地组织数据。一个程序无论采用何种语言，其基本算法思想不会改变。联系到在大一和大二上学期学习的C和C++语言，我深刻认识到了这一点。“软件开发好比写作文，计算机语言提供了许多华丽的辞藻，而数据结构则考虑如何将这些辞藻组织成一篇优秀的文章来。”在学习这门课中，要熟悉对算法思想的一些描述手段，包括文字描述、图形描述和计算机语言描述等。因此，计算机语言基础是必须的，因为它提供了一种重要的算法思想描述手段——机器可识别的描述。

这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。

三．对《数据结构与算法》课程教学的建议

1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生上课积极思考，不会开小差。

2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。

行动规则——算法的学习 第3篇

●生活算法——规则

世界著名教育技术学专家罗伯特·加涅认为, 问题都要通过规则的运用来解决, 规则是思维的材料。规则有许多种类, 语文中有发音、拼写、造句的规则;数学中有运算的规则;在信息技术中则有使用计算机这种技术工具的规则。除了“行”与“不行”、“可以”与“不可以”外, 还有针对方法与步骤等工作程序的规则。这样的规则是另一类形式的算法, 是应用技术工具解决问题的工作步骤的套路——生活算法。

生活算法与程序设计中的算法在形式与对象上有所不同。程序设计中的算法是针对计算机程序, 而生活算法是针对问题解决中的工作程序;程序设计中的算法用伪代码形式表现出来, 生活算法以更接近自然语言的形式表现出来。虽然表现形式不一样, 可它们的内涵却是一致的, 都是针对程序的规则。

能够熟练使用计算机的人, 会在不同的软件中得到一些规律性的知识。有了这些“经验”后, 再面对新的、没有见过的软件, 就会更快地适应、掌握这些软件。

我们可以在常见软件中得出这样的“规则” (见下表) 。

从这里看到, 保存文件的工作程序是先选择“文件”菜单, 然后再寻找“保存”命令……学习计算机操作的过程从陈述形式的程序开始到熟练掌握, 会在变式练习过程中找到其中的规律, 并且在规律中形成更简短的一般性规则。而这种算法性质的规则会在不同的软件使用情境中发挥作用。

面对不同的问题, 算法也会有简单、复杂的区别。一些并不“复杂”的工作程序中也会包含远远超过7±2个的简单操作。像“保存文件”这样常用的方法中, 需要有:1.移动鼠标, 单击菜单中的“文件”命令, 打开文件菜单;2.移动鼠标, 单击“保存”命令, 进入“另存为”对话框;3.移动鼠标到“另存为”对话框中, 单击保存位置右侧的向下箭头, 打开下拉菜单;4.在下拉菜单中移动鼠标, 单击本地磁盘 (D:) , 选择保存的磁盘位置;5.移动鼠标, 单击下面区域中的文件夹名称;6.移动鼠标, 在对话框中单击选择“打开”按钮;7.移动鼠标在“文件名”栏中单击, 使用键盘输入或者修改文件的名称……像“保存”这类常规的工作, 简单操作已经远远超出了人们工作记忆容量的限制。人们记忆计算机操作程序、问题解决的工作程序往往是记忆其工作套路的规则, 而不是记忆每一步的具体操作方法。从这里看, 算法在学习的过程中起到了重要的作用。对方法与步骤的学习以模式化为基础, 主要通过程序化和程序的合成两个机制来完成。程序化是指从陈述性知识到程序性知识的转换。“合成”是指将简单的合成为复杂的。

●生活算法的学习

算法的学习需要符合规则学习的特点。

加涅指出, 规则学习的内部条件是必须掌握与规则相关的概念。其中一个概念的含义搞不清楚, 就无法理解这一规则的含义。学生在学习这一规则的过程中, 单纯理解了这一规则还不够, 还需要通过若干次实验或实际应用才能牢固掌握这一规则。

信息技术课主要学习的是应用信息技术解决问题。算法是规则学习中的一个部分, 等同规则学习的规律。算法的学习也有两种形式, 一种是从例子到算法, 它属于发现学习的范畴;一种是从算法到例子, 它属于接受学习范畴。

算法的学习条件是必须能够获得若干体现算法的例证。当学生们第一次学习“写字板”或者“记事本”软件时, 其中的保存方法 (工作程序:单击“文件”→“保存”→在对话框中选择保存位置、文件名后保存……) 就成为了学生自己构建算法的例子。教师用讲解、演示工作程序来使初学者学会方法, 这对学习“保存”来说是一种接受学习。而“保存”这种方法将存于学生的记忆中, 与其他软件的“保存”发生作用, 对发现其中的规律来说, 就成为了其中的一个例子, 这时则成为一种发现学习。

当学生掌握了写字板中的保存、Word中的保存、PowerPoint的保存……头脑内部形成了保存的算法, 就会更容易地学会其他软件“保存”的方法。这时就是从算法的形成到自行工作的程序, 这是从算法到例子的学习。

算法有着不同的复杂度。学习者一方面在使用不同软件的过程中获得软件应用程序的算法。学习了写字板、记事本这类的软件有助于继续学习Word文字处理软件, 最终对文字处理软件有更深入的理解。另一方面, 会从下一级简单的工作中形成更复杂的算法。在“启动”→“输入文字”→“编辑排版”→“保存”→“退出”方法的规则中积累与形成最终对某个文字处理软件的使用 (如下图) 。

这时的学习者已经从有针对性的、具体的操作中逐渐向体会计算机的应用规则方面发展, 这也是从操作走向应用的一个过程, 是从计算机的知识向生活中的知识发展的过程。

●针对生活算法的教学

与操作方法、步骤相比较, 算法属于规则中的一种, 是更抽象的学习内容。生活算法可以从具体的工作程序中归纳、总结、抽象出来。因此教师的首要任务是促进学生的反思。要经常反思自己面对问题时的方法与步骤, 在面对同类问题时使用哪种工作程序更有效。在教学中, 需要帮助学生激活以往的生活经验, 回忆解决这一类问题的工作程序。然后从工作程序中进行总结与归纳, 得到规则性知识, 从而体会与掌握算法。这是从例子到算法的教学过程。解决具体问题的方法与步骤是形成算法的例子, 具体的问题则成为算法的应用环境。

在教学中, 教师还应当给学生充分尝试、验证的机会。学生的许多经验是在试误的过程中形成的。学生头脑中初步形成了算法后, 就可以设想出某个具体问题的工作程序。这种推理的工作程序需要有足够的时间和机会进行尝试、验证。如果工作程序不适合解决实际的问题, 则需要进行修正与优化。试误过程同时也是对工作程序进行修正与优化的过程。

教师要促进学生表达能力的提高。通过学生与学生之间、学生与教师之间的讨论和交流, 把自己的工作程序明确地表达出来。使学生从“能做”达到“能说”的水平, 这个过程是将程序知识以陈述形式表达出来的过程, 是将算法明确地表达出来的过程。

算法实验报告 第4篇

实验报告

班级

姓名

学号

****年**月**日

目录

实验一

二分查找程序实现…………………………………………………………………03页

实验二

棋盘覆盖问题（分治法）.…………………………………………………………08页

实验三

0-1背包问题的动态规划算法设计……………………………………………….11页

实验四

背包问题的贪心算法………………………………………………………………14页

实验五

最小重量机器设计问题（回溯法）………………………………………………17页

实验六

最小重量机器设计问题（分支限界法）…………………………………………20页

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验一：二分查找程序实现

一、实验时间：2013年10月8日，星期二，第一、二节地点：J13#328

二、实验目的及要求

目的：

建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。要求：

1、用c/c++语言实现二分搜索算法。

2、通过随机产生有序表的方法，测出在平均意义下算法比较次数随问题规模的变化曲线，并作图。

三、实验环境

平台：Win7 32位操作系统 开发工具：Codeblocks10.05

四、实验内容

对已经排好序的n个元素a[0：n-1]，现在要在这n个元素中找出一特定元素x。

五、算法描述及实验步骤

算法描述：

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果xa[n/2]，则我们只要在数组a的右半部继续搜索x。二分搜索法的应用极其广泛，而且它的思想易于理解。确定算法复杂度基本步骤：

1、首先设定问题规模n；

2、随即产生递增数列；

3、在n个有序数中随机取一个作为待查找量，搜索之；

4、记录查找过程中的比较次数，再次生成新的有序表并查找，记录查找次数，每个数组重复10次；

5、改变问题规模n重复上述步骤2~4，n取100、200……1000；

6、依实验数据作图，并与理论图作比较；

7、二分搜索算法平均查找次数： 问题规模为n时，平均查找次数为： A(n)=Int(logn)+ 1/2 // Int()函数为向下取整

即二分搜索算法对于含有n个数据的有序表L平均作了约Int(logn)+1/2次的查找操作。

实验步骤：

1.初始化生成递增随机数列： for(int j=100;j <=1000;j+=100){

array[0]=10+rand()%15;

for(int i=1;i

array[i]=array[i-1]+1+rand()%3+rand()%10;

} } 2.定义二分查找算法：

int BinarySearch(const int b[], int searchKey, int low, int high);其中，返回值为int类型，数组b[]为待查递增序列，searchKey为所查数据，low为数组b[]左下标，hight为数组b[]右下标。该算法实现过程为：

将数组b[]的n个元素分成个数大致相同的两半，取b[n/2]与searchKey作比较。如果searchKey=b[n/2]，则找到searchKey，算法终止；如果searchKeyb[n/2]，则只要在数组b的右半部继续搜索searchKey。

3.实现主函数并完成所有代码。4.算法复杂性分析：

容易看出，没执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O（logn）次。循环体内运算需要O（1）时间，因此整个算法在最坏情况下的计算时间复杂性为O（logn）。

六、调试过程及实验结果

输出结果为：

Every array repeat search times: 10 Number of Elements

理论平均查找次数

实际平均查找次数

6.5

6.1

200

7.5

7.3

300

8.5

7.4

400

8.5

7.4

500

8.5

7.5

600

9.5

8.2

700

9.5

8.8

800

9.5

8.7

900

9.5

8.8

1000

9.5

9.4

七、总结

二分查找在搜索有序表时，效率比较高。通过这次实验我对二分查找算法的认识又有了新的提高。本想写个图形界面，但由于种种原因，没有实现，下次做加密算法时，要写一个图形化界面。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验二：分治法解决棋盘问题

一、实验时间：2013年10月22日，星期二，第一、二节地点：J13#328

二、实验目的及要求

1、用c/c++语言实现分治法解决棋盘问题算法。

2、实现棋盘化以及棋盘覆盖

三、实验环境

Windows 2007 操作系统

以及code blocks软件

四、实验内容

在一个2^k*2^k的方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一个特殊方格。用分治法将整个棋盘除特殊方格以外的方格覆盖。

五、算法描述及实验步骤 将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：

左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格 右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格 左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格 右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格 当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。

六、调试过程及实验结果

七、总结

由于覆盖一个2k*2k棋盘所需的L型骨牌个数为（4k-1）/3，故此算法是一个在渐近意义下最优的算法。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验三：0-1背包问题的动态规划算法设计

一、实验目的及要求

1.了解并掌握动态规划算法的设计思想。

2.利用动态规划算法的设计思想实现0-1背包问题的算法设计。

二、实验环境

使用C++语言；

在windows环境下使用CodeBlocks调试并运行。

三、实验内容

1.了解并掌握动态规划的设计思想。

2.利用动态规划算法的思想解决0-1背包问题。

四、算法描述及实验步骤

每种物品一件，可以选择放1或不放0。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} “将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

五、调试过程及实验结果

六、总结

0-1背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成0-1背包问题求解。通过这次实验我对动态规划算法的认识又有了新的提高。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验四：背包问题的贪心算法

一、实验目的：

运用贪心算法思想，设计解决上述问题的算法，找出最大背包价值的装法。

二、实验要求

1.用c++语言实现背包问题的贪心算法。

2.掌握贪心思想的应用。

三、实验原理

在贪心算法中采用逐步构造最优解的办法，在每个阶段，都做出一个看上去最优的决策（在一定的标准下），决策一旦做出就不可更改。

四、实验过程(步骤)1.定义背包结构体： struct stone { int name;int weight;//物品的剩余重量

int weight_t;//物品的重量

float benefit;//物品的价值

//float b;};2.定义函数void sort(stone *data,int num)//计算物品的单位重量的价值，并进行排序 3.定义主函数并完成贪心选择。4.分析算法复杂性分析：

该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（n*logn）。

与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，可以选择物品i 可以选择物品 的一部分，而不一定要全部装入背包，1≤i≤n。这2类问题都具有最优子结构，最优子结构性质，极为相似，但 最优子结构 背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。

五、运行结果

六、实验分析与讨论 贪心法的基本思路：

——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。该算法存在问题：

1.不能保证求得的最后解是最佳的； 2.不能用来求最大或最小解问题；

3.只能求满足某些约束条件的可行解的范围。实现该算法的过程：

1.Begin 从问题的某一初始解出发； 2．while 能朝给定总目标前进一步 do 3.求出可行解的一个解元素；

4.由所有解元素组合成问题的一个可行解

七、实验心得

贪心算法通过一系列的选择来得知问题的解，它所做的每一个选择都是当前状态下局部最好选择，即贪心选择。通过背包问题的解决，进一步掌握了贪心算法的思想，并能在解问题时灵活运用。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验五：最小重量机器设计问题（回溯法）

一、实验目的

建立算法复杂度的理论分析与实验分析的联系，深刻体会算法复杂度作为算法的好坏评价指标的本质含义。

二、实验要求

1、用c++语言实现最小重量机器设计的回溯算法。

2、分析算法的计算复杂性

三、实验原理

首先，应该明确的确定问题的解空间。确定了解空间的组织结构后，发从开始节点（根节点）出发，以深度优先方式搜索整个解空间。这个开始结点成为活结点，同时也成为当前的扩展结点。在当前的扩展结点处，向纵深方向搜索移至一个新的结点。这个新结点成为新的活结点，并成为新的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点成为死结点。此时，应往回移动（回溯）至最近的活结点，并使这个活结点成为当前的扩展结点。回溯以这种工作方式递归的在解空间中搜索，直至找到所要求的解或解空间中已无活结点为止。

四、实验过程(步骤)由于题目已经给出总价格的上限，因此算法通过使用回溯来选择合适的机器使得在总价格不超过d时得到的机器重量最小。首先初始化当前价格cp=0,当前重量cw=0,此外，还要设置一个变量sum表示选择机器的总重量，初始化其为每个部件从1号供应商购买的重量。在循环选择i号机器时，判断从j号供应商购买机器后的价格是否大于总价格，如果不大于则选择，否则不选，继续选择下一供应商进行判断。在得到一个合适的供应商后，继续选择下一机器的供应商，从第一个选到最后一个供应商。当所有机器选择结束后，判断得到的总重量是否比之前的sum小，如果小就赋给sum，然后从这一步开始，回溯到上一机器，选择下一合适供应商，继续搜索可行解，直到将整个排列树搜索完毕。这样，最终得到的sum即为最优解。

数据说明：

N：零件数量

m：不同的零件商

W[][]:是从供应商j处购得的部件i的重量

c[][]：相应的价值 算法设计：

a.部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j 处购得的部件i的重量和相应价格，d为总价格的上限。

b.用递归函数backtrack(i)来实现回溯法搜索排列树（形式参数i表示递归深度）。

① 若cp>d，则为不可行解，剪去相应子树，返回到i-1层继续执行。

② 若cw>=sum，则不是最优解，剪去相应子树，返回到i-1层继续执行。

③ 若i>n，则算法搜索到一个叶结点，用sum对最优解进行记录，返回到i-1层继续执行；

④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(1≤j≤m）。

c.主函数调用一次Knapsack(1)即可完成整个回溯搜索过程，最终得到的sum即为所求最小总重量。

五、运行结果

六、实验心得

通过这次试验我明白了回溯法的思想，回溯法借助想象出来的树的结构，把问题简单化，使得解问题更方便。通过剪枝函数和约束函数对于求问题的解有很大的帮助，但要把一些限制条件把剪枝函数抽象化。

指导教师对实验报告的评语

成绩：

指导教师签字：

****年**月**日

实验六：最小重量机器设计问题（分支限界法）

一、实验时间：2013年11月12日，星期二，第一、二节地点：J13#328

二、实验目的及要求

1、了解分支限界法的基本思想。

2、运用分支限界法解决最小重量机器设计问题。

三、实验环境

平台：win7操作系统

开发工具：codeblocks10.05

四、实验内容

最小重量机器设计问题：设某一机器由n个部件组成，每一种部件可以从m个不同的供应商处购得。设wij是从供应商j处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过c的最小重量机器设计

五、算法描述及实验步骤

算法描述：

解空间为一棵排列树，采用优先队列式分支限界法找出所给的最小重量机器设计，开始时，将排列树的根节点置为当前扩展结点。在初始扩展结点处还设有选定部件是哪个供应商提供的，故cv=0，cw=0，position=0，peer=0，1≤i≤n。x[1:n]记录供应商的选择while完成对排列树内部结点的有序扩展。循环体内依次从活结点优先队列中取出具有最小重量的结点，依次为当前扩展结点。并且花费不超过c并加以扩展，队列为空时则结束循环。当peer=n时，此时扩展结点是叶节点，得到当前的最小重量和最优解数组x。若peer

实验步骤：

1.定义一个优先队列LinkQueue：

void InitQueue(LinkQueue &Q);//创建一个队列-----首尾结点 void DestroyQueue(LinkQueue &Q);//销毁一个队列 void ClearQueue(LinkQueue &Q);//清空队列

int QueueEmpty(LinkQueue &Q);//判断队列是否为空，空则返回TURE，否则返回FLASE int QueueLength(LinkQueue &Q);//求队列的长度

void EnQueue(LinkQueue &Q,QElemType &e);//拆入e为新的队尾元素 void DeQueue(LinkQueue &Q,QElemType &e);//用e返回队列的对头元素 bool IsEmpty(LinkQueue &Q)//判断队列是否为空 2.定义类MinWeight，实现函数有：

void Add(int wt,int ct,int i);//往队列插入节点 int FindBest();//实现最小重量机器的查找 void setMW();//函数初始化 void printMW();//打印输出结果 3 实现主函数并完成所有代码。

六、调试过程及实验结果

七、总结

利用分支限界法解决最小重量机器问题，就是构造一个优先队列，按照规定的优先级按最大效益优先的方式查找解空间树，找出满足要求的最优解。通过利用分支限界法解决最小重量机器问题，熟练了对分支限界法的使用。

指导教师对实验报告的评语

成绩：

指导教师签字：

算法学习报告 第5篇

关键词：位置信息场,目标定位,粒子群优化算法,极限学习机

0 引言

随着现代科学技术的发展，各种隐身技术日益成熟，使得传统定位技术已经无法满足各种目标跟踪的要求。无源定位是一种被动定位技术，其基于外辐射源实现，也称被动协同定位，因其低空探测能力、抗干扰能力强、隐蔽性高等优点，在航空和电子领域、现代战争中得到广泛的应用，成为当前的研究热点[1]。根据传感器数目，可分为多站无源定位和单站无源定位两类，多站无源定位利用多传感器探测到的目标方位信息，进行时空对准和航迹滤波，达到对目标探测、定位和航迹跟踪的目的[2]。相对于多点定位系统，单站定位系统具有成本低、灵活的优点，且不存多点定位系统的时间和数据同步的问题，引起了人们的广泛关注[3]。

单站定位实质是一种目标跟踪问题，即对目标运动轨迹进行估计，其核心思想为:在空间某个位置对辐射源的信息进行测量，然后通过选择一定算法根据获得的信息对射源目标位置进行建模和估计，从而实现目标定位[4]。测量主信息包括到达时间TOA(Time of Arrival)、波达方向DOA(Direction of Arrival)、到达时间差TDOA(Time Difference of Arrival)和到达频差FDOA(Frequency Difference of Arrival)等[5,6,7]，当前目标定位方法主要有粒子滤波、卡尔曼滤波、最小二乘法、支持向量机和神经网络等，其中粒子滤波、卡尔曼滤波和最小二乘法是一类线性估计方法，由于目标运动轨迹具有突变性，因此它们的定位精度有待进一步提高。支持向量机具有较强的非线性估计能力，可以获得较高的目标定位精度，但是其训练时间耗费相当长，计算复杂度高，不能满足现代目标定位的实时性要求，应用范围比较窄[8]。相对于其他定位方法，神经网络较好的解决了支持向量机训练时间长，粒子滤波、卡尔曼滤波和最小二乘法等非线性拟合能力差的缺陷，成为主要目标定位算法[9,10]。2004年，Huang等提出了极限学习机ELM(Extreme Learning Machine)，相对传统神经网络、支持向量机，其具有学习速度更快、参数少等优点，而且不需要先验知识，为目标定位提供了一种新的估计方法[11]。由于外界因素等影响，传感器测量信息存在一定的偏差，这样单次单站的定位精度比较低，难以满足目标定位的实际应用要求，为此文献[12]提出采用多次单站定位结果融合的目标定位技术，增加了信息量，提高了目标定位的精度。

为了提高了无源目标定位的准确性，提出一种基于粒子群算法优化极限学习机的无源目标定位算法(PSO-ELM)。首先采用单站对目标相关信息进行测量，然后通过高斯型核函数提到目标的位置信息场，最后通过ELM对目标位置进行建模，并采用粒子群优化(PSO)算法优化ELM参数，实现目标精确定位，并通过仿真结果验证了该算法的有效性。

1 目标定位的数学模型

目标位置信息场指目标在指定区域内的位置分布的函数，实际就是对目标位置分布特征进行描述，在二维空间中，可以采用位置概率分布密度描述目标位置特征，即:

其中，NT为目标数量;X表示目标可能分布的位置;KX为归一化系数;αi为目标在位置Xi存在可靠因子;δ()为狄拉克函数[13]。

在目标观测过程中，由于时域、频域限制，难以建立式(1)的方程，因此通常是式(1)的一个估计。设得到一些信号测量数据Z后，位置信息场函数可以描述为:

其中，,i=1，…，NT为Xi的估计结果;是Xi在处取极大值;式(2)中Z可描述成多个独立测量矢量的组合:

由于在位置信息测量过程中，不可避免会受到噪声污染，那么测量矢量可以描述为:

其中，hm(Xe)是目标位置Xe的确定性函数矢量;vm是测量矢量zm的测量误差矢量。

2 构建观测方程

设观测站位置为:XR=[0,0,0]T，目标和辐射源位置分别为:X=[x,y,z]T和XkTr=[xk,yk,zk]T，单站定位跟踪系统如图1所示。

根据目标角度信息建立的观测方程为:

由于测量过程存在一定误差，则有:

可得:

从图1可知:

构建关于俯仰角的观测方程:

对xcosθm+ycosθm在θ处泰勒展开可得:

那么式(9)化为:

俯仰角的观测方程变为:

根据时差的关系，构建方程:

将式(13)代入式(14)，并加上式(13)可得:

最后建立测量方程:

从测量方程可知，目标定位是一个典型的非线性估计问题，采用传统方法难以建立精确的目标定位目标模型，为此本文采用粒子群优化ELM参数，建立单站目标定位模型，以提高定位精度。

3 PSO-ELM模型

3.1 ELM算法

极限学习机是一种基于广义逆矩阵理论的新型前馈神经网络，相对于传统神经网络以及支持向量机，其可以通过一步求出网络的输出权值，加快学习的速度、提高了建模效率，其结构如图2所示[14]。

设有m个训练样本(xi,yi),xi表示输入向量，yi表示相应的输出i=1,2，…，m，一个隐含层，g(x)表示隐含层神经元激活函数，那么有:

设连接输入层与隐含层、连接隐含层和输出层的权重矩阵分别为ω和β，它们分别定义如下:

H为隐含层输出矩阵，其定义如下:

其中，b=[b1,b2，…，bl]T是隐含层的阈值。则根据图2可知:

其中，H+为隐含层输出矩阵H的Moerr-Penrose广义逆。

3.2 粒子群优化算法

粒子群优化(PSO)算法模拟鸟类的群体飞行觅食行为，在D维搜索空间中，第i个粒子(i=1,2，…，m)的位置为Ζi=(zi1,zi2，…，ziD),Vi=(vi1,vi2，…，viD)为粒子i的位置移动距离，Pi=(pi1,pi2，…，piD)表示第i个粒子“飞行”历史中最优位置，Pg=(pg1,pi2，…，piD)表示种群历史最优位置，粒子根据以下公式更新速度和位置:

其中，t表示迭代次数;c1,c2为学习因子;rand()是[0,1]之间的随机数;ω是惯性权重[15]。

由于惯性权重ω影响算法的搜索性能，本文采用线性变化更新惯性权重，具体为:

其中，ωmax为初始权重;ωmin为最终权重;tmax为最大迭代次数;t为当前迭代次数。

3.3 PSO-ELM算法步骤

1)初始化粒子群算法的参数，主要包括:粒子群N，最大迭代次数tmax,c1=c2=2。

2)设定隐含层神经元个数l的值以及参数范围，从而构建ELM网络结构。

3)根据ω、β和b初始化粒子群，并确定粒子自身和群体的历史最优位置。

4)将粒子群进行解码，得到ω、β和b，计算训练样本的输出yk∧，k=1,2，…，n,n为训练样本的数量，并计算粒子群的适应度值。

5)更新粒子飞行的权值、粒子群飞行的速度和位置。

6)将每一个粒子的位置与粒子自身和群体的历史最优位置进行对比，如果更优，就更新相应的位置。

7)更新当前迭代次数的数值，若当前迭代次数小于tmax时，则返回3)继续迭代。

8)根据种群最优粒子位置得以ELM网络参数ω、β和b，并建立的目标定位模型。

4 PSO-ELM的目标定位算法

由于目标位置与其位置信息场存在某种非线性关系，而且ELM具有强大的非线性逼近能力，因此可以采用PSO-ELM建立一种位置信息场到目标位置的映射模型，其步骤如下:

1)采集目标位置的信息场数据，并将其作为输入，目标实际位置作为输出，通过输入、输出构建学习样本。

2)由于信息包括DOA和TDOA，两者的范围比较大，对ELM学习过程产生不利影响，因此采用式(25)对其进行预处理，使DOA和TDOA的值处于[0 1]，以提高ELM学习效率。

其中，x'i是归一化之后的值，xmax和xmin分别是原始数据中的最大值和最小值。

3)将训练样本输入到ELM进行学习，并采用粒子群算法优化ELM参数，得出目标位置与位置信息场的非线性估计模型。

4)将待定位目标信号输入到建立的非线性估计模型中，输出模型的估计位置。

综合上述可知，PSO-ELM的目标定位算法如图3所示。

5 仿真实验

5.1 仿真环境

为了测试本文算法的性能，在Intel P4 4核心2.65 GHz CPU,8 GB内存、Windows 8操作系统上，采用Matlab 2009进行仿真实验。固定测向站的位置分别为(10,0,0)，定位区域内随机产生500个空间目标位置数据，前400个作为训练样本，最后100个作为测试样本。相同的测向条件下，在一定空间区域内，为了体现ELM优于其他神经网络，分别用本文算法和BP神经网络(BPNN)对空间目标进行定位，然后比较两种算法的定位精度。算法性能评价指标采用目标定位误差，其定义如下:

其中，(xp,yp,zp)、(x'p,y'p,z'p)分别表示真实位置和估计位置。

5.2 结果与分析

5.2.1 定位结果比较

PSO-ELM和BPNN的定位结果如图4所示。从图4可以清楚看出，PSO-ELM可以把目标位置进行较好的拟合，获得十分理想的定位结果，但BPNN的估计位置与实际位置偏差比较大，定位误差比较大，这主要由于PSO-ELM较好地克服BPNN过拟合的缺陷，能够建立更优的目标定位模型。结果表明，本文选择ELM进行目标位置建模，充分利用了位置信息场的数据，提高了目标定位精度。

5.2.2 定位误差比较

PSO-ELM与BPNN对目标x、y和z方向上的定位误差对比结果如图5所示。从图5可知，在x、y、z方向上，本文算法的定位精度普遍都高于BPNN，由于在x、y、z方向上定位精度提高，较好地弱化了几何定位误差，从而提高了目标定位的精度。

6 结语

感知机学习算法模拟与改进 第6篇

感知机采用有导师的学习规则,由一组描述网络行为的实例集合(训练集)给出:

其中,P为网络的输入,t为相应的正确输出。当输入作用到网络时,网络的实际输出与目标相比较,然后学习规则调整网络的权值和偏置值,从而使网络的实际输出越来越接近于目标输出。

感知机的结构:

该网络的输出为:a=hardlim(W p+b)

利用该公式可以方便的引用感知机网络中的单个元素。为此,首先考虑如下权值矩阵:

将构成W的第i个行向量定义为:

据此,可以将权值矩阵W重写为:

这样就可以将网络输出向量的第i个元素写成:

再根据hardlim传输函数的定义,如果权值矩阵的第i个行向量与输入向量的内积大于等于-bi,该输出为1,否则输出为0。

二、感知机的判定边界

考察有两个输入的单神经元感知机:

输出为:

将P1、P2看作二维空间的两个变量[3],则上式在输入空间定义了一条直线。该直线一侧的输入向量相应的网络输出为0;而直线上和另一侧的输入向量相应的网络输出侧为1。

图3描绘了权值为1,偏置值为-1的判定边界。权值1W将总是指向神经元输出为1的区域。

三、多输入神经元感知机学习算法模拟

1. 学习算法流程图

2. UML模型

本文用VC++6.0实现了以上算法,各个类UML模型如下:

WPub:

名称:公共函数类

功能:封装基本公用函数

WNNFunction:

名称:传输函数类

功能:封装了常用的传输函数

WMatrix:

名称:矩阵类

功能:封装了矩阵的常用操作方法

WNNLearning:

名称:感知机学习类

功能:封装了感知机学习算法

3. 程序运行界面

输入:

1.神经元个数

2.训练集大小

3.输入维数

4. 最大探测次数——若达到该值限定的循环次数算法仍未收敛则强行退出

5. 传输函数类型——此处仅置用到硬极限函数

6.[W-b]初始值——以矩阵形式输入,每行为一个神经元的权值加偏置向量。其中:每行的最后一个元素是b,其余是W

7. 训练集——以矩阵形式输入,每列是一个输入向量加目标输出。其中,每列的最后一个元素是t,其余是P

输出:

1.[W-b]最终值——形式同[W-b]初始值

运行:

1.输入各个参数

2.对输入参数作简单校验:

1)神经元个数是否与输入的W矩阵行数相等

2)训练集大小是否与输入的P矩阵列数相等

3)输入维数是否正确

3.点击“P”按钮,运行程序,显示结果如下

四、总结:

感知机网络结构简单,学习算法易于实现,但也有其局限性。

1.W,b的初始值对于运算过程和运算时间有影响,为了在有限步内求得收敛解,可以多次选择不同的初始值来求解,从中找到最优的初始值。初始值选取的不好,可能会导致算法长时间不能收敛,可以设定最大循环次数,若算法在此循环次数内不收敛则需要调整初始值。

2.感知机的判定边界是一个线性边界(超平面),因而感知机可以对那些能够被线性边界分开的输入向量进行分类。然而,许多问题并非是线性可分的,如异或。使感知机的应用受到很大限制。

摘要：20世纪50年代末,Frank Rosenblatt等人提出了一种称为感知机的神经元网络。引入了用于训练神经网络解决模式识别问题的学习规则。证明了只要求解问题的权值存在,那么其学习规则通常会收敛到正确的网络权值上。整个学习过程较为简单,而且是自动的。只要把反映网络行为的实例提交给网络,网络就能够根据实例从随机初始化的权值和偏置值开始自动的进行学习。

关键词：神经元,感知机,算法模拟

参考文献

[1].Martin T.Hagan,Howard B.Demuth,Mark H.Beale.神经网络设计[M].机械工业出版社2002.9.

[2].Rodney G.Winter.Madaline Rule II:A new method for training networks of Adalines.Stanford University,1989.

基于改进字典学习算法的人脸识别 第7篇

人脸识别由于其在身份验证、安全系统等方面的广泛用途吸引着众多的研究者,使得人脸识别成为计算机视觉领域中的一个经典问题[1]。

人脸识别领域广泛采用的特征提取方法有:主成分分析(PCA)[2]、线性判别分析法(LDA)[3]、独立成分分析(ICA)[4]等。其中PCA是寻找能表示采样数据的最好的投影子空间,PCA对样本的协方差矩阵进行特征值分解,前k个最大特征值所对应的特征向量为方向的子空间在最大程度上保持了原有数据信息的能量并进行了降维,简化了模型。但PCA要求数据满足高斯先验分布,且其找到的投影方向对于分类却不一定为最优。LDA是寻找能把两类样本分开的投影直线,使用最大化类间散度和类内散度之比作为目标函数来寻优。但LDA在应用时常常遇到维数问题。ICA是需在互相不干扰的情况下将数据进行线性分解,使其分解成统计独立的成分,ICA的前提是信号源独立且互不干扰。这3种方法全都是基于线性的方法,但在现实中数据往往不是特征的线性组合。

在字典学习中引入稀疏编码和判别分类约束项,并将其应用于拓展的稀疏表示模型中,保证了字典的表示能力和判别分类能力的同时保证了稀疏编码系数的鲁棒性。实验结果证明,方法识别率和算法复杂度均优于SRC人脸识别及K-SVD算法人脸识别。

2 拓展的稀疏表示人脸识别模型

稀疏表示人脸识别算法的目标是将测试人脸样本图像分解成少数原子的线性组合。SRC是低维线性模型,假设给定第i类人的n个训练样本Di=di,1,di,2,…di,n∈,则该类的测试样本yi∈Rm可以由已知样本来线性表示:

yi=di,1xi,1+di,2xi,2+…+di,n,xi,n

其中xi,j为标量。将k类训练样本组合成样本字典D=[D1,D2,…,Dk]=[d1,1,d1,2,…dk,nk],则未知类别的人脸图像可表示成y=Dx0其中稀疏编码系数向量x0=[0,…,0,xi,1,xi,2…xi,n,0,…0]T∈Rn,仅第i类的系数非零,其余类的系数全为零。

在实际应用中,因噪声或人脸图像的遮挡、损坏等问题使得上述优化问题中低维线性模型的前提被打破,因此,提出一种针对像素遮挡损坏的稀疏表示人脸识别模型,称为拓展的稀疏表示人脸识别模型,目标方程式为:

其中e表示噪声或者遮挡、损坏的像素,是低维线性模型的系数修正向量,I为单位矩阵。令B=[DI],则上式可改写为:

y=Bx

求解上式的L1范数最小化的解,即为稀疏编码系数:

min‖x‖1 s.t y=Bx

在理想情况下,测试样本可被同一类的训练样本很好地表示,如果这类图像训练的足够多则稀疏系数足够稀疏,但往往由于噪声或人脸图像的遮挡损坏使得特征局部稀疏,系数修正向量e同样稀疏,非零项大大超过理想情况下的,因此拓展的稀疏表示人脸识别模型比原始的稀疏表示人脸识别模型更能使系数修正向量的能量最小。将拓展的稀疏表示人脸识别模型表述为:

上式是NP难问题,最近在稀疏表示和压缩感知领域的研究[13]表明,在某一条件下,上式可等价于下列凸优化问题:

上式可通过基追踪(Base Pursuit,BP)[14]或者贪婪算法如匹配追踪(Matching Pursuit,MP)[15]、正交匹配追踪(Orthogonal Matching Pursuit,OMP)[16]等方法来求解。

根据所得的稀疏编码系数,可计算测试样本与各类训练样本之间的重构误差,根据最小重构误差所在的类来判断测试样本所属的类别,即重构误差系数最小的类别标示着测试样本所在的类别:

其中‖·‖2为L2范数,xi表示仅为第i类的稀疏系数,表示识别结果。

其人脸识别的识别性能取决于字典的表示能力和判别能力,所以字典的构建和优化成为提升人脸识别性能最为关键的一步。

2 字典学习及D-KSVD算法

2.1 字典学习

基于稀疏表示的人脸识别要求每类人有足够多的训练样本数以便能够形成类别子空间,采用的字典是由训练样本集按列排列组合而成,这使得字典过于庞大从而计算量迅速上增。字典学习的方法能有效地解决这些问题,下面详细介绍字典学习经典算法之一——K-SVD算法(广义K-均值算法)。

K-SVD是依据误差最小原则,对误差项进行SVD (singular value decomposition)分解,选择使误差最小的分解项作为更新的字典原子和对应的原子系数,经过不断的迭代从而得到优化的解。

输入训练人脸图像集和稀疏阈值T,K-SVD算法可以表示为:

其中‖.‖F表示F范数,字典D的每一列都是归一化的,X为稀疏编码系数矩阵,xi表示稀疏编码系数矩阵X的第i列,表示重构误差,字典D和稀疏编码系数X都未知,K-SVD是通过学习的方法,得到完备冗余字典,用来寻找一个局部最优解。

2.2 K-SVD算法的改进——D-KSVD

K-SVD的核心思想是:让每个原子最大化的发挥自身的作用来减少重构误差,等同于尽可能地减小字典中每一列的残差。字典的初始化可采用随机矩阵,但如果直接采用训练集中的数据作为初始值能更准确更快捷的获得具有很好的表示能力的字典。但K-SVD着重的是重构误差的最小化和稀疏编码系数的稀疏性,所以学习得到的字典在分类中没有判别能力。

针对K-SVD关注的是字典的表示能力(在字典下有效的稀疏编码),并不考虑字典的判别能力,提出同时具有表示能力和判分类能力的字典。在K-SVD的目标函数中添加约束项,结合字典和分类器的学习过程,将分类器参数嵌入字典中,使字典同时包含表示能力和判别监督信息,在后续字典的更新中约束项也同时更新。将改进的K-SVD算法叫做D-KSVD (Discrimination K-SVD)。该算法在字典学习模型中增加判别分类误差项来使字典学习更具表示能力和判别分类能力。

为了获得适用于分类的字典,在字典学习中引入分类性能项,如将简单的线性分类器用来判定分类器的好坏:

其中W,b为线性分类器H=W*a+b的参数,H表示训练图像的类别信息,每一列中有且仅有一个非零项,非零项标示着训练样本的类别信息,如第i列的类别信息为hi=[0,0,…,1,…,0,0]T,非零元素的位置标示着类别,‖H-W*α-b‖2表示分类误差,为了简单起见,将b设为零,‖W‖2表示正规惩罚项,β用来控制相关项权重的标量。

将线性分类器作为约束项添入K-SVD目标函数式中,则字典既包含表示能力又包含判别能力,表达式为:

其中γ和β均为控制相应项权重的标量。上式的迭代求解过程如图1所示。

一般来说,上式每次迭代都涉及3个优化问题,需3个优化问题同时达到收敛才能使上式达到收敛,所以上式很难达到收敛。为了解决这个问题,利用K-SVD来同步寻找3个优化问题的所有参数的,即D-KSVD的目标函数式可写为:

将矩阵的列归一化为单位向量,进一步归一化惩罚项‖W‖2,则最终的目标表达式可写为:

上式的本质问题同K-SVD一样,可通过更新字典原子来有效地解决,每个原子dk和相关稀疏编码系数xk可通过下式求解:

其中Ek=Y-∑i≠kdixi,xk表示信号yk的稀疏编码系数。上式可通过下式求解:

其中U(:,1)表示U的第一列,V(1,:)表示V的第一行。和表示更新后的dk和xk。

求解给定测试图像y的稀疏编码系数:

这是一个典型的稀疏编码问题,实际求解中常采取下列凸优化问题:

上式可通过L1范数优化求解,解的稳定性取决于字典D的相关性和稀疏编码系数x的稀疏性。最终测试样本图像的分类是将包含类别信息的稀疏编码系数x应用于简单的线性分类器W来获得:

l为一向量,稀疏编码系数x可被视为重构的测试图像的每个原子的权重,因此可以将W中的每一列ωk视为与每类原子dk的相似度,l=W*x则是测试图像y与每一类相似度的权重。其中l={0,0,…,1,…,0,0},l中仅有一个非零项,该非零项等于1,其位置标示着最终判断的类。

3 基于拓展的稀疏表示模型和D-KSVD的人脸识别

D-KSVD算法的目标方程式,其基础是SRC模型,即y=Dx,使用拓展的稀疏表示模型与D-KSVD结合来进行人脸识别,拓展的稀疏表示模型中字典D用D'=[DI]代替,x用代替,E表示所有系数修正向量构成的矩阵,带入目标方程式中可得:

上式因添加了系数修正项,更加鲁棒,同时提高了字典的表示能力,最终求解的稀疏编码系数应去除掉修正的部分。

提出的拓展的稀疏表示模型与D-KSVD的人脸识别方法是将训练样本集分类构造原始字典,通过D-KSVD压缩训练后联合,得到新字典和线性分类器参数,将测试样本在新字典上求解稀疏编码系数,并结合线性分类器参数进行判别分类,最终得到识别结果,流程图如图2所示。

4 结语

为人脸识别提出一种学习方法——基于拓展的稀疏表示和D-KSVD的人脸识别。通过在原始K-SVD算法的目标函数式中添加判别项使学习得到的过完备字典既包含表示能力又包含判别分类能力。该方案源自于K-SVD算法,能被有效地求解。通过同时求解所有参数——具有判别分类信息的字典和分类器,使得字典包含判别分类信息。但在字典更新和求解稀疏编码系数过程中存在着矩阵求逆过程,增加了算法的复杂度,解决矩阵求逆的复杂度问题正在进一步研究中。

摘要：为了提高基于稀疏表示的人脸识别速度和对图像的噪声、遮挡、损坏的鲁棒性,提出了拓展的稀疏表示模型和D-KSVD(Discrimination K-SVD)的人脸识别算法。在原始的稀疏表示模型中添加了残差向量作为系数修正向量,使得拓展的稀疏表示模型具有更强的鲁棒性。针对字典学习中只包含表示能力没有包含类别信息的问题,在字典学习中添加了稀疏编码和分类器参数约束项,在字典学习的过程中同时更新稀疏编码和分类器参数,使字典中包含很好的表示能力和判别分类能力,用其稀疏编码系数进行人脸识别分类时能获得更好的识别性能。

关键词：稀疏表示,字典学习,人脸识别,D-KSVD算法

参考文献

[1]L.K.Chih,J.Ho,D.J.Kriegman.Acquiring linear subspaces for face recognition under variable lighting[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(5):684-698.

[2]陈伏兵,高秀梅,张生亮,杨静宇.基于分块PCA的人脸识别方法[J].小型微型计算机系统,2006,27(1 0):1943—1947.

[3]H.Yu,J.Yang.A direct LDA algorithm for high dimensional data with application to face recognition[J].Journal of Pattern Recognition,2001,34(10):2067-2070.

[4]J.Kim,J.Choi,J.Yi.Effective representation using ICA for face recognition robust to local distortion and partial occlusion[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2005,27(12):1977-1981.

强化学习的一些基本算法和应用 第8篇

强化学习最早可以追溯到巴普洛夫的条件反射实验。它综合了控制理论、统计学、心理学等相关学科发展而来。从20世纪50年代提出到最近的80、90年代, 强化学习才在人工智能、机器学习和自动控制领域得到广泛研究和应用, 取得了飞速发展。特别是随着强化学习的数学基础研究取得较大突破之后, 强化学习的研究成为当前人工智能的热点之一。

2 强化学习的原理和模型

2.1 强化学习模型

强化学习是由智能体根据环境状态s来选择策略做出动作a, 然后状态s在动作a的作用下转变为s’, 环境给出一个瞬时奖励r, 智能体根据回报奖励r和变化状态s’学习到新的知识和策略, 根据策略π, 做出下一动作r’。动作r在同一策略π下的累计回报函数可以由如下算式来表示:

实际要考虑状态变化s’、状态变化概率p、回报奖励函数r’和策略π*, 并考虑由此带来的总收益值V (s’) 。在经典的马尔科夫算法中, 通过建立模型, 多次学习, 获得最佳的期望结果值函数, 让智能体学习到最好的行为。

2.2 马尔科夫决策过程 (Markov Decision Process)

马尔科夫决策过程是对时间参数、离散时间、有限的动作空间和有限的状态空间进行建模, 获得期望报酬值的总和, 是一个折扣报酬值的总和。由四元组<S, A, R, P>定义。S是环境状态集合, A是系统行为集合, R为奖励函数集合:S×A→R和状态转移函数P:S×A→PD (S) 。记Rass′为系统在状态s采用a动作使环境状态转移到s′获得的瞬时奖赏值;记Pass′为系统在状态s采用a动作使环境状态转移到s′的概率。状态转移函数和瞬时奖励函数是描述环境模型的一部分, 这两个函数只与当前动作和当前环境有关, 与历史动作和历史状态无关。

2.3 值函数和最优值函数

值函数在强化学习中是一个最终追求目标, 它可以反映出强化学习效果的好坏, 是某个环境状态 (状态-动作) 对的函数, 由于奖励函数是对状态-动作对的即时评价, 所以值函数也是对奖赏的一种预测, 也就是期望获得奖励的总和。因此, 快速得到值函数的计算方法是强化学习算法中研究的热点问题。

模型中四个要素的关系如图1所示, 智能体根据模型和计算, 通过策略π (某一时刻唯一) 做出一个动作a, 改变当前状态s→s’, 计算出由此动作得到影响后面状态得到的折扣奖励值和Vπ (s) , 用公式表示如下:

其中Eπ{}称为策略π的期望值, Vπ称为策略π的状态值函数。根据相应策略选中动作a作用于状态s→s’, 再考虑环境状态的变化概率, 则该状态-动作对的期望值函数为:

基于环境状态-动作对的策略不同, 执行之后的效果也有不同, 所得到的奖励R也不同, 为了能得到最好的奖励, 在s状态下的值函数要考虑不同学习循环下返回的期望函数, 在这些策略之中, 必然有一个策略π, 其所对应的s状态下的值函数是最高的, 则称其为最佳策略π*。根据Bellman最优策略公式, 在最优策略π*下, 系统在s状态下的最优值函数如下表示:

3 强化学习的几种算法

3.1 差分瞬时学习方法 (Temporal Difference Methods)

比较著名的瞬时差分学习方法是Sutton在1988年于信度分配问题解决方案时提出的, 设观测数据为X1、X2、X3…Xm, Z, 其中XI是在t时刻得到的观测向量, Z是最终的结果, 对每个观测-结果序列, 相应的预测序列为p (1) 、p (2) 、p (3) …p (m) , 其中p (t) 都是z的估计值。

假设p (t) 用神经网络来实现, 每个观测, 就决定了一个变化量△wt, 一个完整的序列处理完毕之后, w按下式修改:

定义目标函数:

监督学习权值的修改过程是:

其中η是学习率, 将[z-p (t) ]表示成时刻t之后的预测变化之和, 即:

这里p (m+) 1=z

这样, (5) 式可以写成:

其中, η为学习效率。

3.2 Q-学习算法

Q-学习和模型无关, 由马尔科夫决策过程变化得来, 不仅依赖当前状态的瞬时奖赏值, 也可以利用下一状态的瞬时奖赏值, 一直到终结状态。Q-学习迭代时采用环境-动作奖赏和Q’ (s, a) 作为衡量和评价的标准。Q-学习算法的基本形式如下:

从这个算式中看到, Q-学习的目标就是估算出, 对某个状态, 状态概率和奖赏值并不是十分重要, 如果后续效果更好, 它的Q值就会较高。Q-学习中较简单的形式为单步Q-学习, 其Q值迭代公式:

其中, Q (s t, at) 是状态动作对的值函数表示按照π策略, 执行动作at之后所得报酬总和, α为学习因子, γ为折扣率。

3.3 sarsa算法

Sarsa也是采用Q-学习的算法进行迭代, 不过在计算时它不用Q-学习中的最大Q值, 而是用和上一步估算得到的等值Q-值进行下一步策略的选择和动作的实施。sarsa是一种通过当前策略选取s′状态下选取动作a′。所以, sarsa是一种在线学习策略算法, sarsa算法的更新如下式表示:

Sarsa算法在每一步中, 根据策略选择动作at+1, 学习到知识, 继续做出下一个时刻 (t+1) 的动作at+1。通过上式的Q值估算, 选定这一刻的动作, 同样通过当前的Q值计算, 确定下一时刻的动作。Sara算法的具体过程如下: (1) 初始化Q (S, A) 值; (2) 重复:根据当前状态Q值, 选择策略π做出动作a; (3) 执行动作a, 得到状态s’和奖励r; (5) 根据s’和策略π'来选择下一个时刻的动作a’; (6) 更新Q (s, a) 值s←s', a←a'; (7) 直至s为目标状态。

4 强化学习的应用

在智能机器人足球比赛中, 机器人可以通过强化学习, 利用环境-动作函数的最优值函数, 调整出最佳策略, 做出动作, 提高学习经验和能力, 赢得比赛。在著名的Robo Cup上, 强化学习在足球机器人上的应用相当广泛和成功, 仿真平台和类人机器人等一系列比赛都需要强化学习的支持。在游戏娱乐方面, 人工智能在游戏中的应用能极大提升娱乐性和交互性。最早的就是Samuel的下棋程序, 近来Tesauro把TD方法应用于Backgammon。Backgammon有1 020个状态, Tesauro采用三层BP神经网络把棋盘上棋子的位置与旗手的获胜概率联系起来, 获得极高胜率。

在管理调度中的应用电梯是一个最典型的例子。在一个10层楼4部电梯的环境中, 如果只用传统的方法, 每个电梯都有位置、方向、速度和一些表示乘客要离开的位置状态。这是一个很庞大的状态集合, 传统方法很难管理。而强化学习可以应用于这种环境的管理调度, 实行随机优化控制, 产生巨大的经济价值。在工业生产中有很多需要进行系统控制的地方, 在强化学习刚刚普及应用的时候, 最典型的例子就是倒立摆控制系统。这是一个非线性不稳定系统, 许多强化学习的讨论都把这一控制系统作为验证各种强化学习算法的实验系统。当倒摆保持平衡, 给它一个奖励, 倒立摆失败时, 给它一个负奖励 (惩罚) 。另外在控制过程中, 通过让控制器自我学习, 得到最终理想的控制动作。

5 结语

国内的强化学习还处于起步阶段, 与欧美、日本等国家相比还有很大差距, 一些专家学者用强化学习方法、瞬时差分TD方法、Q学习的算法在经济预测、非线性控制仿真实验和智能机器人等方面做了很多研究, 取得了一些成果。因此, 要继续加大对强化学习的进一步深入发展, 提高强化学习的实践应用。

参考文献

[1]祝宇虹, 毛俊鑫.基于人工情感与Q学习的机器人行为决策[J].机械与电子, 2011 (7) .

[2]陈学松, 杨宜民.强化学习研究综述[J].计算机应用研究, 2010 (8) .

基于主动学习的支持向量机算法 第9篇

随着现代科技的进步,以及人们管理和知识水平的提高,现实世界中需要处理的数据量越来越大。2008年9月,《Nature》杂志出版了一个专刊,讨论大数据存储、管理和分析问题[1],之后麦肯锡公司、《Science》杂志也相继出版了大数据报告及研究专刊[2],围绕科学研究中大数据的问题进行了深入讨论,说明了大数据问题处理的重要性和必要性。因此,大数据问题的研究目前已经成为人工智能领域的热点问题。为了能够从规模庞大、联系紧密、结构复杂、类型多样的数据中提炼出有用知识,针对大数据的数据挖掘技术研究近年来受到了研究者的广泛关注。数据挖掘[3]是指从大规模的、不完整的、有噪声的、模糊的、随机的复杂数据集中提取潜在有用的信息或知识。

支持向量机[4](Support Vector Machine,SVM)是一种近年来受到广泛关注的机器学习方法,在模式识别[5]、函数回归[6]、图像识别[7]、时间序列预测[8]和生物信息学[9]等诸多领域得到成功的应用。然而,由于支持向量机的训练优化过程中需要构建和计算大规模的核矩阵,因此,当数据规模较大时,矩阵运算非常繁琐,学习器的效率很低。目前,采用支持向量机方法对大规模数据进行处理没有特别有效的方法,使其既能够提高学习效率,又可获得较好的泛化能力。因此,如何提高支持向量机处理大数据的能力成为近年来机器学习领域的一个研究热点[10]。

近年来,主动学习[11]由于其在降低样本复杂度方面比传统机器学习方法具有明显的优势,成为目前的一个提高学习器效率的常见手段。在主动学习过程中,学习器能够主动地选择包含信息量大的未标注样本,将其交由专家标记,然后加入训练集进行训练,从而在训练集较小的情况下获得较优秀的学习结果,有效降低构建学习器的代价[12]。

本文结合主动学习思想,提出了一种基于主动学习的支持向量机加速方法。该方法首先随机选择部分训练样本作为初始工作集,并采用支持向量机训练得到初始的分类器和初始支持向量,然后根据主动学习思想,选择初始分类器附近的样本点与已得到的初始支持向量合并构成新的工作集再次进行支持向量机的学习,并得到新的分类器和新的支持向量集合,以构建新的工作集进行训练,如此循环往复,直到得到的分类器达到要求时为止。由于基于主动学习的支持向量机方法仅保留了前一次训练得到的支持向量和前一次训练所得到的分类器附近的部分样本点,因此其训练样本规模较小,有效提高了其处理海量数据的分类能力。

1 支持向量机分类方法

支持向量机可用来解决分类和回归问题。支持向量机解决二分类问题的目的就是构造最优分类面,所谓最优分类面就是要求分类面不但能将两类示例无错误地分开,而且要使两类示例的分类间隔最大。

假设训练集为{(xi,yi)}li=1,xi∈Rd是空间的向量,yi表示分类标识,yi∈{-1,1}。如果输入向量集合是线性可分离的,则分类面方程为:

对式(1)进行归一化,使得训练集满足:

根据结构风险最小化(SRM)原理,即求解以下约束最优化问题:

对于该模型,采用Lagrange乘子法,上述问题可转化为求其对偶问题:

式中αi为拉格朗日乘子。

一般情况下,训练集不是完全线性可分的,此时分类器允许有一定的误差,因此引入非负变量ξi≥0,构造软间隔最优分类超平面,对应最优化问题变成如下形式:

式中C为软间隔惩罚参数,用于调节分类超平面宽度与分类允许误差的平衡。

对于复杂非线性可分问题,SVM通过引入核方法,将低维空间的训练数据通过映射函数Φ映射到高维空间,使其线性可分,但在实际问题中,显示的映射函数Φ是很难得到的,因此这里采用核函数K(x,x′)进行样本的映射,使得K(x,x′)=Φ(x)⋅Φ(x′)。常见的核函数包含高斯核、多项式核和线性核等[13]。

2 基于主动学习的支持向量机加速算法

设数据集X={x1,···,xi,···,xn}且xi∈Rd,其中n为样本个数,d为样本维度。首先从样本集X中随机选择1 s的样本作为初始训练集X0,以训练SVM得到初始的近似分类器f0及初始支持向量集SV0,然后在剩余的样本集X /X0中选择距离初始分类器f0最近的样本x′,并与初始向量集SV0合并,构成新的训练集 ,并训练新的SVM模型,得到新的分类器f1和新的支持向量集SV1,如此循环往复,直到所得到的学习器的泛化能力不再增强为止。

基于主动学习的支持向量机加速算法具体如下:

初始化:设初始训练数据集为X={x1,⋅⋅⋅,xi,⋅⋅⋅,xn}且xi∈Rd,其中n为样本个数,d为样本维度,设定初始训练样本集规模参数s,支持向量机的核函数为K,核参数为p,惩罚因子为C。

Step1:将初始训练集X随机划分为s个子集,即X→{X1,X2,⋅⋅⋅,Xs};

Step2:取其中任意一个子集作为初始训练集X(0)训练得到SVM学习器,得到初始的分类器f(0)和初始的支持向量集SV(0);并得到当前未处理样本集Xr(1)=X X(0);

Step3:计算当前未处理样本集Xr(t)中任意一个样本xj到当前最新得到的分类器f(t-1)的距离d(xj,f(t-1)),并选择出与f(t-1)距离d(xj,f(t-1))最小的样本x(t),即

Step4:将新计算得到的样本x(t)与上次SVM训练所得到的支持向量集SV(t-1)合并,构成新的训练样本集 ,并训练SVM学习器,得到新的分类器f(t)和新的支持向量样本集SV(t);

Step5:判断新得到的分类器f(t)的泛化性能(测试精度)g(f1),若g(f(t))>g(f(t-1)),则t=t+1并返回Step3继续迭代;否则执行Step6。

Step6:算法结束,得到最终的最优分类器f(t-1)。

3 实验结果及分析

为验证基于主动学习支持向量机加速算法的性能,本文在五个标准数据集[13]上进行实验,具体见表1。支持向量机的核函数采用高斯核,核参数及惩罚参数采用网格搜索的方式确定,核参数P的网格搜索范围为0.5,0.6,0.7,0.8,0.9,1.0,1.1,1.2,1.3,1.4,1.5;惩罚参数的搜索范围为10,100,1 000,10 000和100 000,取每个工作子集上对应精度最高的核函数参数P和惩罚参数C为训练的最优参数;初始训练集构造规模参数s均取5。

为检验本文所提的基于主动学习的SVM方法的性能,本文与标准SVM学习算法进行比较。表2为本文提出的AL_SVM算法与标准SVM算法在各数据集上的训练和测试结果的对比。

从表2可以看出,采用本文提出的基于主动学习的AL_SVM方法在数据集Banana与Letter上与传统SVM方法的测试精度相同,而在数据集Diabetis、Germany及Titanic上测试精度也相差不大,而在5个数据集上,训练所得到的支持向量个数却都减少了很多,这说明采用本文提出的基于主动学习的AL_SVM方法能够舍弃大量不重要的支持向量,使得原本复杂的学习器变得更为简单,一定程度上减少了过拟合效应。此外,从算法运行效率上看,在5个数据集上,本文提出的方法都有非常明显的提高,这是由于本文的方法通过主动学习模型,将原来大规模样本的二次优化问题转化成了一系列小规模的二次优化问题,因此节省了计算优化问题的时间和复杂度。

综上可看出,由于本文提出的基于主动学习的AL_SVM方法采用了主动学习模式,通过随机抽取部分训练集训练得到初始分类器,然后根据训练所得到的分类超平面信息来从剩余样本中选择对于改进学习器最有价值的样本加入训练集,并有效地提取了训练样本中包含重要分类信息的支持向量样本,删除了那些对模型复杂度影响较高而对于分类器泛化性能影响不大的样本,从而以较高的学习效率处理大规模数据的分类问题,同时保证了模型的泛化性能。

4 结论