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

李 旻 何婷婷

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

②(河南大學(xué)計(jì)算機(jī)與信息工程學(xué)院 開封 475001)

1 引言

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

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

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

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

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

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

2.1 初始中心索引對(duì)集合

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

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

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

C*為待分割簇。

2.2 初始中心對(duì)組合三角陣

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

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

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

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

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中元素的行編號(hào)；

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

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

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

圖1 初始中心對(duì)組合三角陣TMP

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

2.3 初始中心對(duì)編號(hào)三角陣

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

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

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

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

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的行號(hào)

圖2 初始中心對(duì)編號(hào)三角陣TMS

2.4 初始中心對(duì)編號(hào)三角陣到初始中心索引對(duì)集合的映射

對(duì)上述映射進(jìn)行整理匯總，可用圖3表示出從TMS到PIIC的整個(gè)映射過程。

由映射f1至f4，可得從TMS到PIIC的映射，推導(dǎo)為

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

由此可得

f : ETMS→PIIC;

圖3 數(shù)據(jù)集映射過程匯總

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

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

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

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

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

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

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

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

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

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

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

4 隨機(jī)樣本碰撞檢測(cè)算法的復(fù)雜度分析

(1) 時(shí)間復(fù)雜度：隨機(jī)樣本碰撞檢測(cè)算法的步驟、運(yùn)算與時(shí)耗情況如圖5所示。

假設(shè)在生成m個(gè)初始中心對(duì)的過程中，共發(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)計(jì)圖5中算法各步驟操作所需時(shí)間，可得K次碰撞情況下算法的近似時(shí)耗為

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

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

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

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

5 實(shí)驗(yàn)

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

5.1 仿真實(shí)驗(yàn)

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

5.1.1 時(shí)間效率實(shí)驗(yàn)

(1)實(shí)驗(yàn)結(jié)果：當(dāng)3≤n≤10時(shí)，對(duì)算法1和算法2的平均時(shí)耗進(jìn)行測(cè)試，其實(shí)驗(yàn)結(jié)果如圖6和圖7所示。

圖5 隨機(jī)樣本碰撞檢測(cè)算法的步驟、運(yùn)算與時(shí)耗分析

表1 算法復(fù)雜度對(duì)比

圖6 算法平均時(shí)耗分步對(duì)比

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

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

圖7 算法平均時(shí)耗疊加對(duì)比

5.1.2 時(shí)間效率穩(wěn)定性實(shí)驗(yàn)

(1) 實(shí)驗(yàn)結(jié)果：當(dāng)3≤n≤10時(shí)，對(duì)算法1和算法2的時(shí)耗標(biāo)準(zhǔn)差進(jìn)行測(cè)試，其實(shí)驗(yàn)結(jié)果如圖8和圖9所示。

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

5.2 高維數(shù)據(jù)集實(shí)驗(yàn)

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

圖8 算法時(shí)耗標(biāo)準(zhǔn)差分步對(duì)比

圖9 算法“時(shí)耗標(biāo)準(zhǔn)差”疊加對(duì)比

(1) 實(shí)驗(yàn)結(jié)果

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

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

(2) 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

6 結(jié)束語

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