机器学习：SVM代码实现，朴素实现基础上的优化

SVM代码实现，朴素实现基础上的优化：

因为二次凸优化已经把解析结果明白表现出来了，所以优化只能体现在两个变量的选择上，或者说是两个样本的选择上：
1、第一个变量的选择：这次实现也并不是选择最不满足KKT条件的样本点，而是优先使用边界上的样本点也就是0<alpha<C的样本点，假如边界上的样本点均满足KKT条件，就遍历全体样本去找不满足的样本点
2、第二个变量的选择：选择和第一个样本误差相差最大的样本点,也就是|e1-e2|最大的点。
3、根据样本误差找第二个变量做了一定的优化：只需要已经更新过样本点误差的样本。

计算样本误差(预测值-实际值)、更新样本误差

def calcEkK(oS, k):
    """
    计算第k个样本点的误差
    :param oS:
    :param k:
    :return:
    """
    # 计算第k个样本点的误差值
    fXk = float(np.multiply(oS.alphas,oS.labelMat).T*(oS.X*oS.X[k,:].T)) + oS.b
    # 计算第k个样本的误差
    Ek = fXk - float(oS.labelMat[k])
    return Ek


def updateEkK(oS, k):
    # 更新误差，根据当前oS里面alphas和b,来更新误差，并标志误差为新的
    Ek = calcEkK(oS, k)
    oS.eCache[k] = [1,Ek]

启发式选择第二个变量：

def selectJK(i, oS, Ei):
    """
    选择第2个变量的过程，即内层循环中的启发规则。选择标准是使alpha_2有足够大的变化。
    :param i:第一个变量
    :param oS:中间结果
    :param Ei:第i个点的误差
    :return:
    """
    # 用于存放最大相距误差的样本点，最大相距误差，该样本点的误差
    maxK = -1; maxDeltaE = 0; Ej = 0
    oS.eCache[i] = [1,Ei]                           #设为有效
    # 找寻产生最大误差变化的alpha
    validEcacheList = np.nonzero(oS.eCache[:,0].A)[0]  #有效位为1的误差列表
    if (len(validEcacheList)) > 1:
        for k in validEcacheList:                   #遍历列表找出最大误差变化
            if k == i: continue                     #第二个alpha不应该等于第一个
            # 遍历计算每一个样本的误差
            Ek = calcEkK(oS, k)
            deltaE = abs(Ei - Ek)
            if (deltaE > maxDeltaE):
                maxK = k; maxDeltaE = deltaE; Ej = Ek
        return maxK, Ej
    else:                                        #找不到，只好随机选择一个
        # 第一次假如所有的样本都没有更新过，就随机选择，假如更新过，就使用上述策略
        j = selectJrand(i, oS.m)
        Ej = calcEkK(oS, j)
    return j, Ej

def selectJrand(i,m):
    """
    随机从0到m挑选一个不等于i的数
    :param i:
    :param m:
    :return:
    """
    j=i             #排除i
    while (j==i):
        j = int(np.random.uniform(0,m))
    return j

选取了第一个变量之后的核心处理：

# 内层循环，选择了第一个样本点之后，选择第二个样本点进行解析求解
def innerLK(i, oS):
    # 计算第一个样本点的误差
    Ei = calcEkK(oS, i)
    #如果误差太大，且alpha满足约束，则尝试优化它
    # 第一个样本点满足kkt条件
    if ((oS.labelMat[i]*Ei < -oS.tol) and (oS.alphas[i] < oS.C)) or ((oS.labelMat[i]*Ei > oS.tol) and (oS.alphas[i] > 0)):
        # 根据第一个样本点找第二个偏离最大的样本点，第一次eCache没有有效的样本误差，随机选择
        j,Ej = selectJK(i, oS, Ei)   #不再是 selectJrand 那种简化的选择方法
        alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy() # 教材中的α_1^old和α_2^old
        # 计算边界
        if (oS.labelMat[i] != oS.labelMat[j]):                           # 两者所在的对角线段端点的界
            L = max(0, oS.alphas[j] - oS.alphas[i])
            H = min(oS.C, oS.C + oS.alphas[j] - oS.alphas[i])
        else:
            L = max(0, oS.alphas[j] + oS.alphas[i] - oS.C)
            H = min(oS.C, oS.alphas[j] + oS.alphas[i])
        if L==H: print("L==H"); return 0
        # 计算-dK
        eta = 2.0 * oS.X[i,:]*oS.X[j,:].T - oS.X[i,:]*oS.X[i,:].T - oS.X[j,:]*oS.X[j,:].T
        if eta >= 0: print("eta>=0"); return 0
        # 计算a_2
        oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
        oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
        # 更新第二个样本点的误差，并设置误差有效
        updateEkK(oS, j)                                                # 更新误差缓存
        # 假如第二个样本点改进不大，换第一个样本点
        if (abs(oS.alphas[j] - alphaJold) < 0.00001): print ("j not moving enough"); return 0
        # 计算a_1
        oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])    #更新α_1
        # 更新a_1的误差
        updateEkK(oS, i)                                                 # # 更新误差缓存
        # 计算b
        b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[i,:].T - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[i,:]*oS.X[j,:].T
        b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.X[i,:]*oS.X[j,:].T - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.X[j,:]*oS.X[j,:].T
        if (0 < oS.alphas[i]) and (oS.C > oS.alphas[i]): oS.b = b1
        elif (0 < oS.alphas[j]) and (oS.C > oS.alphas[j]): oS.b = b2
        else: oS.b = (b1 + b2)/2.0
        return 1
    # 第一个样本点不满足kkt条件，直接下一个样本点
    else: return 0
    

第一个变量选择及主程序：

def smoPK(dataMatIn, classLabels, C, toler, maxIter):
    """
    完整版的Platt SMO算法
    :param dataMatIn:
    :param classLabels:
    :param C:
    :param toler:
    :param maxIter:
    :return:
    """
    oS = optStructK(np.mat(dataMatIn),np.mat(classLabels).transpose(),C,toler)
    iter = 0
    entireSet = True; alphaPairsChanged = 0
    # 这里的实现并没有在训练样本中选取违反KKT条件最严重的样本点，
    # 而是优先顺序遍历间隔边界上的支持向量点，若无法优化模型则遍历整个数据集。

    while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):
        alphaPairsChanged = 0
        # 第一次遍历整个数据集
        if entireSet:           #遍历所有值
            # 遍历每一个样本点，alphaPairsChanged标记了样本点是否做了操作
            for i in range(oS.m):        
                alphaPairsChanged += innerLK(i,oS)
                print ("fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
            iter += 1
        else:                   #遍历间隔边界上的支持向量点
            # 遍历 0< alpha < C上的样本点，也就是支持向量
            nonBoundIs = np.nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]
            for i in nonBoundIs:
                alphaPairsChanged += innerLK(i,oS)
                print ("non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
            iter += 1
        if entireSet: entireSet = False                 #翻转entireSet
        # 假如在支持向量上遍历，没有样本点可以优化，那么就在全集上遍历
        elif (alphaPairsChanged == 0): entireSet = True  
        print ("iteration number: %d" % iter)
    return oS.b,oS.alphas