简单SVM分类器的开源实现，核心代码150行，svm150行,一个小巧，简单，但可能未

简单SVM分类器的开源实现，核心代码150行，svm150行,一个小巧，简单，但可能未

一个小巧，简单，但可能未必高效的SVM分类器，具有可视化功能

采用标准python写成，但如果需要作图功能需要安装matplotlib，否则注释相应代码即可

推荐安装enthought python。

import sys,math,plot# get current tolerance leveldef tolerance(v1,v2,norm):    sum = 0.0    for k in v1.keys()+v2.keys():        t1 = 0        t2 = 0        if k in v1:            t1 = v1[k]        if k in v2:            t2 = v2[k]        sum += (t1-t2) * (t1 - t2)    return math.sqrt(sum/norm)# fill dense alpha list with initial valuesdef init_alpha(num_examples):    alpha_s = []    for i in range(num_examples):        alpha_s.append((0.0,i))    return alpha_s# dot products for two dict format vectorsdef dot(v1,v2):    sum = 0.0    if len(v1) < len(v2):        for id in v1.keys():            if id in v2:                sum += v1[id] * v2[id]    else:        for id in v2.keys():            if id in v1:                sum += v1[id] * v2[id]    return sum# kernel evaluation for two vectorsdef kernel(v1, v2):    return dot(v1,v2)# build lower triangular kernel matrix compute_Qdef compute_Q(es,height):    q = []    for i in range(height):        q.append([])        for j in range(height):            if i>=j:                q[i].append(kernel(es[i],es[j]))    return q# retrieve kernel matrix element on i,j def ret_Q(q,i,j):    if i>=j:        return q[i][j]    else:        return q[j][i]def read_examples(stream):    es = []    cs = []    width = 0    height = 0    for line in stream:        e = {}        c = float(line[0:line.find(" ")])        for t in line[line.find(" ")+1:].split():            ts = t.split(":")            id = int(ts[0])            e[id] = float(ts[1])            if id > width:                width = id        es.append(e)        cs.append(c)        height += 1    return height, width, cs,esdef main(C=1.0, max_iter=100, tol = 0.001, show_plot=False):    alpha_sparse = {} # current sparse alpha list    alpha_s_prim = {} # previous sparse alpha list    print >> sys.stderr, "loading examples..."    height_e, width_e, cs,es = read_examples(sys.stdin)    print >> sys.stderr, "example matrix: " , height_e, ",", width_e    print >> sys.stderr, "kernelizing..."    q = compute_Q(es,height_e)    alpha_s = init_alpha(height_e)    bias = 0    # stochastic gradient descent    for i in range(max_iter):        print >> sys.stderr, "￥nnew iteration:", i+1        gamma = 1        # sort alpha list in reversed order        alpha_s.sort(None, None, True)        print >> sys.stderr, alpha_s[0:30]        print >> sys.stderr, 'sparsity: ', len(alpha_sparse),':',height_e        alpha_s_prim = alpha_sparse.copy()        z_max = float("-infinity"); z_min= float("infinity")        for id in range(len(alpha_s)):            # update from the largest alpha            alpha = alpha_s[id][0]            j = alpha_s[id][1]            t = 0.0            for k in alpha_sparse.keys():                t += cs[k]* alpha_sparse[k] * ret_Q(q,j,k)            # check z_max and z_min for bias computation            if cs[j]>0:                if t < z_min:                    z_min = t            else:                if t > z_max:                    z_max = t            learning_rate = gamma * (1/ret_Q(q,j,j))            delta = learning_rate * ( 1 - t * cs[j] )            # check for soft-margin            alpha += delta            if alpha < 0 :                alpha = 0.0            if alpha > C:                alpha = C            # do update foe dense alpha list            alpha_s[id] = alpha,j            # do update for sparse alpha list            if math.fabs(alpha - 0.0) >= 1e-10:                alpha_sparse[j]=alpha            else:                if j in alpha_sparse:                    del alpha_sparse[j]        # get bias        bias = (z_max+z_min)/2.0        # chekc for tolerance        tol1 = tolerance(alpha_sparse, alpha_s_prim, float(height_e))        print >> sys.stderr, "tolerance:", tol1        if tol1 < tol:            print >> sys.stderr, "￥nfinished in",i+1,"iterations"            break    svm_res ={'sv_s':[],'id_s':[],'alpha_s':[]}    # support vectors    for id,alpha in alpha_sparse.items():        svm_res['sv_s'].append(es[id])        svm_res['id_s'].append(id)        svm_res['alpha_s'].append(cs[id]*alpha)    svm_res['bias'] = bias    # plot graph if needed    if show_plot:        plot.draw(cs, es, svm_res)    return svm_resif __name__ == "__main__":    t= main()    print 'support vectors:', t['sv_s']    print 'example IDs:', t['id_s']    print 'lagrange multipliers:',t['alpha_s']    print 'bias:', t['bias']#该片段来自于http://byrx.net