基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法

趙 穎

(青海廣播電視大學(xué) 繼續(xù)教育學(xué)院，西寧 810000)

近年來，伴隨著計(jì)算機(jī)網(wǎng)絡(luò)的不斷普及，使得計(jì)算效率、存儲(chǔ)容量、多機(jī)聯(lián)合分析以及協(xié)助決策成為可能[1].因?yàn)闆]有便利的數(shù)據(jù)處理工具，人類對(duì)待處理數(shù)據(jù)已經(jīng)無(wú)法處理[2],這就使得待處理數(shù)據(jù)在規(guī)模較大的數(shù)據(jù)庫(kù)中變成“datatomb”，幾乎不會(huì)被使用，決策一般沒有方法使用這個(gè)容量較大的數(shù)據(jù)庫(kù)，但是需要依靠制定者的直覺來做出決策[3-4].所以，使用先進(jìn)的技術(shù)手段將數(shù)據(jù)轉(zhuǎn)化成一種智慧，這是目前數(shù)據(jù)挖掘所要面對(duì)的新任務(wù)[5].MD算法是一種新興的群體智能數(shù)據(jù)挖掘算法，該算法自身對(duì)目標(biāo)函數(shù)的特性不存在具體的要求，它比較容易實(shí)現(xiàn)，同時(shí)具備較好的數(shù)據(jù)優(yōu)化性能，已經(jīng)是目前群體智能數(shù)據(jù)優(yōu)化算法研究的重點(diǎn)，而此算法中使用隨機(jī)數(shù)替換已找到的快速時(shí)序數(shù)據(jù)挖掘算法，這樣會(huì)改變?cè)瓉淼臄?shù)據(jù)造成誤差，并且容易陷入局部最優(yōu)[6].

快速時(shí)序數(shù)據(jù)挖掘算法實(shí)質(zhì)是一種多個(gè)目標(biāo)進(jìn)行優(yōu)化的局部數(shù)據(jù)挖掘算法，而對(duì)于一個(gè)比較復(fù)雜的矩陣來說，若使用快速時(shí)序數(shù)據(jù)挖掘算法對(duì)其進(jìn)行數(shù)據(jù)處理，是不合適的.本文運(yùn)用的方法主要是對(duì)整個(gè)數(shù)據(jù)進(jìn)行全局優(yōu)化的基礎(chǔ)上，再尋找含有最佳子矩陣作為種子，然后對(duì)其運(yùn)用快速時(shí)序數(shù)據(jù)挖掘算法.通過與快速時(shí)序算法和MDO算法進(jìn)行比較可知：基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法具有更好的全局尋優(yōu)能力，且數(shù)據(jù)挖掘效果更佳.

1 數(shù)據(jù)挖掘算法

數(shù)據(jù)挖掘的問題是對(duì)隱含在數(shù)據(jù)中的價(jià)值信息進(jìn)行有效識(shí)別，所謂的識(shí)別就是指具有相同特性數(shù)據(jù)的集合.因?yàn)橄嗤瑪?shù)據(jù)特性的不同表達(dá)，所以對(duì)于數(shù)據(jù)可以使用不同的挖掘算法，例如可以距離來對(duì)數(shù)據(jù)相似性進(jìn)行描述，此方法稱之為距離的數(shù)據(jù)挖掘算法.通常來說，對(duì)于數(shù)據(jù)相似性的描述主要是數(shù)據(jù)挖掘者進(jìn)行定義的.

一個(gè)比較好的數(shù)據(jù)挖掘算法可以對(duì)數(shù)據(jù)進(jìn)行有效的挖掘，進(jìn)而使得不同性質(zhì)的數(shù)據(jù)的相似性降低，但是在相似性較高的數(shù)據(jù)內(nèi)部，本文提出了一種應(yīng)用于數(shù)據(jù)挖掘的算法.目前的研究重點(diǎn)主要是依據(jù)基本的數(shù)據(jù)挖掘模型，使用相應(yīng)的數(shù)據(jù)挖掘算法來進(jìn)行有效數(shù)據(jù)挖掘，而數(shù)據(jù)挖掘算法是一種具體的、確定的數(shù)據(jù)均值算法.它的主要思想是如果相似特性的數(shù)據(jù)確定后，那么數(shù)據(jù)的集合平均數(shù)也隨之確定.進(jìn)行數(shù)據(jù)挖掘之前需要確定數(shù)據(jù)挖掘的中心，而數(shù)據(jù)挖掘算法中心的選擇是隨機(jī)的，這種隨機(jī)選擇的方法使得數(shù)據(jù)挖掘算法的效率大大降低，即數(shù)據(jù)挖掘算法的迭代次數(shù)增多，使得CPU數(shù)據(jù)處理時(shí)間延長(zhǎng).因此，本文提出了一種改進(jìn)的初始數(shù)據(jù)選擇方法.

對(duì)于一個(gè)m行n列的矩陣A，AIJ為A的一個(gè)子矩陣，其中I為行(數(shù)據(jù))的子集，J為列(條件)的子集，若AIJ的均方殘差值滿足一定的條件，則稱AIJ為一個(gè)快速時(shí)序數(shù)據(jù)挖掘算法.其中，均方殘差的計(jì)算公式為:

(1)

其中，aij為AIJ的有效元素，aiJ、aIj和aIJ分別為行平均值、列平均值和矩陣平均值.

2 基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法

2.1 快速時(shí)序數(shù)據(jù)挖掘算法

基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法中已知數(shù)據(jù)表達(dá)矩陣A=(X，Y)，在使用歐幾里德距離作為相似性度量的基礎(chǔ)上，對(duì)數(shù)據(jù)集合進(jìn)行劃分，使所得到的數(shù)據(jù)挖掘劃分能使總體類間差異(TWCV)最小.

(2)

則TWCV可以表示為:

(3)

那么此適應(yīng)度函數(shù)主要是各個(gè)挖掘數(shù)據(jù)同類中的函數(shù)WCV之和，如果WCV數(shù)值變小，則表示類內(nèi)的每個(gè)對(duì)象相互之間比較親密，也說明數(shù)據(jù)挖掘的效果很好.

基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法，可以在全局?jǐn)?shù)據(jù)挖掘和局部數(shù)據(jù)挖掘之間進(jìn)行切換，增強(qiáng)了在多峰優(yōu)化問題中尋找全局最優(yōu)解的概率.粒子基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法度量的公式如下:

(4)

(5)

其中，S表示挖掘數(shù)據(jù)，|L|表示求解空間最長(zhǎng)對(duì)角線的長(zhǎng)度，N表示問題的維數(shù).

在基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法中，單個(gè)粒子的收斂性是受收斂-發(fā)散因子β控制的.粒子進(jìn)入收斂狀態(tài)，種群的基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法減??；粒子進(jìn)入發(fā)散狀態(tài)，種群的基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法增多.挖掘數(shù)據(jù)在初始化后會(huì)進(jìn)入收斂狀態(tài)，這時(shí)β會(huì)從1.0線性減小到0.5，如式(6)所示.

(6)

將表達(dá)式(1)用作進(jìn)化方程的MDO方法中，每個(gè)粒子收斂的充要條件需要滿足β<1.782.所以存在β0=1.782，當(dāng)β<β0時(shí)，粒子收斂；當(dāng)β≥β0時(shí)，粒子進(jìn)入發(fā)散狀態(tài).

2.2 灰色系統(tǒng)理論下的快速時(shí)序數(shù)據(jù)挖掘算法

基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘主要實(shí)現(xiàn)兩個(gè)任務(wù)，其一是快速時(shí)序數(shù)據(jù)挖掘算法下的剩余參數(shù)應(yīng)該盡量取最小值；其二是快速時(shí)序數(shù)據(jù)挖掘算法需要的數(shù)據(jù)處理存儲(chǔ)空間需要最大.但在灰色系統(tǒng)理論下的數(shù)據(jù)挖掘算法運(yùn)行速度的參考只是存儲(chǔ)空間能夠變大，如果出現(xiàn)一組初始化比較大，那么可以認(rèn)為此次運(yùn)行執(zhí)行是有效的，迭代需要不斷進(jìn)行，這顯然是不合適的.

使用評(píng)估函數(shù)F(k，A)來評(píng)價(jià)灰色系統(tǒng)理論下的快速時(shí)序數(shù)據(jù)挖掘算法在每次迭代過程中的數(shù)據(jù)，F(xiàn)(k，A)的計(jì)算公式表達(dá)如下:

(7)

F(k，A)代表初始矩陣A的第k個(gè)快速時(shí)序數(shù)據(jù)挖掘陣的效果，rk表示平均平方差，vk表示容量，λ1和λ2依次表示均方殘差和容量的權(quán)值.F(k，A)的數(shù)值變小，就表示這個(gè)快速時(shí)序數(shù)據(jù)挖掘算法矩陣的質(zhì)量越好；相反，F(xiàn)(k，A)的值越大就表示這個(gè)快速時(shí)序數(shù)據(jù)挖掘算法矩陣的質(zhì)量越差.

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

為了能夠評(píng)估快速時(shí)序數(shù)據(jù)挖掘算法的效果，使用均方殘差(MSR)、矩陣規(guī)模(V)以及行變動(dòng)值(Var)來表達(dá)挖掘數(shù)據(jù)的一致性.目標(biāo)是找到的快速時(shí)序數(shù)據(jù)挖掘算法均方殘差要盡可能小，規(guī)模和行變動(dòng)值要盡可能大.行變動(dòng)值(Var)的計(jì)算方法如式(8)所示.

(8)

本文進(jìn)行的實(shí)驗(yàn)選用的數(shù)據(jù)是急性白血病數(shù)據(jù)表達(dá)(Leukaemia)數(shù)據(jù)集和酵母菌數(shù)據(jù)表達(dá)數(shù)據(jù)集(yeast).選用的急性白血病數(shù)據(jù)一共有38個(gè)樣本共7 129個(gè)數(shù)據(jù).在這些數(shù)據(jù)中已經(jīng)含27個(gè)患有急性淋巴性白血病(ALL)，11個(gè)患有急性骨髓性白血病(AML).因此，該數(shù)據(jù)挖掘算法主要分為兩類.酵母菌數(shù)據(jù)集包含2 884個(gè)數(shù)據(jù)，17個(gè)樣本.標(biāo)準(zhǔn)類的劃分主要是按照數(shù)據(jù)達(dá)到峰值的時(shí)候運(yùn)行的，這些數(shù)據(jù)全部是單獨(dú)運(yùn)行到峰值，細(xì)胞周期全部分為5個(gè)時(shí)相，因此把這些數(shù)據(jù)劃分為5個(gè)標(biāo)準(zhǔn)類.實(shí)驗(yàn)在裝有Win10系統(tǒng)的PC機(jī)上運(yùn)行，CPU為Intel酷睿i5，4 G內(nèi)存，實(shí)驗(yàn)環(huán)境為MATLABR2014a.

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

將SSKMCA、MDO、本文算法，以及未改進(jìn)的快速時(shí)序數(shù)據(jù)挖掘算法進(jìn)行比較.挖掘數(shù)據(jù)規(guī)模為40，迭代次數(shù)300次；將急性白血病數(shù)據(jù)集聚為兩類，酵母菌數(shù)據(jù)集聚為五類；通過實(shí)驗(yàn)確定公式(7)中參數(shù)λ1取1，λ2取1.8；d_low設(shè)置為0.000 5.

表1 四種算法在Leukaemia上的實(shí)驗(yàn)結(jié)果

表2 四種算法在yeast上的實(shí)驗(yàn)結(jié)果

表1、表2分別是快速時(shí)序數(shù)據(jù)挖掘算法、本文算法、MDO算法和SSKMCA快速時(shí)序數(shù)據(jù)挖掘算法在兩個(gè)數(shù)據(jù)集上10次實(shí)驗(yàn)的平均值.

從表中前兩行可以看出，本文算法的均方殘差值比快速時(shí)序數(shù)據(jù)挖掘算法分別減小了19%和6%，改進(jìn)后的本文算法雖然在規(guī)模上略有減小，但相差不大.所以用了本文算法表現(xiàn)結(jié)果更佳；從表中后兩行可以看出SSKMCA和MDO算法的均方殘差值相較于快速時(shí)序數(shù)據(jù)挖掘算法有明顯減小，主要是因?yàn)榇怂惴▽?duì)待挖掘數(shù)據(jù)進(jìn)行劃分，在復(fù)雜的數(shù)據(jù)中劃分為不同的表達(dá)浮動(dòng)比較相近的數(shù)據(jù)模塊，去除沒有關(guān)系的外部干擾數(shù)據(jù)，當(dāng)然這也導(dǎo)致了在第二階段得到的數(shù)據(jù)挖掘矩陣的容量有所減少，但是和本文算法相比，得到的數(shù)據(jù)挖掘矩陣相似性更集中，總體上質(zhì)量有很大幅度提高；本文算法和MDO算法相比，雖然規(guī)模相差不大，但是本文算法均方殘差明顯減小.說明本文算法相較于MDO算法在性能上有所提高，數(shù)據(jù)挖掘效果更佳.

4 結(jié)語(yǔ)

數(shù)據(jù)挖掘繁雜且沒有規(guī)律，針對(duì)此問題，提出了一種基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法.該算法根據(jù)灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法判斷數(shù)據(jù)狀態(tài)，以提高算法的全局?jǐn)?shù)據(jù)挖掘能力；再結(jié)合基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法，修改其迭代目標(biāo)函數(shù)，彌補(bǔ)了基于灰色系統(tǒng)理論的快速時(shí)序數(shù)據(jù)挖掘算法在處理多目標(biāo)優(yōu)化問題時(shí)的不足.經(jīng)過實(shí)驗(yàn)證明，本文提出的算法具有較好的全局尋優(yōu)能力，且數(shù)據(jù)挖掘效果更佳.