基于候選集的相似度度量的計算

王夢迪　程玉勝

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

關鍵詞：數據挖掘；關聯規則；事務間關聯規則

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

0 引言

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

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

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

1 相似關聯規則挖掘算法

1.1 興趣度及其相似度量

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

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

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

1.2 相似度度量方法

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

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

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

2.1 基于相似度候選集挖掘

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

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

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

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

例3：對例2事務數據庫（maxspan=3）轉換

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

3 結束語

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

參 考 文 獻

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

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

[3] 楊國靜.基于數據挖掘的高校教學數據分析研究[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] 陳永峰.大數據背景下數據挖掘在高校固定資產統計中的應用研究[J].河北軟件職業技術學院學報，2015（2）：6-9.

[7] 李勇，陳新華，朱建平，等.第七屆國際數據挖掘與應用統計研究會學術綜述[J].統計與信息論壇，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] 陳艷，褚光磊.關聯規則挖掘算法在股票預測中的應用研究——基于遺傳網絡規劃的方法[J].管理現代化，2014，34（3）：13-15，39.

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

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

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