基于非線性相關發現的數據挖掘算法

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

關鍵詞：數據挖掘； 關聯規則挖掘； 線性相關性發現； 全局相關性； 非線性相關發現

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

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

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

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

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

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

1 相關的概念

1.1 相關類型

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

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

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

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

1.2 全局相關度量

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

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

該算法分三個步驟來完成各種相關類型屬性集合的發現：

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

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

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

3 數據實證

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

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

4 結束語

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

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