当前位置:   article > 正文

机器学习-支持向量机-解决兵王问题(附matlab程序)_king-rook vs king机器学习

king-rook vs king机器学习

一、前提

本文内容是在学习浙江大学胡浩基“机器学习-支持向量机”视频过程中整理出来的,具体可以观看B站视频
最终使用matlab程序解决了兵王问题。

二、兵王问题

国际象棋的兵王问题:棋盘上黑方只剩一个王,白方剩一个王 一个兵,棋局只有两个结果:“白方将死黑方获胜”或者“和棋”,这个问题属于二分类的问题。这里要利用支持向量机解决这个问题,实现在不告诉计算机国际象棋规则的前提下,让计算机可以根据棋子位置判断棋局的结果。

三、数据集

用到的数据集为UCI Machine Learning Repository,检索关键词为Chess (King-Rook vs. King),链接直达,点进去之后可看到krkopt.data。
UCI Machine Learning Repository,兵王数据集
数据集一共包含28056个数据,具体内容解释如下图所示,数据集中一共有2796个“和棋”样本(正样本),25260个“白方胜”样本(负样本)。

四、LIBSVM工具包

LibSVM是支持向量机的工具包,当前版本3.25,官网链接直达
matlab安装LibSVM,网上有很多教程,可以参考链接

五、程序设计

  1. 随机取5000个样本进行训练,其余的样本进行测试;
  2. 对所有样本进行归一化操作;
  1. 设置支持向量机的各种参数,;
    (1)“-s”参数:表示SVM的不同形式,根据目标函数进行选择,这里选择0;
    (2)“-t”参数:表示支持向量机的核函数K(X1,X2),
       0:表示线性内核(linear),该内核的计算结果 与 不使用核函数结果一致,
       1:表示多项式内核(ploy),复杂度可以调节,指数d越大,映射维度也越高,
       2:表示高斯径向积内核(rbf核),σ是人为设置的超参数,映射函数的维度是无限的,实际中最常用
       3:表示sigmoid内核(tanh),β和B是人为设置的超参数,映射函数的维度也是无限的,
       4:表示自定义内核,需要知道矩阵K;
    (3)“-c”参数cValue:原问题中的C或对偶问题限制条件中的C;
    (4)“-g”参数gammaValue:与核函数相对应,不同的核函数g的设定都不一样。

六、Matlab程序

经测试,视频中的程序不能正确运行,研究代码后发现,问题主要出现在数据读取和预处理过程中,我在源程序的基础上进行了修改,并加上了一些备注。修改后程序顺利运行,共用时295秒。需要的大家可以测试一下,有问题评论交流。

备注:我使用的是matlab 2016a;测试集来自UCI Machine Learning Repository;LibSVM工具箱为3.24版本。

具体代码如下:

clear all;
% Read the data.
fid  =  fopen('krkopt.DATA');
%c = fread(fid, 3);              %这行注释掉
vec = zeros(6,1);
xapp = [];                       %用来存放棋子的位置
yapp = [];                       %用来存放棋局结果
while ~feof(fid)                 %检测流上的文件结束符,如果文件结束,则返回非0值,否则返回0
    string = [];                 %用来存放每次读取的一行六个数据
    c = fread(fid,1);            %每次读取一个字节的数据
    %flag = flag+1;              %可以注释掉,没发挥作用
    while c~=10                  %每行读取结束后,最后一个字节数据为10
        string = [string, c];    %将读取到的数据保存到string[]中
        c=fread(fid,1);          %继续读取下一个字节的数据
    end;
    %fread(fid,1);               %这行注释掉
    if length(string)>10
        vec(1) = string(1) - 96; %以下六行是棋子坐标数据的转换,具体可以看ascii码对照表,
        vec(2) = string(3) - 48; 
        vec(3) = string(5) - 96;
        vec(4) = string(7) - 48;
        vec(5) = string(9) - 96;
        vec(6) = string(11) - 48;
        xapp = [xapp,vec];       %将转换后的数据存入xapp[]
        if string(13) == 100     %判断每行最后一个单词首字母是否为小写的d,是则标记为1,否则标记为-1
            yapp = [yapp,1];
        else
            yapp = [yapp,-1];
        end;
    end;
end;
fclose(fid);

[N,M] = size(xapp);
p = randperm(M);                            %打乱训练样本
numberOfSamplesForTraining = 5000;
xTraining = [];
yTraining = [];
for i=1:numberOfSamplesForTraining          %获得训练集
    xTraining  = [xTraining,xapp(:,p(i))];
    yTraining = [yTraining,yapp(p(i))];
end;
xTraining = xTraining';
yTraining = yTraining';

xTesting = [];
yTesting = [];
for i=numberOfSamplesForTraining+1:M        %获得测试集
    xTesting  = [xTesting,xapp(:,p(i))];
    yTesting = [yTesting,yapp(p(i))];
end;
xTesting = xTesting';
yTesting = yTesting';

%%%%%%%%%%%%%%%%%%%%%%%%
%Normalization归一化
[numVec,numDim] = size(xTraining);
avgX = mean(xTraining);                     %求均值
stdX = std(xTraining);                      %QQ方差
for i = 1:numVec                            %训练集归一化:每个样本都减掉均值再除以方差
    xTraining(i,:) = (xTraining(i,:)-avgX)./stdX;
end;
[numVec,numDim] = size(xTesting);

for i = 1:numVec                            %测试集归一化
    xTesting(i,:) = (xTesting(i,:)-avgX)./stdX;
end;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%SVM Gaussian kernel 高斯径向积内核
%Search for the optimal C and gamma, K(x1,x2) = exp{-||x1-x2||^2/gamma} to
%make the recognition rate maximum. 

%首先需要对C和Gamma两个参数的取值进行初步搜索,c的取值范围是:2^-5--2^15,gamma的取值范围:2^-15--2^3,该范围是基于人工的经验;
%对数据进行交叉验证,初步找出识别率最高的c与gamma的组合
CScale = [-5, -3, -1, 1, 3, 5,7,9,11,13,15];
gammaScale = [-15,-13,-11,-9,-7,-5,-3,-1,1,3];
C = 2.^CScale;
gamma = 2.^gammaScale;
maxRecognitionRate = 0;
for i = 1:length(C)
    for j = 1:length(gamma)
        cmd=['-t 2 -c ',num2str(C(i)),' -g ',num2str(gamma(j)),' -v 5'];    %设置支持向量机的参数
        recognitionRate = svmtrain(yTraining,xTraining,cmd);
        if recognitionRate>maxRecognitionRate
            maxRecognitionRate = recognitionRate
            maxCIndex = i;
            maxGammaIndex = j;
        end;
    end;
end;
%进一步缩小搜索范围,再次进行交叉验证,找出识别率最高的更精确的c与gamma的组合
n = 10;
minCScale = 0.5*(CScale(max(1,maxCIndex-1))+CScale(maxCIndex));
maxCScale = 0.5*(CScale(min(length(CScale),maxCIndex+1))+CScale(maxCIndex));
newCScale = [minCScale:(maxCScale-minCScale)/n:maxCScale];

minGammaScale = 0.5*(gammaScale(max(1,maxGammaIndex-1))+gammaScale(maxGammaIndex));
maxGammaScale = 0.5*(gammaScale(min(length(gammaScale),maxGammaIndex+1))+gammaScale(maxGammaIndex));
newGammaScale = [minGammaScale:(maxGammaScale-minGammaScale)/n:maxGammaScale];
newC = 2.^newCScale;
newGamma = 2.^newGammaScale;
maxRecognitionRate = 0;
for i = 1:length(newC)
    for j = 1:length(newGamma)
        cmd=['-t 2 -c ',num2str(newC(i)),' -g ',num2str(newGamma(j)),' -v 5'];    %设置支持向量机的参数
        recognitionRate = svmtrain(yTraining,xTraining,cmd);
        if recognitionRate>maxRecognitionRate
            maxRecognitionRate = recognitionRate
            maxC = newC(i);
            maxGamma = newGamma(j);
        end;
    end;
end;

%Train the SVM model by the optimal C and gamma.
%使用最优的c与gamma的组合训练数据,保存结果
cmd=['-t 2 -c ',num2str(maxC),' -g ',num2str(maxGamma)];
model = svmtrain(yTraining,xTraining,cmd);
save model.mat model;%存储最终训练好的模型
save xTesting.mat xTesting;
save yTesting.mat yTesting;

% test the model on the remaining testing data and obtain the recognition rate.
% 加载训练结果并进行测试,保存结果
load model.mat;
[yPred,accuracy,decisionValues] = svmpredict(yTesting,xTesting,model);
save yPred.mat yPred;
save decisionValues.mat decisionValues;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:【wpsshop博客】
推荐阅读
相关标签
  

闽ICP备14008679号