基于隨機數三角陣映射的高維大數據二分聚類初始中心高效魯棒生成算法

李 旻 何婷婷

①(華中師范大學國家數字化學習工程技術研究中心 武漢 430079)

②(河南大學計算機與信息工程學院 開封 475001)

1 引言

Bisecting K-means是一種十分經典的聚類算法[1,2]，由于該算法優點眾多[3,4]，廣泛應用于各種聚類場景[5-7]，且成為各種聚類算法對比的標桿之一[8,9]。然而，該算法也存在局部最優收斂問題，即以不同的兩個樣本作為初始中心來分割簇，最終得到的“最優聚類模式”可能各不相同[10-12]。為了減輕局部最優收斂的不良影響，最常用的方法是嘗試用多個不同的初始中心對來分割簇，以得到多個局部最優聚類模式，然后從中選取質量最好的聚類模式作為最終聚類結果[13-15]。因此，Bisecting K-means算法首要解決的問題便是：如何從待分割簇中，生成一組符合要求的初始中心對。目前，常用的隨機采樣初始中心生成方法包括兩大類：基于樣本索引采樣的方法、基于樣本特征采樣的方法。其中，第1類方法的處理過程與樣本特征無關，第2類方法的處理過程與樣本特征相關，故此基于樣本索引采樣的方法更適合于處理高維度大數據。在基于樣本索引采樣的方法中，常用的有以下幾種。

(1)隨機選取方法：從待分割簇中，隨機選取兩個不同樣本作為初始中心對[14,16]。該方法優點：簡單；缺點：多次生成的初始中心對可能有重復。選定初始中心對后，因后續進行的二分聚類操作復雜度較大，特別是對于高維大數據而言。所以應避免重復的初始中心對，以防后續做無謂的大復雜度計算。

(2)隨機選取+單點排除方法：選取初始中心對時，把之前曾被選為初始中心的單個樣本點排除在備選范圍之外。該方法優點：簡單、多次生成的初始中心對無重復；缺點：存在缺失值問題(即排除掉從未嘗試過的初始中心對)[17]。

(3)隨機選取+碰撞檢測方法：從待分隔簇中，隨機選取2個不同樣本，構成待用初始中心對，然后檢測其是否已被生成過(即碰撞檢測)。若已生成過(即發生碰撞)，則重復生成操作，直至“無碰撞”[1,3]。該方法優點：無重復、無缺失值問題；缺點：碰撞檢測效率低、隨機碰撞造成時間效率不穩定。

由以上分析可知，現有的隨機采樣初始中心生成方法存在著各種問題，難以勝任大數據聚類場景。有鑒于此，本文提出了基于隨機數三角陣映射的二分聚類初始中心生成方法。

2 隨機數三角陣映射方法

2.1 初始中心索引對集合

待分割簇中兩個不同樣本的索引構成一個樣本索引對，所有不重復對構成的集合便是該待分割簇的初始中心索引對集合(the set of Pairs of Indexes of two Initial centers in the Cluster, PIIC)。其對應于待分割簇的初始中心對池，定義如下

PIIC={ (i, j) | i, j∈Z, 1≤i

i, j為待分割簇中的初始中心索引；

C*為待分割簇。

2.2 初始中心對組合三角陣

若待分割簇有n個樣本，可用下三角矩陣將所有可選初始中心對的組合都表示出來，該矩陣稱為初始中心對組合三角陣(the lower Triangular Matrix composed by the Pairs of initial centers,TMP)，其具體形式如圖1所示。

對于TMP中的任意元素e，其行編號row(e)為第1個初始中心的索引i，其元素大小e為第2個初始中心的索引j，即二元組(row(e), e)與唯一的初始中心對(Si, Sj)相對應(其中i=row(e), j=e)。由此可知，TMP中的元素與PIIC中的元素可構成一對一映射，該映射定義為

(1) TMP中元素位置到元素大小的映射。

觀察圖1可知，TMP中元素位置到元素大小可構成一對一映射，該映射定義為

f : PTMP→ETMP;

PTMP={ (x, y) | x, y∈Z, 1≤x, y≤n-1, x+y≤n, n=|C*| };

e=f (x, y)=x+y;

PTMP: TMP中元素位置的集合；

x=row(e) : TMP中元素的行編號；

y=column(e) : TMP中元素的列編號。

(2) TMP中“元素位置”到“初始中心索引對”的映射。

由映射f : PTMP→ETMP和映射f : ETMP→PIIC，可得由TMP中元素位置到PIIC中初始中心索引對的映射，該映射定義為

圖1 初始中心對組合三角陣TMP

由此可知：隨機生成初始中心對的操作，可轉換為從TMP中隨機選取元素的操作。然而，直接從TMP中隨機選取元素，無法保證每次生成的初始中心對均不重復，為此還需借助于另一個矩 陣。

2.3 初始中心對編號三角陣

若待分割簇有n個樣本，將所有可選初始中心對從1至n(n-1)/2進行編號，然后將這些編號按升序排列成下三角矩陣，便得到初始中心對編號三角陣(the lower Triangular Matrix composed by Serial numbers of the pairs of initial centers,TMS)，其具體形式如圖2所示。

TMS中的每個編號都與TMP中相應位置元素所確定的唯一初始中心對相對應。如TMS中第1行第1列的元素1，對應于TMP中第n-1行第1列的元素n，故TMS中的“元素1”對應的初始中心對為(Sn-1, Sn)。由此可知，TMS中的元素與初始中心對存在映射關系，下面推導該映射。

(1)TMS到TMP的元素位置映射。

觀察兩矩陣的結構可知，其對應元素的位置滿足以下映射關系：

PTMS: TMS中元素位置的集合。

(2) TMS中元素位置到元素大小的映射。

觀察TMS的結構可知，其元素位置到元素大小滿足以下映射：

f : PTMS→ETMS;

ETMS={ e | e∈TMS };

e=f (x, y)=(x2-x)/2+y.

(3) TMS中元素大小到元素位置的映射。

證明：TMS中，任意元素e的行號

圖2 初始中心對編號三角陣TMS

2.4 初始中心對編號三角陣到初始中心索引對集合的映射

對上述映射進行整理匯總，可用圖3表示出從TMS到PIIC的整個映射過程。

由映射f1至f4，可得從TMS到PIIC的映射，推導為

設(i, j)∈PIIC, e∈ETMS，則有

由此可得

f : ETMS→PIIC;

圖3 數據集映射過程匯總

2.5 基于隨機數三角陣映射的初始中心生成算法

由映射f : ETMS→PIIC可得基于隨機數三角陣映射的初始中心生成算法，其步驟如圖4所示。

在圖4所示的算法步驟中：n為待分割簇所含樣本數；m為初始中心對生成數量；randint([1,N], m)表示從[1, N]中“不放回”抽樣m個整數；集合PIIC*保存生成好的初始中心索引對。

3 隨機數三角陣映射算法的復雜度分析

目前共討論了4種初始中心隨機生成算法，其中隨機選取生成的初始中心對可能有重復；隨機選取+單點排除會漏掉從未嘗試過的初始中心對；隨機選取+碰撞檢測(簡稱隨機樣本碰撞檢測)和隨機數三角陣映射算法均不存在上述兩種缺陷，故只對這兩種算法進行復雜度分析。

(1) 時間復雜度：隨機數三角陣映射算法的步驟、運算與時耗情況如圖4所示。其中，T(·)為運算和操作的計時函數；RSN為從N個數中不放回抽樣操作；MA為內存訪問操作。

根據圖4所示，統計算法各步驟中所含運算和操作的時間，可知算法所需時耗約為

由此可得算法時間復雜度為O(T(A))=O(m)。

(2) 空間復雜度：算法需維護兩個數據結構R和PIIC*: R為隨機整數的集合，可包含m個整數，故其所需存儲空間為M(R)=mM(Int)(M(·)為存儲空間占用量統計函數；Int為整型數據)；PIIC*為隨機初始中心索引對集合，最多包含m個整數二元組，故其所需存儲空間為M(PIIC*)=2mM(Int)。

圖4 隨機數三角陣映射算法的步驟、運算與時耗分析

故此，算法所需存儲空間約為M(A)≈3m M(Int)，空間復雜度為O(M(A))=O(m)。

4 隨機樣本碰撞檢測算法的復雜度分析

(1) 時間復雜度：隨機樣本碰撞檢測算法的步驟、運算與時耗情況如圖5所示。

假設在生成m個初始中心對的過程中，共發生了K次碰撞，則算法各層循環次數為

第1層循環總次數：sum(|L1|)=m；

第2層循環總次數：sum(|L2|)=K+m；

第3層平均循環總次數：sum(|L3|)=m(m-1)/2+(m+1)K/3。

據此統計圖5中算法各步驟操作所需時間，可得K次碰撞情況下算法的近似時耗為

由此可得算法時間復雜度為O(A)=O(T(A))=O(m2+mK)。

(2) 空間復雜度：算法在執行時，需維護一個數據結構PIIC*。故此，算法所需存儲空間約為M(A)≈2mM(Int)，空間復雜度為：O(M(A))=O(m)。

總結以上分析結論，可得算法復雜度對比情況如表1所示。

其中，Ob, Ow, Oa分別表示最優、最差、平均復雜度；N=|PIIC|。

5 實驗

實驗所用評估指標有平均時耗和時耗標準差，即測定算法完成指定初始中心生成任務的運行時間，然后統計多次相同實驗所需時耗的平均值及標準差。其中平均時耗用于評估算法的時間效率，時耗標準差用于評估算法的時間效率穩定性。實驗用計算機基本配置如下：CPU為Intel core i7 3 GHz；內存為8 GB；操作系統為Windows 7；算法實現語言為Python 2.7。實驗分為兩部分：第1部分仿真實驗，用于驗證本文算法時間復雜度理論分析的正確性；第2部分高維數據集實驗，用于驗證本文算法對高維大數據處理的適用性。

5.1 仿真實驗

影響隨機數三角陣映射算法性能的因素有兩個：數據集所含樣本數、初始中心對生成數。故驗證該算法的時間復雜度分析結論，只需仿真實驗即可。實驗舉例：當數據集樣本數n=4時，因可用初始中心對總數N=6，則依次統計算法生成1～6個初始中心對時的各項評估指標。下文將隨機樣本碰撞檢測算法稱為算法1(簡寫為A1)，將隨機數三角陣映射算法稱為算法2(簡寫為A2)。

5.1.1 時間效率實驗

(1)實驗結果：當3≤n≤10時，對算法1和算法2的平均時耗進行測試，其實驗結果如圖6和圖7所示。

圖5 隨機樣本碰撞檢測算法的步驟、運算與時耗分析

表1 算法復雜度對比

圖6 算法平均時耗分步對比

在圖6中，將n取不同值時的平均時耗分開繪制，以便于觀察當數據集容量相同而初始中心生成數量不同時的算法時耗對比；圖7中，將n取不同值時的平均時耗變化情況繪制在一起，以便于觀察當數據集容量不同而初始中心生成數量相同時的算法時耗對比。

(2) 實驗結果分析：觀察圖6和圖7可知：隨著初始中心對生成數量的增多，算法1的平均時耗加速增長，算法2的平均時耗約呈線性增長；待分割簇的樣本數越多，算法1生成相同數量初始中心對的平均時耗越小。以上實驗結果與算法時間復雜度分析結論相一致。

圖7 算法平均時耗疊加對比

5.1.2 時間效率穩定性實驗

(1) 實驗結果：當3≤n≤10時，對算法1和算法2的時耗標準差進行測試，其實驗結果如圖8和圖9所示。

(2) 實驗結果分析：觀察圖8和圖9可知：隨著初始中心對生成數量的增多，算法1的時耗標準差隨之總體增大，算法2的時耗標準差基本不變；待分割簇的樣本數越多，算法1生成相同數量初始中心對的時耗標準差總體越小。以上實驗結果與算法時間復雜度分析結論相一致。

5.2 高維數據集實驗

參與對比測試的算法有：本文隨機數三角陣映射算法(the algorithm based on Random integer Triangular Matrix Mappings, RTMM)、隨機樣本碰撞檢測算法(the algorithm based on Random Sample Collision Detection, RSCD)、特征域均勻采樣算法[18](the algorithm based on Feature Range Uniform Sampling, FRUS；當前最流行的基于樣本特征采樣的算法)。實驗引入3個著名高維數據集：20NEWS[19], IMDB[20], MNIST[21]，用于驗證本文算法在高維大數據處理領域的優越性。其中，20NEWS數據集保存的是網絡新聞文本，經數據清洗、特征提取等格式化處理后得到1.8×104個樣本，每個樣本有173451個特征；IMDB數據集保存的是電影評論文本，經處理得到2×104個樣本、73063個特征；MNIST數據集保存的是手寫數字點陣圖像，經處理得到1×104個樣本、784個特征。

圖8 算法時耗標準差分步對比

圖9 算法“時耗標準差”疊加對比

(1) 實驗結果

測試生成不同數量初始中心對時，算法的運行時耗變化情況，其結果如圖10-圖12所示。

測試算法在生成大規模初始中心對(1.8×105個)時的運行時耗，其結果如表2所示。

(2) 實驗結果分析

(a) 數據集維度規模對算法性能的影響：處理20NEWS數據集(約1.7×105維)時，RTMM相較于FRUS算法的效率優勢最明顯；處理IMDB數據集(約7×104維)時，效率優勢沒有在20NEWS數據集上明顯；處理MNIST數據集(約7×102維)時，兩算法的效率基本相當。以上實驗結果表明：數據集維度規模對FRUS算法性能的影響顯著，而對RTMM和RSCD算法沒有影響；數據集維度越高，FRUS算法的效率越低，RTMM算法的效率優勢越明顯。

(b) 初始中心生成規模對算法性能的影響：隨著初始中心生成數量的增加，RSCD算法的運行時耗加速增長，FRUS算法運行時耗約呈線性增長，RTMM算法運行時耗幾乎不變。以上實驗結果表明：初始中心生成規模對RSCD算法的性能影響最顯著，對FRUS算法性能影響次之，對RTMM算法性能影響甚微；初始中心生成數量越多，RSCD和FRUS算法的效率越低，RTMM算法相較于兩算法的效率優勢越明顯。

總結本文實驗與分析結果，可得以下結論：FRUS算法更適合于低維數據集上小規模初始中心生成任務；RSCD算法更適合于高維數據集上小規模初始中心生成任務；RTMM算法更適合于高維數據集上大規模初始中心生成任務。

表2 大規模初始中心生成任務下的算法時耗對比

圖10 20NEWS數據集上算法運行時耗

圖11 IMDB數據集上算法運行時耗

圖12 MNIST數據集上算法運行時耗

6 結束語

本文首先創建出初始中心對組合三角陣和初始中心對編號三角陣，然后通過建立兩矩陣中元素及元素位置間的若干映射，從而提出了一種新的二分聚類初始中心生成方法。理論分析與實驗結果均表明：隨著初始中心對生成數量的增多，新方法的平均時耗近似于線性增長，且其時耗標準差非常穩定、近似于零。新方法的時間效率及穩定性明顯優于常用的隨機采樣方法，且隨著數據集維度規模和初始中心生成規模的增大，其高效性與魯棒性的優勢將更加明顯。故此，本文方法特別適用于高維大數據聚類場景。