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

牛晨晨， 張 昪, 周 暢

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

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

牛晨晨， 張 昪, 周 暢

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

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

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

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

1.1 流數(shù)據(jù)簡(jiǎn)介

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

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

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

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

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

(4)流數(shù)據(jù)一般是變化的、 不可再現(xiàn)的[5]. 也就是說(shuō)流數(shù)據(jù)的模式并不是固定不變的， 而是隨著時(shí)間的變化而不斷變化著. 因?yàn)榱鲾?shù)據(jù)是無(wú)限的， 所以不能存儲(chǔ)所有數(shù)據(jù)， 只能存儲(chǔ)相對(duì)重要的部分?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).

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

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

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

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

(2)時(shí)間復(fù)雜度低. 因?yàn)榱魉惴ㄊ窃诰€實(shí)時(shí)的算法， 這就要求算法能夠快速地處理這些動(dòng)態(tài)流數(shù)據(jù)， 從而確保數(shù)據(jù)的處理速度大于或等于數(shù)據(jù)的產(chǎn)生速度.

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

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

(5)能高效準(zhǔn)確地處理例外點(diǎn)及噪音. 因?yàn)樵胍艋蚶恻c(diǎn)可能會(huì)影響數(shù)據(jù)處理的結(jié)果， 所以一個(gè)具有較好魯棒性的算法就必須具備處理這些問(wèn)題的能力.

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

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

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

2.1 聚類分析

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

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

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

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

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

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//計(jì)算網(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ù)點(diǎn)個(gè)數(shù)的比大于當(dāng)前密度閾值， 更新聚類簇的描述

Compute desk

CS=CS U CIK

End

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

Ψ=[Ψ*(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)格池”中， 在以后的每次聚類中都是從這個(gè)網(wǎng)格池中來(lái)選取對(duì)象. 除了網(wǎng)格的粒度影響聚類質(zhì)量的高低之外， ExCC算法還會(huì)用多余的內(nèi)部存儲(chǔ)空間來(lái)創(chuàng)建“網(wǎng)格池”用以儲(chǔ)存密集網(wǎng)格.

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

4 總結(jié)

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

[1] 胡彧， 閆巧梅． 基于滑動(dòng)窗口的流數(shù)據(jù)聚類算法研究[J]． 計(jì)算機(jī)工程與設(shè)計(jì)， 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].北京：機(jī)械工業(yè)出版社，2012:378-385.

[4] 孫玉芬，盧炎生. 流數(shù)據(jù)挖掘綜述[J]. 計(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].計(jì)算機(jī)科學(xué)與探索， 2010,4(9)：859-964.

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

[9] 周曉云， 孫志揮， 張柏禮， 楊宜東.高維數(shù)據(jù)子空間聚類發(fā)現(xiàn)及維護(hù)算法[J].計(jì)算機(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