文章目录
from google.colab import drive
drive.mount("/content/drive")
Drive already mounted at /content/drive; to attempt to forcibly remount, call drive.mount("/content/drive", force_remount=True).
支持向量机
from numpy import *
def selectJrand(i, m):
j=i
while(j==i):
j = int(random.uniform(0, m))
return j
def clipAlpha(aj, H, L):
if aj > H:
aj = H
if L > aj:
aj = L
return aj
def kernelTrans(X, A, kTup): #calc the kernel or transform data to a higher dimensional space
m,n = shape(X)
K = mat(zeros((m,1)))
if kTup[0]=='lin': K = X * A.T #linear kernel
elif kTup[0]=='rbf':
for j in range(m):
deltaRow = X[j,:] - A
K[j] = deltaRow*deltaRow.T
K = exp(K/(-1*kTup[1]**2)) #divide in NumPy is element-wise not matrix like Matlab
else: raise NameError('Houston We Have a Problem -- \
That Kernel is not recognized')
return K
class optStruct:
def __init__(self,dataMatIn, classLabels, C, toler, kTup): # Initialize the structure with the parameters
self.X = dataMatIn
self.labelMat = classLabels
self.C = C
self.tol = toler
self.m = shape(dataMatIn)[0]
self.alphas = mat(zeros((self.m,1)))
self.b = 0
self.eCache = mat(zeros((self.m,2))) #first column is valid flag
self.K = mat(zeros((self.m,self.m)))
for i in range(self.m):
self.K[:,i] = kernelTrans(self.X, self.X[i,:], kTup)
def calcEk(oS, k):
fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)
Ek = fXk - float(oS.labelMat[k])
return Ek
def selectJ(i, oS, Ei): #this is the second choice -heurstic, and calcs Ej
maxK = -1; maxDeltaE = 0; Ej = 0
oS.eCache[i] = [1,Ei] #set valid #choose the alpha that gives the maximum delta E
validEcacheList = nonzero(oS.eCache[:,0].A)[0]
if (len(validEcacheList)) > 1:
for k in validEcacheList: #loop through valid Ecache values and find the one that maximizes delta E
if k == i: continue #don't calc for i, waste of time
Ek = calcEk(oS, k)
deltaE = abs(Ei - Ek)
if (deltaE > maxDeltaE):
maxK = k; maxDeltaE = deltaE; Ej = Ek
return maxK, Ej
else: #in this case (first time around) we don't have any valid eCache values
j = selectJrand(i, oS.m)
Ej = calcEk(oS, j)
return j, Ej
def updateEk(oS, k):#after any alpha has changed update the new value in the cache
Ek = calcEk(oS, k)
oS.eCache[k] = [1,Ek]
def innerL(i, oS):
Ei = calcEk(oS, i)
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)):
j,Ej = selectJ(i, oS, Ei) #this has been changed from selectJrand
alphaIold = oS.alphas[i].copy(); alphaJold = oS.alphas[j].copy();
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
eta = 2.0 * oS.K[i,j] - oS.K[i,i] - oS.K[j,j] #changed for kernel
if eta >= 0:
print("eta>=0")
return 0
oS.alphas[j] -= oS.labelMat[j]*(Ei - Ej)/eta
oS.alphas[j] = clipAlpha(oS.alphas[j],H,L)
updateEk(oS, j) #added this for the Ecache
if (abs(oS.alphas[j] - alphaJold) < 0.00001):
print("j not moving enough")
return 0
oS.alphas[i] += oS.labelMat[j]*oS.labelMat[i]*(alphaJold - oS.alphas[j])#update i by the same amount as j
updateEk(oS, i) #added this for the Ecache #the update is in the oppostie direction
b1 = oS.b - Ei- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,i] - oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[i,j]
b2 = oS.b - Ej- oS.labelMat[i]*(oS.alphas[i]-alphaIold)*oS.K[i,j]- oS.labelMat[j]*(oS.alphas[j]-alphaJold)*oS.K[j,j]
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
else: return 0
这段代码定义了函数innerL(i, oS)，它是Platt SMO算法的内部循环的一部分，用于选择和优化alpha对。
在函数内部，首先计算样本i的误差Ei，然后根据该误差和一些条件来确定是否对alpha对进行优化。这些条件包括误差是否超出了容错率tol，以及alpha是否在取值范围内。
如果满足优化条件，则调用selectJ函数选择第二个alpha，并计算其误差Ej。接着，根据两个样本的标签，计算alpha对应的约束条件。
然后，根据选择的alpha对，计算更新量，并更新alpha对应的值。同时，根据更新后的alpha值，更新模型的截距b。
最后，函数返回一个标志值，表示是否对alpha对进行了优化。如果没有进行优化，则返回0，否则返回1。
整体而言，该函数负责执行Platt SMO算法的内部循环，用于选择和优化alpha对。
def smoP(dataMatIn, classLabels, C, toler, maxIter,kTup=('lin', 0)): #full Platt SMO
oS = optStruct(mat(dataMatIn),mat(classLabels).transpose(),C,toler, kTup)
iter = 0
entireSet = True; alphaPairsChanged = 0
while (iter < maxIter) and ((alphaPairsChanged > 0) or (entireSet)):
alphaPairsChanged = 0
if entireSet: #go over all
for i in range(oS.m):
alphaPairsChanged += innerL(i,oS)
print("fullSet, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
iter += 1
else:#go over non-bound (railed) alphas
nonBoundIs = nonzero((oS.alphas.A > 0) * (oS.alphas.A < C))[0]
for i in nonBoundIs:
alphaPairsChanged += innerL(i,oS)
print("non-bound, iter: %d i:%d, pairs changed %d" % (iter,i,alphaPairsChanged))
iter += 1
if entireSet: entireSet = False #toggle entire set loop
elif (alphaPairsChanged == 0): entireSet = True
print("iteration number: %d" % iter)
return oS.b,oS.alphas
这段代码定义了一个名为smoP的函数，用于执行完整的Platt SMO算法，用于训练支持向量机模型。
函数接受输入参数dataMatIn（数据集矩阵）、classLabels（类别标签向量）、C（惩罚参数）、toler（容错率）、maxIter（最大迭代次数）以及kTup（核函数类型和参数元组）。
函数首先创建了一个optStruct对象oS，该对象包含了算法所需的所有数据。
接着，函数使用一个while循环来执行算法的主要步骤，直到达到最大迭代次数或者不再有alpha对发生变化。
在每次迭代中，函数会根据entireSet的值来决定遍历整个数据集还是只遍历非边界样本。然后，对于每个样本，调用innerL函数来尝试进行alpha的优化。innerL函数会尝试对alpha对进行优化，并返回是否有alpha对发生了变化。
在每次迭代的末尾，函数会根据是否有alpha对发生变化来更新entireSet的值。
最终，函数返回了训练得到的模型的截距oS.b和权重oS.alphas。
综上所述，该函数是完整的Platt SMO算法的实现，用于训练支持向量机模型。
导入图片
def img2vector(filename):
returnVect = zeros((1,1024))
fr = open(filename)
for i in range(32):
lineStr = fr.readline()
for j in range(32):
returnVect[0,32*i+j] = int(lineStr[j])
return returnVect
这段代码是一个简单的函数，名为img2vector，它的作用是将一个32x32的二进制图像文件转换为一个1x1024的向量。
函数首先创建了一个全零的1x1024的向量returnVect。然后，它打开给定的文件并读取文件的内容。接着，它通过一个嵌套的循环遍历图像的每一行和每一列，将每个像素值（0或1）填充到向量returnVect中。最后，函数返回这个向量。
程序首先创建了一个1x1024的全零向量，然后按行读取文件中的数据。因为每一行都代表图像的一行像素值，所以对于每一行，程序再按列遍历，并将每个像素值（0或1）填充到向量中。最终，函数返回这个1x1024的向量表示图像。
def loadImages(dirName):
from os import listdir
hwLabels = []
trainingFileList = listdir(dirName) #load the training set
m = len(trainingFileList)
trainingMat = zeros((m,1024))
for i in range(m):
fileNameStr = trainingFileList[i]
fileStr = fileNameStr.split('.')[0] #take off .txt
classNumStr = int(fileStr.split('_')[0])
if classNumStr == 9: hwLabels.append(-1)
else: hwLabels.append(1)
trainingMat[i,:] = img2vector('%s/%s' % (dirName, fileNameStr))
return trainingMat, hwLabels
这段代码定义了一个名为loadImages的函数，其目的是加载一个文件夹中的图像数据集，并将它们转换为一个矩阵以及相应的标签。
函数首先从Python的os模块中导入了listdir函数，然后定义了一个空列表hwLabels来存储图像的标签。接着，函数使用listdir函数加载给定目录中的所有文件名，并将其存储在trainingFileList列表中。
然后，函数计算了trainingFileList的长度，即图像的总数，并创建了一个全零的矩阵trainingMat，其大小为(m, 1024)，其中m是图像的数量，1024表示每个图像被转换为的向量的维度。
接下来，函数通过一个循环遍历所有的图像文件，对每个文件进行处理。它首先提取文件名中的类别信息，并将其转换为整数形式作为标签。如果类别是9，那么对应标签设为-1，否则设为1。然后，函数调用之前定义的img2vector函数将图像文件转换为向量，并将其存储在trainingMat的第i行中。
最后，函数返回了转换后的图像数据矩阵trainingMat以及对应的标签hwLabels。
综上所述，该函数的作用是加载一个图像数据集，将图像转换为向量表示，并为每个图像提供相应的标签。
测试算法
def testDigits(kTup=('rbf', 10)):
dataArr,labelArr = loadImages('/content/drive/MyDrive/Colab Notebooks/MachineLearning/《机器学习实战》/支持向量机/手写识别问题/digits/trainingDigits')
b,alphas = smoP(dataArr, labelArr, 200, 0.0001, 10000, kTup)
datMat=mat(dataArr); labelMat = mat(labelArr).transpose()
svInd=nonzero(alphas.A>0)[0]
sVs=datMat[svInd]
labelSV = labelMat[svInd];
print("there are %d Support Vectors" % shape(sVs)[0])
m,n = shape(datMat)
errorCount = 0
for i in range(m):
kernelEval = kernelTrans(sVs,datMat[i,:],kTup)
predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b
if sign(predict)!=sign(labelArr[i]): errorCount += 1
print("the training error rate is: %f" % (float(errorCount)/m))
dataArr,labelArr = loadImages('/content/drive/MyDrive/Colab Notebooks/MachineLearning/《机器学习实战》/支持向量机/手写识别问题/digits/trainingDigits')
errorCount = 0
datMat=mat(dataArr); labelMat = mat(labelArr).transpose()
m,n = shape(datMat)
for i in range(m):
kernelEval = kernelTrans(sVs,datMat[i,:],kTup)
predict=kernelEval.T * multiply(labelSV,alphas[svInd]) + b
if sign(predict)!=sign(labelArr[i]): errorCount += 1
print("the test error rate is: %f" % (float(errorCount)/m))
这段代码定义了一个名为testDigits的函数，用于测试支持向量机在手写数字识别问题上的性能。
该函数首先调用loadImages函数加载训练数据集，然后使用smoP函数训练支持向量机模型。smoP函数返回的b和alphas分别是模型的截距和支持向量的权重。
接着，函数将数据集转换为矩阵形式，并提取出支持向量的索引svInd，支持向量本身sVs以及对应的标签labelSV。然后，函数计算训练错误率，并打印出支持向量的数量和训练错误率。
接下来，函数再次加载测试数据集，并计算测试错误率。在这一过程中，函数使用了之前训练得到的支持向量sVs、支持向量的标签labelSV以及模型的截距b和权重alphas。
最后，函数打印出测试错误率。
总体而言，该函数用于测试支持向量机模型在手写数字识别问题上的性能，包括训练错误率和测试错误率。
testDigits(('rbf', 20))
<ipython-input-10-c1e41c4ea928>:2: DeprecationWarning: Conversion of an array with ndim > 0 to a scalar is deprecated, and will error in future. Ensure you extract a single element from your array before performing this operation. (Deprecated NumPy 1.25.)
fXk = float(multiply(oS.alphas,oS.labelMat).T*oS.K[:,k] + oS.b)
<ipython-input-10-c1e41c4ea928>:3: DeprecationWarning: Conversion of an array with ndim > 0 to a scalar is deprecated, and will error in future. Ensure you extract a single element from your array before performing this operation. (Deprecated NumPy 1.25.)
Ek = fXk - float(oS.labelMat[k])
fullSet, iter: 9 i:216, pairs changed 0
L==H
fullSet, iter: 9 i:217, pairs changed 0
fullSet, iter: 9 i:218, pairs changed 0
fullSet, iter: 9 i:219, pairs changed 0
fullSet, iter: 9 i:220, pairs changed 0
fullSet, iter: 9 i:221, pairs changed 0
fullSet, iter: 9 i:222, pairs changed 0
……
fullSet, iter: 11 i:1923, pairs changed 0
fullSet, iter: 11 i:1924, pairs changed 0
fullSet, iter: 11 i:1925, pairs changed 0
fullSet, iter: 11 i:1926, pairs changed 0
fullSet, iter: 11 i:1927, pairs changed 0
fullSet, iter: 11 i:1928, pairs changed 0
fullSet, iter: 11 i:1929, pairs changed 0
fullSet, iter: 11 i:1930, pairs changed 0
fullSet, iter: 11 i:1931, pairs changed 0
fullSet, iter: 11 i:1932, pairs changed 0
fullSet, iter: 11 i:1933, pairs changed 0
iteration number: 12
there are 177 Support Vectors
the training error rate is: 0.000517