svm分类算法
一、数据源说明
1、数据源说远和理解：
ticeval2000.txt: 这个数据集是需要预测（ 4000个客户记录）的数据集。它和
ticdata2000.txt它具有相同的格式，只是没有最后一列的目标记录。我们只希望返回预测
目标的列表集，所有数据集都用制表符进行分隔。共有4003（自己加了三条数据），根据要
求，用来做预测。
tictgts2000.txt：最终的目标评估数据。这是一个实际情况下的目标数据，将与我们预
测的结果进行校验。我们的预测结果将放在result.txt文件中。
数据集理解：本实验任务可以理解为分类问题，即分为2类，也就是数据源的第86列，
可以分为0、1两类。我们首先需要对ticdata2000.txt进行训练，生成model，再根据model
进行预测。
2、数据清理
代码中需要对数据集进行缩放的目的在于：
a、避免一些特征值范围过大而另一些特征值范围过小；
b、避免在训练时为了计算核函数而计算内积的时候引起数值计算的困难。因此，通常将
数据缩放到 [ -1,1] 或者是 [0,1] 之间。
二、数据挖掘的算法说明
1、 svm算法说明
2、实现过程
在源程序里面，主要由以下2个函数来实现：
(1) struct svm_model *svm_train(const struct svm_problem *prob, const struct
svm_parameter *param);
该函数用来做训练，参数prob，是svm_problem类型数据，具体结构定义如下： struct
svm_problem //存储本次参加运算的所有样本(数据集)，及其所属类别。 { int n; //记录样本总数
double *y; //指向样本所属类别的数组
struct svm_node **x; //指向一个存储内容为指针的数组
};
其中svm_node的结构体定义如下：
struct svm_node //用来存储输入空间中的单个特征
{
int index; //输入空间序号，假设输入空间数为m double value; //该输入空间的值
};
所以，prob也可以说是问题的指针，它指向样本数据的类别和输入向量，在内存中的具
体结构图如下：
图1.1libsvm训练时，样本数据在内存中的存放结构
只需在内存中申请n*(m+1)*sizeof(struct svm_node)大小的空间，并在里面填入每个
样本的每个输入空间的值，即可在程序中完成prob参数的设置。参数param，是
svm_parameter数据结构，具体结构定义如下：
struct svm_parameter // 训练参数
{
int svm_type; //svm类型，
int kernel_type; //核函数类型
int degree; /* for poly */
double gamma; /* for poly/rbf/sigmoid */ double coef0; /* for poly/sigmoid */ /* these are for training only */ double cache_size; /* in mb 制定训练所需要的内存*/ double eps; /* stopping criteria */ double c; /* for c_svc, epsilon_svr and nu_svr ，惩罚因子*/ int nr_weight; /* for c_svc 权重的数目*/ int *weight_label; /* for c_svc 权重，元素个数由nr_weight 决定*/ double* weight;
/* for c_svc */
double nu; /* for nu_svc, one_class, and nu_svr */ double p; /* for epsilon_svr */ int shrinking; /* use the shrinking heuristics 指明训练过程是否使用压缩*/ int probability; /* do probability estimates 指明是否要做概率估计*/ } 其中，svm类型和核函数类型如下：
设定完这两个参数，就可以直接在程序中调用训练函数进行训练了，该其函数返回一个
struct svm_model *svm模型的指针，可以使用svm_save_model(const char
*model_file_name, const struct svm_model *model)函数，把这个模型保存在磁盘中。至
此，训练函数的移植已经完成。
(2) double svm_predict(const struct svm_model *model, const struct svm_node *x);
参数model，是一个svm模型的指针，可以使用函数struct svm_model
*svm_load_model(const char *model_file_name)，导入训练时保存好的svm模型，此函数
返回一个svm模型的指针，可以直接赋值给变量model。
参数x，是const struct svm_node结构体的指针，本意是一个输入空间的指针，但实
际上，该函数执行的时候，是从参数x处计算输入空间，直到遇到单个样本数据结束标记-1
才结束，也就是说，该函数运算了单个样本中的所有输入空间数据。因此，在调用此函数时，
必须先把预测样本的数据按图3.4中的固定格式写入内存中。另外，该函数只能预测一个样
本的值，本文需要对图像中的所有像数点预测，就要使用for循环反复调用。
该函数返回一个double类型，指明被预测数据属于哪个类。面对两分类问题的时候，通
常使用+1代表正样本，即类1；-1代表负样本，即类2。最后根据返回的double值就可以知
道预测数据的类别了。
三、算法源代码及注释说明
1、需要在工程中添加头文件 svm.h 和源文件svm.cpp
2、自己编写的源代码（c++实现）（共230行）：
#include svm.h
#include <iostream>
#include <list>
#include <iterator>
#include <vector>
#include <string>
#include <ctime> using namespace std;
#ifdef win32
#pragma warning (disable: 4514 4786) #endif svm_parameter param;
svm_problem prob;
svm_model *svmmodel;
list<svm_node*> xlist; list<double> ylist ; const int max=10;
const int ntsttimes=10;
vector<int> predictvalue; vector<int> realvalue; int trainnum=0;
//设置参数
void setparam()
{
param.svm_type = c_svc;
param.kernel_type = rbf;
param.degree = 3;
param.gamma = 0.5;
param.coef0 = 0;
param.nu = 0.5;
param.cache_size = 40;
param.c = 500;
param.eps = 1e-3;
param.p = 0.1;
param.shrinking = 1;
// param.probability = 0;
param.nr_weight = 0;
param.weight = null; param.weight_label =null;
}
void train(char *filepath) { file *fp;
int k;
int line=0;
int temp; if((fp=fopen(filepath,rt))==null) return ; while(1)
{
svm_node* features = new svm_node[85+1]; for(k=0;k<85;k++)
{
fscanf(fp,%d,&temp);
features[k].index = k + 1; features[k].value = temp/(max*1.0) ; } features[85].index = -1; fscanf(fp,%d,&temp);
xlist.push_back(features); ylist.push_back(temp); line++;
trainnum=line;
if(feof(fp))
break;
} setparam();
prob.l=line;篇二：svm分类器-人脸识别专题报告
svm分类器-人脸识别专题报告
摘要：本次试验报告，介绍了人脸识别方法分类器的设计并进行人脸识别。主要是设计
svm分类器，并用来进行人脸分类识别，并对分类器实验结果做出分析。实验主要步骤：首
先对图像预处理，转换成向量，再通过pca算法对orl人脸数据库图像进行降维特征提取，
运用svm工具箱对数据进行训练，再利用svm分类方法对特征向量进行分类识别，寻找和待
识别图片最为接近的训练样本第一张图片。最后在matlab上进行实验仿真，分析实验结果。
关键字：最近邻法、pca算法、多类svm、人脸识别
1.引言
人脸识别是模式识别的一个发展方向和重要应用，人脸检测和识别在安全识别、身份鉴
定、以及公安部门的稽查活动中有重要作用。本文主要使用pca算法、多类svm训练和svm
分类器设计人脸识别算法。从orl人脸图像数据库中，构建自建人脸训练数据库和测试数据
库，采用k-l变换进行特征脸提取，并实现人脸识别。通过k-l变换在人脸识别中的应用，
加深对所学内容的理解和认识，进一步加深理解模式识别的算法。
2.人脸识别系统
完整的人脸识别系统至少包括两个主要环节。首先在输入图像中找到人脸的位置即人脸
检测，将人脸从背景中检测出来；其次，将检测到的人脸图像进行预处理、特征提取和识别。
如下图1所示：
图 1
人脸识别系统虽然有诱人的应用前景，但是在现实中却还没有开始大规模的使用。目前，
国内外多所大学和研究机构已研制出一些较好的人脸识别原型系统，一些较成熟的商业人脸
识别系统也已投入应用，但从技术的角度来看，大样本集、非可控条件下的稳健识别技术仍
不成熟，用计算机自动进行人脸的定位和识别十分困难，目前的识别效果（正确率，速度）
不如其他的生物识别技术，如指纹识别，视网膜识别等等。人们在日常生活中就进行了大量
的人脸定位和识别工作，当然全部是由人的视觉系统和大脑“自动”进行的。目前还不清楚
人的视觉系统和大脑的工作原理，因此这项人可以轻而易举完成的任务，牵涉到模式识别、
图
象处理及生理、心理学等方面的诸多知识，对于目前还只会死板地执行程序指令的计算
机来说却是极端困难。
3.算法简述
3.1 pca算法
3.2 svm算法
支持向量机（support vector machine,svm）是在统计学理论的基础上发展起来的新一
代学习算法，它在文本分类、手写识别、图像分类、生物信息学等领域中获得较好的应用。
相比于容易过度拟合训练样本的人工神经网络，支持向量机对于未见过的测试样本具有更好
的推广能力。
svm是一个二分器，只能用于2类样本的分类，现在我们将它推广到多类问题。本文是
对svm进行推广到能够处理多类问题。采用一对一的投票策略。将a、
b、c、d 4类样本两类两类的分成训练集，即（a,b）、(a,c)、（a,d）、(b,c)、（b,d）、（c,d）,
得到6个（对于n类问题，为n(n-1)/2个）svm二分器。在测试的时候，把测试样本x依次
送入这6个二分器，采取投票形式，最后得到一组结果。投票是以如下方式进行。
初始化：vote(a)=vote(b)=vote(c)=vote(d)=0.
投票过程：如果使用训练集（a,b）得到的分类器将x判定为a类，则vote(a)=vote(a)+1，
否则vote(b)=vote(b)+1；如果使用（a,c）训练的分类器将x判定为a类，则
vote(a)=vote(a)+1,否则vote(c)=vote(c)+1；...;如果使用（c,d）训练的分类器将x判定
为c类，则vote(c)=vote(c)+1,否则vote(d)=vote(d)+1。
最终判决：max(vote(a),vote(b),vote(c),vote(d))。如有两个以上的最大值，则一般
可以简单地取第一个最大值所对应的类别。
4.实验步骤
该实验选取的是orl人脸数据库作为实验样本，总共40个人，实验样本分为训练样本和
测试样本。首先设置训练样本集，选择40个人前5张图片作为训练样本，进行训练，并将训
练后的数据存放到multisvmtrain.mat中保存。然后设置测试样本集，将40个人后5张图片
作为测试样本，进行选取识别。实验流程图如下：
整个训练过程，包括读入图像，pca降维，以及多类svm训练，实现的关键代码如下：
display(读入人脸数据...);
[imgrow,imgcol,facecontainer,facelabel]=readfaces(nfacesperperson,nperson); ... display(pca降维...);
[pcafaces, w] = fastpca(facecontainer, 20); % 主成分分析pca % pcafaces是200*20的矩阵, 每一行代表一张主成分脸(共40人，每人5张)，每个脸
20个维特征
...
%数据规格化
display(scaling...);
[x,a0,b0] = scaling(x);
训练完毕后，将数据保存。
（2）开始识别：
打开一张图片（每个人的后5张中选择），然后对该图片进行pca变换降维，特征提取、
规格化，从保存的训练数据库中读取数据，通过svm分类器识别该测试样本的类别，并显示
该图片对应人的第一张图片和类别。主要代码如下： % 读入相关训练结果
display(载入训练参数...);
load(mat/multisvmtrain.mat); xnewface = readaface(newfacepath); % 读入一个测试样本
xnewface = double(xnewface); xnewface = (xnewface-meanvec)*v; % 经过pca变换降维
xnewface = scaling(xnewface,1,a0,b0);
xnewface = readaface(newfacepath); % 读入一个测试样本
xnewface = double(xnewface); xnewface = (xnewface-meanvec)*v; % 经过pca变换降维
xnewface = scaling(xnewface,1,a0,b0);
（3）最后进行测试：
测试是指分类所有的测试样本（40个人的后50张图像，共200个样本），并计算识别率。
主要实现代码如下：
nfacesperperson = 5;
nperson = 40;
btest = 1;
% 读入测试集合
display(读入测试集合...);
[imgrow,imgcol,testface,testlabel] = readfaces(nfacesperperson, nperson,
btest);
% 读入相关训练结果
display(载入训练参数...);
load(mat/pca.mat);
load(mat/scaling.mat);
load(mat/traindata.mat);
load(mat/multisvmtrain.mat); % pca降维
display(pca降维处理...);
[m n] = size(testface);
testface = (testface-repmat(meanvec, m, 1))*v; % 经过pca变换降维 testface =
scaling(testface,1,a0,b0);
% 多类 svm 分类
display(测试集识别中...);
classes = multisvmclassify(testface); display(..............................); % 计算识别率
nerror = sum(classes ~= testlabel); accuracy = 1 - nerror/length(testlabel); display([对于测试集200个人脸样本的识别率为, num2str(accuracy*100), %]);
5.实验仿真
该实验在matlab上进行实验仿真，主要包括样本的训练、保存，打开一张待识别图片，
然后调用训练数据库，对该图片进行识别，并显示出该人的第一张图片和该人的类别，以及
对全部测试样本进行分类，并计算识别率。
实验仿真结果图如下：
篇三：svm算法简介
（一）svm的简介
支持向量机(support vector machine)是cortes和vapnik于1995年首先提出的，它在
解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合
等其他机器学习问题中。
支持向量机方法是建立在统计学习理论的vc 维理论和结构风险最小原理基础上的，根
据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，accuracy）和学习能力
（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力（或称泛
化能力）。
以上是经常被有关svm 的学术文献引用的介绍，我来逐一分解并解释一下。 vapnik是
统计机器学习的大牛，这想必都不用说，他出版的《statistical learning theory》是一本
完整阐述统计机器学习思想的名著。在该书中详细的论证了统计机器学习之所以区别于传统
机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等
等一系列问题。与统计机器学习的精密思维相比，传统的机器学习基本上属于摸着石头过河，
用传统的机器学习方法构造分类系统完全成了一种技巧，一个人做的结果可能很好，另一个
人差不多的方法做出来却很差，缺乏指导和原则。
所谓vc维是对函数类的一种度量，可以简单的理解为问题的复杂程度，vc维越高，一
个问题就越复杂。正是因为svm关注的是vc维，后面我们可以看到，svm解决问题的时候，
和样本的维数是无关的（甚至样本是上万维的都可以，这使得svm很适合用来解决文本分类
的问题，当然，有这样的能力也因为引入了核函数）。
结构风险最小听上去文绉绉，其实说的也无非是下面这回事。
机器学习本质上就是一种对问题真实模型的逼近（我们选择一个我们认为比较好的近似
模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不知道的（如果知道了，
我们干吗还要机器学习？直接用真实模型解决问题不就可以了？对吧，哈哈）既然真实模型
不知道，那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。比如说
我们认为宇宙诞生于150亿年前的一场大爆炸，这个假设能够描述很多我们观察到的现象，
但它与真实的宇宙模型之间还相差多少？谁也说不清，因为我们压根就不知道真实的宇宙模
型到底是什么。
这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。我们
选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我
们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的
结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个
差值叫做经验风险remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标，但
后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却一塌糊涂
（即所谓的推广能力差，或泛化能力差）。此时的情况便是选择了一个足够复杂的分类函数（它
的vc维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。回头看看
经验风险最小化原则我们就会发现，此原则适用的大前
提是经验风险要确实能够逼近真实风险才行（行话叫一致），但实际上能逼近么？答案是
不能，因为样本数相对于现实世界要分类的文本数来说简直九牛一毛，经验风险最小化原则
只在这占很小比例的样本上做到没有误差，当然不能保证在更大比例的真实文本上也没有误
差。
统计学习因此而引入了泛化误差界的概念，就是指真实风险应该由两部分内容刻画，一
是经验风险，代表了分类器在给定样本上的误差；二是置信风险，代表了我们在多大程度上
可以信任分类器在未知文本上分类的结果。很显然，第二部分是没有办法精确计算的，因此
只能给出一个估计的区间，也使得整个误差只能计算上界，而无法计算准确的值（所以叫做
泛化误差界，而不叫泛化误差）。置信风险与两个量有关，一是样本数量，显然给定的样本
数量越大，我们的学习结果越有可能正确，此时置信风险越小；二是分类函数的vc维，显然
vc维越大，推广能力越差，置信风险会变大。
泛化误差界的公式为：
r(w)≤remp(w)+ф(n/h)
公式中r(w)就是真实风险，remp(w)就是经验风险，ф(n/h)就是置信风险。统计学习的
目标从经验风险最小化变为了寻求经验风险与置信风险的和最小，即结构风险最小。
svm正是这样一种努力最小化结构风险的算法。
svm其他的特点就比较容易理解了。
小样本，并不是说样本的绝对数量少（实际上，对任何算法来说，更多的样本几乎总是
能带来更好的效果），而是说与问题的复杂度比起来，svm算法要求的样本数是相对比较少的。
非线性，是指svm擅长应付样本数据线性不可分的情况，主要通过松弛变量（也有人叫
惩罚变量）和核函数技术来实现，这一部分是svm的精髓，以后会详细讨论。多说一句，关
于文本分类这个问题究竟是不是线性可分的，尚没有定论，因此不能简单的认为它是线性可
分的而作简化处理，在水落石出之前，只好先当它是线性不可分的（反正线性可分也不过是
线性不可分的一种特例而已，我们向来不怕方法过于通用）。
高维模式识别是指样本维数很高，例如文本的向量表示，如果没有经过另一系列文章（《文
本分类入门》）中提到过的降维处理，出现几万维的情况很正常，其他算法基本就没有能力应
付了，svm却可以，主要是因为svm 产生的分类器很简洁，用到的样本信息很少（仅仅用到
那些称之为“支持向量”的样本，此为后话），使得即使样本维数很高，也不会给存储和计算
带来大麻烦（相对照而言，knn算法在分类时就要用到所有样本，样本数巨大，每个样本维
数再一高，这日子就没法过了……）。
下一节开始正式讨论svm。别嫌我说得太详细哦。
svm入门（二）线性分类器part 1 线性分类器(一定意义上,也可以叫做感知机) 是最简单也很有效的分类器形式.在一个
线性分类器中,可以看到svm形成的思路,并接触很多svm的核心概念.
用一个二维空间里仅有两类样本的分类问题来举个小例子。如图所示
c1和c2是要区分的两个类别，在二维平面中它们的样本如上图所示。中间的直线就是
一个分类函数，它可以将两类样本完全分开。一般的，如果一个线性函数能够将样本完全正
确的分开，就称这些数据是线性可分的，否则称为非线性可分的。
什么叫线性函数呢？在一维空间里就是一个点，在二维空间里就是一条直线，三维空间
里就是一个平面，可以如此想象下去，如果不关注空间的维数，这种线性函数还有一个统一
的名称——超平面（hyper plane）！
实际上，一个线性函数是一个实值函数（即函数的值是连续的实数），而我们的分类问题
（例如这里的二元分类问题——回答一个样本属于还是不属于一个类别的问题）需要离散的
输出值，例如用1表示某个样本属于类别c1，而用0表示不属于（不属于c1也就意味着属
于c2），这时候只需要简单的在实值函数的基础上附加一个阈值即可，通过分类函数执行时
得到的值大于还是小于这个阈值来确定类别归属。例如我们有一个线性函数
g(x)=wx+b 【看到好多人都在问g(x)=0 和 g(x)的问题，我在这里帮楼主补充一下：g(x)实际是以
w为法向量的一簇超平面，在二维空间表示为一簇直线（就是一簇平行线，他们的法向量都
是w），而g(x)=0只是这么多平行线中的一条。】我们可以取阈值为0，这样当有一个样本
xi需要判别的时候，我们就看g(xi)的值。若g(xi)>0，就判别为类别c1，若g(xi)<0，
则判别为类别c2（等于的时候我们就拒绝判断，呵呵）。此时也等价于给函数g(x)附加一个
符号函数sgn()，即f(x)=sgn [g(x)]是我们真正的判别函数。
关于g(x)=wx+b这个表达式要注意三点：一，式中的x不是二维坐标系中的横轴，而是
样本的向量表示，例如一个样本点的坐标是(3,8)，则xt=(3,8) ，而不是x=3（一般说向量
都是说列向量，因此以行向量形式来表示时，就加上转置）。二，这个形式并不局限于二维的
情况，在n维空间中仍然可以使用这
个表达式，只是式中的w成为了n维向量（在二维的这个例子中，w是二维向量，为了
表示起来方便简洁，以下均不区别列向量和它的转置，聪明的读者一看便知）；三，g(x)不是
中间那条直线的表达式，中间那条直线的表达式是g(x)=0，即wx+b=0，我们也把这个函数叫
做分类面。
实际上很容易看出来，中间那条分界线并不是唯一的，我们把它稍微旋转一下，只要不
把两类数据分错，仍然可以达到上面说的效果，稍微平移一下，也可以。此时就牵涉到一个
问题，对同一个问题存在多个分类函数的时候，哪一个函数更好呢？显然必须要先找一个指
标来量化“好”的程度，通常使用的都是叫做“分类间隔”的指标。下一节我们就仔细说说
分类间隔，也补一补相关的数学知识。 svm入门（三）线性分类器part 2 上回说到对于文本分类这样的不适定问题（有一个以上解的问题称为不适定问题），需要
有一个指标来衡量解决方案（即我们通过训练建立的分类模型）的好坏，而分类间隔是一个
比较好的指标。
在进行文本分类的时候，我们可以让计算机这样来看待我们提供给它的训练样本，每一
个样本由一个向量（就是那些文本特征所组成的向量）和一个标记（标示出这个样本属于哪
个类别）组成。如下：
di=(xi,yi)
xi就是文本向量（维数很高），yi就是分类标记。
在二元的线性分类中，这个表示分类的标记只有两个值，1和-1（用来表示属于还是不
属于这个类）。有了这种表示法，我们就可以定义一个样本点到某个超平面的间隔：
δi=yi(wxi+b)
这个公式乍一看没什么神秘的，也说不出什么道理，只是个定义而已，但我们做做变换，
就能看出一些有意思的东西。
首先注意到如果某个样本属于该类别的话，那么wxi+b>0（记得么？这是因为我们所
选的g(x)=wx+b就通过大于0还是小于0来判断分类），而yi也大于0；若不属于该类别的
话，那么wxi+b<0，而yi也小于0，这意味着yi(wxi+b)总是大于0的，而且它的值就等
于|wxi+b|！（也就是|g(xi)|）
现在把w和b进行一下归一化，即用w/||w||和b/||w||分别代替原来的w和b，那么间
隔就可以写成
【点到直线的距离，做解析几何中为：
d = (ax + by + c) /sqrt(a^2+b^2) sqrt(a^2+b^2)就相当于||w||, 其中向量w=[a, b]; (ax + by + c)就相当于g(x), 其中向量x=[x,y]。】
这个公式是不是看上去有点眼熟？没错，这不就是解析几何中点xi到直线g(x)=0的距
离公式嘛！（推广一下，是到超平面g(x)=0的距离， g(x)=0就是上节中提到的分类超平面）小tips：||w||是什么符号？||w||叫做向量w的范数，范数是对向量长度的一种度量。
我们常说的向量长度其实指的是它的2-范数，范数最一般的表示形式为p-范数，可以写成如
下表达式
向量w=(w1, w2, w3,…… wn) 它的p-范数为
看看把p换成2的时候，不就是传统的向量长度么？当我们不指明p的时候，就像||w||
这样使用时，就意味着我们不关心p的值，用几范数都可以；或者上文已经提到了p的值，
为了叙述方便不再重复指明。
当用归一化的w和b代替原值之后的间隔有一个专门的名称，叫做几何间隔，几何间隔
所表示的正是点到超平面的欧氏距离，我们下面就简称几何间隔为“距离”。以上是单个点到
某个超平面的距离（就是间隔，后面不再区别这两个词）定义，同样可以定义一个点的集合
（就是一组样本）到某个超平面的距离为此集合中离超平面最近的点的距离。下面这张图更
加直观的展示出了几何间隔的现实含义：
h是分类面，而h1和h2是平行于h，且过离h最近的两类样本的直线，h1与h，h2与h
之间的距离就是几何间隔。
之所以如此关心几何间隔这个东西，是因为几何间隔与样本的误分次数间存在关系：篇
四：svm的smo算法实现
svm的smo算法实现
摘要
支持向量机（support vector machine）是一种新近出现的解决模式识别问题的有效工
具。它的数学模型可以归结为一个有约束的二次规划问题。如何快速准确地解这个二次规划，
是svm推广应用中的一个重要环节。我们尝试了数种可能的方法，用程序实现了其中最有效
的一种——smo算法（sequential minimal optimization algorithm），并用块算法的思想
（chunking）对其作出了改进。本文将先给出待解决的数学模型，介绍我们所做的一些尝试，
然后着重讨论smo算法的原理、程序实现及其独特优势，最后阐述我们自己的一些新思想，
主要是经过改进的chunking smo算法，并在附录中介绍svm的基本原理。
svm的数学模型
这里简要介绍支持向量机（svm）数学模型的引出过程，关于svm的详细介绍将在附录中
给出。
支持向量机的原理是用分类超平面将空间中两类样本点正确分离，并取得最大边缘（正
样本与负样本到超平面的最小距离）这样，原问题为一个有约束非线性规划问题：
minimize12w2
yi(xi?w?b)?1?0?(w,b)? i?1,2,...,l 范数最小的满足约束的w就是最优分类超平面的法向量。目标函数是严格上凹的二次型，
约束函数是下凹的，这是一个严格凸规划。按照最优化理论中凸二次规划的解法，我们把它
转化为wolfe对偶问题来求解：
maxmize
s.t.1lw(α)???i???i?jyiyjxi?xj2i,ji?1l??iyi?0 i?1l
?i?0i?1,...,l 其中αi正是样本点xi的lagrange乘子。kuhn-tunker条件定理指出，无效约束所对应
的lagrange乘子一定为0，在这里的物理意义也就是说非支持向量xi（对应着原问题中的约
束 yi(w’xi＋b)－1>0 ）的lagrange乘子一定为0。这样分类规则就仅由恰好在超平面
边缘上的少数支持向量（对应着约束yi(w’xi＋b)－1＝0）决定，而与其它样本无关。“支
持向量机”这一名称由此而来。
对于非线形情况，只需将对偶问题中的点积用卷积核函数k(xi,xj)代替。对于样本点
不可分的情况，构造软边缘分类面，最终得到的wolfe对偶问
题与原来相似，只是α多了一个上限约束。这个上限c代表着对错分样本的惩罚力度，
在边缘之内的样本对分类面的构造所起的作用是有限制的，这就是所谓“软边缘”的含义。
最后，由于求最大值可以转化为取负求最小值，这一数学模型最终表达为：
1minimizewolfe(α)??th??[1,1,...1]l?2 s.t.??yi
i?1li?0
i?1,...,l 0??i?c
其中h是一个半正定的对称阵[yiyjk(xi,xj)]li,j=1（线性的情况也就是(xy)t(xy),
x=[x1,x2,…,xl], y=diag(y1,y2,…,yl), ）α=[α1, α2,…,αl]t 这个对偶问题仍是一个有约束的二次规划，它的kuhn-tucker条件（在svm的文献中多
称为kaush-kuhn-tucker条件）也可等价地表示为
?i?0?yiui?1
0??i?c?yiui?1
?i?c?yiui?1 其中ui就是分类面（在非线性下不一定是超平面）函数作用在xi上的输出：
ui??y?k(x,x)?b jjji
j?1l
这一kkt条件在我们的问题中有其具体的物理意义：第一种情况是说xi是非支持向量，
在分类面边缘以外，其lagrange乘子为0，对分类面的构造没有影响；第二种情况是说xi
是正好在分类面上的支持向量，对应着非零的lagrange乘子；第三种情况是说xi在分类面
边缘以内甚至被错分，其lagrange乘子受到上限的限制而为c。
关于二次规划算法的探索
wolfe对偶问题比原始问题易于处理，它把问题转化成了在非负象限内对以样本的
lagrange乘子为变量的半正定的二次函数wolfe进行优化，并服从一个的等式约束。但由于
问题规模比较大，再加上目标函数的二次型已不是正定的，而且约束个数较多，又是等式约
束和不等式约束的混合问题，在样本点不可分时还要加以上限的约束。这种复杂局面使得很
多高效的算法对此束手无策，svm方法至今未能得到广泛的应用，难以找到快速的算法不能
不说是一个重要的原因。
二次规划是一种常见的优化问题，关于二次规划有一套比较成熟的理论。最初我们试图
把这个问题作为一个纯数学问题来对待，从寻优理论中找到一种能解决我们的问题的数值方
法，但是可以说是以失败告终。不过，我们还是了解到不少二次规划的一般方法，并从中总
结了一些经验。
在二次规划中，条件极值问题的通常解法有罚函数法和单纯形法。
罚函数法在以往曾被作为一种标准的svm算法。其基本思想是将解不满足约束条件的程
度作为惩罚项加在目标函数中，将条件极值问题转化为无条件极值
问题来处理，求得其解后增大惩罚力度，将上一步的结果作为下次寻优的起始迭代点，
再求解无条件极值问题，直到解满足约束为止。其中的无约束极值问题可以用共轭梯度法求
解。典型的共轭梯度法针对的是对称正定的二次规划问题，进行n步迭代一定得到最优解。
对于半正定的问题，共轭梯度法也会是可行的，但n步迭代不能结束，算法的停止条件应设
为梯度范数在允许误差范围内（也就是说目标函数没有很大下降余地了算法就结束）。我实验
室成员曾对此算法进行过研究，并向我介绍了他们当时的工作。此算法用c语言实现后效果
并不理想，当样本点增加到30个时算法开始变慢，并经常出现不收敛的现象。这是因为梯度
范数并不能准确地代表目标函数的下降余地，有时迭代一步调整太大，“过犹不及”，导致了
一种“矫枉过正”的局面。解决的办法是调整惩罚因子大小以及修正迭代步长计算公式。因
此程序的执行伴随着试探性的调试过程，这需要调试者充分了解这种算法的原理并具有丰富
的调试经验。样本数目进一步增多，算法将完全不能收敛。我们参考了算法的c语言源程序，
没有找到可作重大改进的地方。也许共轭梯度法本身并不适合我们的问题。
单纯形法是先随机找到一个可行点作为初值点，构造以可行点为顶点的单纯形，然后按
某种搜索策略逐步缩小单纯形，直至各顶点间的距离在允许误差范围内为止。单纯形法解决
的问题标准形式正与我们的问题相符，我实验室成员也对这种算法进行过研究，发现计算结
果与初值关系较大，如果能凭先验经验选择一个离最优解较近的初值点，算法就能很快收敛，
否则很容易陷入死循环。而这正违背了支持向量机法的初衷之一：仅凭科学的模式识别方法
而不是先验知识来作出划分。这种方法看来也不可行。
其它各种文献中介绍的一些二次规划方法大多是针对某种特殊问题的，如要求目标函数
的hessian矩阵对称正定，或只能解决单纯的等式约束问题，或只能解决单纯的不等式约束
问题，都很难符合我们的要求。
另外，matlab的optimization软件包里有一个适用于各种二次规划问题的现成程序
quadprog，我们用matlab编了一个程序调用这个函数，有一定效果，但样本个数增加到200
个时，不但计算较慢，而且结果很不理想，这可能与数值方法所特有的误差积累效应有关。
matlab的函数是针对很一般的二次规划问题的，不可能考虑到我们这个问题本身的特点，效
率不高也在我们意料之中。
smo算法
在大量地查阅二次规划的一般方法的同时，我们也在努力从svm本身的角度寻求解答，
也就是说，问题所提供的信息并不完全包含在这个二次规划的数学问题中，从问题本身的物
理意义出发还是有可能做出突破的。最终我们果然在john c. platt 1999年的一篇论文[2]
中找到了这样的方法。
一．smo算法的原理
这一被称为“顺次最小优化”的算法和以往的一些svm改进算法一样，是把整个二次规
划问题分解为很多易于处理的小问题（后面我们将探讨smo与以往svm改进算法之间的联系），
所不同的是，只有smo算法把问题分解到可能达到的最小规模：每次优化只处理两个样本的
优化问题，并且用解析的方法进行处理。我们将会看到，这种与众不同的方法带来了一系列
不可比拟的优势。
对svm来说，一次至少要同时对两个样本进行优化（就是优化它们对应的
lagrange乘子），这是因为等式约束的存在使得我们不可能单独优化一个变量。
所谓“最小优化”的最大好处就是使得我们可以用解析的方法求解每一个最小规模的优
化问题，从而完全避免了迭代算法。
当然，这样一次“最小优化”不可能保证其结果就是所优化的lagrange乘子的最终结果，
但会使目标函数向极小值迈进一步。我们再对其它lagrange乘子做最小优化，直到所有乘子
都符合kkt条件时，目标函数达到最小，算法结束。
这样，smo算法要解决两个问题：一是怎样解决两个变量的优化问题，二是怎样决定先
对哪些lagrange乘子进行优化。
二．两个lagrange乘子的优化问题（子程序takestep）
我们在这里不妨设正在优化的两个lagrange乘子对应的样本正是第一个和第二个，对两
个lagrange乘子α1和α2，在其他乘子不改变的情况下，它们的约束条件应表达为正方形
内的一条线段。（如图1）
α1 a1 = c α1 α1 = c α2 = 0 α2 = 0 在这条线段上求一个函数的极值，相当于一个一维的极值问题。我们可以把α1用α2
表示，对α2求无条件极值，如果目标函数是严格上凹的，最小值就一定在这一极值点（极
值点在区间内）或在区间端点（极值点在区间外）。α2确定后，α1也就确定下来了。因此
我们先找到α2优化区间的上下限制，再在这个区间中对α2求最小值。
由图1我们容易得到α2的上下限应为：
l=max(0,α2－α1)，h=min(c,c+α2 –α1) , 若y1与y2异号；
l=max(0,α2 +α1－c), h=min(c, α2 +α1) ,若y1与y2同号；
令s=y1y2标志这两个样本是否同类，则有
l=max(0, α2+sα1－ 1/2 (s+1)c), h=min(c, α2 +sα1 –1/2 (s－1)c) 而α1和
α2在本次优化中所服从的等式约束为：
α1＋sα2=α01+sα02=d
下面我们推导求最小值点α2的公式：由于只有α1，α2两个变量需要考虑，目标函数
可以写成
wolfe(α1,α2)=1/2 k11α21+1/2 k22α22 + sk12α1α2 + y1α1v1 +y2α2v2 －α1
－
α2+常数
其中kij=k(xi,xj) , vi=y3α03ki3+…+ylα0lkil = ui+b0－ y1α01k1i – y2α
01k2i 上标为0的量表示是本次优化之前lagrange乘子的原值。
将α2用α1表示并代入目标函数：
wolfe（α2）=1/2 k11(d-sα2)2+1/2 k22α22+sk12(d-sα2) α2 +y1(d-sα2)v1 – d+sα2+y2α2v2－α2+常数
对α2求导：
dwolfe(α2)/dα2
=－sk11(d－sα2)+k22α2－k12α2+sk12(d－sα2)－y2v2+s+y2v2－1 ＝0 如果wolfe函数总是严格上凹的，即二阶导数k11+k22－2k12>0, 那么驻点必为极小
值点，无条件的极值点就为
α2＝[s(k11－k12)d+y2(v1－v2)＋1－s] / (k11＋k22－2k12) 将d,v与α0,u之间关系代入，就得到用上一步的α02，u1,u2表示的α2的无条件最优
点：
α2＝[α02(k11＋k22－2k12) +y2(u1－u2＋y2－y1)] / (k11＋k22－2k12) 令η=k11＋k22－2k12为目标函数的二阶导数，ei=ui－yi为第i个训练样本的“误差”，
这个式子又可以写为
α2＝α02＋y2(e1－e2)/η
除非核函数k不满足mercer条件（也就是说不能作为核函数），η不会出现负值。但η
=0是可以出现的情况。这时我们计算目标函数在线段两个端点上的取值，并将lagrange乘
子修正到目标函数较小的端点上：
f1=y1(e1+b)－α1k(x1,x1)－sα2k(x1,x1) f2=y2(e2+b)－sα1k(x1,x2)－α2k(x2,x2) l1=α1+s(α2－l)
h1=α1+s(α2－h)
wolfel=l1f1+lf2+1/2 l21k(x1,x1)+1/2 l2k(x2,x2)+sll1k(x1,x2) wolfeh=h1f1+hf2+1/2 h21k(x1,x1)+1/2 h2k(x2,x2)+shh1k(x1,x2) 当两个端点上取得相同的目标函数值时，目标函数在整条线段上的取值都会是一样的（因
为它是上凹的），这时不必对α1，α2作出修正。
α2的无条件极值确定后，再考虑上下限的限制，最终的α2为
?*2?h????2?l?如果?2?h如果l??2?h 如果?2?l 最后，由等式约束确定α1：
α1*=α1+s(α2－α2*)
三．选择待优化lagrange乘子的试探找点法
事实上即使我们不采用任何找点法，只是按顺序抽取αi，αj的所有组合进行优化，目
标函数也会不断下降，直到任一对αi，αj都不能继续优化，目标函数就会收敛到极小值。
我们采取某种找点方法只是为了使算法收敛得更快。
这种试探法先选择最有可能需要优化的α2，再针对这样的α2选择最有可能取得较大修
正步长的α1。这样，我们在程序中使用两个层次的循环：
内层循环（子程序examineexample）针对违反kkt条件的样本选择另一个样本与它配对
优化（指优化它们的lagrange乘子），选择的依据是尽量使这样一对样本能取得最大优化步
长。对其中一个lagrange乘子α2来说优化步长为|(e1－e2)/η|,但由于核函数估算耗时较
大，我们只用|e1－e2|来大致估计有可能取得的步长大小。也就是说，选出使得|e1－e2|最
大的样本作为第二个样本。需要注意的是，这样的步长估计是比较粗略的，选择出来的一对
样本有时非但不能“一劳永逸”地“一步到位”，反而不能作出进一步调整，（例如η=0的情
况，最小优化问题的二次型只是半正定的）。这时我们遍历所有非边界样本（非边界样本篇五：
分享-文本分类实验报告
北京邮电大学 2013-2014学年第1学期实验报告
（代码就不分享了，都是文本格式处理的代
码.欢迎大家批评指正！）
课程名称：数据仓库与数据挖掘
实验名称：svm文本分类
实验完成人：
姓名：学号：
姓名：学号：
姓名：学号：
日期： 2013 年11 月
实验一：svm文本分类
1. 实验目的
? 熟悉爬虫的使用，可以利用网络爬虫抓取所需的网络语料 ? 熟悉中文分词软件，可以
熟练使用接口完成分词任务 ? 熟悉文本分类必要的预处理步骤，并运用到实验实践中 ? 熟
悉特征提取方法，包括chi-square 和 lda特征提取
? 了解svm机器学习方法，可以运用开源工具完成文本分类过程
2. 实验分工
xxx：
(1) 运用爬虫对语料库新闻的收集
(2) 对数据的预处理工作
(3) 后期的不同对比试验的测试
xxx:
(1) 特征的提取
(2) 训练集和测试集的生成
(3) 后期的不同对比试验的测试
3. 实验环境
中文分词与lda特征提取运行环境:
(1) java version 1.7
(2) 开发环境:eclipse
python代码运行环境：
(1)python 3.2 4. 主要设计思想
4.1 实验工具介绍
web crawler:由实验室集体开发的网络爬虫，不对外公开。可以方便的通过正则表达式
的配置，轻松的完成对网络数据的提取，并且可以根据需求完成过滤老新闻、不合适的网址格式等功能。最终的爬取结果文件已经经过程序处理，可以直接得到最需要得到的内容。例如：在此实验中，最终的爬取结果即为已经从网站中提取出的新闻标题和正文。
ictclas：全称为汉语词法分析系统。具有简易的图形演示界面，和不同语言的api接口，开发者可以根据自己的需求选择不同的接口。主要功能包括中文分词；词性标注；命名实体识别；新词识别；同时支持用户词典；在今年的12月中下旬会发布ictclas2014版本。 lib svm: 是由台湾大学林智仁副教授等开发的一个简单、易于使用和快速有效的svm模式识别与回归的软件包。除了主体训练，测试的程序，还提供了一些使用的工具，例如子集的选择，参数的选择与归一化的操作等实用的方法。
jgibblda: 使用java实现了latent dirichlet allocation(lda)，使用了gibbs采样来进行参数估计。
4.2 特征提取与表达方法的设计
在此次实验中，我们采用了两种特征提取的方法。针对不同的方法提取的特征分别作了文本分类实验。所有的特征提取与特征表达的详细步骤会在5.3种进行描述。
chi特征提取：
根据上面的公式，最终建立成了数据字典。
经过chi特征提取建立成数据字典，数据字典如图所示（已经经过了按照字母排序处理）：在每个词的前面是数据字典中，每个词对应的id。
最终的特征向量表达方法为：
class_id word_id:tf-idf ……
第一列class_id为此文本所属的新闻类别，word_id为数据字典中每个词对应的word_id，tf-idf为每篇文档中，对应的tf-idf值。
lda特征提取：
lda是主题模型的一种。假设一篇文章可以由不同的主题组成，把每篇文章中的主题分布概率来当作这篇文章的特征，从而形成了特征向量。主题的数量可以由人工根据情况指定或者通过其他方法科学的得到合理也就是概率最大的主题数量，再对其进行人工指定。
经过lda主题模型分析之后，在通过简单的处理，变换成svm可以接受的输入格式，会得到如下的特征向量：
图中的第一列为文本的所属类别。后面的为topic_id:probability。topic_id为相应的主题id，probability为这篇文档此主题的分布情况。
两种特征提取的方法，都将会在5.3中进行详细描述。
4.3 分类算法的选择
我(转载于:svm算法实验实验报告)们使用的svm（support vector machine）分类算法，是最大margin分类算法中的一种。svm是一种可训练的机器学习方法，在小样本中可以得到优秀的训练模型。
图1
如图中所示，svm分类算法可以根据最边界的样本点，也就是支持向
量，达到二分类的目的。
北京科技大学计算机与通信工程学院 模式分类第二次上机实验报告 姓名：XXXXXX 学号：00000000 班级：电信11 时间：2014-04-16
一、实验目的 1．掌握支持向量机（SVM）的原理、核函数类型选择以及核参数选择原则等； 二、实验内容 2.准备好数据，首先要把数据转换成Libsvm软件包要求的数据格式为： label index1:value1 index2:value2 ... 其中对于分类来说label为类标识，指定数据的种类；对于回归来说label为目标值。（我主要要用到回归） Index是从1开始的自然数，value是每一维的特征值。 该过程可以自己使用excel或者编写程序来完成，也可以使用网络上的FormatDataLibsvm.xls来完成。FormatDataLibsvm.xls使用说明： 先将数据按照下列格式存放（注意label放最后面）： value1 value2 label value1 value2 label 然后将以上数据粘贴到FormatDataLibsvm.xls中的最左上角单元格，接着工具->宏执行行FormatDataToLibsvm宏。就可以得到libsvm要求的数据格式。将该数据存放到文本文件中进行下一步的处理。 3.对数据进行归一化。 该过程要用到libsvm软件包中的svm-scale.exe Svm-scale用法： 用法：svmscale [-l lower] [-u upper] [-y y_lower y_upper] [-s save_filename] [-r restore_filename] filename （缺省值：lower = -1，upper = 1，没有对y进行缩放）其中，-l：数据下限标记；lower：缩放后数据下限；-u：数据上限标记；upper：缩放后数据上限；-y：是否对目标值同时进行缩放；y_lower为下限值，y_upper为上限值；（回归需要对目标进行缩放，因此该参数可以设定为–y -1 1 ）-s save_filename：表示将缩放的规则保存为文件save_filename；-r restore_filename：表示将缩放规则文件restore_filename载入后按此缩放；filename：待缩放的数据文件（要求满足前面所述的格式）。缩放规则文件可以用文本浏览器打开，看到其格式为： y lower upper min max x lower upper index1 min1 max1 index2 min2 max2 其中的lower 与upper 与使用时所设置的lower 与upper 含义相同；index 表示特征序号；min 转换前该特征的最小值；max 转换前该特征的最大值。数据集的缩放结果在此情况下通过DOS窗口输出，当然也可以通过DOS的文件重定向符号“>”将结果另存为指定的文件。该文件中的参数可用于最后面对目标值的反归一化。反归一化的公式为： （Value-lower）*（max-min）/(upper - lower)+lower 其中value为归一化后的值，其他参数与前面介绍的相同。 建议将训练数据集与测试数据集放在同一个文本文件中一起归一化，然后再将归一化结果分成训练集和测试集。 4.训练数据，生成模型。 用法：svmtrain [options] training_set_file [model_file] 其中，options（操作参数）：可用的选项即表示的涵义如下所示-s svm类型：设置SVM 类型，默
实验名 称 作业调度 实验内容1、设计可用于该实验的作业控制块； 2、动态或静态创建多个作业； 3、模拟先来先服务调度算法和短作业优先调度算法。 3、调度所创建的作业并显示调度结果（要求至少显示出各作业的到达时间，服务时间，开始时间，完成时间，周转时间和带权周转时间）； 3、比较两种调度算法的优劣。 实验原理一、作业 作业(Job)是系统为完成一个用户的计算任务（或一次事物处理）所做的工作总和，它由程序、数据和作业说明书三部分组成，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。 二、作业控制块J C B(J o b C o nt r o l Bl o ck) 作业控制块ＪＣＢ是记录与该作业有关的各种信息的登记表。为了管理和调度作业，在多道批处理系统中为每个作业设置了一个作业控制块，如同进程控制块是进程在系统中存在的标志一样，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。在JCB中所包含的内容因系统而异，通常应包含的内容有：作业标识、用户名称、用户帐户、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终端型)、作业状态、调度信息(优先级、作业已运行时间)、资源需求(预计运行时间、要求内存大小、要求I/O设备的类型和数量等)、进入系统时间、开始处理时间、作业完成时间、作业退出时间、资源使用情况等。 三、作业调度 作业调度的主要功能是根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。 四、选择调度算法的准则 1）．面向用户的准则 (1) 周转时间短。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称
华北电力大学 实验报告| | 实验名称算法设计与分析综合实验 课程名称算法设计与分析 | | 专业班级软件12 学生姓名： 学号：成绩： 指导教师：胡朝举实验日期：
实验一分治策略—归并排序 一、实验要求 （1）编写一个模板函数：template
操作系统实验报告（二） 实验题目：进程调度算法 实验环境：C++ 实验目的：编程模拟实现几种常见的进程调度算法，通过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较 各种算法的性能优劣。 实验内容：编程实现如下算法： 1.先来先服务算法； 2.短进程优先算法； 3.时间片轮转调度算法。 设计分析： 程序流程图： 1.先来先服务算法 开始 初始化PCB，输入进程信息 各进程按先来先到的顺序进入就绪队列 结束 就绪队列？ 运行 运行进程所需CPU时间 取消该进程 2.短进程优先算法
3.时间片轮转调度算法 实验代码： 1.先来先服务算法 #include
int atime; //进程到达时间 int runtime; //进程运行时间 }fcs; void main() { int amount,i,j,diao,huan; fcs f[n]; cout<<"请输入进程个数:"<
实验报告 实验名称：机器学习：线性支持向量机算法实现 学员：张麻子学号： *********** 培养类型：硕士年级： 专业：所属学院：计算机学院 指导教员： ****** 职称：副教授 实验室：实验日期：
一、实验目的和要求 实验目的：验证SVM（支持向量机）机器学习算法学习情况 要求：自主完成。 二、实验内容和原理 支持向量机（Support V ector Machine, SVM）的基本模型是在特征空间上找到最佳的分离超平面使得训练集上正负样本间隔最大。SVM是用来解决二分类问题的有监督学习算法。通过引入了核方法之后SVM也可以用来解决非线性问题。 但本次实验只针对线性二分类问题。 SVM算法分割原则：最小间距最大化，即找距离分割超平面最近的有效点距离超平面距离和最大。 对于线性问题： 假设存在超平面可最优分割样本集为两类，则样本集到超平面距离为： 需压求取： 由于该问题为对偶问题，可变换为： 可用拉格朗日乘数法求解。 但由于本实验中的数据集不可以完美的分为两类，即存在躁点。可引入正则化参数Ｃ，用来调节模型的复杂度和训练误差。
作出对应的拉格朗日乘式： 对应的ＫＫＴ条件为： 故得出需求解的对偶问题： 本次实验使用python 编译器，编写程序，数据集共有２７０个案例，挑选其中70%作为训练数据，剩下30%作为测试数据。进行了两个实验，一个是取Ｃ值为１，直接进行ＳＶＭ训练；另外一个是利用交叉验证方法，求取在前面情况下的最优Ｃ值。 三、实验器材 实验环境：windows7操作系统+python 编译器。 四、实验数据（关键源码附后） 实验数据：来自UCI 机器学习数据库，以Heart Disease 数据集为例。 五、操作方法与实验步骤 １、选取Ｃ＝１，训练比例７：３，利用python 库sklearn 下的SVM() 函数进
贵州大学计算机科学与技术学院 计算机科学与技术系上机实验报告 课程名称：算法设计与分析班级：软件101 实验日期：2012-10-23 姓名：学号：指导教师： 实验序号：一实验成绩： 一、实验名称 分治算法实验- 棋盘覆盖问题 二、实验目的及要求 1、熟悉递归算法编写； 2、理解分治算法的特点； 3、掌握分治算法的基本结构。 三、实验环境 Visual C++ 四、实验内容 根据教材上分析的棋盘覆盖问题的求解思路，进行验证性实验； 要求完成棋盘覆盖问题的输入、分治求解、输出。有余力的同学尝试消去递归求解。 五、算法描述及实验步骤 分治算法原理： 分治算法将大的分解成形状结构相同的子问题，并且不断递归地分解，直到子问题规模小到可以直接求解。 棋盘覆盖问题描述： 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其他的不同称为特殊方格，想要求利用四种L型骨牌（每个骨牌可覆盖三个方格）不相互重叠覆盖的将除了特殊方格外的其他方格覆盖。
实验步骤： 1、定义用于输入和输出的数据结构； 2、完成分治算法的编写； 3、测试记录结构； 4、有余力的同学尝试不改变输入输出结构，将递归消除，并说明能否不用栈，直接消除递归，为什么？ 六、调试过程及实验结果 详细记录程序在调试过程中出现的问题及解决方法。 记录程序执行的结果。
七、总结 对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。 通过对本实验的学习，对分治算法有了进一步的认识，对棋盘覆盖问题和其他分治问题进行了对比。 八、附录 源程序（核心代码）清单或使用说明书，可另附纸 ① #include 先来先服务FCFS和短作业优先SJF进程调度算法 1、实验目的 通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 2、需求分析 (1) 输入的形式和输入值的范围 输入值：进程个数Num 范围：0 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 4、详细设计 5、调试分析 (1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析 ○1开始的时候没有判断进程是否到达，导致短进程优先算法运行结果错误，后来加上了判断语句后就解决了改问题。 ○2 基本完成的设计所要实现的功能，总的来说，FCFS编写容易，SJF 需要先找到已经到达的进程，再从已经到达的进程里找到进程服务时间最短的进程，再进行计算。 (2)算法的改进设想 改进：即使用户输入的进程到达时间没有先后顺序也能准确的计算出结果。（就是再加个循环，判断各个进程的到达时间先后，组成一个有序的序列） (3)经验和体会 通过本次实验，深入理解了先来先服务和短进程优先进程调度算法的思想，培养了自己的动手能力，通过实践加深了记忆。 6、用户使用说明 （1）输入进程个数Num SVM分类算法 一、数据源说明 1、数据源说远和理解： 采用的实验数据源为第6组：The Insurance Company Benchmark (COIL 2000) TICDATA2000.txt: 这个数据集用来训练和检验预测模型，并且建立了一个5822个客户的记录的描述。每个记录由86个属性组成，包含社会人口数据（属性1-43）和产品的所有关系（属性44-86 ）。社会人口数据是由派生邮政编码派生而来的，生活在具有相同邮政编码地区的所有客户都具有相同的社会人口属性。第86个属性：“大篷车：家庭移动政策” ，是我们的目标变量。共有5822条记录，根据要求，全部用来训练。 TICEVAL2000.txt: 这个数据集是需要预测（ 4000个客户记录）的数据集。它和TICDATA2000.txt它具有相同的格式，只是没有最后一列的目标记录。我们只希望返回预测目标的列表集，所有数据集都用制表符进行分隔。共有4003（自己加了三条数据），根据要求，用来做预测。 TICTGTS2000.txt：最终的目标评估数据。这是一个实际情况下的目标数据，将与我们预测的结果进行校验。我们的预测结果将放在result.txt文件中。 数据集理解：本实验任务可以理解为分类问题，即分为2类，也就是数据源的第86列，可以分为0、1两类。我们首先需要对TICDATA2000.txt进行训练，生成model，再根据model进行预测。 2、数据清理 代码中需要对数据集进行缩放的目的在于： A、避免一些特征值范围过大而另一些特征值范围过小； B、避免在训练时为了计算核函数而计算内积的时候引起数值计算的困难。因此， 通常将数据缩放到[ -1,1] 或者是[0,1] 之间。 二、数据挖掘的算法说明 1、s vm算法说明 LIBSVM软件包是台湾大学林智仁(Chih-Jen Lin)博士等用C++实现的 SVM库，并且拥有matlab,perl等工具箱或者代码,移植和使用都比较方 便.它可以解决分类问题(包括C-SVC、n-SVC)、回归问题(包括e-SVR、 n-SVR)以及分布估计(one-class-SVM )等问题，提供了线性、多项式、 径向基和S形函数四种常用的核函数供选择，可以有效地解决多类问题、 交叉验证选择参数、对不平衡样本加权、多类问题的概率估计等。 2、实现过程 程序设计》课程设计 姓名：王 学号：20100034 班级：软件工程00 班 指导教师：王会青 成绩： 2010年 6 月 实验一.构造可以使n 个城市连接的最小生成树 专业：__软件工程___ 班级：__软件姓名：_王___ 学号：_20100034 完成日期：_2010/6/26 ________ 一、【问题描述】给定一个地区的n 个城市间的距离网，用Prim 算法或Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。 1 城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道 路，则将相应边的权值设为自己定义的无穷大值。 2 显示出城市间道路网的邻接矩阵。 3 最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。 4 输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal 算法→执行Prim 算法→输出最小生成树 二、【问题分析】 1. 抽象数据类型结构体数组的定义： #ifnd ef ADJACENCYMATRIXED// 防止该头文件被重复引用 #define ADJACENCYMATRIXED // 而引起的数据重复定义 #define INFINITY 32767 // 最大值∞ #define MAX_VERTEX_NUM 20 // 最大顶点个数 typedef int VRType; // 权值，即边的值 typedef char InfoType; // 附加信息的类型，后面使用时会定义成一个指针 typedef char VertexType[MAX_VERTEX_NUM]; // 顶点类型 typedef enum {DG=1, DN, UDG, UDN} GraphKind; //{ 有向图，有向网，无向图，无向网} typedef struct ArcCell { VRType adj; //VRType 是顶点关系类型。对无权图，用1 或0 表示相邻否；对带权图，则为权值类型。 InfoType*info; // 该弧关系信息的指针 作业调度实验报告 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 实验二作业调度 一.实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。 （2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。 （3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 二.实验目的： 本实验要求用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解三 .实验过程 <一>单道处理系统作业调度 1)单道处理程序作业调度实验的源程序: 执行程序: 2)实验分析： 1、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU 时限等因素。 2、每个作业由一个作业控制块JCB 表示，JCB 可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W 。 3、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。 3)流程图: 二.最短作业优先算法 三.高响应比算法 图一.先来先服务流程图 4)源程序: #include <> #include <> #include <> #define getpch(type) (type*)malloc(sizeof(type)) #define NULL 0 int n; float T1=0,T2=0; int times=0; struct jcb .\n",p->name); free(p); .wait...",time); if(times>1000) 代替 代替 一、实验目的 使用数据挖掘中的分类算法，对数据集进行分类训练并测试。应用不同的分类算法，比较他们之间的不同。与此同时了解Weka平台的基本功能与使用方法。 二、实验环境 实验采用Weka 平台，数据使用Weka安装目录下data文件夹下的默认数据集iris.arff。 Weka是怀卡托智能分析系统的缩写，该系统由新西兰怀卡托大学开发。Weka使用Java 写成的，并且限制在GNU通用公共证书的条件下发布。它可以运行于几乎所有操作平台，是一款免费的，非商业化的机器学习以及数据挖掘软件。Weka提供了一个统一界面，可结合预处理以及后处理方法，将许多不同的学习算法应用于任何所给的数据集，并评估由不同的学习方案所得出的结果。 三、数据预处理 Weka平台支持ARFF格式和CSV格式的数据。由于本次使用平台自带的ARFF格式数据，所以不存在格式转换的过程。实验所用的ARFF格式数据集如图1所示 图1 ARFF格式数据集(iris.arff) 对于iris数据集，它包含了150个实例（每个分类包含50个实例），共有sepal length、sepal width、petal length、petal width和class五种属性。期中前四种属性为数值类型，class属性为分类属性，表示实例所对应的的类别。该数据集中的全部实例共可分为三类：Iris Setosa、Iris Versicolour和Iris Virginica。 实验数据集中所有的数据都是实验所需的，因此不存在属性筛选的问题。若所采用的数据集中存在大量的与实验无关的属性，则需要使用weka平台的Filter(过滤器)实现属性的筛选。 实验所需的训练集和测试集均为iris.arff。 四、实验过程及结果 应用iris数据集，分别采用LibSVM、C4.5决策树分类器和朴素贝叶斯分类器进行测试和评价，分别在训练数据上训练出分类模型，找出各个模型最优的参数值，并对三个模型进行全面评价比较，得到一个最好的分类模型以及该模型所有设置的最优参数。最后使用这些参数以及训练集和校验集数据一起构造出一个最优分类器，并利用该分类器对测试数据进行预测。 1、LibSVM分类 Weka 平台内部没有集成libSVM分类器，要使用该分类器，需要下载libsvm.jar并导入到Weka中。 用“Explorer”打开数据集“iris.arff”，并在Explorer中将功能面板切换到“Classify”。点“Choose”按钮选择“functions(weka.classifiers.functions.LibSVM)”，选择LibSVM分类算法。 在Test Options 面板中选择Cross-Validatioin folds=10，即十折交叉验证。然后点击“start”按钮： 实验二作业调度 一. 实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法：分别采用先来先服务（FCFS,最短作业优先（SJF）、响应 比高者优先（HRN的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业, 先提交的先被挑选。 （2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准, 总是优先选取执行时间最短的作业。 （3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比,然后选择响应比最高的作业执行。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进 行设计。 对于多道程序系统,要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 二. 实验目的： 本实验要求用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序,了解作业调度在操作系统中的作用,以加深对作业调度算法的理解 三. 实验过程 < 一>单道处理系统作业调度 1）单道处理程序作业调度实验的源程序: zuoye.c 执行程序: zuoye.exe 2）实验分析： 1、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资 源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到 满足，它所占用的CPU时限等因素。 2、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、 提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业 的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一 每个作业的最初状态总是等待W 3、对每种调度算法都要求打印每个作业幵始运行时刻、完成时刻、周转时 间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间 3) 流程图: .最短作业优先算法 三.高响应比算法 图一.先来先服务流程图 4) 源程序： #in elude Romberg龙贝格算法实验报告 2017-08-09 课程实验报告 课程名称： 专业班级： CS1306班学号： U201314967 姓名：段沛云指导教师：报 告日期： 计算机科学与技术学院 目录 1 实验目的 (1) 2 实验原理 (1) 3 算法设计与流程框图 (2) 4 源程序 (4) 5 程序运行 (7) 6 结果分析 (7) 7 实验体会 (7) 1 实验目的 掌握Romberg公式的用法，适用范围及精度，熟悉Romberg算法的流程，并能够设计算法计算积分 31 得到结果并输出。 1x 2 实验原理 2.1 取k=0,h=b-a,求T0= 数)。 2.2 求梯形值T0( b-a ),即按递推公式（4.1）计算T0。 k 2 h [f(a)+f(b)]，令1→k,(k记区间[a，b]的二分次2 2.3 求加速值，按公式(4.12)逐个求出T表的第k行其余各元素Tj(k-j) (j=1,2,….k)。 2.4 若|Tk+1-Tk| n-1 11T2n=[Tn+hn∑f(xi+)] 22i=0 1 Sn=T2n+(T2n-Tn) 31 Cn=S2n+(S2n-Sn) 151 Rn=C2n+(C2n-Cn) 63 3 算法设计与流程框图 算法设计：(先假定所求积分二分最大次数次数为20) 3.1 先求T[k][0] 3.2 再由公式T (k)m 4m(k+1)1)=mTm-1-mTm(k-1(k=1,2,) 求T[i][j] 4-14-1 3.3 在求出的同时比较T[k][k]与T[k-1][k-1]的大小，如果二者之差的绝对 值小于1e-5，就停止求T[k][k]；此时的k就是所求的二分次数，而此时的T[k][k]就是最终的结果 3.4 打印出所有的T[i][j]；程序流程图 作业调度 一、实验目的 1、对作业调度的相关内容作进一步的理解。 2、明白作业调度的主要任务。 3、通过编程掌握作业调度的主要算法。 二、实验内容及要求 1、对于给定的一组作业, 给出其到达时间和运行时间，例如下表所示： 2、分别用先来先服务算法、短作业优先和响应比高者优先三种算法给出作业的调度顺序。 3、计算每一种算法的平均周转时间及平均带权周转时间并比较不同算法的优劣。 测试数据 workA={'作业名':'A','到达时间':0,'服务时间':6} workB={'作业名':'B','到达时间':2,'服务时间':50} workC={'作业名':'C','到达时间':5,'服务时间':20} workD={'作业名':'D','到达时间':5,'服务时间':10} workE={'作业名':'E','到达时间':12,'服务时间':40} workF={'作业名':'F','到达时间':15,'服务时间':8} 运行结果 先来先服务算法 调度顺序:['A', 'B', 'C', 'D', 'E', 'F'] 周转时间: 带权周转时间: 短作业优先算法 调度顺序:['A', 'D', 'F', 'C', 'E', 'B'] 周转时间: 带权周转时间:1. 响应比高者优先算法 调度顺序:['A', 'D', 'F', 'E', 'C', 'B'] 周转时间: 带权周转时间: 五、代码 #encoding=gbk workA={'作业名':'A','到达时间':0,'服务时间':6,'结束时间':0,'周转时间':0,'带权周转时间':0} workB={'作业名':'B','到达时间':2,'服务时间':50} workC={'作业名':'C','到达时间':5,'服务时间':20} workD={'作业名':'D','到达时间':5,'服务时间':10} workE={'作业名':'E','到达时间':12,'服务时间':40} workF={'作业名':'F','到达时间':15,'服务时间':8} list1=[workB,workA,workC,workD,workE,workF] list2=[workB,workA,workC,workD,workE,workF] list3=[workB,workA,workC,workD,workE,workF] #先来先服务算法 def fcfs(list): resultlist = sorted(list, key=lambda s: s['到达时间']) return resultlist #短作业优先算法 def sjf(list): time=0 resultlist=[] for work1 in list: time+=work1['服务时间'] listdd=[] ctime=0 for i in range(time): for work2 in list: if work2['到达时间']<=ctime: (work2) if len(listdd)!=0: li = sorted(listdd, key=lambda s: s['服务时间']) (li[0]) (li[0]) ctime+=li[0]['服务时间'] listdd=[] 《操作系统》实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037 一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include 课程设计报告课程设计名称共享资源分配与银行家算法 系（部） 专业班级 姓名 学号 指导教师 年月日 目录 一、课程设计目的和意义 (3) 二、方案设计及开发过程 (3) 1.课题设计背景 (3) 2.算法描述 (3) 3.数据结构 (4) 4.主要函数说明 (4) 5.算法流程图 (5) 三、调试记录与分析 四、运行结果及说明 (6) 1．执行结果 (6) 2．结果分析 (7) 五、课程设计总结 (8) 一、程设计目的和意义 计算机科学与技术专业学生学习完《计算机操作系统》课程后，进行的一次全面的综合训练，其目的在于加深催操作系统基础理论和基本知识的理解，加强学生的动手能力.银行家算法是避免死锁的一种重要方法。通过编写一个模拟动态资源分配的银行家算法程序，进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法 二、方案设计及开发过程 1.课题设计背景 银行家算法又称“资源分配拒绝”法，其基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源数做比较，找出剩余资源能满足最大需求量的进程，从而保证进程运行完成后还回全部资源。这时系统将该进程从进程集合中将其清除。此时系统中的资源就更多了。反复执行上面的步骤，最后检查进程的集合为空时就表明本次申请可行，系统处于安全状态，可以实施本次分配，否则，只要进程集合非空，系统便处于不安全状态，本次不能分配给他。请进程等待 2.算法描述 1）如果Request[i] 是进程Pi的请求向量，如果Request[i，j]=K,表示进程Pi 需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 如果Requesti[j]<= Need[i,j]，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 2）如果Requesti[j]<=Available[j],便转向步骤3，否则，表示尚无足够资源，进程Pi须等待。 3）系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Available[j]:=Available[j]-Requesti[j]; Allocation[i,j]:=Allocation[i,j]+Requesti[j]; Need[i,j]:=Need[i,j]-Requesti[j]; FCFS和SJF进程调度算法实验报告 【实验题目】：编写程序，实现FCFS和SJF算法，模拟作 业调度过程，加深对作业调度的理解。 【实验内容】 实现FCFS和SJF调度算法。 –数据结构设计（JCB，后备作业队列） –算法实现与模拟（排序、调度） –输出调度结果，展示调度过程并解释 【实验要求】 1. 设计作业控制块(JCB)的数据结构 –应包含实验必须的数据项，如作业ID、需要的服务时间、进入系 统时间、完成时间，以及实验者认为有必要的其他数据项。 2. 实现排序算法（将作业排队） –策略1：按“进入系统时间”对作业队列排序(FCFS) –策略2：按“需要的服务时间”对作业队列排序（SJF） 3. 实现调度过程模拟 （1）每个作业用一个JCB表示，如果模拟FCFS，按策略1将作业排队，如果模拟SJF，按策略2将作业排队（2）选择队首的作业，将其从后备队列移出 （3）（作业运行过程，在本实验中，无需实现，可认为后备队列的 作业一但被调度程序选出，就顺利运行完毕，可以进入第4步） （4）计算选中作业的周转时间 （5）进行下一次调度（去往第2步） 4.实现结果输出 –输出作业状态表，展示调度过程 ?初始作业状态（未调度时） ?每次调度后的作业状态 设计作业控制块(JCB)的数据结构 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下：typedef struct jcb{ char name[10]; /* 作业名*/ char state; /* 作业状态*/ int ts; /* 提交时间*/ float super; /* 优先权*/ int tb; /* 开始运行时间*/ int tc; /* 完成时间*/ float ti; /* 周转时间*/ float wi; /* 带权周转时间*/ int ntime; /* 作业所需运行时间*/ char resource[10]; /* 所需资源*/ struct jcb *next; /* 结构体指针*/ } JCB; JCB *p,*tail=NULL,*head=NULL; 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。，组成一个后备队列等待，总是首先调度等待队列中队首的作业。先来先服务FCFS和短作业优先SJF进程调度算法_实验报告材料
SVM实验报告
算法程序设计实验报告
作业调度实验报告
大数据挖掘weka大数据分类实验报告材料
作业调度实验报告
Romberg龙贝格算法实验报告.
操作系统实验报告-作业调度
作业调度算法(先来先服务算法,短作业算法)
银行家算法_实验报告
FCFS和SJF进程调度算法实验报告
相关主题
文本预览