王夢迪　程玉勝

摘 要：關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘作為數(shù)據(jù)挖掘的一種重要模式，已成為目前數(shù)據(jù)挖掘領(lǐng)域的一個非常重要的研究課題。其中如何度量和尋找有效的候選集一直是眾多學者研究的課題之一。本文在置信度及其興趣度度量的基礎上，提出了產(chǎn)生候選集的相似度度量計算方法，并對比了該方法和置信度及其興趣度之間的聯(lián)系，并利用相關(guān)結(jié)論進一步討論了大數(shù)據(jù)集環(huán)境下如何更加有效地計算相似度的度量計算方法。

關(guān)鍵詞：數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；事務間關(guān)聯(lián)規(guī)則

中圖分類號： TP274 文獻標識碼： A 文章編號： 1673-1069（2016）12-145-3

0 引言

關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘分為事務內(nèi)關(guān)聯(lián)規(guī)則（Intra-Transaction）的數(shù)據(jù)挖掘和事務間（Inter-Transaction）關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘。非經(jīng)典關(guān)聯(lián)規(guī)則挖掘始終會面臨所謂的“高階邏輯”問題。對股價描述，特別是對一些基于（標的股票）價格之上的衍生資產(chǎn)，如期貨或期權(quán)，這樣的表述會更準確些，即在N維空間下（隨機過程）的套利測量場。對其直接套用泛Apriori算法是不合適的。

當以基于事務的觀點應用滑動窗口技術(shù)將股票原始事務數(shù)據(jù)庫D轉(zhuǎn)化為擴展事務數(shù)據(jù)庫De時會大量出現(xiàn)這樣一個很有趣（是因為它有別于經(jīng)典購物籃的高支持度）也很值得注意的現(xiàn)象。因為得到的擴展事務數(shù)據(jù)庫De往往會很大數(shù)據(jù)集很豐富，但就某只股票在某個時間點上的事件出現(xiàn)頻率計數(shù)。（例如，如果以一只股票當天收盤價比上一天收盤價超過2%作為一次事件發(fā)生記為1否則記為0。那么就在前不久，上證指數(shù)從16.01.04開盤的3536.59一路跌到16.01.29收于2737.60。期間共有二十個交易日，1只出現(xiàn)過三次，其他都記為0。支持度為3/20=0.15。韶鋼松山從16.01.04開盤價14.28元一路跌到16.01.29的收盤價12.21元。期間共有20個交易日，1出現(xiàn)了5次，其他都記為0。支持度為5/20=0.25。顯然，它們的支持度都很低。那么能由此推斷出走勢背后的資金流沒有關(guān)聯(lián)嗎？肯定不是，資金流之間的進出絕對是有關(guān)聯(lián)的。這其中暗藏的有趣關(guān)聯(lián)肯定還不少。）與整個擴展事務數(shù)據(jù)庫De數(shù)據(jù)集相比結(jié)果很小甚至小到都可不予考慮即支持度顯然很低。然而依“規(guī)則的可信度是指包含I1和I2的事務數(shù)與包含I1的事務數(shù)之比”來看置信度卻較高。這其中有許多有趣的關(guān)聯(lián)規(guī)則它們支持度很低但置信度卻較高，如果一味用傳統(tǒng)的挖掘算法會很難發(fā)現(xiàn)這些（有趣的）關(guān)聯(lián)規(guī)則。

事務間關(guān)聯(lián)規(guī)則通常的支持度都較低。在對支持度很低但置信度很高的關(guān)聯(lián)規(guī)則進行挖掘時，用最小支持度門檻值的算法顯然不夠有效。對此本文打算用相似度來衡量事務間可能產(chǎn)生關(guān)聯(lián)規(guī)則的項，進而得到事務間關(guān)聯(lián)規(guī)則，而且還可用來挖掘感興趣的事務間多個項間排斥規(guī)則。

1 相似關(guān)聯(lián)規(guī)則挖掘算法

1.1 興趣度及其相似度量

復旦大學的施伯樂教授在文獻中提出了基于差異思想的興趣度定義，用以指導關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)。其定義規(guī)則X=>Y的興趣度為：

這個定義是由關(guān)聯(lián)規(guī)則的支持度和可信度而產(chǎn)生的，分母只是個標準化因子，使得| Interest（X=>Y）|<1。根據(jù)這個定義，一條關(guān)聯(lián)規(guī)則的興趣度越大于0，說明對這條規(guī)則越感興趣；一條關(guān)聯(lián)規(guī)則的興趣度越小于0，說明對這條規(guī)則的反面規(guī)則越感興趣。

可事先由用戶指定最小興趣度閥值minInterest，若Interest（X=>Y）的絕對值越大于minInterest，說明Y的支持度與規(guī)則X=>Y的信任度的差異越大，我們說規(guī)則X=>Y是新奇的，用戶對這些規(guī)則越感興趣；若Interest（X=>Y）的絕對值小于minInterest時，說明Y的支持度與規(guī)則X=>Y的信任度差異較小，則可以說規(guī)則X=>Y不是新奇的，不會引起用戶對該規(guī)則感興趣。

1.2 相似度度量方法

事務間的特征或多或少都會存在一定的相似性，相似性是普遍存在的，其間差別只在相似程度多少而已。具有高支持度的關(guān)聯(lián)規(guī)則往往是顯然的大家比較熟悉的規(guī)則，而相比較而言，低支持度關(guān)聯(lián)規(guī)則可能更具新穎性和有趣性。

相似關(guān)聯(lián)規(guī)則挖掘的初衷是用置信度度量來替代支持度度量，為了便于運算引入了相似度度量，因為它極好地近似了置信度的概念。對原始數(shù)據(jù)庫利用相似度進行關(guān)聯(lián)規(guī)則挖掘，首先需要把原始數(shù)據(jù)庫轉(zhuǎn)換成0/1矩陣。轉(zhuǎn)換方法是：原始數(shù)據(jù)庫的每一項將生成新0/1矩陣的一列；原始數(shù)據(jù)庫的每一個事務將生成新0/1矩陣的一行。如果第i個項在第j個事務中出現(xiàn)，那么這個矩陣的第j行第i列取值為1，反之沒有出現(xiàn)就取值為0。

2 基于相似度及其最小哈希變換的候選集挖掘

2.1 基于相似度候選集挖掘

鑒別相似列對的算法包括三個階段：計算特征標識、產(chǎn)生候選集和對已產(chǎn)生候選集進行剪枝。第一階段首先是掃描整個數(shù)據(jù)庫進而為每列生成一個小的哈希特征標識。這一步主要是對存放在外存上的大規(guī)模數(shù)據(jù)進行一次概括性的處理以便能把初步處理結(jié)果存入內(nèi)存，好在內(nèi)存中對其操作。第二階段，在內(nèi)存操作中，根據(jù)列特征標識生成候選對。最后階段，再一次掃描原始數(shù)據(jù)庫來決定每一候選對是否確實具有高的相似度。在掃描數(shù)據(jù)庫時，為每個候選列對（Ci，Cj）計算兩個計數(shù)：一個是在兩列中至少有一列中有1的行的個數(shù)，即Ci∪Cj，另一個是當兩列中同一行都為1的行的數(shù)目，即Ci∩Cj。

2.2 基于最小哈希變換的候選集挖掘

先將原始事務數(shù)據(jù)庫轉(zhuǎn)換成擴展了的大事務數(shù)據(jù)庫，再按照擴展項是否出現(xiàn)再轉(zhuǎn)換成0/1數(shù)據(jù)庫M。如果原始數(shù)據(jù)庫有n個事務，m個項，maxspan=w，則M成為了n行，m×w列的0/1矩陣。然后確定要置換變換的k值。k值可根據(jù)事務數(shù)據(jù)庫事務總數(shù)及對變換后所得矩陣與原始陣的相似度要求來確定。

最小哈希變換的候選集挖掘偽碼：

例3：對例2事務數(shù)據(jù)庫（maxspan=3）轉(zhuǎn)換

可見通過哈希法對矩陣M的轉(zhuǎn)化，不僅降低了矩陣的大小，而且很好地保持了原矩陣M的相似度。

3 結(jié)束語

相似性研究認為事務間的特征或多或少都會存在一定的相似性，相似性是普遍存在的，其間差別只在相似程度多少而已。這種繼承性和相似性反映在以往的數(shù)據(jù)上可使我們得到很多設計靈感，特征間不同程度的相似性具有重要的啟發(fā)和借鑒作用。這一觀點對海量數(shù)據(jù)挖掘知識發(fā)現(xiàn)尤顯重要。本文使用最小哈希方法可減少矩陣的行數(shù)，這使運算對象在縱向上數(shù)量大量減少，但如果在項數(shù)較大的情況下，運算對象在橫向上的數(shù)量就會大量增加，所占空間也就會相應增大，如考慮把它放入內(nèi)存恐有困難，這也需要繼續(xù)研究。

參 考 文 獻

[1] JiaWei Han，Micheline Kamber著.范明，孟小峰譯.數(shù)據(jù)挖掘[M].機械工業(yè)出版社，2001，第一版，14-18.

[2] 劉紹清.基于頻繁項集分類統(tǒng)計的增量式關(guān)聯(lián)規(guī)則應用[J].重慶工商大學學報（自然科學版），2015，32（12）：43-47.

[3] 楊國靜.基于數(shù)據(jù)挖掘的高校教學數(shù)據(jù)分析研究[D].河北師范大學，2015.

[4] Edith Cohen，Mayur Datar，Shinji Fujiwara，etc..Finding Interesting Associations without Support Pruning.IEEE Trans.on Knowledge and Data Eng.，2001，13（1）：64-77.

[5] Anthony K.H. Tung， Hongjun Lu，Jiawei Han，etc..Efficient Mining of Intertrsaction Association Rules. IEEE Trans. on Knowledge and Data Eng.2003，15（1），43.

[6] 陳永峰.大數(shù)據(jù)背景下數(shù)據(jù)挖掘在高校固定資產(chǎn)統(tǒng)計中的應用研究[J].河北軟件職業(yè)技術(shù)學院學報，2015（2）：6-9.

[7] 李勇，陳新華，朱建平，等.第七屆國際數(shù)據(jù)挖掘與應用統(tǒng)計研究會學術(shù)綜述[J].統(tǒng)計與信息論壇，2015（10）：111-111.

[8] J.Hna，J.Pei.Mining Frequent Patterns Without Candidate Generation. In Proc.2000 ACM-SIGMOD Intl. Contf.on Management of Data（SIGMOD′2000）Dallas TX 2000，1-12.

[9] 陳艷，褚光磊.關(guān)聯(lián)規(guī)則挖掘算法在股票預測中的應用研究——基于遺傳網(wǎng)絡規(guī)劃的方法[J].管理現(xiàn)代化，2014，34（3）：13-15，39.

[10] 陳健.人工神經(jīng)網(wǎng)絡模型在股票價格預測問題中的實證研究[D].南開大學，2014.

[11] 褚光磊.進化算法在數(shù)據(jù)挖掘與金融工程中的應用研究[D].上海財經(jīng)大學，2014.

[12] 張筱梅，朱家明.基于Pearson相關(guān)系數(shù)模型對股票間相關(guān)性研究[J].赤峰學院學報（自然科學版），2015（10）：32-33.