多表數(shù)據(jù)的物理聯(lián)接

多表數(shù)據(jù)的物理聯(lián)接

挖掘來自大數(shù)據(jù)庫的信息。大多數(shù)傳統(tǒng)的數(shù)據(jù)挖掘方法只適用于在數(shù)據(jù)庫的單表上進(jìn)行挖掘。當(dāng)面對(duì)多表時(shí),不得不把這些表物理上連接到一張表中,這樣會(huì)出現(xiàn)準(zhǔn)確率低、效率低等問題。在這種情況下,多關(guān)系數(shù)據(jù)挖掘應(yīng)運(yùn)而生1相關(guān)工作1.1傳統(tǒng)頻率模式的挖掘算法挖掘頻繁模式算法最有代表性的是Apriori算法1.2基于ilp的多關(guān)系挖掘算法目前大多數(shù)的多關(guān)系數(shù)據(jù)挖掘算法都是借鑒ILP思想WARMR1.3id傳播思想除了ILP思想,多關(guān)系數(shù)據(jù)挖掘也可以借鑒文獻(xiàn)中提出的元組ID傳播思想。元組ID傳播是一種在多表間建立虛連接的思想,它的定義如下:假設(shè)有兩個(gè)關(guān)系CrossMineCrossclusMFP1.4模式挖掘算法本文針對(duì)傳統(tǒng)的頻繁模式挖掘算法不適用于解決基于ILP思想的多關(guān)系頻繁模式挖掘算法效率低的問題,提出了一種多關(guān)系頻繁模式挖掘算法。借助于元組ID傳播的思想,對(duì)表進(jìn)行虛連接,使算法可以直接在多張表上挖掘出所有頻繁模式,提高了在多關(guān)系中挖掘頻繁模式的效率。在挖掘多表頻繁項(xiàng)集時(shí),只考慮來自以下兩種情況的表所產(chǎn)生的項(xiàng)集:a)兩個(gè)表之間存在主鍵與外鍵的對(duì)應(yīng);b)兩個(gè)表的主鍵同時(shí)是某個(gè)第三表的外鍵。不考慮其他情況,因?yàn)槠渌闆r在數(shù)據(jù)庫中代表這些表沒有很強(qiáng)的相關(guān)性。2支持度計(jì)數(shù)多關(guān)系頻繁模式1項(xiàng)。包含于任一個(gè)表的非主鍵和外鍵屬性的每個(gè)不同取值稱為一個(gè)項(xiàng),記為一個(gè)屬性和取值對(duì):屬性=取值,或用惟一的一個(gè)標(biāo)志符表示,如用標(biāo)志符2項(xiàng)集。多個(gè)項(xiàng)構(gòu)成的集合稱為項(xiàng)集。3單表項(xiàng)集。項(xiàng)集中的每個(gè)項(xiàng),若都來自同一個(gè)表,則稱為單表項(xiàng)集。4多表項(xiàng)集。項(xiàng)集中的每個(gè)項(xiàng),若涉及多個(gè)表,則稱為多表項(xiàng)集。5支持度計(jì)數(shù)。一個(gè)項(xiàng)集6頻繁項(xiàng)集。由用戶給定一個(gè)支持度計(jì)數(shù)閾值,所有支持度計(jì)數(shù)不小于該閾值的項(xiàng)集稱為頻繁項(xiàng)集。7多關(guān)系頻繁模式挖掘。給定支持度計(jì)數(shù)閾值,發(fā)現(xiàn)存在于一個(gè)數(shù)據(jù)庫的多個(gè)表中的所有不小于閾值的頻繁項(xiàng)集,包括單表頻繁項(xiàng)集和多表頻繁項(xiàng)集。3算法步驟3.1屬性取值的處理常見的數(shù)據(jù)庫屬性包括二元屬性、分類屬性、序數(shù)型屬性、區(qū)間標(biāo)度屬性。由于二元屬性、分類屬性、序數(shù)型屬性的取值是有限的,可以直接進(jìn)行挖掘。而區(qū)間標(biāo)度屬性的取值包含有無限多個(gè)連續(xù)值,不利于統(tǒng)計(jì)計(jì)數(shù),因此必須對(duì)其預(yù)處理。對(duì)區(qū)間標(biāo)度屬性預(yù)處理的方法是使用預(yù)定義的概念分層對(duì)其進(jìn)行離散化3.2支持度計(jì)數(shù)2-頻繁項(xiàng)集的創(chuàng)建算法的工作過程如下:a)由用戶設(shè)定支持度計(jì)數(shù)的閾值。b)對(duì)任何一對(duì)存在主鍵外鍵對(duì)應(yīng)的兩個(gè)表之間進(jìn)行元組ID傳播。c)對(duì)每個(gè)表的每個(gè)屬性(除了主鍵、外鍵、IDset)進(jìn)行掃描,對(duì)該屬性所產(chǎn)生的每個(gè)項(xiàng)進(jìn)行支持度計(jì)數(shù),支持度計(jì)數(shù)不小于閾值的項(xiàng)都是1-頻繁項(xiàng)集。為了區(qū)別每個(gè)項(xiàng),把它表示成“表.屬性(值)”的形式。在存儲(chǔ)每個(gè)1-頻繁項(xiàng)集時(shí),保存它的三類信息:(a)該項(xiàng)集的名稱,即“表.屬性(值)”。(b)該項(xiàng)集的支持度計(jì)數(shù),設(shè)項(xiàng)集名稱為(c)包含該項(xiàng)集的所有元組ID的值,也就是保存該表中的包含該項(xiàng)集的所有元組的主鍵值,設(shè)項(xiàng)集名稱為d)把每兩個(gè)1-頻繁項(xiàng)集組合起來,產(chǎn)生候選2-項(xiàng)集。在產(chǎn)生候選2-項(xiàng)集時(shí),不用考慮同一個(gè)表的同一個(gè)屬性所產(chǎn)生的項(xiàng)組合而成的2-項(xiàng)集,因?yàn)楸厝粵]有哪個(gè)元組包含這個(gè)2-項(xiàng)集,其支持度計(jì)數(shù)必然是0。只考慮組合不同屬性所產(chǎn)生的項(xiàng)。設(shè)有兩個(gè)項(xiàng),分別是(a)如果(b)如果如果這兩個(gè)表是有一個(gè)表包含另一個(gè)表的IDset,假設(shè)如果這兩個(gè)表是同時(shí)包含某個(gè)第三方表的IDset,假設(shè)支持度計(jì)數(shù)不小于閾值的候選2-項(xiàng)集都是2-頻繁項(xiàng)集。在保存2-頻繁項(xiàng)集時(shí),類似于1-頻繁項(xiàng)集,也需要保存以下三類:(a)該項(xiàng)集的名稱,因?yàn)橐獏^(qū)分出項(xiàng)所在的表的名稱,所以應(yīng)該保存為“表.屬性(值),表.屬性(值)”。(b)該項(xiàng)集的支持度計(jì)數(shù)。(c)包含該項(xiàng)集的所有元組ID集的值,對(duì)于任意一個(gè)產(chǎn)生該項(xiàng)集一個(gè)支持度的情況,無論是單表項(xiàng)集,還是多表項(xiàng)集,都保存為“表.ID(值),表.ID(值)”。例如,假設(shè)一個(gè)由e)在發(fā)現(xiàn)了2-頻繁項(xiàng)集后,就要找出候選3-項(xiàng)集。利用Apriori算法的性質(zhì)——頻繁項(xiàng)集的所有非空子集也必須是頻繁的。因此,候選3-項(xiàng)集的所有子集都必須是頻繁項(xiàng)集。根據(jù)這一點(diǎn),產(chǎn)生候選3-項(xiàng)集。為候選3-項(xiàng)集計(jì)數(shù)的方法與前面的1-項(xiàng)集和2-項(xiàng)集有所不同,不再通過掃描數(shù)據(jù)庫來計(jì)數(shù),而是通過如下方法來為候選3-項(xiàng)集計(jì)數(shù)。為候選3-項(xiàng)集計(jì)數(shù)的方法是:假設(shè)有三個(gè)項(xiàng)舉一個(gè)計(jì)數(shù)方法的例子,并說明理由。假設(shè)有三個(gè)表支持度計(jì)數(shù)不小于閾值的候選3-項(xiàng)集都是3-頻繁項(xiàng)集。需要保存的3-頻繁項(xiàng)集的信息與前面2-頻繁項(xiàng)集是類似的。f)4-頻繁項(xiàng)集,以及項(xiàng)的個(gè)數(shù)大于4的頻繁項(xiàng)集的挖掘方法,與3-頻繁項(xiàng)集類似。算法的偽碼如下:算法:在多關(guān)系中挖掘頻繁項(xiàng)集。輸入:一個(gè)多關(guān)系數(shù)據(jù)庫輸出:方法:=傳播元組ID(=挖1-項(xiàng)集(iffor({foreach{項(xiàng)集foreachIDifID.count++;if把}returnProcedure傳播元組ID(foreach關(guān)系foreach關(guān)系if把returnProcedure挖1-項(xiàng)集(foreach關(guān)系foreach屬性if為if把returnProcedure挖2-項(xiàng)集(foreach1-頻繁項(xiàng)集foreach1-頻繁項(xiàng)集合并if比較elseif取項(xiàng)的ID對(duì)應(yīng)的元組的IDset值的并集,與另一個(gè)項(xiàng)的ID進(jìn)行比較,相同的ID個(gè)數(shù)為項(xiàng)集{if取if{把{returnProcedureapriori_gen(foreach項(xiàng)集foreach項(xiàng)集if({ifhas_infrequent_subset(刪除else把returnProcedurehas_infrequent_subset(foreach(ifreturnfalse;4支持度計(jì)數(shù)閾值2.本文使用PKDDCUP1999中的包含八個(gè)表的金融數(shù)據(jù)庫(http://lisp.vse.cz/pkdd99/Challenge/chall.ht),作為實(shí)驗(yàn)數(shù)據(jù)集,做兩個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境:操作系統(tǒng)為WindowsXPProfessional;內(nèi)存為512MB;CPU為Pentium43.0GHz;平臺(tái)為BorlandC++Builder6.0。1目的:比較多關(guān)系頻繁模式挖掘算法和物理連接多表并采用傳統(tǒng)的單表頻繁模式挖掘算法的運(yùn)行時(shí)間。過程:從數(shù)據(jù)集中選擇兩個(gè)表(loan、account),進(jìn)行裁剪,保留200個(gè)元組;設(shè)定支持度閾值為4%,也就是支持度計(jì)數(shù)閾值為200×4%=8。結(jié)果:運(yùn)行時(shí)間對(duì)比如表1所示。從實(shí)驗(yàn)結(jié)果可以看到,本文提出的算法有較高的效率。2目的:分別在表的個(gè)數(shù)、元組個(gè)數(shù)、支持度變化的情況下,比較運(yùn)行時(shí)間的變化。過程:保持元組個(gè)數(shù)不變(對(duì)八個(gè)表都進(jìn)行裁剪,使每個(gè)表都只保留200個(gè)元組)、支持度不變(設(shè)定支持度閾值為4%,也就是支持度計(jì)數(shù)閾值為200×4%=8),改變表的個(gè)數(shù)(分別從八個(gè)表中選擇其中的兩個(gè)表(loan、account)、四個(gè)表(loan、account、order、transaction)、六個(gè)表(loan、account、order、transaction、district、disposition),以及全部八個(gè)表),作為算法的輸入,得出它們的運(yùn)行時(shí)間。結(jié)果:運(yùn)行時(shí)間變化如圖1所示。從圖1可以看到,隨著表的個(gè)數(shù)的不斷增加,運(yùn)行時(shí)間不斷增加,并且增長速度越來越快。過程:保持表的個(gè)數(shù)不變(選擇loan、account兩個(gè)表)、元組個(gè)數(shù)不變(對(duì)兩個(gè)表都進(jìn)行裁剪,使每個(gè)表都只保留500個(gè)元組),改變支持度(設(shè)定三個(gè)支持度閾值2%、4%、6%),作為算法的輸入,得出它們的運(yùn)行時(shí)間。結(jié)果:運(yùn)行時(shí)間變化如圖2所示。從圖2可以看出,隨著支持度閾值的不斷增加,運(yùn)行時(shí)間不斷下降。過程:保持表的個(gè)數(shù)不變(選擇loan、account、district三個(gè)表)、支持度不變(設(shè)定支持度閾值為4%),改變?cè)M的個(gè)數(shù)(對(duì)三個(gè)表都進(jìn)行裁剪,使三個(gè)表分別都保留50、100、200、300、400、500個(gè)元組),作為算法的輸入,得出它們的運(yùn)行時(shí)間。結(jié)果:運(yùn)行時(shí)間變化如圖3所示。從圖3可以看出,隨著每張表的元組的個(gè)數(shù)的不斷增加,運(yùn)行時(shí)間不斷增加,并且增長速度越來越快。5基于ilp的多關(guān)系頻繁模式挖掘算法由于傳統(tǒng)的數(shù)據(jù)挖掘方法在處理多關(guān)系頻繁