李 旻 何婷婷

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

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

1 引言

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

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

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

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

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

2 隨機數(shù)三角陣映射方法

2.1 初始中心索引對集合

待分割簇中兩個不同樣本的索引構(gòu)成一個樣本索引對，所有不重復對構(gòu)成的集合便是該待分割簇的初始中心索引對集合(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中的元素可構(gòu)成一對一映射，該映射定義為

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

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

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

由此可知：隨機生成初始中心對的操作，可轉(zhuǎn)換為從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的元素位置映射。

觀察兩矩陣的結(jié)構(gòu)可知，其對應元素的位置滿足以下映射關系：

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

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

觀察TMS的結(jié)構(gòu)可知，其元素位置到元素大小滿足以下映射：

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 數(shù)據(jù)集映射過程匯總

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

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

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

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

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

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

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

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

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

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

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

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

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

假設在生成m個初始中心對的過程中，共發(fā)生了K次碰撞，則算法各層循環(huán)次數(shù)為

第1層循環(huán)總次數(shù)：sum(|L1|)=m；

第2層循環(huán)總次數(shù)：sum(|L2|)=K+m；

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

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

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

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

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

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

5 實驗

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

5.1 仿真實驗

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

5.1.1 時間效率實驗

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

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

表1 算法復雜度對比

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

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

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

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

5.1.2 時間效率穩(wěn)定性實驗

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

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

5.2 高維數(shù)據(jù)集實驗

參與對比測試的算法有：本文隨機數(shù)三角陣映射算法(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個著名高維數(shù)據(jù)集：20NEWS[19], IMDB[20], MNIST[21]，用于驗證本文算法在高維大數(shù)據(jù)處理領域的優(yōu)越性。其中，20NEWS數(shù)據(jù)集保存的是網(wǎng)絡新聞文本，經(jīng)數(shù)據(jù)清洗、特征提取等格式化處理后得到1.8×104個樣本，每個樣本有173451個特征；IMDB數(shù)據(jù)集保存的是電影評論文本，經(jīng)處理得到2×104個樣本、73063個特征；MNIST數(shù)據(jù)集保存的是手寫數(shù)字點陣圖像，經(jīng)處理得到1×104個樣本、784個特征。

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

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

(1) 實驗結(jié)果

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

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

(2) 實驗結(jié)果分析

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

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

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

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

圖10 20NEWS數(shù)據(jù)集上算法運行時耗

圖11 IMDB數(shù)據(jù)集上算法運行時耗

圖12 MNIST數(shù)據(jù)集上算法運行時耗

6 結(jié)束語

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