粗集挖掘策略在時間序列分析系統中的應用

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

關鍵詞：粗糙集；時間序列；信息系統；屬性約簡；規則提取

中圖分類號：TP391 文獻標識碼：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 引言

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

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

2 粗糙集理論

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

2.1 粗糙集基本概念

2.1.1 知識的含義和信息系統

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

定義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負域（negative region）。

相關概念如圖1所示。

2.2 約簡與核

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

定義5 對于一給定的決策系統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 數據預處理

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

3.2 約簡

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

3.3 規則提取

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

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

輸出：最小規則集

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

Step1 初始化對象數i=1，屬性數j=1，規則中包含的屬性個數r=1；

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

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

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

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

Step5 i=i+1；如果i≠n，則轉Step3；

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

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

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

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

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

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

4 結論

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

參考文獻：

[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] 曾黃麟.粗集理論及其應用[M].重慶:重慶大學出版社，1998.

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

[4] 王軍.數據庫知識發現的研究[J].天津理工學院學報，1998(S1):75-77.

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