四阶行列式的计算方法(SVM（支持向量机）算法)

支持向量机（Support Vector Machine）是Cortes和Vapnik与1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。

支持向量机方法是建立在统计学理论的VC维理论和结构风险最小原理的基础上，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误的识别任意样本的能力）之间寻求最佳折中，以期获得最好的推广能力（或称为泛化能力）

SVM算法大概可以分为三类，硬间隔最大化、软间隔最大化、非线性

• 硬间隔最大化

svm最初是为了解决二分类问题，寻找到一个超平面使样本分为两类，并且间隔最大。而我们求得的w就代表着我们需要寻找的超平面的系数。

与超平面的距离表示分类的确信度，距离越远则分类正确的确信度就越高。

有时候为了能将数据更好的分类，可能需要将数据代入到高维的空间中去解决，比如二维空间难分割的数据或许在三维空间就能被解决，当然，维度越高，计算复杂度也就越高。这里可以引入超平面方程的概念：

一条直线方程，其中斜率定义为m，c用来表示直线在y轴的截距，那么整个的直线方程表达式可以是：

那么对应的超平面方程式就可以这样表示：

其中w和x是向量，wTx 是两个向量的点积。向量w通常被称为权重。在二维空间里一条直线的方程可以表示为Ax+By+C = 0。在三维空间里，平面的方程则可以表示为Ax+By+Cz+D = 0。由此可推断在n为空间里，超平面方程的表示方式为：

简化用x1,x2,...xn表示n维坐标系，各个维度的系数用w1,w2,...wn表示，所以n维空间的超平面方程亦可以表示为如下形式

以二维空间为例，我们将x1和x2代入公式中来寻找两条直线之间的最大间隔：

两式相减得：

最终将问题转换为求|w|最小值的问题。此处引入拉格朗日乘子：

约束条件为：

又：

代入拉格朗日乘子法得：

分别对w和b求偏导，得到：

代入方程求解max：

通过求解a，得到w，b，进而得到模型

• 软间隔最大化

为了解决个别正例和负例样本点很接近时，引入松弛因子，当C趋近于无穷大时，容忍度越低，分类越严格；当C趋近于很小时，意味着容忍度很高：

目标函数：

可以推出：

代入原式得到：

SVM采用间隔点最大因为间距增大了超平面到支持向量点的距离，增强对未知分类的泛化能力

• 非线性支持向量机

现实任务中原始的样本空间D中很可能并不存在一个能正确划分两类样本的超平面。例如下图中所示的问题就无法找到一个超平面将两类样本进行很好的划分。对于这样的问题，可以通过将样本从原始空间映射到特征空间使得样本在映射后的特征空间里线性可分。

• 优点

解决小样本机器学习问题，非线性问题，无局部极小值问题。可很好的处理高维数据集，有优秀的泛化能力

SVM是一种有坚实理论基础的新颖的适用小样本学习方法。他基本上不涉及概率测度及大数定律等，也简化了通常的分类和回归等问题

计算机的复杂性取决于支持向量的数目，而不是样本空间的维数。这从某种意义上避免了维数灾难

SVM学习问题可以表示为凸优化问题，因此可以利用已知的有效算法发现目标函数的全局最小值。

少数支持向量决定了最终结果，对异常值不敏感，这不但可以帮我们抓住关键样本、删除大量冗余样本，而且注定了该方法不但算法简单，而且具有较好的鲁棒性

• 缺点

对大规模训练样本难以实施。SVM的空间消耗主要是存储训练样本和核矩阵。由于SVM是借助于二次规划来求支持向量。而求解二次规划将涉及m阶矩阵的计算。当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。

解决多分类问题困难。经典的支持向量机算法，只给出了二类分类的算法，而实际中一般要解决多类分类的问题。

对参数和核函数选择敏感。目前比较成熟的核函数及其参数的选择都是人为的，根据经验来选取的，带有一定的随意性。在不同的问题领域，核函数应当具有不同的形式和参数，但目前还没有好的方法来解决核函数的问题

import csv import numpy as np import matplotlib.pyplot as plt import copy from time import sleep import random import types def loadDataset(filename): with open(filename, 'r') as f: lines = csv.reader(f) data_set = list(lines) if filename != 'titanic.csv': for i in range(len(data_set)): del(data_set[i][0]) # 整理数据 for i in range(len(data_set)): del(data_set[i][0]) del(data_set[i][2]) data_set[i][4] += data_set[i][5] del(data_set[i][5]) del(data_set[i][5]) del(data_set[i][6]) del(data_set[i][-1]) category = data_set[0] del (data_set[0]) # 转换数据格式 for data in data_set: data[0] = int(data[0]) data[1] = int(data[1]) if data[3] != '': data[3] = float(data[3]) else: data[3] = None data[4] = float(data[4]) data[5] = float(data[5]) # 补全缺失值 转换记录方式 分类 for data in data_set: if data[3] is None: data[3] = 28 # male : 1, female : 0 if data[2] == 'male': data[2] = 1 else: data[2] = 0 # 经过测试，如果不将数据进行以下处理，分布会过于密集，处理后，数据的分布变得稀疏了 # age <25 为0, 25<=age<31为1，age>=31为2 if data[3] < 25: data[3] = 0 elif data[3] >= 21 and data[3] < 60: # 但是测试得60分界准确率最高？？？！！！ data[3] = 1 else: data[3] = 2 # sibsp&parcg以2为界限，小于为0，大于为1 if data[4] < 2: data[4] = 0 else: data[4] = 1 # fare以64为界限 if data[-1] < 64: data[-1] = 0 else: data[-1] = 1 return data_set, category def split_data(data): data_set = copy.deepcopy(data) data_mat = [] label_mat = [] for i in range(len(data_set)): if data_set[i][0] == 0: data_set[i][0] = -1 label_mat.append(data_set[i][0]) del(data_set[i][0]) data_mat.append(data_set[i]) print(data_mat) print(label_mat) return data_mat, label_mat def select_j_rand(i ,m): # 选取alpha j = i while j == i: j = int(random.uniform(0, m)) return j def clip_alptha(aj, H, L): # 修剪alpha if aj > H: aj = H if L > aj: aj = L return aj def smo(data_mat_In, class_label, C, toler, max_iter): # 转化为numpy的mat存储 data_matrix = np.mat(data_mat_In) label_mat = np.mat(class_label).transpose() # data_matrix = data_mat_In # label_mat = class_label # 初始化b，统计data_matrix的纬度 b = 0 m, n = np.shape(data_matrix) # 初始化alpha，设为0 alphas = np.mat(np.zeros((m, 1))) # 初始化迭代次数 iter_num = 0 # 最多迭代max_iter次 while iter_num < max_iter: alpha_pairs_changed = 0 for i in range(m): # 计算误差Ei fxi = float(np.multiply(alphas, label_mat).T*(data_matrix*data_matrix[i, :].T)) + b Ei = fxi - float(label_mat[i]) # 优化alpha，松弛向量 if (label_mat[i]*Ei < -toler and alphas[i] < C) or (label_mat[i]*Ei > toler and alphas[i] > 0): # 随机选取另一个与alpha_j成对优化的alpha_j j = select_j_rand(i, m) # 1.计算误差Ej fxj = float(np.multiply(alphas, label_mat).T*(data_matrix*data_matrix[j, :].T)) + b Ej = fxj - float(label_mat[j]) # 保存更新前的alpha，deepcopy alpha_i_old = copy.deepcopy(alphas[i]) alpha_j_old = copy.deepcopy(alphas[j]) # 2.计算上下界L和H if label_mat[i] != label_mat[j]: L = max(0, alphas[j] - alphas[i]) H = min(C, C + alphas[j] - alphas[i]) else: L = max(0, alphas[j] + alphas[i] - C) H = min(C, alphas[j] + alphas[i]) if L == H: print("L == H") continue # 3.计算eta eta = 2.0 * data_matrix[i, :]*data_matrix[j, :].T - data_matrix[i, :]*data_matrix[i, :].T - data_matrix[j, :]*data_matrix[j, :].T if eta >= 0: print("eta >= 0") continue # 4.更新alpha_j alphas[j] -= label_mat[j]*(Ei - Ej)/eta # 5.修剪alpha_j alphas[j] = clip_alptha(alphas[j], H, L) if abs(alphas[j] - alphas[i]) < 0.001: print("alpha_j变化太小") continue # 6.更新alpha_i alphas[i] += label_mat[j]*label_mat[i]*(alpha_j_old - alphas[j]) # 7.更新b_1和b_2 b_1 = b - Ei - label_mat[i]*(alphas[i] - alpha_i_old)*data_matrix[i, :]*data_matrix[i, :].T - label_mat[j]*(alphas[j] - alpha_j_old)*data_matrix[i, :]*data_matrix[j, :].T b_2 = b - Ej - label_mat[i]*(alphas[i] - alpha_i_old)*data_matrix[i, :]*data_matrix[j, :].T - label_mat[j]*(alphas[j] - alpha_j_old)*data_matrix[j, :] * data_matrix[j, :].T # 8.根据b_1和b_2更新b if 0 < alphas[i] and C > alphas[i]: b = b_1 elif 0 < alphas[j] and C > alphas[j]: b = b_2 else: b = (b_1 + b_2)/2 # 统计优化次数 alpha_pairs_changed += 1 # 打印统计信息 print("第%d次迭代 样本：%d , alpha优化次数：%d" % (iter_num, i, alpha_pairs_changed)) # 更新迭代次数 if alpha_pairs_changed == 0: iter_num += 1 else: iter_num = 0 print("迭代次数：%d" % iter_num) return b, alphas def caluelate_w(data_mat, label_mat, alphas): # 计算w alphas = np.array(alphas) data_mat = np.array(data_mat) label_mat = np.array(label_mat) # numpy.tile(A, reps):通过重复A给出的次数来构造数组。 # numpy中reshape函数的三种常见相关用法 # reshape(1, -1)转化成1行： # reshape(2, -1)转换成两行： # reshape(-1, 1)转换成1列： # reshape(-1, 2)转化成两列 w = np.dot((np.tile(label_mat.reshape(1, -1).T, (1, 5))*data_mat).T, alphas) return w.tolist() def prediction(test, w, b): test = np.mat(test) result = [] for i in test: if i*w+b > 0: result.append(1) else: result.append(-1) print(result) return result if __name__ == "__main__": test_set, category = loadDataset('titanic_test.csv') data_set, category = loadDataset('titanic_train.csv') test_mat, test_label = split_data(test_set) data_mat, label_mat = split_data(data_set) b, alphas = smo(data_mat, list(label_mat), 0.6, 0.001, 40) print(b) print(alphas) w = caluelate_w(data_mat, label_mat, alphas) print(w) print(test_mat) print(test_label) result = prediction(test_mat, w, b) count = 0 for i in range(len(result)): if result[i] == test_label[i]: count += 1 print(count) print(count/len(result))