摘要：我們將它稱作異端審判。除了全部分類方案以外，我們同時維護(hù)另一個列表，記錄被移動的元素，以便于撤回。

上文鏈接：異端審判器！一個泛用型文本聚類模型的實(shí)現(xiàn)(1)

上回，我們提出了一種只要輸入一堆字符串，就能根據(jù)字符串的構(gòu)造挑揀出“少數(shù)派”，以識別異常參數(shù)的構(gòu)想。我們將它稱作“異端審判”。

前文中我們已經(jīng)定義好了一些必要概念，并寫出了函數(shù)實(shí)現(xiàn)。我們的程序遞進(jìn)地量化了字符之間的差異、字符串之間的差異，最終得到了字符串集合之間的差異。有了這項(xiàng)指標(biāo)，我們就能完成分揀工作。

在生活中，我們常有幾排人一起合影的經(jīng)歷。有時是前排蹲下后排站立，有時是矮個子站在前排高個子位居后排。不妨假想一下，如果你就是那位攝影師，正指揮大家列隊(duì)，你習(xí)慣于怎樣安排隊(duì)形呢？

通常情況下，你會直接要求站成大致均勻的兩排，再逐個調(diào)整細(xì)節(jié)，直到整個隊(duì)形看上去令人滿意。

這為我們識別“異端”提供了靈感。

想象一位“主教”威立于尖塔的陽臺，望著城樓下的人群，現(xiàn)在他要做的就是將人分成兩類，一類大致可信，一類有些可疑，再逐個把后者中的信眾移進(jìn)前者，“異端”自然被剩下。

這篇文章中，我們就是要實(shí)現(xiàn)這樣一件事。

我們先將每個輸入都視作多帶帶的一類，以啟動整個流程。整個全集記作 C。

# 初始化
# 輸入一個列表，如["a","b","c"]
# 輸出一個把每個元素都封裝為列表的列表，如[["a"],["b"],["c"]]
def init(sample_list):
    C = []
    for x in sample_list:
        C.append([x])
    return C

基于此前定義的字符串集間距離（在文章中簡稱為類間距離），選擇最接近的兩類，合并它們。

這步操作聽上去很簡單，實(shí)際上確實(shí)也很簡單，但我們會遇到一些麻煩：我們一直使用列表來簡單表示集合這個數(shù)學(xué)概念，它們性質(zhì)并不相同。集合的三個主要特性中，列表不滿足無序性與互異性，因此需要一些額外的處理。

例如，找到最接近的兩類，無論如何我們也需要計(jì)算出 n^2 個距離，這就不是一件輕松的事。我們將最小距離記作d——

def find_min(C):
    # 邏輯告訴我們無論怎樣做都必須計(jì)算兩兩之間的全部距離，這里用一個二維列表來記錄
    # 數(shù)學(xué)告訴我們 a->b 與 b->a 的距離是一樣的，其實(shí)開銷可以減小一半
    # 作者告訴大家由于我很懶，就不做這個優(yōu)化了……
    scale = len(C)
    d = [[0 for i in range(scale)] for i in range(scale)]
    min_d = classesDistanse(C[0], C[1])
    where_min_d = [0, 1]
    for i in range(scale):
        for j in range(scale):
            d[i][j] = classesDistanse(C[i], C[j])
            if i != j and d[i][j] < min_d:
                min_d = d[i][j]
                where_min_d = [i, j]
    return where_min_d

找到了最小的 d 以后，就該合并它們了。在進(jìn)行并運(yùn)算時，我們就會遇到列表與集合的性質(zhì)差異、邏輯與運(yùn)算的表示差異等問題，我們重新定義運(yùn)算函數(shù)來彌補(bǔ)這些偏差。

如果這部分讓你有點(diǎn)眩暈，不要為此擔(dān)心。你可以將它們都視作 dirty hack，記住我們只是在做一件簡單的事情：將剛才已經(jīng)找到的類間距離最小的兩個集合，合并成一個。

# C:=C-Ci-Cj+CiUCj
# 輸入全集列表C及其選出的兩個子列表Ci、Cj，如C=[["a"],["b"],["c"]]，Ci=["a"], Cj=["b"]
# 需要注意的是，邏輯上，集合Ci與集合Cj是集合C的【元素】，而交并差都是【集合】之間的運(yùn)算
# 輸出合并Ci與Cj之后的全集列表，如[[["a"],["b"]],["c"]]
def merge(C, i, j):
    # 在數(shù)學(xué)上，集合[[1],[2]]與集合[[1,2]]的并集有三個元素，因?yàn)閇1],[2],[1,2]都是完全不同的元素。但在這里的邏輯上，需要結(jié)果為[[1,2]]，所以另外定義了特殊的“交集”運(yùn)算
    # 交集與差集的運(yùn)算是針對集合的（如[[1]]）而非元素（如[1])，所以需要手動裝進(jìn)列表再傳參。（其實(shí)已經(jīng)特殊處理的交集運(yùn)算無必要這樣做，但為了邏輯一致遵守了統(tǒng)一的寫法）
    C_u = special_union([C[i]], [C[j]])
    C_d = difference(difference(C, [C[i]]), [C[j]])
    C_n = C_d
    C_n.append(C_u)
    return C_n

我們將最接近的兩類合并成一類了，而目標(biāo)是“一刀切”，即把整個全集劃分為大致均勻的兩類。所以我們不斷查找最接近的兩類，將其合并，直到有某個集合的總量超過全集的一半。

# 查找規(guī)模最大的一個子列表
# 輸入全集C，如[[["a"],["b"]],["c"]]
# 輸出規(guī)模最大即集合內(nèi)元素最多的列表的下標(biāo)，如 0
def find_largest(C):
    s = [0] * len(C)
    max_s = len(C[0])
    where_max_s = 0
    for x in range(len(C)):
        s[x] = len(C[x])
        if s[x] > max_s:
            max_s = s[x]
            where_max_s = x
    return where_max_s

每個步驟都已經(jīng)定義就緒，整個操作流程是這樣的：

def layerClassification(sample_list):
    C = init(sample_list)
    while True:
        where_min_d = find_min(C)
        i, j = where_min_d
        C = merge(C, i, j)
        where_max_s = find_largest(C)
        if count_elem(C[where_max_s]) > 0.5 * len(C):
            break
    CM = C[where_max_s]
    CN = difference(C, [CM])
    return flatten(CM), flatten(CN)

這段代碼中提到了兩個輔助函數(shù)，其中 count_elem() 用于遞歸遍歷每個集合中實(shí)際包含的字符串個數(shù)（而非子元素個數(shù)），分類的最終結(jié)果可能出現(xiàn)復(fù)雜的多維列表，而我們只需要兩個簡單的一維列表用于表示兩個集合，定義 flatten() 來展開嵌套。

經(jīng)過了剛才的分類，現(xiàn)在我們有了兩個集合。其中的一個包含了原本聚類性比較明顯的元素，他們可能長相非常近似，剩下一半只是單純被剩下了而已，風(fēng)馬牛齊聚一堂，看上去亂糟糟的。

接下來就是“微調(diào)”時間啦，我們要從那個泥沙俱下的集合中，把“信眾”逐個移動到前面那個相對齊整的集合里，從而將“異端”孤立。

這件事的關(guān)鍵是何時停止：移到哪一步時，那個混亂的集合恰好只?！爱惗恕?，而又沒有“異端”錯誤地赦免呢？

好在我們的主教無需落子無悔，移錯了就倒回去嘛。他甚至可以命人把所有結(jié)果都羅列出來，由他來判斷哪一個方案是最好的。

那我們不妨先不考慮決策的事情，提供全部方案就好。

我們將分類方案記作 S，一個分類方案由兩個集合構(gòu)成，即{C1, C2}，同樣地，我們使用列表來表示。為了在不斷移動的過程中，存儲每一時刻的 C1 與 C2，而不作為引用跟隨變化，我們需要使用深拷貝。

def note_solution(S, C1, C2, N):
    _C1 = copy.deepcopy(C1)
    _C2 = copy.deepcopy(C2)
    S.append([_C1, _C2])
    N = N + 1
    return S

基于此前定義的類間距離，我們能夠選到 C2 中最接近 C1 的樣本：

def select_min(C1, C2):
    min_x = C2[0]
    min_d = classesDistance(C1, min_x)
    for x in C2:
        temp = classesDistance(C1, x)
        if temp < min_d:
            min_d = temp
            min_x = x
    return min_x

把這個樣本從 C2 中放進(jìn) C1：

def update(min_x, C1, C2):
    C1.append(min_x)
    C2.remove(min_x)
    return [C1, C2]

我們不斷搬運(yùn)元素，直到那個沒有聚類性的 C2 被搬空。記錄下這個過程中所有分類方案。除了全部分類方案 S 以外，我們同時維護(hù)另一個列表，記錄被移動的元素，以便于撤回。由于這個列表里所有元素都是我們每一步選出的到 C1 距離最小元素，不妨就將這個列表稱作 M，整個過程如下：

def iterateClassification(C):
    N = 0
    S = []
    M = []
    C1 = C[0]
    C2 = C[1]
    while True:
        note_solution(S, C1, C2, N)
        min_x = select_min(C1, C2)
        M.append(min_x)
        update(min_x, C1, C2)
        if len(C2) == 0:
            break
    del(S[0])
    return S, M

到這里為止，我們反復(fù)運(yùn)用上篇文章中定義的類間距離，做了一次粗選，又列出了所有微調(diào)生成的方案。最佳方案必然就是其中之一，留給我們大主教的，只剩一個優(yōu)化問題。

讓我們下回再見～

編者按：

本文未完待續(xù)，敬請期待后續(xù)推送。參考文獻(xiàn)及整理后的示例代碼將在完整文章末給出。

文 / YvesX
反正你也猜不出我是做什么的
編 / 熒聲

本文由創(chuàng)宇前端作者授權(quán)發(fā)布，版權(quán)屬于作者，創(chuàng)宇前端出品。 歡迎注明出處轉(zhuǎn)載本文。文章鏈接：https://www.yvesx.com/archive...

想要訂閱更多來自知道創(chuàng)宇開發(fā)一線的分享，請搜索關(guān)注我們的微信公眾號：創(chuàng)宇前端（KnownsecFED）。歡迎留言討論，我們會盡可能回復(fù)。

歡迎點(diǎn)贊、收藏、留言評論、轉(zhuǎn)發(fā)分享和打賞支持我們。打賞將被完全轉(zhuǎn)交給文章作者。

感謝您的閱讀。