标签 机器学习 下的文章

摘要

SVM是神经网络兴起之前最常用的机器学习分类器,本篇主要介绍SVM的具体实现,包括硬间隔/软间隔、合页损失函数。PPT参考https://www.bilibili.com/video/BV1zq4y1g74J/?spm_id_from=333.788&vd_source=6e11e901eb83e70a9bb55225ac28b9d9

SVM推导

SVM一般用于解决数据的二分类问题,对于高维数据,就是找到一个超平面将两类数据分开。以二维平面为例,就是找到一条直线作为分割线。

当然有时候我们无法找到理想直线将两类数据分离,这个时候就需要用到非线性SVM,通过核函数将数据点映射到高维空间,以期望在高维空间找到一个超平面分离数据。

image-20230709104533915

SVM的思想不仅是找到一个分割直线,它还希望这条直线离两类数据都尽可能远,也就是最大小下图中的$margin$。

image-20230709104825169

$margin(W,b)$与直线参数$W,b$有关,形式化表示可以写成:

$$ max \space margin(W,b)=max\mathop{min}\limits_{i=1,2,...N} \frac{1}{||W||_2}|W^TX^{(i)}+b| $$

$margin$的表达式为什么是直接将数据点$X^{(i)}$带入直线(高维数据时其实是超平面,但是为了描述方便之后都用直线方程替代)方程然后除以W的L2范数?推导如下,首先写出某个数据点到直线的距离方程,距离可以表达成W和数据点向量之间的点积除以W的模。假设$x^{(0)}$是平面上的一点(所以$W^TX^{(0)}+b=0$),那么距离H就可以表示为:

$$ \begin{aligned} H &= |\frac{W}{||W||_2}(X^{(i)}-X^{(0)})|\\ &= |\frac{1}{||W||_2}(W^TX^{(i)}-W^TX^{(0)})|\\ &= |\frac{1}{||W||_2}(W^TX^{(i)}+b)| \end{aligned} $$

image-20230709105549162

除了满足最大$margin$外,我们还希望这个超平面可以正确分割数据点,我们将数据点的标签标为1或-1,那么如果直线可以正确分类,那么满足以下两个条件:

image-20230709110437048

进一步将优化问题转变成以下条件:

image-20230709110531551

为了简化问题,我们将离直线最近的数据点$X^{(i)}$离直线的距离$|(W^TX^{(i)}+b)|$约束到1,那么优化问题就变成了下图,并且添加了一个约束条件。之所以可以这么优化,是因为对于原来的$margin$,$W,b$同时扩大N倍,都不会影响margin的结果,所以这里可以扩大(缩小)两者的值,使$|(W^TX^{(i)}+b)|$约束到1,从而简化问题

注意,这里的$X^{(i)}$是离直线最近的那个数据点,所以可以把$margin$的min脱掉

image-20230709110840827

合并约束条件得到以下优化条件:

image-20230709111411569

将max转换成min,得到:

image-20230709111525424

进一步写成矩阵相乘的形式,并通过拉格朗日乘子法优化,这里约束条件是不等式,满足KKT条件。数据点在边界上时$\lambda$不等于0,存在约束;如果不在边界上则不存在约束。具体可查阅KKT条件相关知识。

这里引入1/2不会影响结果,但是可以方便之后的求导运算

image-20230709111644213

对上图中的L求导,得到最优解。此时W可以表示为边界上各个数据点的线性组合,这些数据点$X^{(j)}$就被称为支持向量

image-20230709111852303

SVM的损失函数

我们回过头看SVM需要优化的那个拉格朗日函数,其实它和神经网络中的损失函数很像,第一项相当于W的L2正则化项,第二项则是”损失函数“。

image-20230709112110624

上述的SVM是硬间隔SVM,因为它的损失函数要求SVM直线对于每个数据点都分类正确,然而实际上会出现不可分的情况。那么这个时候就需要对优化函数进行修正,从而得到软间隔SVM。

image-20230709112358327

通过添加$\xi$,使约束条件放开。同时也将$\xi$的常数倍加入损失函数优化,从而尽可能找到一个小的间隔$\xi$。

image-20230709112419232

合并约束条件,我们可以得到以下结果。这个时候我们已经可以看到Hinge loss的身影了。

image-20230709113135754

把约束项合并到损失函数中,就可以得到软间隔SVM最终的损失函数形态。第一项是损失函数,第二项是W的正则化项。

image-20230709114151469

而第一项就是我们熟知的Hinge Loss,合页损失函数。

image-20230709114258657

背景

一般来说在训练时会将数据分为两部分,一部分用于训练,另一部分用于验证。这会引起以下几点问题:

  • 首先数据的切割是人为/随机的,不同切割可能会导致模型的不同精度。或者说人为切割的验证集有可能偏离了真实分布
  • 其次训练数据被分为两部分,验证集不参与训练,网络的数据来源缩水了,影响训练效果。虽然最后会将所有训练数据都丢入模型中来评估测试集,但是在这之前评估模型或者说模型调参还是只能使用一部分的训练数据

基本概念

K是一个指定的数字。执行K折交叉验证时,首先会将数据划分成(大致)相等的K个部分,每部分叫做一个。每次选取其中一个折作为验证集,由其他K-1个折作为训练集训练模型,训练好的模型用验证集评估正确性。

换句话说,K折交叉验证将会产生K个模型,最后得到的精度将是这K个模型精度的均值

交叉验证一般用于评估模型的泛化性能,也可以使用带交叉验证的网格搜索确定超参数

image-20230328104210900

优缺点

  • K折交叉验证的精度结果反映了模型对数据集中的所有样本都有较好的泛化性
  • 通过对数据的多次划分,提供了模型对于训练集选择的敏感性信息。即反映了数据在最好/最坏情况下模型的表现情况。
  • 交叉验证使数据使用更高效,K越大时,训练集的占比可以更大。更多的数据自然可以得到更精确的模型。

sklearn

from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
from sklearn.linear_model import LogisticRegression

iris = load_iris()
logreg = LogisticRegression(max_iter=1000)

scores = cross_val_score(logreg, iris.data, iris.target)
print("Cross-validation scores: {}".format(scores))

分层K折交叉验证 .etc

分层K折交叉验证

分层K折交叉验证保证了每个折中类别的比例和整个数据集中的相同。比如该数据集中90%的样本是A类,10%的样本是B类。那么K折中的每一折都是符合A占90%,B占10%。

分层K折避免这种情况发生:某一折里只包含A类的样本,导致验证精度很差,无法给出分类器的整体性能

随机K折交叉验证

为了避免标准K折交叉验证中折内类别比例异常的情况,还可以使用随机K折交叉验证。

kfold = KFold(n_splits=3, shuffle=True, random_state=0)
print("Cross-validation scores:\n{}".format(
    cross_val_score(logreg, iris.data, iris.target, cv=kfold))

留一法交叉验证

留一法可以看作是每折只有单个样本的K折交叉验证.

from sklearn.model_selection import LeaveOneOut
loo = LeaveOneOut()
scores = cross_val_score(logreg, iris.data, iris.target, cv=loo)
print("Number of cv iterations: ", len(scores))
print("Mean accuracy: {:.2f}".format(scores.mean()))

打乱划分交叉验证

每次划分为训练集采样train_size个点,为测试集(或者说验证集)采样test_size个点.将这种方法重复n_iter次.

image-20230328110830120

from sklearn.model_selection import ShuffleSplit
shuffle_split = ShuffleSplit(test_size=.5, train_size=.5, n_splits=10)
scores = cross_val_score(logreg, iris.data, iris.target, cv=shuffle_split)
print("Cross-validation scores:\n{}".format(scores))

打乱划分交叉验证允许在训练集和测试集大小之外指定迭代次数.也可以允许每次迭代仅使用部分数据.对于二次采样大型数据的试验比较有效.

分组交叉验证

有时候数据是分组的,比如每个人有多个数据.那么测试集中的数据最好是整组出现的,不应该出现测试集中某个人的数据出现在训练集中,这会影响对模型的泛化能力的评估.

image-20230328111504785

from sklearn.model_selection import GroupKFold
# create synthetic dataset
X, y = make_blobs(n_samples=12, random_state=0)
# assume the first three samples belong to the same group,
# then the next four, etc.
groups = [0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3]
scores = cross_val_score(logreg, X, y, groups=groups, cv=GroupKFold(n_splits=3))
print("Cross-validation scores:\n{}".format(scores))

基本概念

K折交叉验证用于评估一个模型的泛化性能,那么网格搜索通过调参来提高模型的泛化性能.

简单的网格搜索实现

提前划分好训练集和测试集,简单通过两个for循环寻找最佳参数,评估效果直接使用模型自带的score.

# naive grid search implementation
from sklearn.svm import SVC
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, random_state=0)
print("Size of training set: {}   size of test set: {}".format(
      X_train.shape[0], X_test.shape[0]))

best_score = 0

for gamma in [0.001, 0.01, 0.1, 1, 10, 100]:
    for C in [0.001, 0.01, 0.1, 1, 10, 100]:
        # for each combination of parameters, train an SVC
        svm = SVC(gamma=gamma, C=C)
        svm.fit(X_train, y_train)
        # evaluate the SVC on the test set
        score = svm.score(X_test, y_test)
        # if we got a better score, store the score and parameters
        if score > best_score:
            best_score = score
            best_parameters = {'C': C, 'gamma': gamma}

print("Best score: {:.2f}".format(best_score))
print("Best parameters: {}".format(best_parameters))

验证集的引进

上节实现的简单网格搜索存在一个致命问题:将用来调整参数的测试集用于评估模型的好坏!

换句话说,我们是在测试集上选择出来的最佳参数,整个参数不能保证对于新数据也work well.所以需要引入一组新数据.那么数据总共就被分为三份:

  • 用于训练模型的训练集
  • 用于调整超参数的验证集
  • 用于评估模型的测试集

测试集模型训练阶段从未见过,只在评估时使用.

验证集用来衡量训练集训练出来的模型好坏

最后评估时,模型会选择表现最好的超参,用训练集+验证集重新训练,再用测试集进行评估.这一步主要是充分利用验证集数据.

from sklearn.svm import SVC
# split data into train+validation set and test set
X_trainval, X_test, y_trainval, y_test = train_test_split(
    iris.data, iris.target, random_state=0)
# split train+validation set into training and validation sets
X_train, X_valid, y_train, y_valid = train_test_split(
    X_trainval, y_trainval, random_state=1)
print("Size of training set: {}   size of validation set: {}   size of test set:"
      " {}\n".format(X_train.shape[0], X_valid.shape[0], X_test.shape[0]))

best_score = 0

for gamma in [0.001, 0.01, 0.1, 1, 10, 100]:
    for C in [0.001, 0.01, 0.1, 1, 10, 100]:
        # for each combination of parameters, train an SVC
        svm = SVC(gamma=gamma, C=C)
        svm.fit(X_train, y_train)
        # evaluate the SVC on the validation set
        score = svm.score(X_valid, y_valid)
        # if we got a better score, store the score and parameters
        if score > best_score:
            best_score = score
            best_parameters = {'C': C, 'gamma': gamma}

# rebuild a model on the combined training and validation set,
# and evaluate it on the test set
svm = SVC(**best_parameters)
svm.fit(X_trainval, y_trainval)
test_score = svm.score(X_test, y_test)
print("Best score on validation set: {:.2f}".format(best_score))
print("Best parameters: ", best_parameters)
print("Test set score with best parameters: {:.2f}".format(test_score))

带交叉验证的网格搜索

上一节中人为分出了测试集\训练集\验证集,这钟方法对于数据的划分也比较敏感.因此可以在划分训练集/验证集时使用交叉验证,更好的评估模型的泛化能力.

for gamma in [0.001, 0.01, 0.1, 1, 10, 100]:
    for C in [0.001, 0.01, 0.1, 1, 10, 100]:
        # for each combination of parameters,
        # train an SVC
        svm = SVC(gamma=gamma, C=C)
        # perform cross-validation
        scores = cross_val_score(svm, X_trainval, y_trainval, cv=5)
        # compute mean cross-validation accuracy
        score = np.mean(scores)
        # if we got a better score, store the score and parameters
        if score > best_score:
            best_score = score
            best_parameters = {'C': C, 'gamma': gamma}
# rebuild a model on the combined training and validation set
svm = SVC(**best_parameters)
svm.fit(X_trainval, y_trainval)

image-20230328113803191

GridSearchCV 热图可视化

from sklearn.model_selection import GridSearchCV
from sklearn.svm import SVC
param_grid = {'C': [0.001, 0.01, 0.1, 1, 10, 100],
              'gamma': [0.001, 0.01, 0.1, 1, 10, 100]}
grid_search = GridSearchCV(SVC(), param_grid, cv=5,
                          return_train_score=True)
                          
X_train, X_test, y_train, y_test = train_test_split(
    iris.data, iris.target, random_state=0)
grid_search.fit(X_train, y_train)

scores = np.array(results.mean_test_score).reshape(6, 6)

# plot the mean cross-validation scores
mglearn.tools.heatmap(scores, xlabel='gamma', xticklabels=param_grid['gamma'],
                      ylabel='C', yticklabels=param_grid['C'], cmap="viridis")

image-20230328114043350

不同的交叉验证策略

嵌套交叉验证

在交叉验证的网格搜索中,我们使用交叉验证来完成训练集/验证集的划分,测试集的划分我们还是手动的.嵌套交叉验证让我们测试集的划分也使用交叉验证.这会使结果更合理,当然需要训练模型的个数也upup~(比如36个模型超参数组合,嵌套交叉验证都是5折,那就需要训练900个模型)

param_grid = {'C': [0.001, 0.01, 0.1, 1, 10, 100],
              'gamma': [0.001, 0.01, 0.1, 1, 10, 100]}
scores = cross_val_score(GridSearchCV(SVC(), param_grid, cv=5),
                         iris.data, iris.target, cv=5)
print("Cross-validation scores: ", scores)
print("Mean cross-validation score: ", scores.mean())

聚类概念

  • 属于无监督学习(无标签)
  • 顾名思义,就是将相似的东西分到一组
  • 难点在于如何评估聚类效果以及调整参数

基本概念

  • K代表最后需要得到的簇个数(比如二分类K=2)
  • 一个簇的质心计算:采用均值,即每个特征向量取平均值
  • 距离度量:经常使用欧几里得距离余弦相似度(高维特征最好先执行一次标准化)
  • 优化目标:实现$min\sum_{i=1}^{k}\sum_{x∈C_i}dist(C_i,x)^2$

优缺点

优点:

  • 算法简单、快速
  • 适合常规数据集(就是一坨一坨的那种,没有特定形状)

缺点:

  • K值难以确定(一般是遍历K值取Inertia的拐点)
  • 算法复杂度与样本呈线性关系(一次迭代)
  • 很难发现任意形状的簇,比如二维特征的样本,一个圆环套一个球的形状KMeans就很难检测出来。

image-20230327102339790

算法流程

  • 首先随机选取K个样本作为K个簇的中心(在KMeans++中,使用最大距离进行初始化)

    • KMeans++逐个选取K个簇中心,且离其它簇中心越远的样本点越有可能被选为下一个簇中心
  • 将每个样本分配到K个簇中,具体选择哪个簇取决于该样本和K个簇的距离,选择距离最近的簇(分配样本)
  • 此时所有样本都分配到对应的簇,在每个簇中更新簇中心。新的簇中心采用简单的均值计算(更新簇中心)
  • 回到第二步再次分配样本,直到达到迭代次数上限损失指标小于某个阈值(损失指标有inertia/轮廓系数)

KMeans代码实现

import numpy as np
class KMeans:
    def __init__(self,data,num_clusters):
        self.data = data
        self.num_clusters = num_clusters
        
    def train(self,max_iterations):
        # 1.choose k centers
        centroids = KMeans.centroids_init(self.data,self.num_clusters)
        # 2.begin train
        num_examples = self.data.shape[0]
        closest_centroids_ids = np.empty((num_examples,1))
        for _ in range(max_iterations):
            # 3.get closest center id
            closest_centroids_ids = KMeans.centroids_find_closest(self.data,centroids)
            # 4.update k centers
            centroids = KMeans.centroids_compute(self.data,closest_centroids_ids,self.num_clusters)
        return centroids,closest_centroids_ids
    
    @staticmethod
    def centroids_init(self,data,num_clusters):
        num_examples = data.shape[0]
        random_ids = np.random.permutation(num_examples)
        centroids = data[random_ids[:num_clusters],:]
        return centroids
    
    @staticmethod
    def centroids_find_closest(self,data,entroids):
        num_examples = data.shape[0]
        num_centroids = centroids.shape[0]
        closest_centroids_ids = np.zeros((num_examlpes,1))
        for example_index in range(num_examples):
            distance = np.zeros(num_centroids,1)
            for centroid_index in range(num_centroids):
                distance_diff = data[example_index,:] - centroids[centroid_index,:]
                distance[centroid_index] = np.sum(distance_diff**2)
            closest_centroids_ids[example_index] = np.argmin(distance)
        return closest_centroids_ids
    
    @staticmethod
    def centroids_compute(self.data,closest_centroids_ids,self.num_clusters):
        num_features = data.shape[1]
        centroids = np.zeros((num_clusters,num_features))
        for centroid_id in range(num_clusters):
            closest_ids = closest_centroids_ids == centroid_id
            centroids[centroid_ids] = np.mean(data[closest_ids.flatten(),:],axis=0)
        return centroids

sklearn

接下来介绍sklearn库中的KMeans实现.

文档见sklearn.cluster.KMeans — scikit-learn 1.2.2 documentation

Attributes

image-20230327110345259

__init__

  • n_clusters : 簇个数K
  • random_state : 随机数种子
  • init : K个簇中心的初始化方式
  • n_init : 算法执行次数,取结果最好的一次
  • max_iter : 单次算法迭代次数(分配簇/更新簇)
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=2,random_state=0,init='k-means++',n_init=10,max_iter=300)

fit

kmeans.fit(X) # input X
kmeans.cluster_centers_ # center coordinate
kmeans.label_ # every sample's label
kmeans.inertia # loss

pred

kmeans.predict(New_X)
kmeans.label_

tranform

Transform(): Method using these calculated parameters apply the transformation to a particular dataset.

返回值shape : (num_examples,num_clusters) 即每个样本和每个类的距离 通过这个方法也可以得到predict结果(argmin)

from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
sc.fit_tranform(X_train)
sc.tranform(X_test) # 一定是tranform 保证train和test使用同一个转化标准

可视化

# draw cluster points
def plot_data(feature,snr,label):
    df = pd.DataFrame(dict(x=snr, y=feature, color=label))
    fig, ax = plt.subplots()
    colors = {0:'red', 1:'blue'}
    ax.scatter(df['x'], df['y'], c=df['color'].apply(lambda x: colors[x]))
    plt.show()

# draw cluster centers
def plot_centriods(snr,centroids,weights=None,circle_color='g',cross_color='k'):
    if weights is not None:
        centroids = centroids[weights>weights.max()/10]
    plt.scatter(snr,centroids[:],
               marker='o',s=30,linewidths=8,
               color=circle_color,zorder=10,alpha=0.9)
    plt.scatter(snr,centroids[:],
               marker='x',s=50,linewidths=50,
               color=circle_color,zorder=11,alpha=1)

评估指标

inertia指标

inertia : 每个样本距离质心的距离

score方法的结果是inertia的负值(绝对值越大分数越小)

kmeans.inertia_
X_dist = kmeans.transform(X)
np.sum(X_dist[np.arange(len(X_dist)),kmeans.labels_]**2) # inertia计算
kmeans.score(X) == -1*kmeans.inertia_

轮廓系数

某个样本的轮廓系数定义为:

$$ s = \frac {disMean_{out} - disMean_{in}}{max(disMean_{out}-disMean_{in})} $$

其中$disMean_{in}$为该点与本类其他点的平均距离,$disMean_{out}$为该点与非本类点的平均距离。该值取值范围为[−1,1], 越接近1则说明分类越优秀。在sklearn中函数 silhouette_score() 计算所有点的平均轮廓系数,而silhouette_samples()返回每个点的轮廓系数。

K值选取(拐点法)

kmeans_per_k = [KMeans(n_clusters=k).fit(X) for k in range(1,10)]
inertias = [model.inertia_ for model in kmeans_per_k]
# draw fig
plt.figure(figsize=(8,4))
plt.plot(range(1,10),inertias,'bo-')
plt.show()

image-20230327114805748

半监督学习

KMeans也可以用于半监督学习

比如在一个少样本训练场景下,相比于随机选取50个训练样本打标加入训练这种方式,可以先使用聚类挑出50个簇中心,每个簇选取一个样本作为典型样本;用这些样本打标训练,最后测试出来的acc会更高。除此之外,还可以通过标签传播(同一个簇内的标签一致)的方式扩大训练集。