13.1 未标记样本

• 有标记样本
  有训练集D_l={(x₁,y₁),(x₂,y₂),…,(x_l,y_l)}，这l个样本的类别标记已知，即"有标记样本"。如田地里，老农拿来一箩筐瓜(D_l)，说这三四个是好瓜、这五六个是坏瓜，这些瓜都是有标记的。
• 未标记样本
  有D_u={x_l+1,x_l+2,……,x_l+u}，l＜u，这u个样本没有标记，称为"未标记样本"。除了箩筐里的瓜有标记外，田地里其他的瓜(D_u)是没有标记的。

田地里未标记的瓜很多，即未标记样本很多，就造成浪费。我们要想方法把这u个未标记样本利用起来。有主动学习和半监督学习两种方法：

• 主动学习
  先用D_l训练一个模型，拿这个模型去地里挑一个瓜，询问瓜农好不好，然后把这个新获得的有标记样本加入D_l中重新训练一个模型，再去挑瓜。这样，若每次都挑出对改善模型性能帮助大的瓜，则只需询问瓜农比较少的瓜就能构建出比较强的模型，从而大幅降低标记成本。这种学习方法就是"主动学习"，目的是以尽量少的"查询"次数来获取尽量好的性能。可以看出，主动学习需要通过与外界的专家进行交互才能获取标记信息，我们也可以用半监督学习(不与外界交互)来获取。

• 半监督学习
  未标记样本虽然没有直接包含标记信息，但如果它们与有标记样本是从同样的数据源独立同分布采样而来，则它们所包含的关于数据分布的信息对建立模型有很大的益处。

  
  若只有一个正例和反例，由于待判别样本恰位于两者正中间，只能随机猜测；若能观察到未标记样本，则很有把握判别为正例。

  让学习器不依赖外界交互、自动地利用未标记样本来提升学习性能，就是半监督学习。

  基本假设
  要利用未标记样本，必然要做一些将未标记样本所揭示的数据分布信息与类别标记相联系的假设。
  ① 聚类假设：假设数据存在簇结构，同一个簇的样本属于同一个类别。
  ② 流形假设：假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值。"邻近" 程度常用"相似"程度来刻画。

  半监督学习包括：
  1）纯半监督学习
  假定训练数据中的未标记样本并非待预测的数据。基于"开放世界"
  假设，希望学得模型能适用于训练过程未观察到的数据。
  2）直推学习
  假定学习过程中所考虑的未标记样本恰是待预测数据。基于"封闭世界"假设，仅试图对学习过程中观察到的未标记数据进行预测。

13.2 生成式方法

生成式方法是基于生成式模型的方法。其假设所有样本(不论有标记与否)是由同一个潜在模型“生成”的，未标记的可看做模型的缺失参数，通常可用EM算法进行极大似然估计求解。
前面已经接触到的贝叶斯分类器与高斯混合聚类，都属于生成式模型。

给定样本x，其真实类别标记为y∈Y，Y={1,2,3,…,N}是所有可能的类别。假设样本由高斯混合模型生成，且每个类别对应一个高斯分布，即样本基于以下概率密度生成：

给定有标记样本集D_l={(x₁,y₁),(x₂,y₂),…,(x_l,y_l)}和未标记样本集D_u={x_l+1,x_l+2,…,x_l+u}，l+u=m，m个样本独立同分布，由同个高斯混合模型生成。用极大似然来估计高斯混合模型中每个高斯分布的三个参数α_i、u_i、Σ_i，D_l∪D_u的对数似然为

• 基于EM算法的半监督学习用于贝叶斯方法对20个新闻文本进行分类
  
  流程图
  由于代码冗长，所以只显示结果。
  20个新闻在sklearn下datasets中的fetch_20newsgroups，分类之前先对这个20个新闻进行词云处理，看看每个新闻的主要词。
  20个新闻的主要词
  然后经过半监督学习分类后，获得9个类别
  分类后的wordcloud

这是GitHub上的源代码
https://github.com/jerry-shijieli/Text_Classification_Using_EM_And_Semisupervied_Learning

13.3 半监督SVM

不考虑未标记样本，SVM只试图找到有标记样本的最大间隔划分超平面。而在考虑未标记样本后，SVM变成了半监督SVM(S3VM)，它试图找到将两类有标记样本分开，且穿过数据低密度区域的划分超平面。

• TSVM
  给定有标记样本集D_l={(x₁,y₁),(x₂,y₂),…,(x_l,y_l)}，y_i取-1或+1；未标记样本集D_u={x_l+1,x_l+2,…,x_l+u}，l+u=m。TSVM的目标是为D_u进行标记指派，D中的样本给出标记y^ =(y^ _l+1,y^ _l+2,…,y^ _l+u)，y^_i取+1或-1，使得
  
  TSVM采用局部搜索来迭代求得上式的近似解。
  具体来说：
  1）先用有标记样本集D_l训练一个SVM；
  2）用SVM对未标记样本的进行预测，将结果作为未标记样本的标记；
  3）将得到的y^代入到上式中，得到标准SVM问题，再求解出新的划分超平面和松弛变量。由于伪标记样本可能不正确，因此设置C_u＜C_l，使有标记样本所起作用更大。
  在未标记样本的伪标记中，找出两个伪标记相反的且很可能错误的未标记样本，将它们的标记对换，然后用所有样本重新训练SVM，得到新的划分超平面和松弛变量；
  4）标记指派调整完成后，逐渐增大C_u以提高未标记样本对优化目标的影响，进行下一轮标记指派调整
  5）重复2）、3）、4）直到到达停止条件C_u=C_I为止；
  6）此时，在未标记数据的基础上获得了一个SVM分类器，即未标记样本进行了标记，还能用来对未见的样本进行预测。

标准算法流程如下

• TSVM代码实现

import random
import numpy as np
import sklearn.svm as svm
from sklearn.datasets.samples_generator import make_classification
from sklearn.externals import joblib
import warnings; warnings.filterwarnings(action='ignore')

class TSVM(object):
    def __init__(self, kernel='linear'):
        self.Cl, self.Cu = 1.5, 0.001
        self.kernel = kernel
        self.clf = svm.SVC(C=1.5, kernel=self.kernel)

    def train(self, X1, Y1, X2):
        N = len(X1) + len(X2)
        # 样本权值初始化
        sample_weight = np.ones(N)
        sample_weight[len(X1):] = self.Cu

        # 用已标注部分训练出一个初始SVM
        self.clf.fit(X1, Y1)
        
        # 对未标记样本进行标记
        Y2 = self.clf.predict(X2)
        Y2 = Y2.reshape(-1,1)
        
        X = np.vstack([X1, X2])
        Y = np.vstack([Y1, Y2])
        
        # 未标记样本的序号
        Y2_id = np.arange(len(X2))
        
        while self.Cu < self.Cl:
            # 重新训练SVM, 之后再寻找易出错样本不断调整
            self.clf.fit(X, Y, sample_weight=sample_weight)
            while True:
                Y2_decision = self.clf.decision_function(X2)   # 参数实例到决策超平面的距离
                Y2 = Y2.reshape(-1)
                epsilon = 1 - Y2 * Y2_decision
                negative_max_id = Y2_id[epsilon==min(epsilon)]

                print(epsilon[negative_max_id][0])
                if epsilon[negative_max_id][0] > 0:
                    # 寻找很可能错误的未标记样本，改变它的标记成其他标记
                    pool = list(set(np.unique(Y1))-set(Y2[negative_max_id]))
                    Y2[negative_max_id] = random.choice(pool)
                    Y2 = Y2.reshape(-1, 1)
                    Y = np.vstack([Y1, Y2])
                    
                    self.clf.fit(X, Y, sample_weight=sample_weight)
                else:
                    break
            self.Cu = min(2*self.Cu, self.Cl)
            sample_weight[len(X1):] = self.Cu

    def score(self, X, Y):
        return self.clf.score(X, Y)

    def predict(self, X):
        return self.clf.predict(X)

    def save(self, path='./TSVM.model'):
        joblib.dump(self.clf, path)

    def load(self, model_path='./TSVM.model'):
        self.clf = joblib.load(model_path)

if __name__ == '__main__':
    features, labels = make_classification(n_samples=200, n_features=3, n_redundant=1, n_repeated=0, n_informative=2, n_clusters_per_class=2)
    n_given = 70
    # 取前n_given个数字作为标注集
    X1 = np.copy(features)[:n_given]
    X2 = np.copy(features)[n_given:]
    Y1 = np.array(np.copy(labels)[:n_given]).reshape(-1,1)
    Y2_labeled = np.array(np.copy(labels)[n_given:]).reshape(-1,1)

    model = TSVM()
    model.train(X1, Y1, X2)

    # Y2_hat = model.predict(X2)
    accuracy = model.score(X2, Y2_labeled)
    print(accuracy)

代码链接：https://www.jianshu.com/p/bc9b3803018b

13.4 图半监督学习

我们可以将一个数据集映射为一个图。每个样本对应于一个结点；两个样本之间的相似度对应于一条边。在该数据集中，有标记样本所对应的结点是有颜色的，而未标记样本是无色的。于是，半监督学习就相当于"颜色"在途中进行传播的过程，即标记传播的过程。

给定有标记样本集D_l={(x₁,y₁),(x₂,y₂),…,(x_l,y_l)}；未标记样本集D_u={x_l+1,x_l+2,…,x_l+u}，l+u=m。对所有样本(D_l∪D_u)构建一个图G(V,E)，V为结点集={x₁,…,x_l,…,x_l+u}，E为边集，可表示为一个亲和矩阵，为

image.png

• 二分类标记传播
  假设图G将学得一个实值函数f，其分类规则是y∈{-1,+1}。定义关于f的"能量函数"

  具有最小能量的函数f在有标记样本上满足f(x_i)=y_i(i=1,2,…,l)；
  在未标记样本上满足Δf=0，其中Δ=D-W为拉普拉斯矩阵。以第l行和第l列为界，用分块矩阵表示D和W
  因此，可以将E(f)重写为
  对f_u求偏导令其为0，得到
  再令P=D^-1W，即
  则有P_uu=D^-1_uuW_uu，P_ul=D^-1_uuW_ul，则f_u可以重写为
  于是，将D_l上的标记信息f_l=(y₁;y₂;…;y_l)代入f_u，再利用求得的f_u对未标记样本进行预测。

• 多分类标记传播
  基于D_l∪D_u构建一个图G=(V,E)，点集V、边集E对应的W、对角矩阵D与上相同。假定y_i∈Y，定义一个(l+u) x |Y|的非负标记矩阵F=(F₁^T,F₂^T,…,F_l+u^T)^T，F的第i行元素F_i=((F)_i1,(F)_i2,…,(F)_i|Y|)为样本x的标记，分类规则为：

  F矩阵
  基于W构造一个标记传播矩阵S=D^-½WD^-½
  基于上式迭代直至收敛得到
  由F* 可获得D_u中的样本标记(y^ _l+1,y^ _l+2,…,y^_l+u)。算法流程如下

LPA

• LPA代码实现

import time  
import numpy as np  
  
# return k neighbors index  
def navie_knn(dataSet, query, k):  
    numSamples = dataSet.shape[0]  
  
    ## step 1: calculate Euclidean distance  
    diff = np.tile(query, (numSamples, 1)) - dataSet  
    squaredDiff = diff ** 2  
    squaredDist = np.sum(squaredDiff, axis = 1) # sum is performed by row  
  
    ## step 2: sort the distance  
    sortedDistIndices = np.argsort(squaredDist)  
    if k > len(sortedDistIndices):  
        k = len(sortedDistIndices)  
  
    return sortedDistIndices[0:k]  
  
  
# build a big graph (normalized weight matrix)  
def buildGraph(MatX, kernel_type, rbf_sigma = None, knn_num_neighbors = None):  
    num_samples = MatX.shape[0]  
    affinity_matrix = np.zeros((num_samples, num_samples), np.float32)  
    if kernel_type == 'rbf':  
        if rbf_sigma == None:  
            raise ValueError('You should input a sigma of rbf kernel!')  
        for i in xrange(num_samples):  
            row_sum = 0.0  
            for j in xrange(num_samples):  
                diff = MatX[i, :] - MatX[j, :]  
                affinity_matrix[i][j] = np.exp(sum(diff**2) / (-2.0 * rbf_sigma**2))  
                row_sum += affinity_matrix[i][j]  
            affinity_matrix[i][:] /= row_sum  
    elif kernel_type == 'knn':  
        if knn_num_neighbors == None:  
            raise ValueError('You should input a k of knn kernel!')  
        for i in xrange(num_samples):  
            k_neighbors = navie_knn(MatX, MatX[i, :], knn_num_neighbors)  
            affinity_matrix[i][k_neighbors] = 1.0 / knn_num_neighbors  
    else:  
        raise NameError('Not support kernel type! You can use knn or rbf!')  
      
    return affinity_matrix  
  
  
# label propagation  
def labelPropagation(Mat_Label, Mat_Unlabel, labels, kernel_type = 'rbf', rbf_sigma = 1.5, \  
                    knn_num_neighbors = 10, max_iter = 500, tol = 1e-3):  
    # initialize  
    num_label_samples = Mat_Label.shape[0]  
    num_unlabel_samples = Mat_Unlabel.shape[0]  
    num_samples = num_label_samples + num_unlabel_samples  
    labels_list = np.unique(labels)  
    num_classes = len(labels_list)  
      
    MatX = np.vstack((Mat_Label, Mat_Unlabel))  
    clamp_data_label = np.zeros((num_label_samples, num_classes), np.float32)  
    for i in xrange(num_label_samples):  
        clamp_data_label[i][labels[i]] = 1.0  
      
    label_function = np.zeros((num_samples, num_classes), np.float32)  
    label_function[0 : num_label_samples] = clamp_data_label  
    label_function[num_label_samples : num_samples] = -1  
      
    # graph construction  
    affinity_matrix = buildGraph(MatX, kernel_type, rbf_sigma, knn_num_neighbors)  
      
    # start to propagation  
    iter = 0; pre_label_function = np.zeros((num_samples, num_classes), np.float32)  
    changed = np.abs(pre_label_function - label_function).sum()  
    while iter < max_iter and changed > tol:  
        if iter % 1 == 0:  
            print "---> Iteration %d/%d, changed: %f" % (iter, max_iter, changed)  
        pre_label_function = label_function  
        iter += 1  
          
        # propagation  
        label_function = np.dot(affinity_matrix, label_function)  
          
        # clamp  
        label_function[0 : num_label_samples] = clamp_data_label  
          
        # check converge  
        changed = np.abs(pre_label_function - label_function).sum()  
      
    # get terminate label of unlabeled data  
    unlabel_data_labels = np.zeros(num_unlabel_samples)  
    for i in xrange(num_unlabel_samples):  
        unlabel_data_labels[i] = np.argmax(label_function[i+num_label_samples])  
      
    return unlabel_data_labels 

代码链接以及测试
https://blog.csdn.net/zouxy09/article/details/49105265

13.5 基于分歧的方法

基于分歧的方法使用多学习器，而学习器之间的“分歧”对未标记数据的利用至关重要。其代表是协同训练，针对多视图数据。

• 视图
  一个数据对象往往同时具有多个"属性集"，每个属性集就构成了一个"视图"。
  如，一个人往往具有多面性格。再如一部电影，拥有多个属性集：图像画面信息所对应的属性集、声音信息所对应的属性集。
  每个属性集就是一个视图。只考虑图像和声音的视图，那么一个电影片段可以表示为样本(<x¹,x²>,y)，xⁱ是样本在视图i中的示例，即基于该视图属性描述而得到的属性向量。
  x¹是图像视图中的属性向量，x²是声音视图中的属性向量。y是标记，如电影类型，"动作片"、"爱情片"。(<x¹,x²>,y)就是多视图数据。
  视图有以下两个特点：
  1）相容性
  使用单个视图数据训练出的学习器的输出空间是一致的。
  如y¹表示通过图像信息判别的标记空间，y²表示通过声音信息判别的标记空间，则y¹=y²=y，如都是y={爱情片,动作片}。
  2）互补性
  不同视图所提供的信息是相辅相成的。
  如仅仅依靠图像视图信息(两人对视的画面)难以判断电影类型，但辅之声音视图信息("我爱你")，则可以电影类型很可能是"爱情片"。

• 协同训练
  协同训练假设数据拥有两个充分且条件独立视图。
  充分：指每个视图包含足以产生最优学习器的信息。
  条件独立：指在给定类别标记条件下两个视图独立。

  协同训练在此假设下，用以下简单的方法利用未标记样本：
  1）首先在每个视图上基于有标记样本都训练一个初始分类器；
  2）然后让每个分类器去挑选分类置信度最高的未标记样本并预测赋予伪标记
  3）将带有伪标记的样本数据传给另一个分类器去作为新增的有标记样本用于训练更新；
  4）重复2）3）直到两个学习器不再变化或达到预设的迭代次数时停止

  若在每轮学习中都考察分类器在所有未标记样本上的分类置信度，会有很大的计算开销，因此在算法中使用了未标记样本缓冲区。分类置信度的估计则因基学习算法而异，例如若使用朴素贝叶斯分类器，则可将后验概率转化为分类置信度；若使用支持向量机，则可将间隔大小转化为分类置信度。

• 算法流程

13.6 半监督聚类

聚类是一种无监督学习，然而我们可以利用一些监督信息来辅助聚类学习，获得更好的效果。
半监督聚类则是借助已有的监督信息来辅助聚类的过程。
一般而言，监督信息大致有两种类型：
1）"必连"约束与"勿连"约束
"必连"约束指样本必属于同一簇类；"勿连"约束指样本必不属于同一簇类。
2）少量的有标记样本

下面主要介绍两种基于半监督的K-Means聚类算法：
第一种是数据集包含一些必连与勿连关系；
第二种则是包含少量带有标记的样本。

• 约束k-均值算法
  给定样本集D={x₁,x₂,…,x_m}；
  "必连"关系集合M，(x_i,x_j)∈M表示x_i与x_j必属于同簇；
  "勿连"关系集合N，(x_i,x_j)∈N表示x_i与x_j必不属于同簇。

  思路如下：
  1）首先初始化k个簇，随机选择 k 个样本作为 k 个簇的初始均值向量；
  2）然后，不断迭代以下步骤
  ① 对每个样本 x ，计算其与每个簇均值向量的距离 d；
  ② 找出距离样本 x 最近的簇 i ，判断将 x 放进 i 是否违反“约束”：
  如果不违反，则将簇 i 作为 x 的簇标记，并将 x 放入该簇集合 Ci 中；
  如果违反，则找次近的簇，以此类推直到找到满足约束的最近簇 i'，将x 放入该簇集合 Ci' 中；
  ③ 对所有的簇集合，根据本次迭代得到的簇集合计算新的均值向量；
  ④ 当均值向量均未更新时，退出迭代步骤；
  3）最终，我们获得了聚类计算的结果簇划分

  算法流程如下

  约束k-均值算法
  
  举例
  以西瓜数据集4.0为例
  有约束如下
  设聚类簇数k=3，随机选取样本x₆，x₁₂，x₂₇为初始均值向量，有
  4轮迭代的结果
  聚类结果为

• 约束种子k-均值算法
  数据集D中包含少量有标记样本，记为S，其中S_j为属于第j个簇的样本。将这些样本作为"种子"，用有标记样本进行k个聚类中心的指定，同时在对样本进行划分更新时，不需要改变这些有标记样本的簇隶属关系。算法流程如下所示：
  
  举例
  以上面西瓜数据集为例，假设作为种子的有标记样本为
  以这三组种子样本的平均向量作为初始均值向量，经过3轮迭代后，第4轮与第3轮一样，故停止，得到结果为
  
  算法实现代码

# -*- coding: utf-8 -*-
import numpy as np

def distEclud(vecA, vecB):
    '''
    输入：向量A和B
    输出：A和B间的欧式距离
    '''
    return np.sqrt(sum(np.power(vecA - vecB, 2)))
 
def newCent(L):
    '''
    输入：有标签数据集L
    输出：根据L确定初始聚类中心
    '''
    centroids = []
    label_list = np.unique(L[:,-1])
    for i in label_list:
        L_i = L[(L[:,-1])==i]
        cent_i = np.mean(L_i,0)
        centroids.append(cent_i[:-1])
    return np.array(centroids) 

def semi_kMeans(L, U, distMeas=distEclud, initial_centriod=newCent):
    '''
    输入：有标签数据集L（最后一列为类别标签）、无标签数据集U（无类别标签）
    输出：聚类结果
    '''
    dataSet = np.vstack((L[:,:-1],U))#合并L和U
    label_list = np.unique(L[:,-1])
    k = len(label_list)           #L中类别个数
    m = np.shape(dataSet)[0]
    
    clusterAssment = np.zeros(m)#初始化样本的分配                             
    centroids = initial_centriod(L)#确定初始聚类中心
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):#将每个样本分配给最近的聚类中心
            minDist = np.inf; minIndex = -1
            for j in range(k):
                distJI = distMeas(centroids[j,:],dataSet[i,:])
                if distJI < minDist:
                    minDist = distJI; minIndex = j
            if clusterAssment[i] != minIndex: clusterChanged = True
            clusterAssment[i] = minIndex
    return clusterAssment  
    
L =np.array([[1.0, 4.2 ,1],
    [1.3, 4.0 , 1],
    [1.0, 4.0 , 1],
    [1.5, 4.3 , 1],
    [2.0, 4.0 , 0],
    [2.3, 3.7 , 0],
    [4.0, 1.0 , 0]])
 #L的最后一列是类别标签   
U =np.array([[1.4, 5.0],
    [1.3, 5.4],
    [2.0, 5.0],
    [4.0, 2.0],
    [5.0, 1.0],
    [5.0, 2.0]])

clusterResult = semi_kMeans(L,U)

代码链接：https://blog.csdn.net/tyh70537/article/details/80483654

思维导图(简易)