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

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

基于模擬退火的量化空間關(guān)聯(lián)規(guī)則挖掘

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

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

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

空間關(guān)聯(lián)規(guī)則；量化關(guān)聯(lián)規(guī)則；FP-growth；模擬退火

關(guān)聯(lián)規(guī)則挖掘最先由Agrawal[1]等提出，并應(yīng)用于商業(yè)活動(dòng)[2]，旨在挖掘形如A→B（support，confidence）形式的規(guī)則。然而當(dāng)面對(duì)結(jié)構(gòu)復(fù)雜同時(shí)隱含著豐富而又不明確空間關(guān)系的空間數(shù)據(jù)[3]時(shí)，這些方法無(wú)法有效地從中得到空間數(shù)據(jù)的關(guān)聯(lián)規(guī)則。針對(duì)此問題，Koperski[4]和Han首次將關(guān)聯(lián)規(guī)則擴(kuò)展并引入空間數(shù)據(jù)挖掘領(lǐng)域，提出了一種空間關(guān)聯(lián)規(guī)則挖掘方法，后來逐步形成了空間關(guān)聯(lián)規(guī)則挖掘[5-6]。目前大多數(shù)的空間關(guān)聯(lián)規(guī)則挖掘方法只能得到形如A→B定性的關(guān)系，無(wú)法得到其定量關(guān)系。然而在實(shí)際生產(chǎn)生活中定量的關(guān)聯(lián)規(guī)則對(duì)決策更有幫助，如利用城市內(nèi)地址點(diǎn)定量關(guān)聯(lián)規(guī)則指導(dǎo)城市規(guī)劃和地址選址。

1 基于FP-growth的包含事務(wù)信息關(guān)聯(lián)規(guī)則挖掘

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

由于構(gòu)建FP-tree時(shí)，只針對(duì)事務(wù)數(shù)據(jù)庫(kù)中項(xiàng)的類型計(jì)數(shù)，并不記錄每個(gè)節(jié)點(diǎn)對(duì)的事務(wù)數(shù)據(jù)，因此最后得到的關(guān)聯(lián)規(guī)則也沒有對(duì)應(yīng)的事務(wù)信息，無(wú)法進(jìn)行量化規(guī)則挖掘。本文針對(duì)該問題，對(duì)現(xiàn)有FP-tree進(jìn)行了部分改進(jìn)，為樹中每個(gè)節(jié)點(diǎn)增加了其對(duì)應(yīng)的事務(wù)信息。對(duì)表1中的事務(wù)數(shù)據(jù)構(gòu)建包含事務(wù)信息的FP-tree結(jié)構(gòu)，如圖1所示。圖中每個(gè)節(jié)點(diǎn)信息中{}內(nèi)為事務(wù)信息，具體對(duì)應(yīng)如表2所示。

表1 事務(wù)數(shù)據(jù)

圖1 包含事務(wù)信息的FP-tree

表2 FP-tree事務(wù)集對(duì)照表

對(duì)數(shù)據(jù)構(gòu)建包含事務(wù)信息的FP-tree后，便可使用FP-growth提取包含事務(wù)信息的頻繁模式，例如由圖1中FP-tree可以得到后綴C7的頻繁模式，其中，“C2,C1,C6,C7”為頻繁模式；“3”為支持度計(jì)數(shù)；“”為頻繁模式對(duì)應(yīng)的事務(wù)數(shù)據(jù)。對(duì)于事務(wù)T1{C2,C4,C6}，其構(gòu)成的FP-tree分支為C2-C6-C4，該分支內(nèi)每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的事務(wù)數(shù)據(jù)均為T1，因此最后組成的FP-tree中C2-C6-C4分支內(nèi)每個(gè)節(jié)點(diǎn)都包含事務(wù)數(shù)據(jù)T1。

2 基于模擬退火的量化關(guān)聯(lián)規(guī)則提取

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

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

其中，

若m個(gè)項(xiàng)表示有m維，n個(gè)事務(wù)數(shù)據(jù)表示n個(gè)m維空間的點(diǎn)，則該公式可看作是n個(gè)m維空間的點(diǎn)到這n個(gè)點(diǎn)的中心的距離的平均值。f（T）越小，說明n個(gè)點(diǎn)分布越集中，n條事務(wù)數(shù)據(jù)的數(shù)值區(qū)間也就越小。最后通過模擬退火對(duì)包含事務(wù)信息的關(guān)聯(lián)規(guī)則進(jìn)行進(jìn)一步挖掘，可以得到形如的關(guān)聯(lián)規(guī)則，關(guān)聯(lián)規(guī)則中每項(xiàng)后邊都包含該項(xiàng)的量化區(qū)間信息。

3 實(shí)驗(yàn)分析

3.1 數(shù)據(jù)準(zhǔn)備

本文使用某市市區(qū)內(nèi)各類地址數(shù)據(jù)進(jìn)行量化空間關(guān)聯(lián)規(guī)則挖掘，共計(jì)8類地址數(shù)據(jù)，34 405個(gè)數(shù)據(jù)點(diǎn)，各類數(shù)據(jù)的代號(hào)和數(shù)量如表3所示。

表3 實(shí)驗(yàn)數(shù)據(jù)類別和數(shù)量情況

為了進(jìn)行量化關(guān)聯(lián)規(guī)則挖掘，將所有的數(shù)據(jù)點(diǎn)按該市的社區(qū)一級(jí)行政區(qū)劃分成230個(gè)區(qū)域，每個(gè)區(qū)域看作一個(gè)事務(wù)，并構(gòu)建對(duì)應(yīng)的事務(wù)數(shù)據(jù)庫(kù)。行政區(qū)劃示意圖見圖2。

圖2 社區(qū)行政區(qū)劃示意圖

3.2 提取包含事務(wù)的量化關(guān)聯(lián)規(guī)則

在進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)，當(dāng)支持度相同、置信度較高時(shí)得到的關(guān)聯(lián)規(guī)則集一定是置信度較低時(shí)得到關(guān)聯(lián)規(guī)則集的子集；當(dāng)置信度相同、支持度較高時(shí)得到的關(guān)聯(lián)規(guī)則集一定是支持度較低時(shí)得到關(guān)聯(lián)規(guī)則集的子集；當(dāng)支持度不變時(shí)，得到的關(guān)聯(lián)規(guī)則數(shù)量隨置信度的增加而減少；當(dāng)置信度不變時(shí)，得到的關(guān)聯(lián)規(guī)則數(shù)量隨置信度的增加而減少。

于是，在進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)，為了研究支持度和置信度對(duì)關(guān)聯(lián)規(guī)則產(chǎn)生結(jié)果的影響，只需抽取幾個(gè)置信度和支持度的值進(jìn)行實(shí)驗(yàn)即可獲得在此區(qū)間內(nèi)產(chǎn)生關(guān)聯(lián)規(guī)則的整體趨勢(shì)。本文實(shí)驗(yàn)分別采用的支持度為30%、40%、50%、60%、70%、80%，置信度為40%、50%、60%、70%、80%、90%。以前文得到的事務(wù)數(shù)據(jù)庫(kù)為數(shù)據(jù)，對(duì)支持度和置信度交叉配對(duì)依次進(jìn)行關(guān)聯(lián)規(guī)則挖掘，共進(jìn)行36次實(shí)驗(yàn)，每次所得關(guān)聯(lián)規(guī)則個(gè)數(shù)如表4所示。

表4 不同支持度和置信度下得到的規(guī)則數(shù)量

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

表5 關(guān)聯(lián)規(guī)則

3.3 提取量化規(guī)則

得到關(guān)聯(lián)規(guī)則后，根據(jù)其對(duì)應(yīng)的事務(wù)數(shù)據(jù)集可直接找到其對(duì)應(yīng)的關(guān)系數(shù)據(jù)。表6中所示為規(guī)則{醫(yī)院，餐飲，娛樂}→商店對(duì)應(yīng)的5條事務(wù)數(shù)據(jù)。

表6 事務(wù)數(shù)據(jù)

由于按行政區(qū)劃劃分后得到的規(guī)模大小不一，因此每個(gè)區(qū)域內(nèi)包含的數(shù)據(jù)總量也不一樣。當(dāng)區(qū)域的規(guī)模相差較大時(shí)，2個(gè)區(qū)域內(nèi)包含的數(shù)據(jù)總量也相差較大，轉(zhuǎn)換得到的關(guān)系數(shù)據(jù)庫(kù)中，同一類型項(xiàng)目的絕對(duì)數(shù)量也就可能相差較大，如表6中第1條數(shù)據(jù)與第2條數(shù)據(jù)相差10倍之多。當(dāng)項(xiàng)目數(shù)量相差較大時(shí)，無(wú)法根據(jù)關(guān)系數(shù)據(jù)庫(kù)得到各項(xiàng)目間的準(zhǔn)確絕對(duì)數(shù)量關(guān)系。因此需要對(duì)數(shù)據(jù)進(jìn)行變化，對(duì)每一條事務(wù)數(shù)據(jù)進(jìn)行數(shù)據(jù)歸一，注重每條事務(wù)中各項(xiàng)的比例關(guān)系，忽略事務(wù)中所有項(xiàng)的數(shù)據(jù)總量，將所有的事務(wù)數(shù)據(jù)的數(shù)據(jù)總量統(tǒng)一，使所有事務(wù)數(shù)據(jù)具有相同的權(quán)重。因此，對(duì)規(guī)則對(duì)應(yīng)的事務(wù)數(shù)據(jù)進(jìn)行歸一化，表6中的數(shù)據(jù)歸一化后如表7所示。

表7 歸一化后的事務(wù)數(shù)據(jù)

表8 量化關(guān)聯(lián)規(guī)則

量化關(guān)聯(lián)規(guī)則中，每項(xiàng)后小括號(hào)內(nèi)2個(gè)數(shù)值表示該項(xiàng)在量化關(guān)聯(lián)規(guī)則所有項(xiàng)中所占比例的上下閾值。例如，表8中第1條量化關(guān)聯(lián)規(guī)則{學(xué)校（0.01,0.12），醫(yī)院（0.02,0.12）}→商店（0.78,0.97），某區(qū)域內(nèi)學(xué)校、醫(yī)院和商店三者中，學(xué)校所占比例在0.01～0.12，且醫(yī)院所占比例在0.02～0.12時(shí)，商店所占比例應(yīng)該在0.78～0.97。根據(jù)得到的量化關(guān)聯(lián)規(guī)則，可以找到該市商店數(shù)量過剩的區(qū)域，如圖3中紅色區(qū)域所示。根據(jù)此結(jié)果，在為新商店選址時(shí)可以避開這些區(qū)域，為選址提供參考信息。

P208

B

1672-4623（2016）05-0008-03

10.3969/j.issn.1672-4623.2016.05.003

2015-04-10。

項(xiàng)目來源：國(guó)家自然科學(xué)基金資助項(xiàng)目（41271392）；國(guó)家自然科學(xué)基金青年基金資助項(xiàng)目（41401463）；河南省科技攻關(guān)計(jì)劃（高新技術(shù)領(lǐng)域）資助項(xiàng)目。