一種面向大數(shù)據(jù)的快速自動(dòng)聚類算法

于海鵬，李宜晨

(1.河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191；2.山東大學(xué) 軟件學(xué)院，山東 濟(jì)南 250101)

一種面向大數(shù)據(jù)的快速自動(dòng)聚類算法

于海鵬1，李宜晨2

(1.河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191；2.山東大學(xué) 軟件學(xué)院，山東 濟(jì)南 250101)

為了提高大數(shù)據(jù)的快速處理和識別能力，需要進(jìn)行數(shù)據(jù)快速聚類分析.針對傳統(tǒng)的模糊C均值聚類算法對初始值敏感且容易陷入局部優(yōu)化解的問題，提出了一種基于Logistics混沌映射聚類中心小擾動(dòng)抑制的大數(shù)據(jù)快速聚類算法.采用非線性時(shí)間序列分析方法構(gòu)建大數(shù)據(jù)信息流模型，提取大數(shù)據(jù)信息流的時(shí)延尺度特征值，以提取的該特征值為聚類搜索目標(biāo)函數(shù)，用模糊C均值聚類算法計(jì)算大數(shù)據(jù)聚類的最優(yōu)聚類中心，采用Logistics混沌映射差分進(jìn)化方法進(jìn)行聚類中心的小擾動(dòng)抑制，實(shí)現(xiàn)了優(yōu)化聚類，可避免陷入局部最優(yōu)解.仿真結(jié)果表明，采用該方法進(jìn)行大數(shù)據(jù)聚類，能有效提高數(shù)據(jù)召回率，計(jì)算速度較快，實(shí)現(xiàn)了大數(shù)據(jù)的快速自動(dòng)聚類.

大數(shù)據(jù)；聚類；模糊C均值；混沌；Logistics映射

大數(shù)據(jù)信息處理的關(guān)鍵環(huán)節(jié)就是進(jìn)行數(shù)據(jù)聚類，即通過挖掘大數(shù)據(jù)中具有同類屬性的數(shù)據(jù)特征參量，對數(shù)據(jù)進(jìn)行分門別類的分析.在數(shù)據(jù)聚類的基礎(chǔ)上建立專家系統(tǒng)和大數(shù)據(jù)庫，以進(jìn)行相關(guān)的模式識別和診斷分析服務(wù).大數(shù)據(jù)的優(yōu)化聚類技術(shù)研究在故障診斷、目標(biāo)識別、云存儲數(shù)據(jù)庫模型的構(gòu)建及情報(bào)檢索等領(lǐng)域具有較高的應(yīng)用價(jià)值，研究面向大數(shù)據(jù)的優(yōu)化聚類方法已受到了人們的重視.

當(dāng)前，數(shù)據(jù)聚類算法主要有基于網(wǎng)格技術(shù)的數(shù)據(jù)聚類方法[1]、模糊C均值聚類方法[2]、模糊K均值聚類方法和基于自適應(yīng)波束形成的聚類算法等[3-5]，上述方法均是通過求取大數(shù)據(jù)信息流屬性特征之間的相似度進(jìn)行分類的.其中，模糊C均值和模糊K均值聚類算法需要反復(fù)調(diào)整聚類結(jié)果來進(jìn)行聚類優(yōu)化.隨著數(shù)據(jù)規(guī)模的擴(kuò)大對初始聚類中心有較大敏感性；網(wǎng)格聚類算法沒有考慮數(shù)據(jù)密度和類別距離給聚類中心搜索帶來的影響，導(dǎo)致聚類的精度受到了限制；自適應(yīng)波束形成聚類算法通過波束聚類性進(jìn)行自動(dòng)聚類，該方法對數(shù)據(jù)直接進(jìn)行處理，計(jì)算開銷較小，但該方法在受到較大的干擾影響時(shí)容易出現(xiàn)誤分和漏分[6].對此，相關(guān)文獻(xiàn)進(jìn)行了算法的改進(jìn)設(shè)計(jì).文獻(xiàn)[7]提出了一種基于全鄰模糊聚類的聯(lián)合概率數(shù)據(jù)互聯(lián)挖掘方法，提高了數(shù)據(jù)塊索引的效率，從而提高了聚類的時(shí)效性，但該方法在對特征敏感性較強(qiáng)的數(shù)據(jù)進(jìn)行聚類處理時(shí)，容易出現(xiàn)聚類中心的擾動(dòng)，導(dǎo)致分類出錯(cuò)；文獻(xiàn)[8]提出了一種基于面板數(shù)據(jù)的接近性和相似性關(guān)聯(lián)度分析的大數(shù)據(jù)自動(dòng)聚類方法，把數(shù)據(jù)的分割轉(zhuǎn)化為對空間的分割，采用模糊C均值聚類算法實(shí)現(xiàn)數(shù)據(jù)聚類，但該方法的缺陷是對初始值聚類中心和噪聲數(shù)據(jù)敏感，容易陷入局部優(yōu)化解的問題.為了解決上述問題，本課題提出了一種基于Logistics混沌映射聚類中心小擾動(dòng)抑制的大數(shù)據(jù)快速聚類算法.基于模糊C均值聚類算法計(jì)算大數(shù)據(jù)聚類的最優(yōu)聚類中心，采用Logistics混沌映射差分進(jìn)化方法進(jìn)行聚類中心的小擾動(dòng)抑制，以實(shí)現(xiàn)大數(shù)據(jù)的優(yōu)化.改進(jìn)的算法利用Logistics混沌映射的均勻遍歷特性和高效的全局搜索能力，使數(shù)據(jù)聚類中心能有效克服小擾動(dòng)的影響導(dǎo)致的計(jì)算偏差，避免陷入聚類中心的局部收斂，實(shí)現(xiàn)聚類中心解向量的全局尋優(yōu)，彌補(bǔ)了模糊C均值算法的缺陷.

1 大數(shù)據(jù)非線性時(shí)間序列分析模型及特征參量的提取

1.1 大數(shù)據(jù)非線性時(shí)間序列分析模型

通過對大數(shù)據(jù)信息流的前期統(tǒng)計(jì)和采樣，構(gòu)建了大數(shù)據(jù)時(shí)間序列的單變量時(shí)間序列{xn}，數(shù)據(jù)樣本長度為N.在數(shù)據(jù)的采樣時(shí)間段內(nèi)，數(shù)據(jù)分布是標(biāo)量時(shí)間序列，設(shè)X和Y為數(shù)據(jù)流的聚類特征屬性類別，采用相空間重構(gòu)分析方法進(jìn)行大數(shù)據(jù)的非線性映射處理，選擇最小嵌入維數(shù)m與最佳時(shí)延τ，當(dāng)數(shù)據(jù)特征的平均測度ε滿足2-λt<ε(λ>0)時(shí)，大數(shù)據(jù)時(shí)間序列的信息流模型如下：

xn=x(t0+nΔt)=h[z(t0+nΔt)]+ωn,

(1)

式中:h(·)為大數(shù)據(jù)時(shí)間序列的每個(gè)樣本中包含的相似性特征量.通過計(jì)算關(guān)聯(lián)度來表達(dá)大數(shù)據(jù)非線性時(shí)間序列的高維幾何屬性[9]，通過相空間重構(gòu)，可得到大數(shù)據(jù)非線性時(shí)間序列的特征空間分布軌跡表達(dá)式：

X=[x(t0)，x(t0+Δt)，…，x(t0+(K-1)Δt)]=

(2)

式中：x(t)表示面板數(shù)據(jù)的采樣時(shí)間序列；J是相似性關(guān)聯(lián)系數(shù)；m是嵌入維數(shù)；Δt是抽樣時(shí)間間隔；K=N-(m-1)J.為了最大限度地反映前期統(tǒng)計(jì)測量的大數(shù)據(jù)時(shí)間序列的分類屬性，采用指標(biāo)數(shù)據(jù)投射方法得到大數(shù)據(jù)的特征非線性時(shí)間序列標(biāo)量模型為{x(t0+iΔt)},i=0，1，…，N-1，其特征空間高維映射矢量為

X=[s1，s2，…，sK]n=(xn，xn-τ，…，xn-(m-1)τ)，

(3)

式中：K=N-(m-1)τ，表示大數(shù)據(jù)時(shí)間序列的接近性關(guān)聯(lián)系數(shù)；τ為對大數(shù)據(jù)時(shí)間序列采樣的時(shí)間延遲.

1.2 大數(shù)據(jù)信息流時(shí)延尺度特征參量的提取

以上述構(gòu)建的大數(shù)據(jù)信息流為輸入進(jìn)行時(shí)延尺度特征的提取，以提取的特征值為基礎(chǔ)建立聚類搜索目標(biāo)函數(shù)，用Ru，v表示大數(shù)據(jù)屬性集的模糊集合自相關(guān)量，為數(shù)據(jù)特征向量之間的互相關(guān)函數(shù)，則大數(shù)據(jù)屬性集的交叉分布模型可表示為

(4)

式中：a0為初始大數(shù)據(jù)時(shí)間序列的采樣幅值；xn-1為具有相同均值和方差的大數(shù)據(jù)標(biāo)量時(shí)間序列；bj為大數(shù)據(jù)的最優(yōu)分裂屬性.對于大數(shù)據(jù)的標(biāo)量時(shí)間序列為x(t)，t=0，1，…，n-1，采用非線性自回歸滑動(dòng)時(shí)間窗口構(gòu)建多層空間模糊聚類中心[10]，采用模糊C均值聚類算法進(jìn)行初始聚類中心搜索，假設(shè)有限數(shù)據(jù)集向量

X={x1，x2，…，xn}?Rs，

(5)

通過屬性集分類，可得到數(shù)據(jù)集合中含有n個(gè)樣本.其中，樣本xi(i=1，2，…，n)的信息增益矢量為

xi=(xi1，xi2，…，xis)T.

(6)

在數(shù)據(jù)集中選擇K個(gè)實(shí)例，求得聚類目標(biāo)函數(shù)的極值：

(7)

(8)

在上述構(gòu)建了大數(shù)據(jù)聚類目標(biāo)函數(shù)的基礎(chǔ)上，通過對大數(shù)據(jù)最優(yōu)聚類中心的搜索，進(jìn)行數(shù)據(jù)聚類算法的改進(jìn)設(shè)計(jì).

2 數(shù)據(jù)快速自動(dòng)聚類算法的改進(jìn)

2.1 聚類中心的小擾動(dòng)抑制

采用Logistics混沌映射差分進(jìn)化方法進(jìn)行聚類中心的小擾動(dòng)抑制，避免聚類中心對初始值敏感而陷入局部優(yōu)化解.根據(jù)混沌理論，定義Logistic混沌映射表達(dá)式[11]為

xn+1=μxn(1-xn),

(9)

式中:x∈[0，1]；μ∈[0，4]；n=1，2，3，….

以此為訓(xùn)練函數(shù)進(jìn)行大數(shù)據(jù)模糊聚類中心的尺度調(diào)整，在聚類中心檢索t和t+τ時(shí)刻的時(shí)延尺度：

V={vij|i=1，2，…，c，j=1，2，…，s}，

(10)

式中：Vi為鄰近數(shù)據(jù)點(diǎn)對聚類中心的擾動(dòng)權(quán)重.對于大數(shù)據(jù)時(shí)間序列的第i個(gè)聚類中心矢量，采用Logistics混沌映射進(jìn)行差分?jǐn)_動(dòng)，將每個(gè)數(shù)據(jù)點(diǎn)作為一個(gè)可能的聚類中心，得到聚類中心穩(wěn)定的周期解：

U={μik|i=1，2，…，c，k=1，2，…，n}，

(11)

(12)

結(jié)合大數(shù)據(jù)聚類目標(biāo)函數(shù)，在聚類中心初始值已經(jīng)給定的情況下進(jìn)行聚類中心的小擾動(dòng)抑制，抑制過程如下：

(1)當(dāng)式(9)中的0≤μ≤1時(shí)，大數(shù)據(jù)聚類中心的最優(yōu)解只有x=0這樣一個(gè)穩(wěn)定的周期點(diǎn)；

(13)

(14)

通過Logistics混沌映射進(jìn)行周期解的差分進(jìn)化，排除鄰近數(shù)據(jù)點(diǎn)的擾動(dòng)，得到兩個(gè)穩(wěn)定的2周期點(diǎn)；

圖1 Logistics混沌映射差分進(jìn)化的聚類中心小擾動(dòng)抑制Fig.1 Logistics chaotic mapping differential evolution of cluster centers with small disturbance rejection

(4)當(dāng)3.449≤μ≤3.544時(shí)，2周期點(diǎn)變得不穩(wěn)定，此時(shí)出現(xiàn)了4個(gè)穩(wěn)定的4周期點(diǎn)；當(dāng)參數(shù)μ繼續(xù)變大，μ>3.544，Logistics混沌映射采用差分進(jìn)化方法，通過倍周期分岔通向最優(yōu)值[12]，實(shí)現(xiàn)了對大數(shù)據(jù)快速聚類中心的小擾動(dòng)抑制，如圖1所示.

2.2 聚類算法構(gòu)建實(shí)現(xiàn)的具體步驟

通過上述分析，基于模糊C均值聚類算法計(jì)算大數(shù)據(jù)聚類的最優(yōu)聚類中心，采用Logistics混沌映射差分進(jìn)化方法進(jìn)行聚類中心的小擾動(dòng)抑制，實(shí)現(xiàn)了面向大數(shù)據(jù)的快速自動(dòng)聚類算法的改進(jìn)設(shè)計(jì)，步驟描述如下：

(1)定義模糊聚類中心矩陣，首先選擇一個(gè)C值，確定大數(shù)據(jù)分類屬性的總數(shù).若數(shù)據(jù)集為m，令A(yù)j(L)為聚類中心，j=1，2，…，k，構(gòu)建數(shù)據(jù)聚類目標(biāo)函數(shù).

(2)提取數(shù)據(jù)信息流的時(shí)延尺度特征，在數(shù)據(jù)集中選擇K個(gè)實(shí)例，采用替代數(shù)據(jù)法進(jìn)行大數(shù)據(jù)時(shí)間序列的歸一化幅值的隨機(jī)化處理，初始化數(shù)據(jù)聚類中心F(xi，Aj(L))，i=1，2，…，m，j=1，2，…，k.

(3)使用Logistics混沌差分進(jìn)化方法進(jìn)行聚類中心的擾動(dòng)抑制，如滿足

D(xi，Aj(L))=min{D(xi，Aj(L))}，

(15)

那么xi∈ωk，此時(shí)的聚類中心取得最優(yōu)解.

(4)把混沌擾動(dòng)量引入進(jìn)化分類簇的實(shí)例中，計(jì)算初始隸屬度矩陣，以平均值作為新的聚類屬性特征向量的平均值：

(16)

3 仿真實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本算法在實(shí)現(xiàn)大數(shù)據(jù)快速自動(dòng)聚類中的性能，進(jìn)行仿真實(shí)驗(yàn).實(shí)驗(yàn)建立在Matlab仿真軟件的基礎(chǔ)上，使用的計(jì)算機(jī)主頻為3 G、內(nèi)存為2 G.用Microsoft .NET Framework 4.0開發(fā)工具建立數(shù)據(jù)聚類分析軟件，實(shí)驗(yàn)數(shù)據(jù)來自2個(gè)大數(shù)據(jù)集：KDDP201大型網(wǎng)絡(luò)數(shù)據(jù)庫模擬數(shù)據(jù)集(包括2個(gè)規(guī)模為22.4 MB的分區(qū))和CSLOGS實(shí)際數(shù)據(jù)集(含規(guī)模為6.45 MB的分區(qū)).在測試數(shù)據(jù)集中進(jìn)行大數(shù)據(jù)樣本選取，大數(shù)據(jù)采集的時(shí)間間隔為0.43 s，采樣頻率fs=4f0=20 kHz，在不同的采集時(shí)間段內(nèi)得到了6組大數(shù)據(jù)采樣樣本，其時(shí)域波形如圖2所示.

圖2 大數(shù)據(jù)聚類實(shí)驗(yàn)測試樣本的時(shí)域波形Fig.2 Time domain waveform of large data clustering experiment test sample

根據(jù)仿真環(huán)境和實(shí)驗(yàn)樣本的設(shè)定，以上述數(shù)據(jù)樣本為研究對象進(jìn)行數(shù)據(jù)聚類分析.通過特征提取和聚類中心搜索，以其中一組樣本為例，得到了大數(shù)據(jù)聚類的最優(yōu)聚類中心搜索軌跡，如圖3所示.

從圖3可知，采用本方法引入Logistics混沌映射進(jìn)行聚類中心的擾動(dòng)抑制，使搜索軌跡具有較好的正則規(guī)律性，提高了數(shù)據(jù)聚類的準(zhǔn)確性，可避免陷入局部最優(yōu)解.為了定量地刻畫某算法進(jìn)行數(shù)據(jù)聚類的準(zhǔn)確性和時(shí)效性，以上述樣本為測試集,采用不同方法進(jìn)行數(shù)據(jù)的聚類性能測試，通過1 000次實(shí)驗(yàn)并取平均值，得到了數(shù)據(jù)聚類的準(zhǔn)確召回率對比結(jié)果，如圖4所示.

圖3 聚類中心搜索軌跡Fig.3 Cluster center search trajectory

圖4 數(shù)據(jù)聚類的準(zhǔn)確性對比Fig.4 Accuracy comparison of data clustering

由圖4得知，采用本方法進(jìn)行數(shù)據(jù)聚類，對數(shù)據(jù)的準(zhǔn)確召回性能較好，誤分率較低，數(shù)據(jù)聚類的精準(zhǔn)度較高.表1給出了采用不同方法進(jìn)行數(shù)據(jù)聚類時(shí)不同數(shù)據(jù)規(guī)模下的平均時(shí)間開銷，分析得知本方法的時(shí)間開銷最小，這是因?yàn)楸痉椒ㄟM(jìn)行了數(shù)據(jù)特征的壓縮和降維處理，并進(jìn)行了擾動(dòng)抑制，避免了冗余數(shù)據(jù)的干擾，從而降低了運(yùn)算量.

表1 時(shí)間開銷對比Tab.1 Time overhead comparison s

4 結(jié)語

為研究大數(shù)據(jù)的優(yōu)化聚類分析問題，本課題提出了一種基于Logistics混沌映射聚類中心小擾動(dòng)抑制的大數(shù)據(jù)快速聚類算法，采用Logistics混沌映射差分進(jìn)化方法進(jìn)行聚類中心的小擾動(dòng)抑制，實(shí)現(xiàn)了大數(shù)據(jù)優(yōu)化聚類，避免陷入局部最優(yōu)解.分析得出，采用本方法進(jìn)行大數(shù)據(jù)聚類，聚類中心搜索較為準(zhǔn)確，數(shù)據(jù)的召回性較好，計(jì)算速度較快，具有較好的應(yīng)用價(jià)值.

[1] 梁聰剛，王鴻章.微分進(jìn)化算法的優(yōu)化研究及其在聚類分析中的應(yīng)用[J].現(xiàn)代電子技術(shù)，2016，39(13):103-107.

[2] 李牧東,趙輝,翁興偉,等.基于最優(yōu)高斯隨機(jī)游走和個(gè)體篩選策略的差分進(jìn)化算法[J].控制與決策,2016,31(8):1379-1386.

[3] PATEL V M,NGUYEN H V,VIDAL R.Latent space sparse and low-rank subspace clustering[J].IEEE Journal of Selected Topics in Signal Processing,2015,9(4):691-701.

[4] 孫力娟,陳小東,韓崇,等.一種新的數(shù)據(jù)流模糊聚類方法[J].電子與信息學(xué)報(bào),2015,37(7):1620-1625.

[5] 邢長征,劉劍.基于近鄰傳播與密度相融合的進(jìn)化數(shù)據(jù)流聚類算法[J].計(jì)算機(jī)應(yīng)用,2015,35(7):1927-1932.

[6] 畢安琪,王士同.基于Kullback-Leiber距離的遷移仿射聚類算法[J].電子與信息學(xué)報(bào),2016,38(8):2076-2084.

[7] 劉俊,劉瑜,何友,等.雜波環(huán)境下基于全鄰模糊聚類的聯(lián)合概率數(shù)據(jù)互聯(lián)算法[J].電子與信息學(xué)報(bào),2016,38(6):1438-1445.

[8] 吳鴻華,穆勇,屈忠鋒,等.基于面板數(shù)據(jù)的接近性和相似性關(guān)聯(lián)度模型[J].控制與決策,2016,31(3):555-558.

[9] 胡光波,梁紅,徐騫.艦船輻射噪聲混沌特征提取方法研究[J].計(jì)算機(jī)仿真,2011,28(2):22-24.

[10]MAHMOUD E E.Complex complete synchronization of two nonidentical hyperchaotic complex nonlinear systems[J].Mathematical Methods in the Applied Sciences,2014,37(3):321-328.

[11]PALOMARES I,MARTINEZ L,HERRERA F.A consensus model to detect and manage non-cooperative behaviors in large scale group decision making[J].IEEE Trans on Fuzzy System,2014,22(3):516-530.

[12]MAREY M,DOBRE O A,LIAO B.Classification of STBC system over frequency-selective channels[J].IEEE Transactions on Vehicular Technology,2015,64(5):2159-2164.

A fast and automatic clustering algorithm for large data

YU Haipeng1，LI Yichen2

(1.CollegeofComputerScience,HenanUniversityofEngineering,Zhengzhou451191,China；2.SoftwareCollege,ShandongUniversity,Jinan250101,China)

In order to improve the recognition and rapid processing of large data capacity, the need for rapid data clustering analysis, according to the conventional fuzzy C means clustering algorithm is sensitive and easy to fall into local optimal solution to the initial problem, we propose a fast clustering algorithm for large data suppression of small disturbance Logistics chaotic map based on clustering center. By using the nonlinear time series analysis method to construct data flow model, time scale characteristic parameters extraction of large data flow of information, in order to extract the eigenvalue searching objective function for clustering, the optimal clustering center calculation data clustering and fuzzy C means clustering algorithm based on Logistics chaotic map, using the differential evolution method of clustering center small disturbance inhibition of large data clustering, to avoid falling into local optimal solution. The simulation results show that the method can effectively improve the recall rate of data, calculate cost is less, and the anti-interference ability is stronger.

large data; clustering; fuzzy C mean; chaos; Logistics map

2017-01-04

河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(16A520004)

于海鵬(1979-)，男，河南魯山人，副教授，主要研究方向?yàn)閳D像處理與計(jì)算機(jī)應(yīng)用.

TP391

A

1674-330X(2017)02-0062-05