于海鵬，李宜晨

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

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

于海鵬1，李宜晨2

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

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

大數(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)建及情報檢索等領(lǐng)域具有較高的應(yīng)用價值，研究面向大數(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)行自動聚類，該方法對數(shù)據(jù)直接進(jìn)行處理，計算開銷較小，但該方法在受到較大的干擾影響時容易出現(xiàn)誤分和漏分[6].對此，相關(guān)文獻(xiàn)進(jìn)行了算法的改進(jìn)設(shè)計.文獻(xiàn)[7]提出了一種基于全鄰模糊聚類的聯(lián)合概率數(shù)據(jù)互聯(lián)挖掘方法，提高了數(shù)據(jù)塊索引的效率，從而提高了聚類的時效性，但該方法在對特征敏感性較強的數(shù)據(jù)進(jìn)行聚類處理時，容易出現(xiàn)聚類中心的擾動，導(dǎo)致分類出錯；文獻(xiàn)[8]提出了一種基于面板數(shù)據(jù)的接近性和相似性關(guān)聯(lián)度分析的大數(shù)據(jù)自動聚類方法，把數(shù)據(jù)的分割轉(zhuǎn)化為對空間的分割，采用模糊C均值聚類算法實現(xiàn)數(shù)據(jù)聚類，但該方法的缺陷是對初始值聚類中心和噪聲數(shù)據(jù)敏感，容易陷入局部優(yōu)化解的問題.為了解決上述問題，本課題提出了一種基于Logistics混沌映射聚類中心小擾動抑制的大數(shù)據(jù)快速聚類算法.基于模糊C均值聚類算法計算大數(shù)據(jù)聚類的最優(yōu)聚類中心，采用Logistics混沌映射差分進(jìn)化方法進(jìn)行聚類中心的小擾動抑制，以實現(xiàn)大數(shù)據(jù)的優(yōu)化.改進(jìn)的算法利用Logistics混沌映射的均勻遍歷特性和高效的全局搜索能力，使數(shù)據(jù)聚類中心能有效克服小擾動的影響導(dǎo)致的計算偏差，避免陷入聚類中心的局部收斂，實現(xiàn)聚類中心解向量的全局尋優(yōu)，彌補了模糊C均值算法的缺陷.

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

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

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

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

(1)

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

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

(2)

式中：x(t)表示面板數(shù)據(jù)的采樣時間序列；J是相似性關(guān)聯(lián)系數(shù)；m是嵌入維數(shù)；Δt是抽樣時間間隔；K=N-(m-1)J.為了最大限度地反映前期統(tǒng)計測量的大數(shù)據(jù)時間序列的分類屬性，采用指標(biāo)數(shù)據(jù)投射方法得到大數(shù)據(jù)的特征非線性時間序列標(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ù)時間序列的接近性關(guān)聯(lián)系數(shù)；τ為對大數(shù)據(jù)時間序列采樣的時間延遲.

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

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

(4)

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

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

(5)

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

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

(6)

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

(7)

(8)

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

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

2.1 聚類中心的小擾動抑制

采用Logistics混沌映射差分進(jìn)化方法進(jìn)行聚類中心的小擾動抑制，避免聚類中心對初始值敏感而陷入局部優(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+τ時刻的時延尺度：

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

(10)

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

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

(11)

(12)

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

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

(13)

(14)

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

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

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

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

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

(1)定義模糊聚類中心矩陣，首先選擇一個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ù)據(jù)集中選擇K個實例，采用替代數(shù)據(jù)法進(jìn)行大數(shù)據(jù)時間序列的歸一化幅值的隨機(jī)化處理，初始化數(shù)據(jù)聚類中心F(xi，Aj(L))，i=1，2，…，m，j=1，2，…，k.

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

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

(15)

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

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

(16)

3 仿真實驗與結(jié)果分析

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

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

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

從圖3可知，采用本方法引入Logistics混沌映射進(jìn)行聚類中心的擾動抑制，使搜索軌跡具有較好的正則規(guī)律性，提高了數(shù)據(jù)聚類的準(zhǔn)確性，可避免陷入局部最優(yōu)解.為了定量地刻畫某算法進(jìn)行數(shù)據(jù)聚類的準(zhǔn)確性和時效性，以上述樣本為測試集,采用不同方法進(jìn)行數(shù)據(jù)的聚類性能測試，通過1 000次實驗并取平均值，得到了數(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ù)據(jù)規(guī)模下的平均時間開銷，分析得知本方法的時間開銷最小，這是因為本方法進(jìn)行了數(shù)據(jù)特征的壓縮和降維處理，并進(jìn)行了擾動抑制，避免了冗余數(shù)據(jù)的干擾，從而降低了運算量.

表1 時間開銷對比Tab.1 Time overhead comparison s

4 結(jié)語

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

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

[2] 李牧東,趙輝,翁興偉,等.基于最優(yōu)高斯隨機(jī)游走和個體篩選策略的差分進(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é)報,2015,37(7):1620-1625.

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

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

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

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

[9] 胡光波,梁紅,徐騫.艦船輻射噪聲混沌特征提取方法研究[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é)校重點科研項目(16A520004)

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

TP391

A

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