粗集挖掘策略在時間序列分析系統(tǒng)中的應(yīng)用

摘要：時間序列分析是當(dāng)今知識挖掘的研究熱點之一。該文引入粗糙集理論與方法，對信息系統(tǒng)屬性進行約簡，然后對約簡后的決策表提出一種改進的規(guī)則獲取方法，并描述其算法。

關(guān)鍵詞：粗糙集；時間序列；信息系統(tǒng)；屬性約簡；規(guī)則提取

中圖分類號：TP391 文獻標(biāo)識碼：A 文章編號：1009-3044(2009)05-1179-02

Application of the mining Strategy of Rough Sets in Time Series Analytical System

LIU Yan-qing， CAO Jia-lian

(Software college， Dalian Jiaotong University， Dalian 116028， China）

Abstract: Analysis of time series has been a focus in knowledge discovery. In this paper， the rough sets theory is introduced to reduce attributes. Then this paper provides a improved strategy on rule acquisition under the reduced decision table， and describe the algorithm.

Key words: rough sets; time series; information system; attribute reduction; rule acquisition

1 引言

隨著計算機技術(shù)的快速發(fā)展和廣泛應(yīng)用，人們在日常事務(wù)處理和研究工作中積累了大量的多種類型的數(shù)據(jù)。在這些數(shù)據(jù)中，有許多是“時間序列”(an ordered set of real values)[1]數(shù)據(jù)。所謂時間序列是指按時間順序排列的觀測值的集合。對于這些大量的時間序列進行分析處理，挖掘其背后蘊涵的價值信息，對于我們揭示事物發(fā)展變化的內(nèi)部規(guī)律，以及不同事物之間的相互作用關(guān)系，為人們正確認(rèn)識事物和科學(xué)決策提供依據(jù)等等具有重要的實際意義。

粗糙集理論可以不需要任何附加的信息或先驗知識，就能有效地分析和處理不精確、不完整和不一致的數(shù)據(jù)，并從中發(fā)現(xiàn)隱含的知識，揭示潛在的規(guī)律[2]。根據(jù)這個特點，可以將基于粗糙集理論的數(shù)據(jù)挖掘思想和方法引入時間序列分析系統(tǒng)中，從時間序列中探索性地獲取各種有價值的模式或規(guī)則。

2 粗糙集理論

粗糙集理論是由波蘭華沙理工大學(xué)的Pawlak Z教授于1982年提出的分析數(shù)據(jù)的數(shù)學(xué)理論，主要用于研究不完整和不精確知識的表達、學(xué)習(xí)和歸納[2]。

2.1 粗糙集基本概念

2.1.1 知識的含義和信息系統(tǒng)

在粗糙集理論中，知識被看作是關(guān)于論域的劃分，是一種對對象進行分類的能力。根據(jù)事物的特征將其分門別類的能力，就是“知識”。知識可以用信息系統(tǒng)來表示。

定義3X的R邊界域（boundary region）定義為BNR(X)=R(X)-R(X)

定義4 集合POSR(X)=R(X)稱為X的R正域（positive region），NEGR(X)=U-R(X)稱為X的R負(fù)域（negative region）。

相關(guān)概念如圖1所示。

2.2 約簡與核

屬性約簡包括兩個概念：約簡（reduce）和核（core）。屬性約簡是指關(guān)系的最小不可省略子集，而屬性的核則是指最重要的關(guān)系集。

定義5 對于一給定的決策系統(tǒng)S=(U，C∪D，V，f)，條件屬性集合C的約簡是C的一個非空子集P。它滿足：1) ?坌a∈P，a都是D不可省略的; 2) POSP(D)=POSC(D)則稱P是C的一個約簡，C中所有約簡的集合記作RED(C)。

3 粗糙集分析過程

3.1 數(shù)據(jù)預(yù)處理

對于時序信息系統(tǒng)，如果直接運用粗糙集工具分析，只能得到各條件屬性與決策屬性以及它們之間的關(guān)系，從中無法得到與時間屬性的聯(lián)系。所以必須要將時序信息系統(tǒng)轉(zhuǎn)換成信息系統(tǒng)。文獻[3]給出了詳細的轉(zhuǎn)換方法，現(xiàn)將其算法思想簡要描述如圖2所示。

3.2 約簡

眾所周知，知識庫中的屬性并不是同等重要的，甚至其中某些知識是冗余的。而粗糙集理論中的一個非常重要的概念屬性約簡[4]，它可以保持知識庫的分類和決策能力不變的條件下，刪除其中不相關(guān)或不重要的屬性。這里主要采用基于部分差別矩陣的知識相對約簡算法[5]進行屬性約簡，可以有效減少知識約簡過程中的搜索空間并且得到?jīng)Q策表。

3.3 規(guī)則提取

一般的規(guī)則獲取方法在一次性獲取的最小規(guī)則集上會存在不足，本文采用一種改進的規(guī)則獲取方法，算法描述如下：

輸入：條件屬性集約簡后得到的屬性集與決策屬性集組成的決策表

輸出：最小規(guī)則集

令Reduct為屬性約簡，m=│Reduct│，n=│U│；

Step1 初始化對象數(shù)i=1，屬性數(shù)j=1，規(guī)則中包含的屬性個數(shù)r=1；

Step2 對約簡中單屬性求S(Q→d)，并從大到小排序，K←排序后屬性順序；

Step3 對象i從K中屬性aj開始掃描。如果屬性值aij=”*”，則轉(zhuǎn)Step5；

Step4 對所有的k≠i，如果aij≠akj或者aij=akj∧di=dk，則aij可以生成r屬性規(guī)則；

如果K中屬性沒有全部遍歷，則j=j+1，轉(zhuǎn)Step3；

Step5 i=i+1；如果i≠n，則轉(zhuǎn)Step3；

Step6 修改原決策表T，用”*”代替生成單屬性規(guī)則所有aij≠”Null”，生成新決策表T’；

Step7 r=r+1，如果r>m，則結(jié)束；否則，i=1；

Step8 對約簡中r屬性求S(Q→d)，并從大到小排序，K←排序后屬性順序；

Step9 在對象i上查找K中合適的屬性值{aij1，…，aijr}，如果不存在，則轉(zhuǎn)Step11；

Step10 對所有的k≠i，j=j1，…，jr，如果aij≠akj，或者aij=akj且d1=dk，則{aij1，…，aijr}可以生成r屬性規(guī)則；用”*r”代替{aij1，…，aijr}，轉(zhuǎn)Step9；

Step11 i=i+1，如果i>n，則轉(zhuǎn)Step8；否則，轉(zhuǎn)Step9；

4 結(jié)論

時序數(shù)據(jù)由于采樣、處理的過程中難免會存在噪聲、不完整或不精確數(shù)據(jù)。概率論、模糊集理論和粗糙集理論相對而言，概率論中常需要前提假設(shè)，模糊集理論中則需要隸屬函數(shù)假設(shè)，而粗糙集理論可以直接處理。因此可以認(rèn)為，基于粗糙集的時序數(shù)據(jù)挖掘策略有較好的應(yīng)用前景。

參考文獻：

[1] Agral R，Lin K I，Sawhney H，Shim K.Fast Similarity Search in the Presence of Noise，Scaling，and Translation of Time-series Database[C].In:Proc Twenty-first International Conference on Very Large Database.San Francisco，CA，1995.490-501

[2] 曾黃麟.粗集理論及其應(yīng)用[M].重慶:重慶大學(xué)出版社，1998.

[3] 馬云鋒，刑汗承，鄭曉妹.一種基于Rough集的時間序列數(shù)據(jù)挖掘策略[J].系統(tǒng)工程理論與實踐，2001(12):23-30.

[4] 王軍.數(shù)據(jù)庫知識發(fā)現(xiàn)的研究[J].天津理工學(xué)院學(xué)報，1998(S1):75-77.

[5] 徐一新，葉東毅.知識約簡的差別矩陣啟發(fā)式算法[J].福州大學(xué)學(xué)報(自然科學(xué)版)，2000，28（3）：120-123.