亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2016-12-27 02:36:32杜澤欣李宏偉連世偉范瑞杰
        地理空間信息 2016年5期
        關鍵詞:模擬退火置信度事務

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

        (1.信息工程大學 地理空間信息學院,河南 鄭州 450000;2. 61206部隊,北京 100042)

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

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

        (1.信息工程大學 地理空間信息學院,河南 鄭州 450000;2. 61206部隊,北京 100042)

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

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

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

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

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

        由于構建FP-tree時,只針對事務數據庫中項的類型計數,并不記錄每個節(jié)點對的事務數據,因此最后得到的關聯(lián)規(guī)則也沒有對應的事務信息,無法進行量化規(guī)則挖掘。本文針對該問題,對現(xiàn)有FP-tree進行了部分改進,為樹中每個節(jié)點增加了其對應的事務信息。對表1中的事務數據構建包含事務信息的FP-tree結構,如圖1所示。圖中每個節(jié)點信息中{}內為事務信息,具體對應如表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,該分支內每個節(jié)點對應的事務數據均為T1,因此最后組成的FP-tree中C2-C6-C4分支內每個節(jié)點都包含事務數據T1。

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

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

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

        其中,

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

        3 實驗分析

        3.1 數據準備

        本文使用某市市區(qū)內各類地址數據進行量化空間關聯(lián)規(guī)則挖掘,共計8類地址數據,34 405個數據點,各類數據的代號和數量如表3所示。

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

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

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

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

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

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

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

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

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

        3.3 提取量化規(guī)則

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

        表6 事務數據

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

        表7 歸一化后的事務數據

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

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

        P208

        B

        1672-4623(2016)05-0008-03

        10.3969/j.issn.1672-4623.2016.05.003

        2015-04-10。

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

        猜你喜歡
        模擬退火置信度事務
        “事物”與“事務”
        基于分布式事務的門架數據處理系統(tǒng)設計與實現(xiàn)
        硼鋁復合材料硼含量置信度臨界安全分析研究
        河湖事務
        模擬退火遺傳算法在機械臂路徑規(guī)劃中的應用
        測控技術(2018年3期)2018-11-25 09:45:08
        正負關聯(lián)規(guī)則兩級置信度閾值設置方法
        計算機應用(2018年5期)2018-07-25 07:41:26
        基于模糊自適應模擬退火遺傳算法的配電網故障定位
        SOA結合模擬退火算法優(yōu)化電容器配置研究
        電源技術(2015年5期)2015-08-22 11:18:24
        置信度條件下軸承壽命的可靠度分析
        軸承(2015年2期)2015-07-25 03:51:04
        基于遺傳-模擬退火算法的城市軌道交通快慢車停站方案
        国产成人福利av一区二区三区| 亚洲欧美激情精品一区二区| 人妻去按摩店被黑人按中出| 久久久久久久尹人综合网亚洲 | 色综合久久蜜芽国产精品| 国产精品毛片久久久久久久| 2021国产精品视频| 日韩av在线不卡一二三区| 日本男人精品一区二区| 亚洲日韩一区精品射精| 久久6国产| 日韩av免费在线不卡一区| 在线观看 国产一区二区三区 | 国产真人无码作爱视频免费| 日本道免费精品一区二区| 久久婷婷综合激情亚洲狠狠| 国产午夜av秒播在线观看| 亚洲av无码1区2区久久| 亚洲嫩草影院久久精品| 精品老熟女一区二区三区在线| 久久久久人妻一区二区三区| 欧美性videos高清精品| 久久丁香花综合狼人| 久久伊人精品色婷婷国产| 精品久久人妻av中文字幕| 84pao强力打造免费视频34| 在线观看国产精品自拍| 成人免费在线亚洲视频| 国产成熟人妻换╳╳╳╳ | 久久热免费最新精品视频网站| 国产精品久线在线观看| 可以免费观看的毛片| 日韩国产自拍成人在线| 免费人成视频网站网址| 蜜臀av 国内精品久久久| 国产精品丝袜美女在线观看| 亚洲av综合av国一区二区三区| 玩弄人妻少妇精品视频| 亚洲av之男人的天堂| 少妇裸淫交视频免费看| 久久久久久夜精品精品免费啦 |