基于非線性相關發(fā)現(xiàn)的數(shù)據(jù)挖掘算法

摘 要：現(xiàn)有的關聯(lián)規(guī)則挖掘算法均致力于頻繁集搜索，基于預先設置的支持度—置信度之上，具有很大的偶然性，不利于控制；并且關聯(lián)規(guī)則沒有體現(xiàn)數(shù)據(jù)整體的相關性。為了克服以上缺點，引入了非線性相關的概念，應用于不同相關類型規(guī)則的挖掘，且無須人為設置參數(shù)，從而大大提高了規(guī)則發(fā)現(xiàn)的實效性。

關鍵詞：數(shù)據(jù)挖掘； 關聯(lián)規(guī)則挖掘； 線性相關性發(fā)現(xiàn)； 全局相關性； 非線性相關發(fā)現(xiàn)

中圖分類號：TP391文獻標志碼：A

文章編號：1001—3695(2007)03—0047—03

關聯(lián)規(guī)則挖掘發(fā)現(xiàn)大量數(shù)據(jù)中項集之間有趣的關聯(lián)或相關聯(lián)系。Agrawal等人于1993年首先提出了挖掘顧客交易數(shù)據(jù)庫中項集間的關聯(lián)規(guī)則問題[1]，它同時給出了關聯(lián)規(guī)則挖掘的概念，由此改進到后來所謂的Apriori算法[2]以及更多基于頻繁集發(fā)現(xiàn)的算法[3—8]。它在數(shù)據(jù)挖掘中是一個重要的課題，最近幾年已被業(yè)界廣泛研究?，F(xiàn)有的關聯(lián)規(guī)則挖掘算法一般都是基于支持度—置信度模型的，其主要思想是在數(shù)據(jù)庫中挖掘符合最小支持度和最小置信度閾值的規(guī)則。

Chiang R.H.L.等人結合統(tǒng)計技術和數(shù)據(jù)挖掘技術，設計出線性相關發(fā)現(xiàn)（LCD）的數(shù)據(jù)處理模型[9]，實現(xiàn)了對象數(shù)據(jù)庫中屬性集合線性相關規(guī)則的發(fā)現(xiàn)自動化，推廣了前面關于關聯(lián)規(guī)則挖掘的概念和應用，在實際應用中具有重要意義。

但是LCD沒有考慮到相關性的方向性問題，這是個棘手而又重要的問題，因為對于成對的對象間的相關性問題使用一般的統(tǒng)計技術可以解決，但是對于兩個集合來說就不能由一般的技術來處理；同時它對于兩個相關的屬性集合來說又是很重要的因素，僅僅知道其相關是不夠的，還知道如何相關，即它們之間如何相互影響。

本文提出了全局相關的概念及其量化方法[10]，并通過對該策略進行改進，使用非線性相關分析技術，以及將數(shù)據(jù)表示為布爾序列的形式，來處理以上提出的問題。給出了非線性相關發(fā)現(xiàn)（NLCD）算法，使用實際數(shù)據(jù)進行驗證，通過與LCD算法進行對比后得出，本文算法具有更強的應用價值。

1 相關的概念

1.1 相關類型

首先給出有關規(guī)范關聯(lián)規(guī)則的概念。設I={i₁，i₂，…，i_m}是項集。其中ik(k=₁，₂，…，_m)可以是購物籃中的物品，也可以是保險公司的顧客。設任務相關的數(shù)據(jù)，其中每個事務T是項集，即TI。則關聯(lián)規(guī)則可以表示為

本文需要考慮的是屬性集合之間的定性和定量的關系，即發(fā)現(xiàn)具有一定關系的屬性或屬性集合的相關規(guī)則。為此假設事務數(shù)據(jù)為n個對象m個屬性的陣列，采用布爾序列

定義布爾序列對的相關函數(shù)f(x，y)，這里的x和y是維數(shù)為t的布爾序列，即

同樣可以得到關于多序列的全正相關、k正相關、完全負相關、k負相關的定義。對于這些定義需要說明一下，通過逐一比較序列對應位置的布爾值相同的個數(shù)來確定是否相關，只有兩個序列完全相同時才會有x∧y的各位是全1的序列，即式(1)所示，此時它們是等價的，故而定義為完全正相關；有k個位置相同的稱為k正相關；如果兩個序列位值均相反時它們完全相反，此時它們的變化是反向的，把這種關系定為完全負相關；同樣有k個位置相反的稱為k負相關。

1.2 全局相關度量

本文關于全局相關度量的概念取自于Bo L.等人的文章。經(jīng)典的相關性分析都是基于相關因素的概率分布描述的，使用的是統(tǒng)計的策略。全局相關度量考慮相關因素的整體度量，從而確定它們相關的定量指標。下面給出形式化描述。

由表1通過一遍元數(shù)據(jù)掃描可以得到其布爾序列表示(表2)，以后的相關發(fā)現(xiàn)就只是在這個布爾陣列上面進行。

該算法分三個步驟來完成各種相關類型屬性集合的發(fā)現(xiàn)：

(1)數(shù)據(jù)的規(guī)范化，即將事務數(shù)據(jù)集合轉換為用全部屬性長度的布爾序列表示(表2)。

(2)基于完全正相關類型的規(guī)范化數(shù)據(jù)集合的劃分，即要得到彼此獨立的完全正相關分類，為它們之間更為詳細的相關作準備。

(3)在各個完全正相關劃分之間判斷相關類型，從而確定其他各種相關類型以及定量描述。

3 數(shù)據(jù)實證

本文的實驗環(huán)境是Intel Pentium 4，1843 MHz CPU，DDR 512 MB的臺式電腦。 實驗利用了兩個人工數(shù)據(jù)集(T15I5D100k和 T25I10D10k)，該數(shù)據(jù)具有較低的相關性；另外使用一個具有較強相關性的數(shù)據(jù)集(Connect—4) [11]（這些數(shù)據(jù)規(guī)格的說明如表3所示）；并且與算法LCD作比較。表4是實驗結果以及其分析報告。

通過實證，該算法具有比較好的運行速度（約占LCD的66.9％），在相關性規(guī)則發(fā)現(xiàn)上有很大的改進，不但可以發(fā)現(xiàn)較多的相關規(guī)則，而且能夠區(qū)分不同的相關類型。

4 結束語

本文討論了在數(shù)據(jù)相關性挖掘過程中的相關性類型以及其定量描述的問題，引入了非線性相關和全局相關的概念及其度量方法，給出了相應的NLCD算法。這些工作是對以往的關聯(lián)規(guī)則挖掘概念及技術的推廣。這樣有利于從整體來分析和量化相關的事務，特別是金融業(yè)務的整體相關評估以及投資組合的優(yōu)化問題。關于這方面的應用是筆者正在進行的工作。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。