牛晨晨， 張 昪, 周 暢

(蘭州財經(jīng)大學(xué)信息工程學(xué)院， 甘肅蘭州 730000)

基于ExCC算法的流數(shù)據(jù)挖掘研究

牛晨晨， 張 昪, 周 暢

(蘭州財經(jīng)大學(xué)信息工程學(xué)院， 甘肅蘭州 730000)

隨著現(xiàn)代科學(xué)技術(shù)的快速發(fā)展，出現(xiàn)了諸如無線通信網(wǎng)絡(luò)的數(shù)據(jù)、傳感器網(wǎng)絡(luò)的數(shù)據(jù)、證券交易的數(shù)據(jù)等的新型數(shù)據(jù)，即流數(shù)據(jù)．流數(shù)據(jù)呈現(xiàn)的特點不同于傳統(tǒng)的數(shù)據(jù)集，其所表現(xiàn)的是數(shù)據(jù)規(guī)模宏大、時序性、數(shù)據(jù)快速變化等．傳統(tǒng)的聚類分析算法對于流數(shù)據(jù)挖掘已不再具有可行性，因此，本文就ExCC算法對于流數(shù)據(jù)挖掘的相關(guān)問題進(jìn)行了深入研究．

流數(shù)據(jù)；聚類分析；ExCC；數(shù)據(jù)挖掘

1 流數(shù)據(jù)及其挖掘算法簡介

1.1 流數(shù)據(jù)簡介

流數(shù)據(jù)是一組順序、 大量、 快速、 不斷增加的數(shù)據(jù)序列， 一般情況下， 其可被看作是無限增加的動態(tài)數(shù)據(jù)集合[1]. Henzinger[2]第一次把流數(shù)據(jù)作為新型的研究對象提出來了. 參考文獻(xiàn)[3-6]都對流數(shù)據(jù)的相關(guān)特征進(jìn)行了詳細(xì)的描述與深入的探討.

綜合已有文獻(xiàn)的研究， 我們可以把流數(shù)據(jù)的特征概括為以下幾點：

(1)流數(shù)據(jù)中的數(shù)據(jù)是海量的并且具有不斷增加的特征[3]， 如果想將這些海量的數(shù)據(jù)全部儲存起來， 那么存儲這些數(shù)據(jù)所需要的空間就必須是無限的.

(2)流數(shù)據(jù)中數(shù)據(jù)的傳遞速度是很快的. 例如：通信收集的數(shù)據(jù)、 流量監(jiān)控的數(shù)據(jù)、 證券交易的數(shù)據(jù)等， 這些數(shù)據(jù)的傳遞速度是很快的.

(3)流數(shù)據(jù)還具有時序的特征， 這就使得對流數(shù)據(jù)的訪問是單次遍歷的[4]. 也就是對數(shù)據(jù)元素的讀取只能按照數(shù)據(jù)流入的時間順序來依次進(jìn)行， 而不能對那些順序流入的數(shù)據(jù)進(jìn)行隨機訪問.

(4)流數(shù)據(jù)一般是變化的、 不可再現(xiàn)的[5]. 也就是說流數(shù)據(jù)的模式并不是固定不變的， 而是隨著時間的變化而不斷變化著. 因為流數(shù)據(jù)是無限的， 所以不能存儲所有數(shù)據(jù)， 只能存儲相對重要的部分?jǐn)?shù)據(jù)， 這就導(dǎo)致必須舍棄大部分的數(shù)據(jù)， 因此流數(shù)據(jù)通常是不可再現(xiàn)的.

(5)流數(shù)據(jù)還具有高維的特征[6]， 即流數(shù)據(jù)并不是由最初生成的數(shù)據(jù)聚集后才形成高維的， 而是自數(shù)據(jù)產(chǎn)生后就已經(jīng)達(dá)到了高維的標(biāo)準(zhǔn).

以上幾點都是流數(shù)據(jù)所具備的基本特征， 人們往往根據(jù)流數(shù)據(jù)的這些基本特點， 有針對性地采取不同的數(shù)據(jù)挖掘方法來獲取所需要的信息.

1.2 流數(shù)據(jù)挖掘算法簡介

流數(shù)據(jù)挖掘就是在動態(tài)到達(dá)的數(shù)據(jù)上發(fā)現(xiàn)并提取那些有用信息的過程. 傳統(tǒng)的數(shù)據(jù)挖掘算法通常是針對靜態(tài)數(shù)據(jù)集的， 顯然對于流數(shù)據(jù)已不再適用. 根據(jù)流數(shù)據(jù)自身所具有的特點， 我們可將其數(shù)據(jù)挖掘算法的特點歸納為：

(1)單次掃描. 由于流數(shù)據(jù)是無限持續(xù)到達(dá)的， 但是存儲數(shù)據(jù)的容量是有限的， 這就使得我們無法把所收集到的源源不斷的數(shù)據(jù)都存放在有限的內(nèi)存中并進(jìn)行多次的挖掘訪問， 而只能相應(yīng)地保存一些重要的數(shù)據(jù). 所以流數(shù)據(jù)只能被用來分析處理一次， 而不能再次掃描過往的記錄.

(2)時間復(fù)雜度低. 因為流算法是在線實時的算法， 這就要求算法能夠快速地處理這些動態(tài)流數(shù)據(jù)， 從而確保數(shù)據(jù)的處理速度大于或等于數(shù)據(jù)的產(chǎn)生速度.

(3)數(shù)據(jù)處理后的結(jié)果極其相似. 由于內(nèi)存的有限性只能存儲數(shù)據(jù)的一些概要信息， 并且流數(shù)據(jù)是無法全部存儲以及重復(fù)掃描的， 所以也就得不到精確的處理結(jié)果.

(4)算法本身的自適應(yīng)性. 數(shù)據(jù)的流速與內(nèi)容在不斷地變化， 所以流數(shù)據(jù)挖掘算法能夠針對不同的流數(shù)據(jù)特點做出相應(yīng)的改變.

(5)能高效準(zhǔn)確地處理例外點及噪音. 因為噪音或例外點可能會影響數(shù)據(jù)處理的結(jié)果， 所以一個具有較好魯棒性的算法就必須具備處理這些問題的能力.

(6)在任意時間點都可以提供當(dāng)前數(shù)據(jù)處理的結(jié)果. 其算法并不是間斷性地來處理數(shù)據(jù)提供結(jié)果， 而是對任意時間點的數(shù)據(jù)都進(jìn)行了分析處理， 而且能夠提供任意時間點的處理結(jié)果.

(7)算法的處理結(jié)果具備通用性. 也就是說算法的數(shù)據(jù)結(jié)構(gòu)不僅能支持算法當(dāng)前的目標(biāo)計算， 還能夠支持其他計算.

2 聚類分析以及它在流數(shù)據(jù)挖掘中的應(yīng)用

2.1 聚類分析

聚類分析(cluster analysis)簡稱聚類(clustering),其是把所收集到的數(shù)據(jù)元素劃分成相應(yīng)的類， 并組成相應(yīng)的簇， 從而使得劃分成的簇內(nèi)之間的數(shù)據(jù)具有相似性， 而不同的簇之間具有相異性[3]. 聚類分析是數(shù)據(jù)挖掘中一種重要的分析方法， 也是一種重要的無監(jiān)督學(xué)習(xí)方法. 其數(shù)學(xué)的形式化定義可以表達(dá)為：在某個數(shù)據(jù)空間S中， 數(shù)據(jù)集X是由不同的樣本點所組成， 樣本點Xi∈S,(i=1,2,......,m),其中xij表示樣本點Xi在屬性Aj(j=1,2,......,n)上的性質(zhì)特征值. 假設(shè)樣本集的樣本總數(shù)是m， 那么數(shù)據(jù)集X就是一個m×n的矩陣. 通過定義準(zhǔn)則函數(shù)可把數(shù)據(jù)集X劃分成C個類別Ci(i=1,2,......,c),也有部分?jǐn)?shù)據(jù)樣本點沒有劃分到Ci中， 這部分?jǐn)?shù)據(jù)樣本點記為噪聲Cs， 則所有的類別和噪聲的并集便是整個數(shù)據(jù)集X， 而且類別相互之間沒有交集， 即X=C1UC2U......UCn， 且Ci∩Cj=φ,(i≠j),這就是聚類的結(jié)果[7-9]. 聚類分析是數(shù)據(jù)挖掘中很重要的一部分， 它可以用來觀測數(shù)據(jù)的分布狀況以及每個簇的不同特征， 并能夠?qū)μ囟ù丶仙系臄?shù)據(jù)進(jìn)行進(jìn)一步的分析與研究.

2.2 流數(shù)據(jù)挖掘中的聚類分析

傳統(tǒng)的數(shù)據(jù)集是靜態(tài)的， 并且規(guī)模相對來說比較小， 這些數(shù)據(jù)集都儲存在一個穩(wěn)定的存儲介質(zhì)中， 而且大部分?jǐn)?shù)據(jù)都是不變的， 因此一些傳統(tǒng)的數(shù)據(jù)挖掘方法就能夠很好地處理這些數(shù)據(jù). 然而流數(shù)據(jù)卻與傳統(tǒng)靜態(tài)數(shù)據(jù)是完全不同的， 它是一種流動的海量數(shù)據(jù)的集合， 這就會使傳統(tǒng)的數(shù)據(jù)挖掘方法不能直接適用于這些流數(shù)據(jù)， 所以針對流數(shù)據(jù)的挖掘就需要采用最新的算法. 流數(shù)據(jù)聚類分析經(jīng)過這么多年的發(fā)展， 已經(jīng)取得了很大的進(jìn)步， 例如：基于K-平均算法的Stream算法[10]. 這種算法的聚類是通過質(zhì)心和權(quán)重表示得到的， 它比傳統(tǒng)算法具備更好的性能， 并且產(chǎn)生的聚類結(jié)果的質(zhì)量也更高； 基于BIRCH算法的CluStream算法[11]開創(chuàng)性地將聚類過程分為在線聚類和離線聚類， 并利用金字塔時間窗口技術(shù)來存儲和處理不同時間粒度上的流數(shù)據(jù)， 提供給用戶感興趣的聚類結(jié)果； 基于DBSCAN算法的DenStream算法[12]可以發(fā)現(xiàn)任意形狀的簇， 并著重指出了例外點的檢測問題. 而這些都是解決流數(shù)據(jù)的經(jīng)典的聚類分析算法. 本文所介紹的ExCC算法也是適用于流數(shù)據(jù)模型且滿足其特點的高效聚類算法.

3 ExCC算法在流數(shù)據(jù)中的應(yīng)用

ExCC算法是Bhatnagar等人提出的一種基于網(wǎng)格與密度的、 可以較好處理流數(shù)據(jù)的高效聚類算法. 該算法對簇聚類的完備性與排他性進(jìn)行了深入的研究， 并在此研究的基礎(chǔ)上提出了相完備性聚類的概念. ExCC算法分為了在線和離線兩個部分， 在線部分算法的基本處理過程就是將數(shù)據(jù)元素的屬性值映射到相應(yīng)的網(wǎng)格中， 并根據(jù)每個屬性到該屬性所屬域集的距離據(jù)此來劃分網(wǎng)格的粒度， 離線部分則根據(jù)實際的情況形成最終的聚類簇[13]. ExCC算法的基本框架用下面的偽碼來表示：

Input:All cells in grid (G);

Output:Clustering Scheme CS;

Prune G to remove non-recent cell.//剪去“舊”網(wǎng)格單元

Compute Ψ and store dense cells in a cell pool L//計算網(wǎng)格密度Ψ并將密集網(wǎng)格存入網(wǎng)格池L

Compute Ψ //算出當(dāng)前的密度閾值

Let CS=NULL,K=0

While (L not empty) Do

Begin

K=K+1

CK=clustering(L,K)//然后從L中選取網(wǎng)格進(jìn)行聚類

If([(ρK/ηK) > ω])//如果網(wǎng)格數(shù)量與數(shù)據(jù)點個數(shù)的比大于當(dāng)前密度閾值， 更新聚類簇的描述

Compute desk

CS=CS U CIK

End

ExCC算法實際上是運用了一種全新的剪枝策略， 這種策略的核心思想是在給定的時間間隔內(nèi)對簇的權(quán)值進(jìn)行相應(yīng)的檢查， 并設(shè)置一個最低權(quán)限或規(guī)則， 將那些不滿足要求的數(shù)據(jù)將被視為噪聲或例外點， 并把其從所存儲的隊列中刪除. ExCC算法常采用以下的數(shù)學(xué)公式來動態(tài)地計算密度閾值：

Ψ=[Ψ*(ln g + ln d)]/(2*ln g*ln d)

其中， Ψ是當(dāng)前網(wǎng)格的密度閾值， g為平均網(wǎng)格粒度， d表示數(shù)據(jù)空間的維度.

之后將密集網(wǎng)格和最新收集到的數(shù)據(jù)落入的網(wǎng)格放入相同的“網(wǎng)格池”中， 在以后的每次聚類中都是從這個網(wǎng)格池中來選取對象. 除了網(wǎng)格的粒度影響聚類質(zhì)量的高低之外， ExCC算法還會用多余的內(nèi)部存儲空間來創(chuàng)建“網(wǎng)格池”用以儲存密集網(wǎng)格.

ExCC算法由于是基于密度與網(wǎng)格的高效的聚類算法， 能明顯提高該算法的運行速度， 并使得空間復(fù)雜度大大下降. 因此ExCC算法能夠極好的適應(yīng)海量流數(shù)據(jù)的挖掘.

4 總結(jié)

隨著科技的進(jìn)步， 人們對流數(shù)據(jù)進(jìn)行了更為深入的研究， 并由此提出了多種算法來處理. 本文所提到的ExCC算法就是其中一種能較好處理流數(shù)據(jù)的算法， 但對于這種算法的研究還有待深入探討. 針對流數(shù)據(jù)的聚類分析仍就是一個充滿挑戰(zhàn)的領(lǐng)域， 但是可以預(yù)見的是， 未來一定會有更高效的算法來處理流數(shù)據(jù)， 從而可以更好地解決相關(guān)領(lǐng)域的問題.

[1] 胡彧， 閆巧梅． 基于滑動窗口的流數(shù)據(jù)聚類算法研究[J]． 計算機工程與設(shè)計， 2008， 29(21): 5621-5623．

[2] Henzinger M R, Raghavan P, Rajagopalan S. Computing on data streams. SRC Technical Note 1998-011.Digital systems research center: Palo Alto, California, 1998-95.

[3] 范明， 孟曉峰.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機械工業(yè)出版社，2012:378-385.

[4] 孫玉芬，盧炎生. 流數(shù)據(jù)挖掘綜述[J]. 計算機科學(xué)，2007, 34(1): 1-6,11.

[5] Babcock B.,Babu S.,Datar M.,Motwani R,Widom J. Models and issues in data stream systems[Z].In Proc.of the 2002 ACM Symp.on Principles of Database Systems(PODS’02),2002,1-16.

[6] Aggarwal C C,Han J,Yu P S. A framework for projected clustering of high dimensional data streams[Z].In Proc.of the 30thConf.on Very Large Data Bases(VLDB’04),2004,852-863.

[7] 任家東， 周瑋瑋， 何海濤.高維數(shù)據(jù)流的自適應(yīng)子空間聚類算法[J].計算機科學(xué)與探索， 2010,4(9)：859-964.

[8] 顏曉龍， 沈鴻.一種適用于高維數(shù)據(jù)流的子空間聚類方法[J].計算機應(yīng)用， 2007,27(7)：1680-1684.

[9] 周曉云， 孫志揮， 張柏禮， 楊宜東.高維數(shù)據(jù)子空間聚類發(fā)現(xiàn)及維護(hù)算法[J].計算機研究與發(fā)展， 2006,43(5)：834-840.

[10] Callaghan O L,Mishra N,Meyerson A,et al.Streaming-data algorithms for high-quality clustering [C]//Proc.Of ICDE Conf.of IEEE International Conference on Data Engineering,March 2002:685-694.

[11] Aggarwal C,Han J,Wwang J,et al.A framework for clusteering evolving data streams [C]//Proceedings of the 30thVLDB Conference,Berlin,Germany,2003.

[12] Udommanetanakit K,Rakthanmanon T,Waiyamai K. E-Stream:Evolution-Based Technique for Stream Clustering [M].Berlin :Springer-Verlag,2007:605-615.

[13] Bhatnagar V,Kaur S, Exclusive and Complete Clustering of Streams [M].Berlin :Springer-Verlag,2007:629-638.

[責(zé)任編輯 徐 剛]

Research on Stream Data Mining Based on ExCC Algorithm

NIU Chen-chen, Zhang Bian, Zhou Chang

(Department of information and engineering, Lanzhou University of Finance and Economics, Lanzhou 730000, China)

With the rapid development of modern network information technology and science technology, a kind of new data, such as wireless communication network, sensor network, financial stock transaction and so on daily application, has appeared. The characteristics of streaming data presentation are different from traditional data sets, which show the large-scale data, timing, rapid data changes. The traditional clustering algorithm is no longer feasible for streaming data mining, so this paper deeply studies the related problems of stream data mining in ExCC algorithm.

streaming data; cluster analysis; ExCC; data mining

2016-12-17

牛晨晨(1989—)， 男， 河南周口人，碩士研究生. 研究方向：數(shù)據(jù)挖掘.

TP311

A

1009-4970(2017)02-0055-04