放牧代码和思想
专注自然语言处理、机器学习算法

CS229编程6:支持向量机

目录

visual.png斯坦福ML(Matlab)公开课,本次练习试验支持向量机,并应用于垃圾邮件分类。代码本身非常简单,理论知识参考《统计学习方法》或公开课视频。

支持向量机

这部分先在多个2D数据集上熟悉熟悉SVM和惩罚参数。

线性可分数据

简单的线性可分数据集:

data1.png

不要求实现SVM训练(实现可参考http://www.hankcs.com/ml/support-vector-machine.html),只要求使用不同的惩罚因子C(类似于正则化的hankcs.com 2016-11-09 上午10.44.55.png)调用写好的训练代码即可。C控制着对误分类的惩罚力度,C越大,SVM越努力地试图将训练样本全分对。

当C=1时,

c1.png

几何间隔很大,模型泛化能力应该不错。

当C=100时,

100.png

几何间隔很小,过拟合了。

SVM和高斯核

对于非线性可分数据,就必须上核函数了。比如这个数据集:

不可分.png

高斯核

高斯核函数定义为:

hankcs.com 2016-11-09 上午10.56.51.png

实现如下:

function sim = gaussianKernel(x1, x2, sigma)
%RBFKERNEL returns a radial basis function kernel between x1 and x2
%   sim = gaussianKernel(x1, x2) returns a gaussian kernel between x1 and x2
%   and returns the value in sim
 
% Ensure that x1 and x2 are column vectors
x1 = x1(:); x2 = x2(:);
 
% You need to return the following variables correctly.
sim = 0;
 
% ====================== YOUR CODE HERE ======================
% Instructions: Fill in this function to return the similarity between x1
%               and x2 computed using a Gaussian kernel with bandwidth
%               sigma
%
%
sim = exp(-(x1 - x2)' * (x1 - x2) / (2 * sigma ^2))
 
 
 
 
 
% =============================================================
    
end

Instruction里面说高斯核是求the similarity between x1 and x2,的确是个很深刻的解释。我以前都没注意到,高斯核里面不就是个欧氏距离公式嘛。

决策边界可视化如下:

visual.png

可视化代码也不要求实现,但斯坦福给的代码在matlab2016b上面无法绘制决策边界,我认为是浮点数精度的问题,将限制放宽松一些即可:

contour(X1, X2, vals, [0 0], 'Color', 'b');

改为:

contour(X1, X2, vals, [0 0.5], 'Color', 'b');

还可以在另外一个数据集上做做试验:

data3.png

决策边界:

data3model.png

垃圾邮件分类

其实就是文本分类的应用了。

预处理

对于这样一封邮件

> Anyone knows how much it costs to host a web portal ?
>
Well, it depends on how many visitors youre expecting. This can be
anywhere from less than 10 bucks a month to a couple of $100. You
should checkout http://www.rackspace.com/ or perhaps Amazon EC2 if
youre running something big..

						
To unsubscribe yourself from this mailing list, send an email to:
groupname-unsubscribe@egroups.com

进行如下预处理

  • 大写转小写

  • 去除HTML标签

  • URL、邮箱地址、数字、美元替换为标记符

  • 单词形态转换

  • 去掉标点符号

实现如下:

function word_indices = processEmail(email_contents)
%PROCESSEMAIL preprocesses a the body of an email and
%returns a list of word_indices 
%   word_indices = PROCESSEMAIL(email_contents) preprocesses 
%   the body of an email and returns a list of indices of the 
%   words contained in the email. 
%
 
% Load Vocabulary
vocabList = getVocabList();
 
% Init return value
word_indices = [];
 
% ========================== Preprocess Email ===========================
 
% Find the Headers ( \n\n and remove )
% Uncomment the following lines if you are working with raw emails with the
% full headers
 
% hdrstart = strfind(email_contents, ([char(10) char(10)]));
% email_contents = email_contents(hdrstart(1):end);
 
% Lower case
email_contents = lower(email_contents);
 
% Strip all HTML
% Looks for any expression that starts with < and ends with > and replace
% and does not have any < or > in the tag it with a space
email_contents = regexprep(email_contents, '<[^<>]+>', ' ');
 
% Handle Numbers
% Look for one or more characters between 0-9
email_contents = regexprep(email_contents, '[0-9]+', 'number');
 
% Handle URLS
% Look for strings starting with http:// or https://
email_contents = regexprep(email_contents, ...
                           '(http|https)://[^\s]*', 'httpaddr');
 
% Handle Email Addresses
% Look for strings with @ in the middle
email_contents = regexprep(email_contents, '[^\s]+@[^\s]+', 'emailaddr');
 
% Handle $ sign
email_contents = regexprep(email_contents, '[$]+', 'dollar');
 
 
% ========================== Tokenize Email ===========================
 
% Output the email to screen as well
fprintf('\n==== Processed Email ====\n\n');
 
% Process file
l = 0;
 
while ~isempty(email_contents)
 
    % Tokenize and also get rid of any punctuation
    [str, email_contents] = ...
       strtok(email_contents, ...
              [' @$/#.-:&*+=[]?!(){},''">_<;%' char(10) char(13)]);
   
    % Remove any non alphanumeric characters
    str = regexprep(str, '[^a-zA-Z0-9]', '');
 
    % Stem the word 
    % (the porterStemmer sometimes has issues, so we use a try catch block)
    try str = porterStemmer(strtrim(str)); 
    catch str = ''; continue;
    end;
 
    % Skip the word if it is too short
    if length(str) < 1
       continue;
    end
 
    % Look up the word in the dictionary and add to word_indices if
    % found
    % ====================== YOUR CODE HERE ======================
    % Instructions: Fill in this function to add the index of str to
    %               word_indices if it is in the vocabulary. At this point
    %               of the code, you have a stemmed word from the email in
    %               the variable str. You should look up str in the
    %               vocabulary list (vocabList). If a match exists, you
    %               should add the index of the word to the word_indices
    %               vector. Concretely, if str = 'action', then you should
    %               look up the vocabulary list to find where in vocabList
    %               'action' appears. For example, if vocabList{18} =
    %               'action', then, you should add 18 to the word_indices 
    %               vector (e.g., word_indices = [word_indices ; 18]; ).
    % 
    % Note: vocabList{idx} returns a the word with index idx in the
    %       vocabulary list.
    % 
    % Note: You can use strcmp(str1, str2) to compare two strings (str1 and
    %       str2). It will return 1 only if the two strings are equivalent.
    %
 
for idx = 1:1899
    if(strcmp(str, vocabList{idx}) == 1)
        word_indices = [word_indices ; idx];
    end
end
 
 
 
 
 
 
 
 
 
 
    % =============================================================
 
 
    % Print to screen, ensuring that the output lines are not too long
    if (l + length(str) + 1) > 78
        fprintf('\n');
        l = 0;
    end
    fprintf('%s ', str);
    l = l + length(str) + 1;
 
end
 
% Print footer
fprintf('\n\n=========================\n');
 
end

这段代码一看就很垃圾,连个Map Container都不用,非要用strcmp一个个去找。

特征提取

很低级的特征提取,特征向量每一维都是一位二进制,代表第i个词语是否出现。

hankcs.com 2016-11-09 上午11.31.37.png

function x = emailFeatures(word_indices)
%EMAILFEATURES takes in a word_indices vector and produces a feature vector
%from the word indices
%   x = EMAILFEATURES(word_indices) takes in a word_indices vector and 
%   produces a feature vector from the word indices. 
 
% Total number of words in the dictionary
n = 1899;
 
% You need to return the following variables correctly.
x = zeros(n, 1);
 
% ====================== YOUR CODE HERE ======================
% Instructions: Fill in this function to return a feature vector for the
%               given email (word_indices). To help make it easier to 
%               process the emails, we have have already pre-processed each
%               email and converted each word in the email into an index in
%               a fixed dictionary (of 1899 words). The variable
%               word_indices contains the list of indices of the words
%               which occur in one email.
% 
%               Concretely, if an email has the text:
%
%                  The quick brown fox jumped over the lazy dog.
%
%               Then, the word_indices vector for this text might look 
%               like:
%               
%                   60  100   33   44   10     53  60  58   5
%
%               where, we have mapped each word onto a number, for example:
%
%                   the   -- 60
%                   quick -- 100
%                   ...
%
%              (note: the above numbers are just an example and are not the
%               actual mappings).
%
%              Your task is take one such word_indices vector and construct
%              a binary feature vector that indicates whether a particular
%              word occurs in the email. That is, x(i) = 1 when word i
%              is present in the email. Concretely, if the word 'the' (say,
%              index 60) appears in the email, then x(60) = 1. The feature
%              vector should look like:
%
%              x = [ 0 0 0 0 1 0 0 0 ... 0 0 0 0 1 ... 0 0 0 1 0 ..];
%
%
 
for i = 1:length(word_indices)
    x(word_indices(i)) = 1;
end
 
 
 
 
 
 
% =========================================================================
    
 
end

训练分类器

特征向量有了,剩下的就跟普通的数据集一摸一样了。

%% =========== Part 3: Train Linear SVM for Spam Classification ========
%  In this section, you will train a linear classifier to determine if an
%  email is Spam or Not-Spam.
 
% Load the Spam Email dataset
% You will have X, y in your environment
load('spamTrain.mat');
 
fprintf('\nTraining Linear SVM (Spam Classification)\n')
fprintf('(this may take 1 to 2 minutes) ...\n')
 
C = 0.1;
model = svmTrain(X, y, C, @linearKernel);
 
p = svmPredict(model, X);
 
fprintf('Training Accuracy: %f\n', mean(double(p == y)) * 100);

得到:

Training Accuracy: 99.825000

Evaluating the trained Linear SVM on a test set ...
Test Accuracy: 98.500000

你看,这么弱的特征+线性核也能拿到这么高的分数,可见SVM还是很好用的。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » CS229编程6:支持向量机

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机