新手园地& & & 硬件问题Linux系统管理Linux网络问题Linux环境编程Linux桌面系统国产LinuxBSD& & & BSD文档中心AIX& & & 新手入门& & & AIX文档中心& & & 资源下载& & & Power高级应用& & & IBM存储AS400Solaris& & & Solaris文档中心HP-UX& & & HP文档中心SCO UNIX& & & SCO文档中心互操作专区IRIXTru64 UNIXMac OS X门户网站运维集群和高可用服务器应用监控和防护虚拟化技术架构设计行业应用和管理服务器及硬件技术& & & 服务器资源下载云计算& & & 云计算文档中心& & & 云计算业界& & & 云计算资源下载存储备份& & & 存储文档中心& & & 存储业界& & & 存储资源下载& & & Symantec技术交流区安全技术网络技术& & & 网络技术文档中心C/C++& & & GUI编程& & & Functional编程内核源码& & & 内核问题移动开发& & & 移动开发技术资料ShellPerlJava& & & Java文档中心PHP& & & php文档中心Python& & & Python文档中心RubyCPU与编译器嵌入式开发驱动开发Web开发VoIP开发技术MySQL& & & MySQL文档中心SybaseOraclePostgreSQLDB2Informix数据仓库与数据挖掘NoSQL技术IT业界新闻与评论IT职业生涯& & & 猎头招聘IT图书与评论& & & CU技术图书大系& & & Linux书友会二手交易下载共享Linux文档专区IT培训与认证& & & 培训交流& & & 认证培训清茶斋投资理财运动地带快乐数码摄影& & & 摄影器材& & & 摄影比赛专区IT爱车族旅游天下站务交流版主会议室博客SNS站务交流区CU活动专区& & & Power活动专区& & & 拍卖交流区频道交流区
空间积分0 信誉积分26 UID阅读权限10积分62帖子精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
白手起家, 积分 62, 距离下一级还需 138 积分
帖子主题精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
论坛徽章:0
在sed命令下 怎么实现输出倒数第二行的内容呢？？？怎么把内容插入到倒数第二行？？？
&&nbsp|&&nbsp&&nbsp|&&nbsp&&nbsp|&&nbsp&&nbsp|&&nbsp
空间积分0 信誉积分26 UID阅读权限10积分62帖子精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
白手起家, 积分 62, 距离下一级还需 138 积分
帖子主题精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
论坛徽章:0
再补充一下 输出倒数第五行的内容
空间积分0 信誉积分2324 UID阅读权限100积分3882帖子精华可用积分3882 专家积分15 在线时间3753 小时注册时间最后登录
帖子主题精华可用积分3882 专家积分15 在线时间3753 小时注册时间最后登录
论坛徽章:1
你一天不看基础,就光来问,名堂好多噢.
空间积分0 信誉积分26 UID阅读权限10积分62帖子精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
白手起家, 积分 62, 距离下一级还需 138 积分
帖子主题精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
论坛徽章:0
没看基础您都能看出来？？？？佩服佩服~~~~回复
空间积分0 信誉积分2324 UID阅读权限100积分3882帖子精华可用积分3882 专家积分15 在线时间3753 小时注册时间最后登录
帖子主题精华可用积分3882 专家积分15 在线时间3753 小时注册时间最后登录
论坛徽章:1
sophia3333
& & 每个帖子我都看过,从你问的那些问题来看,就大概知道一二.
空间积分0 信誉积分26 UID阅读权限10积分62帖子精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
白手起家, 积分 62, 距离下一级还需 138 积分
帖子主题精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
论坛徽章:0
那就请您帮我解答一下问题吧。。。您说的这些都不是我问的。。。。我会输出倒数第二行的内容了 要怎么把abc添加到倒数第二行呢？？？回复
空间积分0 信誉积分2324 UID阅读权限100积分3882帖子精华可用积分3882 专家积分15 在线时间3753 小时注册时间最后登录
帖子主题精华可用积分3882 专家积分15 在线时间3753 小时注册时间最后登录
论坛徽章:1
seq 5|sed '$i\abc'复制代码
空间积分0 信誉积分26 UID阅读权限10积分62帖子精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
白手起家, 积分 62, 距离下一级还需 138 积分
帖子主题精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
论坛徽章:0
要是不用seq呢？？？？都用sed命令。。。。回复
空间积分0 信誉积分990 UID阅读权限20积分561帖子精华可用积分561 专家积分5 在线时间885 小时注册时间最后登录
丰衣足食, 积分 561, 距离下一级还需 439 积分
帖子主题精华可用积分561 专家积分5 在线时间885 小时注册时间最后登录
论坛徽章:0
sed '$i\abc' file复制代码回复
sophia3333
& & 版主都该无语了。。。。
空间积分0 信誉积分26 UID阅读权限10积分62帖子精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
白手起家, 积分 62, 距离下一级还需 138 积分
帖子主题精华可用积分62 专家积分0 在线时间19 小时注册时间最后登录
论坛徽章:0
恩恩 我试过了。。。。。那个是没试之前发的。。。。。回复收藏，3.3k 浏览
PageRank算法
PageRank算法是谷歌曾经独步天下的“倚天剑”，该算法由Larry Page和Sergey Brin在斯坦福大学读研时发明的，。
本文首先通过一些参考文献引出问题，然后给出了PageRank的几种实现算法，最后将其推广至在MapReduce框架下如何实现PageRank算法。
PageRank的核心思想有2点：
1.如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是pagerank值会相对较高；
2.如果一个pagerank值很高的网页链接到一个其他的网页，那么被链接到的网页的pagerank值会相应地因此而提高。
下面是一张来自的图，每个球代表一个网页，球的大小反应了网页的pagerank值的大小。指向网页B和网页E的链接很多，所以B和E的pagerank值较高，另外，虽然很少有网页指向C，但是最重要的网页B指向了C，所以C的pagerank值比E还要大。
参考内容：
3. Page 161 应用实例：Google的PageRank算法
5. Page 62 PageRank和马尔可夫链
1.问题背景
来自参考内容3
2.数学建模
来自参考内容3，理解网页连接矩阵$G$，马尔科夫过程("网上冲浪")，转移矩阵$A$，概率$p$为用户点击当前网页中的某个链接地址的概率(一般都为0.85)。
最后得到一个等式$Ax=x$，这实际上就是求矩阵$A$的特征值为1的特征向量！
下面的内容使用圆盘定理解释了1是矩阵$A$的主特征值，所以我们可以使用幂法来求解。
关于幂法的详细介绍参考另一篇文章
3.求解PageRank
假设有如上图右侧所示的网页链接模型。
wiki上有一个PageRank的简便算法，它不考虑转移概率，而是采用的是迭代的方式，每次都更新所有网页的pagerank值，更新的方式就是将每个网页的pagerank值平摊分给它指向的所有网页，每个网页累计所有指向它的网页平摊给它的值作为它该回合的pagerank值，直到全部网页的pagerank值收敛了或者满足一定的阈值条件就停止。
后面的MapReduce框架下PageRank算法的实现就采用了这个思想。考虑转移概率的情况和这个算法类似，乘上一个转移概率再加上一个随机跳转的概率。
根据上面的思想，下面Matlab代码实现可以得到各个网页的PageRank值。
i=[2 3 4 4 5 6 1 6 1];
j=[1 2 2 3 3 3 4 5 6];
G=sparse(i,j,1,n,n);
% Power method
for j = 1:n
L{j} = find(G(:,j));
c(j) = length(L{j});
delta = (1-p)/n;
x = ones(n,1)/n;
z = zeros(n,1);
while max(abs(x-z)) & .0001
x = zeros(n,1);
for j = 1:n
if c(j) == 0
x = x + z(j)/n;%转移到任意一个网页
x(L{j}) = x(L{j}) + z(j)/c(j);%将上次的pagerank值平摊给所有指向的网页
cnt = cnt+1;
得到的向量$x$保存了各个网页的pagerank值，虽然链接数目一样，但是网页①比网页④和网页⑤都高，而网页②的pagerank值第二高，因为网页①链接到了它上面，相当于沾了网页①的光。
，该博主使用第三方模块，python-graph模块实现了很多图算法，，使用前需要先安装，代码如下：
easy_install python-graph-core
easy_install python-graph-dot
Python版本的算法实现：
# coding=utf-8
# python-graph /p/python-graph/
# Import graphviz
import graphviz as gv
# Import pygraph
from pygraph.classes.digraph import digraph
from pygraph.readwrite.dot import write
# Define pagerank function
def pagerank(graph, damping_factor=0.85, max_iterations=100, \
min_delta=0.00001):
Compute and return the PageRank in an directed graph.
graph: digraph
@param graph: Digraph.
damping_factor: number
@param damping_factor: PageRank dumping factor.
max_iterations: number
@param max_iterations: Maximum number of iterations.
min_delta: number
@param min_delta: Smallest variation required for a new iteration.
@return: Dict containing all the nodes PageRank.
nodes = graph.nodes()
graph_size = len(nodes)
if graph_size == 0:
# value for nodes without inbound links
min_value = (1.0-damping_factor)/graph_size
# itialize the page rank dict with 1/N for all nodes
#pagerank = dict.fromkeys(nodes, 1.0/graph_size)
pagerank = dict.fromkeys(nodes, 1.0)
for i in range(max_iterations):
diff = 0 #total difference compared to last iteraction
# computes each node PageRank based on inbound links
for node in nodes:
rank = min_value
for referring_page in graph.incidents(node):
rank += damping_factor * pagerank[referring_page] / \
len(graph.neighbors(referring_page))
diff += abs(pagerank[node] - rank)
pagerank[node] = rank
print 'This is NO.%s iteration' % (i+1)
print pagerank
#stop if PageRank has converged
if diff & min_delta:
return pagerank
# Graph creation
gr = digraph()
# Add nodes and edges
gr.add_nodes(["1","2","3","4"])
gr.add_edge(("1","2"))
gr.add_edge(("1","3"))
gr.add_edge(("1","4"))
gr.add_edge(("2","3"))
gr.add_edge(("2","4"))
gr.add_edge(("3","4"))
gr.add_edge(("4","2"))
# Draw as PNG
# dot = write(gr)
# gvv = gv.readstring(dot)
# gv.layout(gvv,'dot')
# gv.render(gvv,'png','Model.png')
pagerank(gr)
经过32次迭代之后得到的结果如下，和前面的结果一致：
This is NO.32 iteration
{'1': 0.6491, '3': 0.86046, '2': 0.0518, '5': 0.127136, '4': 0.1491, '6': 0.6352}
(2) 利用马尔可夫矩阵的特殊结构
来自参考内容4，其中$\delta=\frac{1-p}{n}$
也就是将矩阵$A$进行分解，并不需要显示求出矩阵$A$，然后便是求解一个线性方程组即可。
function x = pagerank1(G)
% PAGERANK1
Google's PageRank modified version 1 - hujiawei
%if nargin & 3, p = .85; end
% Eliminate any self-referential links
G = G - diag(diag(G));
% c = out-degree, r = in-degree
[n,n] = size(G);
c = sum(G,1);%each row's sum
r = sum(G,2);%each col's sum
% Scale column sums to be 1 (or 0 where there are no out links).
k = find(c~=0);
D = sparse(k,k,1./c(k),n,n);
% Solve (I - p*G*D)*x = e
e = ones(n,1);
I = speye(n,n);
x = (I - p*G*D)\e;
% Normalize so that sum(x) == 1.
x = x/sum(x);
(3) 巧妙解法：逆迭代算法
巧妙利用Matlab中的精度误差导致原本是一个奇异矩阵的$I-A$变成一个非奇异矩阵，运行时只是会有些警告提示，但是运行结果和其他算法一样。
function x = pagerank2(G)
% PAGERANK1
Google's PageRank modified version 2 - hujiawei
% using inverse iteration method
%if nargin & 3, p = .85; end
% Eliminate any self-referential links
G = G - diag(diag(G));
% c = out-degree, r = in-degree
[n,n] = size(G);
c = sum(G,1);%each row's sum
r = sum(G,2);%each col's sum
% Scale column sums to be 1 (or 0 where there are no out links).
k = find(c~=0);
D = sparse(k,k,1./c(k),n,n);
% Solve (I - p*G*D)*x = e
e = ones(n,1);
I = speye(n,n);
% x = (I - p*G*D)\e;
delta=(1-p)/n;
x=(I-A)\e;
% Normalize so that sum(x) == 1.
x = x/sum(x);
最后，附上参考内容4中给出的一份好代码，用于模拟随机冲浪生成矩阵$G$的代码
function [U,G] = surfer(root,n)
Create the adjacency graph of a portion of the Web.
[U,G] = surfer(root,n) starts at the URL root and follows
Web links until it forms an adjacency graph with n nodes.
U = a cell array of n strings, the URLs of the nodes.
G = an n-by-n sparse matrix with G(i,j)=1 if node j is linked to node i.
[U,G] = surfer('http://www.harvard.edu',500);
See also PAGERANK.
This function currently has two defects.
(1) The algorithm for
finding links is naive.
We just look for the string 'http:'.
(2) An attempt to read from a URL that is accessible, but very slow,
might take an unacceptably long time to complete.
In some cases,
it may be necessary to have the operating system terminate MATLAB.
Key words from such URLs can be added to the skip list in surfer.m.
% Initialize
set(gcf,'doublebuffer','on')
axis([0 n 0 n])
axis square
set(gca,'position',[.12 .20 .78 .78])
uicontrol('style','frame','units','normal','position',[.01 .09 .98 .07]);
uicontrol('style','frame','units','normal','position',[.01 .01 .98 .07]);
t1 = uicontrol('style','text','units','normal','position',[.02 .10 .94 .04], ...
'horiz','left');
t2 = uicontrol('style','text','units','normal','position',[.02 .02 .94 .04], ...
'horiz','left');
slow = uicontrol('style','toggle','units','normal', ...
'position',[.01 .24 .07 .05],'string','slow','value',0);
quit = uicontrol('style','toggle','units','normal', ...
'position',[.01 .17 .07 .05],'string','quit','value',0);
U = cell(n,1);
hash = zeros(n,1);
G = logical(sparse(n,n));
hash(m) = hashfun(root);
while j & n & get(quit,'value') == 0
% Try to open a page.
set(t1,'string',sprintf('%5d %s',j,U{j}))
set(t2,'string','');
page = urlread(U{j});
set(t1,'string',sprintf('fail: %5d %s',j,U{j}))
if get(slow,'value')
pause(.25)
% Follow the links from the open page.
for f = findstr('http:',page);
% A link starts with 'http:' and ends with the next quote.
e = min([findstr('"',page(f:end)) findstr('''',page(f:end))]);
if isempty(e), continue, end
url = deblank(page(f:f+e-2));
url(url&' ') = '!';
% Nonprintable characters
if url(end) == '/', url(end) = []; end
% Look for links that should be skipped.
skips = {'.gif','.jpg','.pdf','.css','lmscadsi','cybernet', ...
'search.cgi','.ram','www.w3.org', ...
'scripts','netscape','shockwave','webex','fansonly'};
skip = any(url=='!') | any(url=='?');
while ~skip & (k & length(skips))
skip = ~isempty(findstr(url,skips{k}));
if isempty(findstr(url,'.gif')) & isempty(findstr(url,'.jpg'))
set(t2,'string',sprintf('skip: %s',url))
if get(slow,'value')
pause(.25)
% Check if page is already in url list.
for k = find(hash(1:m) == hashfun(url))';
if isequal(U{k},url)
% Add a new url to the graph there if are fewer than n.
if (i == 0) & (m & n)
hash(m) = hashfun(url);
% Add a new link.
G(i,j) = 1;
set(t2,'string',sprintf('%5d %s',i,url))
line(j,i,'marker','.','markersize',6)
if get(slow,'value')
pause(.25)
delete(t1)
delete(t2)
delete(slow)
set(quit,'string','close','callback','close(gcf)','value',0)
%------------------------
function h = hashfun(url)
% Almost unique numeric hash code for pages already visited.
h = length(url) + 1024*sum(url);
4.MapReduce框架下PageRank算法的实现
利用前面wiki上的迭代(或者幂法)的思想来实现MapReduce框架下PageRank算法很简单，可以先阅读下参考内容5。
这篇文章更加详细，可以参考
以下是我的大数据的一次作业，要求是参考wiki上的简便算法，实现MapReduce框架下的PageRank算法。给的数据集是Twitter的用户之间的关系，可以看做是网页之间的关系，但是助教没要求写代码以及运行这个数据集(有1G多)，所以下面只是一个Python版本的理想可行版本，并没有通过实际大数据集的验证，另外，博主暂时还不太会Python的mapreduce框架中的一些函数，所以实现的是一个简明的可以测试的PageRank算法。
1.输入输出格式
map函数的输入是&节点，从该节点引出的边列表&，其中节点是一个类，包含了其当前的pagerank值，输出是&节点，反向节点pagerank值/反向节点引出边的总数&；
reduce函数的输入是&节点，反向节点pagerank值/反向节点引出边的总数&，输出是&节点，从该节点引出的边列表&，其中节点包含了其更新后的pagerank值。
伪代码： [一时犯二写了个英文形式的 ]
process the data to the form of {node i:[its adjacent node list],...}
while the sum of difference between the last two pagerank values & threshold
map({node i:[its adjacent node list],...}):
map_output={}
for every node j in adjacent node list:
put or sum up {j:(i, PageRank(i)/length(adjacent node list))} into map_output
return map_output
reduce(map_output):
reduce_output={}
for every entry {j:(i, PageRank(i)/length(adjacent node list))} in map_output:
put or sum up all values pagerank values for node j with its adjacent node list into reduce_output
return reduce_output
2.示例演示
假设用户1，2，3，4是如下图所示的关系：
假设有2个mapper(A和B)和1个reducer(C)，初始时4个节点的pagerank值都是0.25
其中，关于用户1和2的数据被mapperA读取并处理，关于用户3和4的数据被mapperB读取并处理 [经验证，即使一个用户的数据是由不同的mapper来读取的，最终收敛到的结果差不多]
map的输入输出结果如下：
reduce的输入输出结果如下，输入是2个mapper的输出，输出的结果中更新了节点的pagerank值
reducer处理完了之后又将它的结果输入给mapper处理，直到迭代的次数超过了设定值或者两次迭代之后得到的所有节点的pagerank值之差的总和(也可以是取二范数)小于设定的阈值。
3.示例的实验结果
(1)首先是使用Matlab采用幂法的方式计算出在p=1.0的情况下示例得到的结果 [它的主要作用是验证后面python版本的正确性]
matlab源码如下：
i=[2 3 4 3 4 4 1 2];
j=[1 1 1 2 2 3 3 4];
G=sparse(i,j,1,n,n);
[n,n] = size(G);
for j = 1:n
L{j} = find(G(:,j));
c(j) = length(L{j});
% Power method
delta = (1-p)/n;
x = ones(n,1)/n;
z = zeros(n,1);
while max(abs(x-z)) & .0001
x = zeros(n,1);
for j = 1:n
if c(j) == 0
x = x + z(j)/n;
x(L{j}) = x(L{j}) + z(j)/c(j);
cnt = cnt+1;
sprintf('pagerank result:')
(2)matlab版本的page rank没有采用mapreduce的思想进行迭代，所以我另外写了一个python版本的利用mapreduce思想实现的pagerank算法(注：我并没有使用python的map和reduce函数去实现，而是使用更加容易明白的实现)，使用的阈值为0.0001，最多迭代的次数为100次。
# coding=utf-8
__author__ = 'hujiawei'
__doc__ = 'pagerank mapreduce'
class Node:
def __init__(self,id,pk):
self.id=id
self.pk=pk
def pk_map(map_input):
map_output={}
for node,outlinks in map_input.items():
for link in outlinks:
size=len(outlinks)
if link in map_output:
map_output[link]+=(float)(node.pk)/size
map_output[link]=(float)(node.pk)/size
return map_output
def pk_reduce(reduce_input):
for result in reduce_input:
for node,value in result.items():
node.pk+=value
def pk_clear(nodes):
for node in nodes:
def pk_last(nodes):
lastnodes=[]
for node in nodes:
lastnodes.append(Node(node.id,node.pk))
return lastnodes
def pk_diff(nodes,lastnodes):
for i in range(len(nodes)):
print('node pk %f, last node pk %f ' % (nodes[i].pk, lastnodes[i].pk))
diff+=abs(nodes[i].pk-lastnodes[i].pk)
return diff
def pk_test1():
node1 = Node(1, 0.25)
node2 = Node(2, 0.25)
node3 = Node(3, 0.25)
node4 = Node(4, 0.25)
nodes = [node1, node2, node3, node4]
threshold = 0.0001
max_iters = 100
for iter_count in range(max_iters):
iter_count += 1
lastnodes=pk_last(nodes)
print('============ map count %d =================' % (iter_count))
in1 = {node1: [node2, node3, node4], node2: [node3, node4]}
in2 = {node3: [node1, node4], node4: [node2]}
mapout1 = pk_map(in1)
mapout2 = pk_map(in2)
for node, value in mapout1.items():
print str(node.id) + ' ' + str(value)
for node, value in mapout2.items():
print str(node.id) + ' ' + str(value)
print('============ reduce count %d =================' % (iter_count))
reducein = [mapout1, mapout2]
pk_clear(nodes)
pk_reduce(reducein)
for node in nodes:
print str(node.id) + ' ' + str(node.pk)
diff=pk_diff(nodes,lastnodes)
if diff & threshold:
if __name__ == '__main__':
pk_test1()
得到的结果为如下，总共迭代了15次
上面的结果和Matlab用幂法得到的pagerank值差别很小，可以认为是正确的，所以说明了使用这种mapreduce输入输出格式的正确性。
OK，差不多了，希望对需要理解PageRank算法的人有帮助！ :-)
欢迎来到最专业的开发者社区
终于被你注意到了 ^_^，如果你觉得这个社区还不错，记得要加入我们哦
最专业的开发者社区
最前沿的技术问答，最纯粹的技术切磋。让你不知不觉中开拓眼界，提高技能，认识更多朋友。
分享到微博？
举报理由：
带有人身攻击、辱骂、仇恨等违反条款的内容
与已有问题重复
内容质量差，或不适合在本网站出现
答非所问，不符合答题要求
其他原因（请补充说明）
补充说明：机器学习中的算法(2)-支持向量机(SVM)基础 - LeftNotEasy - 博客园
版权声明：
&&& 本文由LeftNotEasy发布于, 本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系
&&& 又有很长的一段时间没有更新博客了，距离上次更新已经有两个月的时间了。其中一个很大的原因是，不知道写什么好-_-，最近一段时间看了看关于SVM(Support Vector Machine)的文章，觉得SVM是一个非常有趣，而且自成一派的方向，所以今天准备写一篇关于关于SVM的文章。
&&& 关于SVM的论文、书籍都非常的多，引用强哥的话“SVM是让应用数学家真正得到应用的一种算法”。SVM对于大部分的普通人来说，要完全理解其中的数学是非常困难的，所以要让这些普通人理解，得要把里面的数学知识用简单的语言去讲解才行。而且想明白了这些数学，对学习其他的内容也是大有裨益的。我就是属于绝大多数的普通人，为了看明白SVM，看了不少的资料，这里把我的心得分享分享。
&&& 其实现在能够找到的，关于SVM的中文资料已经不少了，不过个人觉得，每个人的理解都不太一样，所以还是决定写一写，一些雷同的地方肯定是不可避免的，不过还是希望能够写出一点与别人不一样的地方吧。另外本文准备不谈太多的数学（因为很多文章都谈过了），尽量简单地给出结论，就像题目一样-机器学习中的算法（之前叫做机器学习中的数学），所以本系列的内容将更偏重应用一些。如果想看更详细的数学解释，可以看看参考文献中的资料。
一、线性分类器：
&&& 首先给出一个非常非常简单的分类问题（线性可分），我们要用一条直线，将下图中黑色的点和白色的点分开，很显然，图上的这条直线就是我们要求的直线之一（可以有无数条这样的直线）
&&& 假如说，我们令黑色的点 = -1， 白色的点 =& +1，直线f(x) = w.x + b，这儿的x、w是向量，其实写成这种形式也是等价的f(x) = w1x1 + w2x2 … + wnxn + b, 当向量x的维度=2的时候，f(x) 表示二维空间中的一条直线， 当x的维度=3的时候，f(x) 表示3维空间中的一个平面，当x的维度=n & 3的时候，表示n维空间中的n-1维超平面。这些都是比较基础的内容，如果不太清楚，可能需要复习一下微积分、线性代数的内容。
&&& 刚刚说了，我们令黑色白色两类的点分别为+1, -1，所以当有一个新的点x需要预测属于哪个分类的时候，我们用sgn(f(x))，就可以预测了，sgn表示符号函数，当f(x) & 0的时候，sgn(f(x)) = +1, 当f(x) & 0的时候sgn(f(x)) = –1。
&&& 但是，我们怎样才能取得一个最优的划分直线f(x)呢？下图的直线表示几条可能的f(x)
&&& 一个很直观的感受是，让这条直线到给定样本中最近的点最远，这句话读起来比较拗口，下面给出几个图，来说明一下：
&&& 第一种分法：
&&& 第二种分法：
&&& 这两种分法哪种更好呢？从直观上来说，就是分割的间隙越大越好，把两个类别的点分得越开越好。就像我们平时判断一个人是男还是女，就是很难出现分错的情况，这就是男、女两个类别之间的间隙非常的大导致的，让我们可以更准确的进行分类。在SVM中，称为Maximum Marginal，是SVM的一个理论基础之一。选择使得间隙最大的函数作为分割平面是由很多道理的，比如说从概率的角度上来说，就是使得置信度最小的点置信度最大（听起来很拗口），从实践的角度来说，这样的效果非常好，等等。这里就不展开讲，作为一个结论就ok了，:)
&&& 上图被红色和蓝色的线圈出来的点就是所谓的支持向量(support vector)。
&& &&& 上图就是一个对之前说的类别中的间隙的一个描述。Classifier Boundary就是f(x)，红色和蓝色的线（plus plane与minus plane）就是support vector所在的面，红色、蓝色线之间的间隙就是我们要最大化的分类间的间隙。
&&& 这里直接给出M的式子：（从高中的解析几何就可以很容易的得到了，也可以参考后面Moore的ppt）
&&& 另外支持向量位于wx + b = 1与wx + b = -1的直线上，我们在前面乘上一个该点所属的类别y（还记得吗?y不是+1就是-1），就可以得到支持向量的表达式为：y(wx + b) = 1，这样就可以更简单的将支持向量表示出来了。
&&& 当支持向量确定下来的时候，分割函数就确定下来了，两个问题是等价的。得到支持向量，还有一个作用是，让支持向量后方那些点就不用参与计算了。这点在后面将会更详细的讲讲。
&&& 在这个小节的最后，给出我们要优化求解的表达式：
&&& ||w||的意思是w的二范数，跟上面的M表达式的分母是一个意思，之前得到，M = 2 / ||w||，最大化这个式子等价于最小化||w||, 另外由于||w||是一个单调函数，我们可以对其加入平方，和前面的系数，熟悉的同学应该很容易就看出来了，这个式子是为了方便求导。
&&& 这个式子有还有一些限制条件，完整的写下来，应该是这样的：（原问题）
&&& s.t的意思是subject to，也就是在后面这个限制条件下的意思，这个词在svm的论文里面非常容易见到。这个其实是一个带约束的二次规划(quadratic programming, QP)问题，是一个凸问题，凸问题就是指的不会有局部最优解，可以想象一个漏斗，不管我们开始的时候将一个小球放在漏斗的什么位置，这个小球最终一定可以掉出漏斗，也就是得到全局最优解。s.t.后面的限制条件可以看做是一个凸多面体，我们要做的就是在这个凸多面体中找到最优解。这些问题这里不展开，因为展开的话，一本书也写不完。如果有疑问请看看wikipedia。
二、转化为对偶问题，并优化求解:
&&& 这个优化问题可以用去解，使用了的理论，这里直接作出这个式子的拉格朗日目标函数：
&&& 求解这个式子的过程需要的相关知识（另外pluskid也有专门讲这个问题），并且有一定的公式推导，如果不感兴趣，可以直接跳到后面用蓝色公式表示的结论，该部分推导主要参考自。
&&& 首先让L关于w，b最小化，分别令L关于w，b的偏导数为0，得到关于原问题的一个表达式
&&& 将两式带回L(w,b,a)得到对偶问题的表达式
&&& 新问题加上其限制条件是（对偶问题）:
&&& 这个就是我们需要最终优化的式子。至此，得到了线性可分问题的优化式子。
&&& 求解这个式子，有很多的方法，比如等等，个人认为，求解这样的一个带约束的凸优化问题与得到这个凸优化问题是比较独立的两件事情，所以在这篇文章中准备完全不涉及如何求解这个话题，如果之后有时间可以补上一篇文章来谈谈:)。
三、线性不可分的情况（软间隔）：
&&& 接下来谈谈线性不可分的情况，因为线性可分这种假设实在是太有局限性了：
&&& 下图就是一个典型的线性不可分的分类图，我们没有办法用一条直线去将其分成两个区域，每个区域只包含一种颜色的点。
&&&& 要想在这种情况下的分类器，有两种方式，一种是用曲线去将其完全分开，曲线就是一种非线性的情况，跟之后将谈到的核函数有一定的关系：
&&&& 另外一种还是用直线，不过不用去保证可分性，就是包容那些分错的情况，不过我们得加入惩罚函数，使得点分错的情况越合理越好。其实在很多时候，不是在训练的时候分类函数越完美越好，因为训练函数中有些数据本来就是噪声，可能就是在人工加上分类标签的时候加错了，如果我们在训练（学习）的时候把这些错误的点学习到了，那么模型在下次碰到这些错误情况的时候就难免出错了（假如老师给你讲课的时候，某个知识点讲错了，你还信以为真了，那么在考试的时候就难免出错）。这种学习的时候学到了“噪声”的过程就是一个过拟合（over-fitting），这在机器学习中是一个大忌，我们宁愿少学一些内容，也坚决杜绝多学一些错误的知识。还是回到主题，用直线怎么去分割线性不可分的点：
&&&& 我们可以为分错的点加上一点惩罚，对一个分错的点的惩罚函数就是这个点到其正确位置的距离：
&&& 在上图中，蓝色、红色的直线分别为支持向量所在的边界，绿色的线为决策函数，那些紫色的线表示分错的点到其相应的决策面的距离，这样我们可以在原函数上面加上一个惩罚函数，并且带上其限制条件为：
&&& 公式中蓝色的部分为在线性可分问题的基础上加上的惩罚函数部分，当xi在正确一边的时候，ε=0，R为全部的点的数目，C是一个由用户去指定的系数，表示对分错的点加入多少的惩罚，当C很大的时候，分错的点就会更少，但是过拟合的情况可能会比较严重，当C很小的时候，分错的点可能会很多，不过可能由此得到的模型也会不太正确，所以如何选择C是有很多学问的，不过在大部分情况下就是通过经验尝试得到的。
&&& 接下来就是同样的，求解一个拉格朗日对偶问题，得到一个原问题的对偶问题的表达式：
&&& 蓝色的部分是与线性可分的对偶问题表达式的不同之处。在线性不可分情况下得到的对偶问题，不同的地方就是α的范围从[0, +∞)，变为了[0, C]，增加的惩罚ε没有为对偶问题增加什么复杂度。
四、核函数：
&&& 刚刚在谈不可分的情况下，提了一句，如果使用某些非线性的方法，可以得到将两个分类完美划分的曲线，比如接下来将要说的核函数。
&&& 我们可以让空间从原本的线性空间变成一个更高维的空间，在这个高维的线性空间下，再用一个超平面进行划分。这儿举个例子，来理解一下如何利用空间的维度变得更高来帮助我们分类的（例子以及图片来自）：
&&& 下图是一个典型的线性不可分的情况
&&& 但是当我们把这两个类似于椭圆形的点映射到一个高维空间后，映射函数为：
&&& 用这个函数可以将上图的平面中的点映射到一个三维空间（z1,z2,z3)，并且对映射后的坐标加以旋转之后就可以得到一个线性可分的点集了。
&&& 用另外一个哲学例子来说：世界上本来没有两个完全一样的物体，对于所有的两个物体，我们可以通过增加维度来让他们最终有所区别，比如说两本书，从(颜色，内容)两个维度来说，可能是一样的，我们可以加上 作者 这个维度，是在不行我们还可以加入 页码，可以加入 拥有者，可以加入 购买地点，可以加入 笔记内容等等。当维度增加到无限维的时候，一定可以让任意的两个物体可分了。
&&& 回忆刚刚得到的对偶问题表达式：
&&& 我们可以将红色这个部分进行改造，令：
&&&& 这个式子所做的事情就是将线性的空间映射到高维的空间,k(x, xj)有很多种，下面是比较典型的两种：
&&& 上面这个核称为多项式核，下面这个核称为高斯核，高斯核甚至是将原始空间映射为无穷维空间，另外核函数有一些比较好的性质，比如说不会比线性条件下增加多少额外的计算量，等等，这里也不再深入。一般对于一个问题，不同的核函数可能会带来不同的结果，一般是需要尝试来得到的。
五、一些其他的问题：
&&&& 1）如何进行多分类问题：
&&&& 上面所谈到的分类都是2分类的情况，当N分类的情况下，主要有两种方式，一种是1 vs (N – 1)一种是1 vs 1，前一种方法我们需要训练N个分类器，第i个分类器是看看是属于分类i还是属于分类i的补集（出去i的N-1个分类）。
&&&& 后一种方式我们需要训练N * (N – 1) / 2个分类器，分类器(i,j)能够判断某个点是属于i还是属于j。
&&&& 这种处理方式不仅在SVM中会用到，在很多其他的分类中也是被广泛用到，从林教授（libsvm的作者）的结论来看，1 vs 1的方式要优于1 vs (N – 1)。
&&&& 2）SVM会overfitting吗？
&&&& SVM避免overfitting，一种是调整之前说的惩罚函数中的C，另一种其实从式子上来看，min ||w||^2这个看起来是不是很眼熟？在最小二乘法回归的时候，我们看到过这个式子，这个式子可以让函数更平滑，所以SVM是一种不太容易over-fitting的方法。
参考文档：
&&& 主要的参考文档来自4个地方，wikipedia（在文章中已经给出了超链接了），，（文章中不少图片都是引用或者改自Andrew Moore的ppt，以及prml}