基于模擬退火的量化空間關聯規則挖掘

杜澤欣，李宏偉，連世偉，周 海，范瑞杰

（1.信息工程大學 地理空間信息學院，河南 鄭州 450000；2. 61206部隊，北京 100042）

基于模擬退火的量化空間關聯規則挖掘

杜澤欣1，李宏偉1，連世偉1，周 海1，范瑞杰2

（1.信息工程大學 地理空間信息學院，河南 鄭州 450000；2. 61206部隊，北京 100042）

目前在空間關聯規則挖掘研究中，對數據的處理和算法的改進主要針對布爾關聯規則挖掘，存在對空間關聯規則的量化表示不夠重視等問題。在FP-growth算法的基礎上增加規則的事務信息，并使用模擬退火算法，對得到的規則進行進一步挖掘，得到量化空間關聯規則。

空間關聯規則；量化關聯規則；FP-growth；模擬退火

關聯規則挖掘最先由Agrawal[1]等提出，并應用于商業活動[2]，旨在挖掘形如A→B（support，confidence）形式的規則。然而當面對結構復雜同時隱含著豐富而又不明確空間關系的空間數據[3]時，這些方法無法有效地從中得到空間數據的關聯規則。針對此問題，Koperski[4]和Han首次將關聯規則擴展并引入空間數據挖掘領域，提出了一種空間關聯規則挖掘方法，后來逐步形成了空間關聯規則挖掘[5-6]。目前大多數的空間關聯規則挖掘方法只能得到形如A→B定性的關系，無法得到其定量關系。然而在實際生產生活中定量的關聯規則對決策更有幫助，如利用城市內地址點定量關聯規則指導城市規劃和地址選址。

1 基于FP-growth的包含事務信息關聯規則挖掘

FP-growth即頻繁模式增長，是由Han[7]等在2000年提出的。該算法為提高挖掘效率、解決關聯規則提取時需要重復掃描數據庫而產生大量候選項集的問題而提出的。它采取如下策略：首先，將代表頻繁項集的事務數據庫壓縮到一棵FP-tree，該樹仍保留頻繁項集的關聯規則；然后，將壓縮后的FP-tree劃分成一組條件數據庫，其中每一個數據庫關聯一個頻繁項或“模式段”，對每個數據庫進行挖掘。因此，對于每個頻繁項，只需考察與其相關聯的數據庫，隨著被考察的模式的“增長”，這種方法可以顯著壓縮被搜索的數據集大小。

由于構建FP-tree時，只針對事務數據庫中項的類型計數，并不記錄每個節點對的事務數據，因此最后得到的關聯規則也沒有對應的事務信息，無法進行量化規則挖掘。本文針對該問題，對現有FP-tree進行了部分改進，為樹中每個節點增加了其對應的事務信息。對表1中的事務數據構建包含事務信息的FP-tree結構，如圖1所示。圖中每個節點信息中{}內為事務信息，具體對應如表2所示。

表1 事務數據

圖1 包含事務信息的FP-tree

表2 FP-tree事務集對照表

對數據構建包含事務信息的FP-tree后，便可使用FP-growth提取包含事務信息的頻繁模式，例如由圖1中FP-tree可以得到后綴C7的頻繁模式，其中，“C2,C1,C6,C7”為頻繁模式；“3”為支持度計數；“”為頻繁模式對應的事務數據。對于事務T1{C2,C4,C6}，其構成的FP-tree分支為C2-C6-C4，該分支內每個節點對應的事務數據均為T1，因此最后組成的FP-tree中C2-C6-C4分支內每個節點都包含事務數據T1。

2 基于模擬退火的量化關聯規則提取

本文提取量化關聯規則的基本思路為：假設進行關聯規則挖掘的數據總個數為N，挖掘時設定的最小支持度和最小置信度分別為min_support和min_ confidence，則一條關聯規則最少需要n條數據支持（n=min_support×N）。對于一條已得到的關聯規則AR，共有m條事務符合該條關聯規則，要提取該關聯規則AR的量化表示，即從支持AR的m條數據中選出n條數據，同時使這n條數據的屬性區間盡可能小，使用最終得到的n條數據的數據區間作為關聯規則AR的量化表示。由于該量化關聯規則使用n條數據的數據區間，所以至少有n條數據滿足該量化關聯規則，也就滿足了關聯規則的最小支持度限制；同時這n條數據本身就滿足關聯規則AR，也就保證了其滿足最小置信度閾值。因此，量化關聯規則的提取也就轉換成了從m條數據中挑選n條數據，并使n條數據的數據區間盡量小的問題。假設m=100，n=50，如果要遍歷所有選擇可能，則需要計算種組合，這已經是一個天文數字，當數據量增加時，組合的情況會更多，因此要使用組合優化算法進行量化信息的提取。本文選用模擬退火算法進行組合優化選擇。

模擬退火[8]算法的基本思想是模擬熱力學中的退火過程，整個過程符合Metropolis準則[9]。該準則可以使算法在進行組合選擇時跳出局部最優解，得到全局最優解。在使用模擬退火過程中，需要設定退火過程中的狀態能量函數f（T）來判斷每種組合的優劣。假設需要量化的關聯規則前件和后件共有m項，模擬退火選取的n個事務分別為T1，T2，…，Tn，對于事務Ti，i∈（1，n），其m個項的值分別為，，…，在量化關聯規則提取中，得到的量化區間越小，規則的可用性就越強，因此，參照多維空間距離公式設計了n條事務組合的狀態能量函數f（T）為：

其中，

若m個項表示有m維，n個事務數據表示n個m維空間的點，則該公式可看作是n個m維空間的點到這n個點的中心的距離的平均值。f（T）越小，說明n個點分布越集中，n條事務數據的數值區間也就越小。最后通過模擬退火對包含事務信息的關聯規則進行進一步挖掘，可以得到形如的關聯規則，關聯規則中每項后邊都包含該項的量化區間信息。

3 實驗分析

3.1 數據準備

本文使用某市市區內各類地址數據進行量化空間關聯規則挖掘，共計8類地址數據，34 405個數據點，各類數據的代號和數量如表3所示。

表3 實驗數據類別和數量情況

為了進行量化關聯規則挖掘，將所有的數據點按該市的社區一級行政區劃分成230個區域，每個區域看作一個事務，并構建對應的事務數據庫。行政區劃示意圖見圖2。

圖2 社區行政區劃示意圖

3.2 提取包含事務的量化關聯規則

在進行關聯規則挖掘時，當支持度相同、置信度較高時得到的關聯規則集一定是置信度較低時得到關聯規則集的子集；當置信度相同、支持度較高時得到的關聯規則集一定是支持度較低時得到關聯規則集的子集；當支持度不變時，得到的關聯規則數量隨置信度的增加而減少；當置信度不變時，得到的關聯規則數量隨置信度的增加而減少。

于是，在進行關聯規則挖掘時，為了研究支持度和置信度對關聯規則產生結果的影響，只需抽取幾個置信度和支持度的值進行實驗即可獲得在此區間內產生關聯規則的整體趨勢。本文實驗分別采用的支持度為30%、40%、50%、60%、70%、80%，置信度為40%、50%、60%、70%、80%、90%。以前文得到的事務數據庫為數據，對支持度和置信度交叉配對依次進行關聯規則挖掘，共進行36次實驗，每次所得關聯規則個數如表4所示。

表4 不同支持度和置信度下得到的規則數量

由表4可以看出，當置信度不變時，支持度由30%增長到50%，規則的數目變化不大，而從50%到80%的每次增長規則數目都會急劇減小；當支持度不變時，置信度增加，規則數目減少幅度較小。由此可見，該關聯規則挖掘得到的所有結果置信度基本趨于穩定且置信度較高，因此，使用置信度無法有效地對規則進行篩選；同時，在支持度小于50%時，支持度變化對規則數目影響也很小，只有支持度從50%增長到60%和從60%增長到70%兩次變化時，規則數目下降較快，達到了對規則很好的篩選效果。本文選取支持度為70%，置信度為80%時得到的32條規則進行進一步挖掘。對生成的32條規則進行整理，如果規則A與規則B的后件相同，且B的前件是A的前件的子集，則只保留規則A，最后得到3條典型的關聯規則，如表5所示。由于在挖掘過程中始終保留著事務信息，因此得到的量化規則也保留了其對應事務數據集。

表5 關聯規則

3.3 提取量化規則

得到關聯規則后，根據其對應的事務數據集可直接找到其對應的關系數據。表6中所示為規則{醫院，餐飲，娛樂}→商店對應的5條事務數據。

表6 事務數據

由于按行政區劃劃分后得到的規模大小不一，因此每個區域內包含的數據總量也不一樣。當區域的規模相差較大時，2個區域內包含的數據總量也相差較大，轉換得到的關系數據庫中，同一類型項目的絕對數量也就可能相差較大，如表6中第1條數據與第2條數據相差10倍之多。當項目數量相差較大時，無法根據關系數據庫得到各項目間的準確絕對數量關系。因此需要對數據進行變化，對每一條事務數據進行數據歸一，注重每條事務中各項的比例關系，忽略事務中所有項的數據總量，將所有的事務數據的數據總量統一，使所有事務數據具有相同的權重。因此，對規則對應的事務數據進行歸一化，表6中的數據歸一化后如表7所示。

表7 歸一化后的事務數據

表8 量化關聯規則

量化關聯規則中，每項后小括號內2個數值表示該項在量化關聯規則所有項中所占比例的上下閾值。例如，表8中第1條量化關聯規則{學校（0.01,0.12），醫院（0.02,0.12）}→商店（0.78,0.97），某區域內學校、醫院和商店三者中，學校所占比例在0.01～0.12，且醫院所占比例在0.02～0.12時，商店所占比例應該在0.78～0.97。根據得到的量化關聯規則，可以找到該市商店數量過剩的區域，如圖3中紅色區域所示。根據此結果，在為新商店選址時可以避開這些區域，為選址提供參考信息。

P208

B

1672-4623（2016）05-0008-03

10.3969/j.issn.1672-4623.2016.05.003

2015-04-10。

項目來源：國家自然科學基金資助項目（41271392）；國家自然科學基金青年基金資助項目（41401463）；河南省科技攻關計劃（高新技術領域）資助項目。