【機器學習基礎】半監(jiān)督算法概覽(Python)
前言
前階段時間梳理了機器學習開發(fā)實戰(zhàn)的系列文章：
現(xiàn)階段的寫作計劃會對各類機器學習算法做一系列的原理概述及實踐，主要包括無監(jiān)督聚類、異常檢測、半監(jiān)督算法、強化學習、集成學習等。
一、機器學習簡介
機器學習按照數(shù)據(jù)的標簽情況可以細分為：監(jiān)督學習，無監(jiān)督學習，半監(jiān)督學習以及強化學習。
監(jiān)督學習是利用數(shù)據(jù)特征及其標簽 D ＝｛（ｘ１，ｙ１），…，（ｘｌ，ｙｌ）｝學習輸入到輸出的映射ｆ：Ｘ→Ｙ的方法。
無監(jiān)督學習是僅利用無類標簽的樣本數(shù)據(jù)特征 D＝｛ｘ１，…，ｘｎ｝學習其對應的簇標簽、特征表示等方法。
強化學習從某種程度可以看作是有延遲標簽信息的監(jiān)督學習。
半監(jiān)督學習是介于傳統(tǒng)監(jiān)督學習和無監(jiān)督學習之間，其思想是在標記樣本數(shù)量較少的情況下，通過在模型訓練中直接引入無標記樣本，以充分捕捉數(shù)據(jù)整體潛在分布，以改善如傳統(tǒng)無監(jiān)督學習過程盲目性、監(jiān)督學習在訓練樣本不足導致的學習效果不佳的問題。
半監(jiān)督學習的有效性通常基于如下假設：1）平滑假設：稠密數(shù)據(jù)區(qū)域的兩個距離很近的樣例的類標簽相似。2）聚類假設：當兩個樣例位于同一聚類簇時，很大的概率下有相同的類標簽。3）流形假設：高維數(shù)據(jù)嵌入到低維流形中，當兩個樣例位于低維流形中的一個小局部鄰域內時，具有相似的類標簽。當模型假設不正確時，無標簽的樣本可能無法有效地提供增益信息，反而會惡化學習性能。
二、半監(jiān)督算法的類別
2.1 按理論差異劃分
按照統(tǒng)計學習理論差異，半監(jiān)督學習可以分為：(純)歸納半監(jiān)督學習和直推學習。
直推學習只處理樣本空間內給定的訓練數(shù)據(jù)，利用訓練數(shù)據(jù)中有類標簽的樣本和無類標簽的樣例進行訓練，僅預測訓練數(shù)據(jù)中無類標簽的樣例的類標簽，典型如標簽傳播算法(LPA)。
歸納半監(jiān)督學習處理整個樣本空間中所有給定和未知的樣例，不僅預測訓練數(shù)據(jù)中無類標簽的樣例的類標簽，更主要的是預測未知的測試樣例的類標簽，典型如半監(jiān)督SVM。
2.2 按學習場景劃分
從不同的學習場景看，半監(jiān)督學習可分為四類：半監(jiān)督分類（Semi-supervised classification）、半監(jiān)督回歸（Semi-supervised regression）、半監(jiān)督聚類（Semi-supervised clustering）及半監(jiān)督降維（Semi-supervised dimensionality reduction）。
半監(jiān)督分類 半監(jiān)督分類算法的思想是通過大量的未標記樣本幫助學習一個好的分類系統(tǒng)，代表算法可以劃分為四類，包括生成式方法、判別式方法、半監(jiān)督圖算法和基于差異的半監(jiān)督方法(此外還可擴展出半監(jiān)督深度學習方法，限于篇幅本文沒有展開)。結合現(xiàn)實情況多數(shù)為半監(jiān)督分類場景，下節(jié)會針對半監(jiān)督分類算法原理及實戰(zhàn)進行展開。
半監(jiān)督聚類 半監(jiān)督聚類算法的思想是如何利用先驗信息以更好地指導未標記樣本的劃分過程。現(xiàn)有的算法多數(shù)是在傳統(tǒng)聚類算法基礎上引入監(jiān)督信息發(fā)展而來，基于不同的聚類算法可以將其擴展成不同的半監(jiān)督聚類算法。
半監(jiān)督回歸 半監(jiān)督回歸算法的思想是通過引入大量的未標記樣本改進監(jiān)督學習方法的性能，訓練得到性能更優(yōu)的回歸器?，F(xiàn)有的方法可以歸納為基于協(xié)同訓練(差異)的半監(jiān)督回歸和基于流形的半監(jiān)督回歸兩類。
半監(jiān)督降維 半監(jiān)督降維算法的思想在大量的無類標簽的樣例中引入少量的有類標簽的樣本，利用監(jiān)督信息找到高維數(shù)據(jù)的低維結構表示，同時保持數(shù)據(jù)的內在固有信息。而利用的監(jiān)督信息既可以是樣例的類標簽，也可以是成對約束信息，還可以是其他形式的監(jiān)督信息。主要的半監(jiān)督降維方法有基于類標簽的方法、基于成對約束等方法。
三、半監(jiān)督分類算法(Python)
3.1 基于差異的方法
基于差異的半監(jiān)督學習起源于協(xié)同訓練算法，其思想是利用多個擬合良好的學習器之間的差異性提高泛化能力。假設每個樣本可以從不同的角度（view）訓練出不同的分類器，然后用這些從不同角度訓練出來的分類器對無標簽樣本進行分類，再選出認為可信的無標簽樣本加入訓練集中。
3.2 判別式方法
判別式方法利用最大間隔算法同時訓練有類標簽的樣本和無類標簽的樣例學習決策邊界，使其通過低密度數(shù)據(jù)區(qū)域，并且使學習得到的分類超平面到最近的樣例的距離間隔最大。常見的如直推式支持向量機（TSVM）及最近鄰（KNN）等。
TSVM采用局部搜索的策略來進行迭代求解，即首先使用有標記樣本集訓練出一個初始SVM，接著使用該學習器對未標記樣本進行打標，這樣所有樣本都有了標記，并基于這些有標記的樣本重新訓練SVM，之后再尋找易出錯樣本不斷調整。
import random
import numpy as np
import sklearn.svm as svm
from sklearn.datasets import make_classification
class TSVM(object):
'''
半監(jiān)督TSVM
'''
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) # 參數(shù)實例到決策超平面的距離
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)
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個數(shù)字作為標注集
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)
accuracy = model.score(X2, Y2_labeled)
print(accuracy)
3.3 生成式方法
生成式的模型有高斯模型、貝葉斯網絡、樸素貝葉斯、隱馬爾可夫模型等，方法關鍵在于對來自各個種類的樣本分布進行假設以及對所假設模型的參數(shù)估計。首先通過假設已知樣本數(shù)據(jù)的密度函數(shù) p(x|yi)的形式，比如多項式、高斯分布等。接著可采用迭代算法(如 EM 算法)計算 p(x|yi)的參數(shù)，然后根據(jù)貝葉斯全概率公式對全部未標簽樣本數(shù)據(jù)進行分類。
生成式方法可以直接關注半監(jiān)督學習和決策中的條件概率問題，避免對邊緣概率或聯(lián)合概率的建模以及求解，然而該方法對一些假設條件比較苛刻，一旦假設的 p(x|yi)與樣本數(shù)據(jù)的實際分布情況差距比較大，其分類效果往往不佳。
3.4 基于圖半監(jiān)督學習方法
基于圖的方法的實質是標簽傳播，基于流形假設根據(jù)樣例之間的幾何結構構造邊（邊的權值可以用樣本間的相近程度），用圖的結點表示樣例，利用圖上的鄰接關系將類標簽從有類標簽的樣本向無類標簽的樣例傳播?；趫D的方法通常圖計算復雜度較高，且對異常圖結構缺乏魯棒性，主要方法有最小分割方法、標簽傳播算法（LPA）和流形方法 (manifold method)等。
標簽傳播算法（LPA）是基于圖的半監(jiān)督學習算法，基本思路是從已標記的節(jié)點標簽信息來預測未標記的節(jié)點標簽信息。
1、首先利用樣本間的關系（可以是樣本客觀關系，或者利用相似度函數(shù)計算樣本間的關系）建立完全圖模型。
2、接著向圖中加入已標記的標簽信息，無標簽節(jié)點是在用一個唯一的標簽初始化。
3、該算法會重復地將一個節(jié)點的標簽設置為該節(jié)點的相鄰節(jié)點中出現(xiàn)頻率最高(有權圖需要考慮權重)的標簽，重復迭代，直到標簽不變算法收斂。
import random
import networkx as nx
import matplotlib.pyplot as plt
class LPA():
'''
標簽傳播算法：傳播標簽來劃分社區(qū)
算法終止條件：迭代次數(shù)超過設定值
self.G：圖
return：None
'''
def __init__(self, G, iters=10):
self.iters = iters
self.G = G
def train(self):
max_iter_num = 0 # 迭代次數(shù)
while max_iter_num < self.iters:
max_iter_num += 1
print('迭代次數(shù)',max_iter_num)
for node in self.G:
count = {} # 記錄鄰居節(jié)點及其標簽
for nbr in self.G.neighbors(node): # node的鄰居節(jié)點
label = self.G.node[nbr]['labels']
count[label] = count.setdefault(label,0) + 1
# 找到出現(xiàn)次數(shù)最多的標簽
count_items = sorted(count.items(),key=lambda x:-x[-1])
best_labels = [k for k,v in count_items if v == count_items[0][1]]
# 當多個標簽頻次相同時隨機選取一個標簽
label = random.sample(best_labels,1)[0]
self.G.node[node]['labels'] = label # 更新標簽
def draw_picture(self):
# 畫圖
node_color = [float(self.G.node[v]['labels']) for v in self.G]
pos = nx.spring_layout(self.G) # 節(jié)點的布局為spring型
plt.figure(figsize = (8,6)) # 圖片大小
nx.draw_networkx(self.G,pos=pos,node_color=node_color)
plt.show()
if __name__ == "__main__":
G = nx.karate_club_graph() # 空手道
# 給節(jié)點添加標簽
for node in G:
G.add_node(node, labels = node) # 用labels的狀態(tài)
model = LPA(G)
# 原始節(jié)點標簽
model.draw_picture()
model.train()
com = set([G.node[node]['labels'] for node in G])
print('社區(qū)數(shù)量',len(com))
# LPA節(jié)點標簽
model.draw_picture()
文章首發(fā)于算法進階，公眾號閱讀原文可訪問GitHub項目源碼
往期精彩回顧
本站qq群851320808，加入微信群請掃碼：