均勻分布下不確定數(shù)據(jù)的關(guān)聯(lián)規(guī)則變粒度查詢(xún)＊

陳愛(ài)東，劉國(guó)華，肖 瑞，萬(wàn)小妹，石丹妮

（東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海201600）

1 引言

云計(jì)算為大數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘與查詢(xún)提供了平臺(tái)。通過(guò)對(duì)大數(shù)據(jù)的分析、挖掘和查詢(xún)，能夠更好地發(fā)掘大數(shù)據(jù)的潛在價(jià)值，提高用戶(hù)預(yù)測(cè)的準(zhǔn)確性。

出于隱私保護(hù)目的，大數(shù)據(jù)本身就包含人為添加的不確定因素，對(duì)該類(lèi)不確定數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘后，規(guī)則體左邊依舊為泛化值，傳統(tǒng)的查詢(xún)方法不再適用于不確定數(shù)據(jù)查詢(xún)［1］。表1所示為一不確定數(shù)據(jù)表，對(duì)該表進(jìn)行屬性間關(guān)聯(lián)規(guī)則挖掘（以age和disease為例）時(shí)，忽略age屬性值之間可能存在的相交或包含關(guān)系，得到的所有關(guān)聯(lián)規(guī)則如表2所示。表2中，age屬性有三種粒度的規(guī)則（25～45，40～50，20～50），而在實(shí)際使用中，用戶(hù)的查詢(xún)需求很難恰好與已存在的粒度吻合。如查詢(xún)age為28，disease為CANCER的可能性，從表2中查到四條可能相關(guān)的規(guī)則｛25～45＝＞CANCER（0.5）；25～45＝＞AIDS，CANCER（0.25）；20～50＝＞CANCER（0.5）；20～50＝＞CANCER，NONE（0.25）｝，其中括號(hào)里的值表示規(guī)則的置信度，但究竟28歲得CANCER的可能性為多少目前還無(wú)法得知。另外，若每次用戶(hù)有查詢(xún)請(qǐng)求時(shí)，都做一次挖掘處理后再返回相應(yīng)的規(guī)則集，會(huì)導(dǎo)致很長(zhǎng)的響應(yīng)時(shí)間，因此，有必要構(gòu)建關(guān)聯(lián)規(guī)則庫(kù)以提高用戶(hù)的查詢(xún)效率?；陉P(guān)聯(lián)規(guī)則庫(kù)，如何使用戶(hù)實(shí)現(xiàn)任意粒度查詢(xún)是目前亟待解決的問(wèn)題。在用于共享的大數(shù)據(jù)中，不確定數(shù)據(jù)通過(guò)對(duì)精確數(shù)據(jù)的泛化處理來(lái)實(shí)現(xiàn)，具有均勻分布特性，這一特性不利于精確查詢(xún)，但可為關(guān)聯(lián)規(guī)則挖掘結(jié)果集的變粒度查詢(xún)提供可能。

借助云平臺(tái)的強(qiáng)大存儲(chǔ)和計(jì)算能力，本文提出了一種新的算法，用于對(duì)關(guān)聯(lián)規(guī)則庫(kù)進(jìn)行變粒度查詢(xún)。該算法基于定期更新的關(guān)聯(lián)規(guī)則庫(kù)和為泛化標(biāo)識(shí)符及敏感屬性分別構(gòu)建的 Hilbert packed R樹(shù)索引［2］，根據(jù)用戶(hù)請(qǐng)求分別在不同的計(jì)算節(jié)點(diǎn)上并行執(zhí)行條件判斷與結(jié)果集篩選，以得到滿(mǎn)足用戶(hù)請(qǐng)求的結(jié)果。貢獻(xiàn)如下：

（1）根據(jù)不確定數(shù)據(jù)表中泛化值之間可能存在的相交或包含關(guān)系，提出關(guān)聯(lián)規(guī)則庫(kù)概念及構(gòu)造方法；

（2）提出了四條泛化值粒度轉(zhuǎn)換性質(zhì)及相應(yīng)的轉(zhuǎn)換方法；

（3）基于四條重要性質(zhì)，提出了滿(mǎn)足用戶(hù)查詢(xún)透明化的U-ARS查詢(xún)算法。

Table 1 Uncertain data set表1 不確定數(shù)據(jù)表

Table 2 Association rules set表2 關(guān)聯(lián)規(guī)則集

2 相關(guān)工作

目前對(duì)不確定數(shù)據(jù)查詢(xún)的研究，根據(jù)查詢(xún)類(lèi)型和查詢(xún)特點(diǎn)主要分為不確定Skyline查詢(xún)［3，4］、不確定Top-k查詢(xún)、不確定最近鄰（NN）查詢(xún)以及不確定聚集查詢(xún)，這些查詢(xún)?cè)跊Q策制定、環(huán)境監(jiān)視、數(shù)據(jù)挖掘等領(lǐng)域都發(fā)揮著重要作用。不確定Top－k查詢(xún)［5～10］的目標(biāo)在于查詢(xún)返回k個(gè)排序函數(shù)值最大的元組，Re C等人［5］從查詢(xún)語(yǔ)義的合理性出發(fā)，定義了各式各樣的不確定Top-k查詢(xún)語(yǔ)義。不確定最近鄰查詢(xún)主要分為基于概率計(jì)算的方法和基于概率過(guò)濾的方法，Cheng R等人［11］提出了利用APLA-tree索引的查詢(xún)方法，Cheng R 等人［12］提出了約束概率最近鄰（C-PNNQ）的概念，Thomas B等人［13，14］從反最近鄰的角度出發(fā)，提出高效的概率不確定數(shù)據(jù)查詢(xún)算法。Ross R等人［15］在2005年針對(duì)概率數(shù)據(jù)庫(kù)上的聚集查詢(xún)問(wèn)題，提出了一種基于分桶策略的概率聚集操作，周遜等人［16］針對(duì)不確定數(shù)據(jù)，提出了基于過(guò)濾的分布式聚集算法。不確定數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘得到的規(guī)則都帶有一定的不確定性，而用戶(hù)不會(huì)考慮規(guī)則庫(kù)中的規(guī)則是否有不確定性，目前也無(wú)法從不確定的關(guān)聯(lián)規(guī)則庫(kù)中返回用戶(hù)的指定查詢(xún)。

3 構(gòu)建關(guān)聯(lián)規(guī)則庫(kù)

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘領(lǐng)域最基本的分析方法，其目的是從大量數(shù)據(jù)中發(fā)現(xiàn)頻繁項(xiàng)集和屬性間有價(jià)值的關(guān)聯(lián)關(guān)系［17，18］。“滿(mǎn)足均勻分布的不確定數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法”中提出了一種基于不確定頻繁模式樹(shù)的UFI-DM算法，可以高效地對(duì)滿(mǎn)足均勻分布的不確定數(shù)據(jù)集進(jìn)行關(guān)聯(lián)規(guī)則挖掘，并結(jié)合云計(jì)算的特點(diǎn)，將大數(shù)據(jù)均衡分配到足夠多的計(jì)算節(jié)點(diǎn)，分布式并行挖掘以大幅提高挖掘效率。

定義1 （關(guān)聯(lián)規(guī)則庫(kù)）關(guān)聯(lián)規(guī)則庫(kù)是一個(gè)面向主題的、集成的、大容量的、相對(duì)穩(wěn)定的、反映不確定數(shù)據(jù)集間關(guān)系的以及存有關(guān)聯(lián)規(guī)則對(duì)應(yīng)支持度、置信度的數(shù)據(jù)集合，用于實(shí)現(xiàn)關(guān)聯(lián)規(guī)則的透明化查詢(xún)。

以表1為例構(gòu)造關(guān)聯(lián)規(guī)則庫(kù)。首先，針對(duì)表1中的age泛化值進(jìn)行擴(kuò)展泛化標(biāo)識(shí)符EGI（Extension Generalization Identifier）值構(gòu)造，合并具有泛化值相交或者包含關(guān)系的相關(guān)區(qū)間，生成新的EGI值并計(jì)算相應(yīng)的支持?jǐn)?shù)，具體過(guò)程如圖1所示；然后，根據(jù)表1和EGI值表，用不確定頻繁模式UFP（Uncertain Frequent Pattern）樹(shù)構(gòu)造算法構(gòu)造一棵不確定頻繁模式樹(shù)以及對(duì)應(yīng)的 Header table List，如圖2所示，該樹(shù)完整地保存了數(shù)據(jù)集中與關(guān)聯(lián)規(guī)則挖掘相關(guān)的所有信息，并去除了與挖掘無(wú)關(guān)的信息，大幅減少了數(shù)據(jù)集的存儲(chǔ)空間；再次，按順序分別用UFI-DM算法和關(guān)聯(lián)規(guī)則生成算法 GAR （algorithm for Generating Association Rules），得到與該不確定數(shù)據(jù)集相關(guān)的所有關(guān)聯(lián)規(guī)則，此時(shí)任一規(guī)則體左邊都為某一EGI值；最后，對(duì)所有的關(guān)聯(lián)規(guī)則進(jìn)行提取、清洗與加載，將相關(guān)信息存儲(chǔ)到相應(yīng)的數(shù)據(jù)表中。對(duì)應(yīng)表1的關(guān)聯(lián)規(guī)則庫(kù)由表3和表4構(gòu)成，其中，表3存儲(chǔ)了所有的關(guān)聯(lián)規(guī)則相關(guān)信息，表4存儲(chǔ)了所有的EGI值相關(guān)信息?；诖岁P(guān)聯(lián)規(guī)則庫(kù)，可以實(shí)現(xiàn)用戶(hù)查詢(xún)透明化。

Figure 1 Construction process of EGI value in table 1圖1 表1中EGI值構(gòu)造過(guò)程

Table 3 Association rules library表3 關(guān)聯(lián)規(guī)則庫(kù)－關(guān)聯(lián)規(guī)則相關(guān)

Figure 2 Corresponding UFP tree in table 1圖2 表1對(duì)應(yīng)的UFP樹(shù)

Table 4 Association rules libraryrelationship between EGI values表4 關(guān)聯(lián)規(guī)則庫(kù)-EGI值關(guān)系

4 關(guān)聯(lián)規(guī)則查詢(xún)

上節(jié)通過(guò)UFI-DM算法實(shí)現(xiàn)對(duì)滿(mǎn)足均勻分布的不確定數(shù)據(jù)進(jìn)行屬性間關(guān)聯(lián)規(guī)則挖掘，進(jìn)而構(gòu)建關(guān)聯(lián)規(guī)則庫(kù)，但規(guī)則庫(kù)中的規(guī)則體左邊為泛化值，粒度較大，不能滿(mǎn)足用戶(hù)的查詢(xún)要求。接下來(lái)介紹相關(guān)性質(zhì)和引理用于計(jì)算得到符合用戶(hù)查詢(xún)要求的關(guān)聯(lián)規(guī)則。

引理1 若變量X在區(qū)間［a，b］上服從均勻分布（它的可能取值為x1，x2，…，xn，且a≤x1≤x2≤…≤xn≤b），那么當(dāng)Y取任意常量C時(shí)，（X，Y）在二維空間上符合均勻分布。

證明 因?yàn)閄在區(qū)間［a，b］上服從均勻分布，所以取任一可能值xi的概率均為1／n，即P（X＝xi）＝1／n（i∈［1，n］），而Y 維取值為常量C，所以我們得到（X，Y）的聯(lián)合分布如圖3所示。

Figure 3 Joint distribution of（X，Y）圖3 （X，Y）聯(lián)合分布

因?yàn)镻i1＝P（X＝xi，Y＝C）＝1／n，P（X＝xi）＝1／n，P（Y ＝C）＝1，所以對(duì)任意i、j，有P｛X ＝xi，Y ＝y(tǒng)j｝＝1／n＝P｛X ＝xi｝·P｛Y ＝y(tǒng)j｝成立，因此，由隨機(jī)變量獨(dú)立性定理得到變量X和Y相互獨(dú)立。再根據(jù)上面的聯(lián)合概率分布圖可知，對(duì)（X，Y）的n個(gè)不同取值，取每個(gè)值的概率相等，即 f（X，Y）＝ 1／n（X ∈ （x1，…，xn），Y ＝C），所以，（X，Y）在區(qū)間［a，b］上均勻分布。 □

基于泛化值區(qū)間取值可能是均勻分布的前提，分別從精確值和區(qū)間值兩個(gè)查詢(xún)角度，研究將泛化值轉(zhuǎn)換成精確值或區(qū)間值的置信度計(jì)算方法。

4.1 精確查詢(xún)

4.1.1 泛化值不相交

性質(zhì)1 規(guī)則X＝＞Y，conf（X＝＞Y）＝α，其中X是泛化值，Y是敏感信息，且X的可能取值由x1，x2，…，xn組成。那么，對(duì)任意xi（i∈ ［1..n］），有conf（xi＝＞Y）＝α。

證明 因?yàn)閄取任一可能值是等概率的，所以，對(duì)任意i∈ ［1..n］，有p（X ＝xi）＝1／n和supp（xi）＝1／n·supp（X），由引理1可知，（X，Y）服從均勻分布，即supp（xi∪Y）＝1／n·supp（X∪Y）。由已知得conf（X＝＞Y）＝α＝supp（X ∪Y）／supp（X），而conf（xi＝＞Y）＝supp（xi∪ Y）／supp（xi）＝ （1／n·supp（X ∪Y））／（1／n·supp（X））＝conf（X ＝＞Y），所以conf（xi＝＞Y）＝α。

4.1.2 泛化值相交但不包含

性質(zhì)2 對(duì)于區(qū)間［x11，x12］和［x21，x22］有x11＜x21＜x12＜x22，即區(qū)間［x11，x12］和區(qū)間［x21，x22］相交，且在［x11，x12］上有a個(gè)可能取值，在 ［x21，x22］上 有b 個(gè) 可 能 取 值。如 果 有conf（［x11，x12］＝＞ Y）＝ α 和conf（［x21，x22］＝＞Y）＝β，那么對(duì)于任意xi∈ ［x11，x21］有conf（xi＝＞Y）＝α；對(duì)于任意xi∈［x12，x22］，有conf（xi＝＞Y）＝β；對(duì)任意xi∈ ［x21，x12］，有：conf（xi＝＞Y）＝

4.1.3 泛化值包含

性質(zhì)3 對(duì)于區(qū)間［x11，x12］和［x21，x22］有x11≥x21，x12≤x22，即［x21，x22］包含區(qū)間［x11，x12］，并且在區(qū)間［x11，x12］上有a個(gè)可能取值，在區(qū)間［x21，x22］上有b個(gè)可能取值。如果有conf（［x11，x12］＝＞ Y）＝ α 和conf（［x21，x22］＝＞Y）＝β，那么對(duì)于任意xi∈ ［x21，x11］∪［x12，x22］有conf（xi＝＞Y）＝β；對(duì)于任意xi∈［x11，x12］， 有 conf（xi＝＞ Y） ＝

證明 對(duì)任意xi∈［x21，x11］∪［x12，x22］，有conf（xi＝＞Y）＝β，該證明同性質(zhì)1。

對(duì)任意xi∈ ［x11，x12］，有supp（xi）＝1／a·supp（［x11，x12］）＋ 1／b ·supp（［x21，x22］） 和supp（xi∪Y）＝1／a·supp（［x11，x12］∪Y）＋1／b·supp（［x21，x22］∪Y），由conf（［x11，x12］＝＞

4.2 區(qū)間查詢(xún)

性質(zhì)4 對(duì)任意區(qū)間［x11，x12］和［x21，x22］，區(qū)間［x11，x12］上有a 個(gè)可能取值，區(qū)間［x21，x22］上有b個(gè)可能取值。如果有conf（［x11，x12］＝＞Y）＝α和conf（［x21，x22］＝＞Y）＝β，［k1，k2］為查詢(xún)區(qū)間，該區(qū)間與泛化區(qū)間的可能關(guān)系如圖4所示，那么：

（1）對(duì)于不相交和相交（圖4b1）、包含（圖4c1）的情況：

Figure 4 Relationship between generalized interval and query interval圖4 泛化區(qū)間與查詢(xún)區(qū)間的關(guān)系

conf（［k1，k2］＝＞Y）＝ （（x12－k1）·1／a·α·supp（［x11，x12］）＋ （k2－ x21）·1／b·β ·supp（［x21，x22］））／（（x12－k1）·1／a·supp（［x11，x12］）＋（k2－x21）·1／b·supp（［x21，x22］））

（2）對(duì)于相交（圖4b2）和包含（圖4c2）的情況：

conf（［k1，k2］＝＞Y）＝ （（k2－k1）·1／a·α·supp（［x11，x12］）＋（k2－x21）·1／b·β·supp（［x21，x22］））／（（k2－k1）·1／a·supp（［x11，x12］）＋（k2－x21）·1／b·supp（［x21，x22］））

（3）對(duì)于相交（圖4b3）的情況：

conf（［k1，k2］＝＞Y）＝ （（x12－k1）·1／a·α·supp（［x11，x12］）＋ （k2－ k1）·1／b ·β ·supp（［x21，x22］））／（（x12－k1）·1／a·supp（［x11，x12］）＋（k2－k1）·1／b·supp（［x21，x22］））

（4）對(duì)于相交（圖4b4）和包含（圖4c4）的情況：

conf（［k1，k2］＝＞Y）＝ （（k2－k1）·1／a·α·supp（［x11，x12］）＋（k2－k1）·1／b·β·supp（［x21，x22］））／（（k2－k1）·1／a·supp（［x11，x12］）＋（k2－k1）·1／b·supp（［x21，x22］））

（5）對(duì)于包含（圖4c3）的情況：

conf（［k1，k2］＝＞Y）＝ （（k2－k1）·1／a·α·supp（［x11，x12］）＋（x22－k1）·1／b·β·supp（［x21，x22］））／（（k2－k1）·1／a·supp（［x11，x12］）＋（x22－k1）·1／b·supp（［x21，x22］））

4.3 粒度轉(zhuǎn)換的完整性

通過(guò)上述性質(zhì)可將粗粒度的關(guān)聯(lián)規(guī)則轉(zhuǎn)換成任意粒度，以滿(mǎn)足不同用戶(hù)的需求，實(shí)現(xiàn)對(duì)用戶(hù)查詢(xún)透明化。將不確定數(shù)據(jù)的規(guī)則結(jié)果轉(zhuǎn)換成確定規(guī)則的過(guò)程可提高規(guī)則的準(zhǔn)確性，且可去除部分異常規(guī)則，因?yàn)榇_定數(shù)據(jù)的支持度相對(duì)較小，而對(duì)泛化后的數(shù)據(jù)，一方面泛化值的支持?jǐn)?shù)是包含的確定值的支持?jǐn)?shù)之和，另一方面減少了頻繁項(xiàng)個(gè)數(shù)，加快了挖掘過(guò)程。并且，泛化值生成的關(guān)聯(lián)規(guī)則是泛化前的確定值生成相應(yīng)規(guī)則的置信度的中間值，有效地避免了特殊情況帶來(lái)的異常。下面通過(guò)引理具體說(shuō)明。

引理2 對(duì)于規(guī)則X＝＞Y有conf（X＝＞Y）＝α，其中X是確定數(shù)據(jù)x1，…，xn的泛化值，則α必處于所有xi（i∈［1，n］）＝＞Y規(guī)則對(duì)應(yīng)置信度的中間值。

證明 假設(shè)幾個(gè)確定值A(chǔ)i泛化后都為A，且conf（Ai＝＞B）＝supp（Ai∪B）／supp（Ai）＝n／m（n ≤ m），則 supp（A） ＝ ∑supp（Ai），supp（A∪B）＝∑supp（Ai∪B）。以?xún)蓚€(gè)值A(chǔ)1、A2泛化到A為例，有conf（A1＝＞B）＝supp（A1∪B）／supp（A1）＝n／m（n≤m）和conf（A2＝＞B）＝supp（A2∪B）／supp（A2）＝N／M（N≤M），則 conf（A ＝＞ B） ＝ ∑supp（Ai∪ B）／∑supp（Ai）＝ （n＋N）／（m＋M）（n≤m，N ≤M），而n／m－（n＋N）／（m＋M）＝ （n（m＋M）－m（n＋N））／（m（m＋M））＝ （mn＋nM －mnmN）／（m（m＋M））＝ （nM－mN）／（m（m＋M））＝T，所以當(dāng)T＞0時(shí)，nM－mN ＞0，有n／m＞（n＋N）／（m＋M）＞N／M；當(dāng)T＜0時(shí)，nM－mN＜0，有n／m＜ （n＋N）／（m＋M）＜N／M；當(dāng)T＝0時(shí)有n／m ＝ （n＋N）／（m＋M）＝N／M。因此，引理2成立，證畢。 □

引理3 假定X是確定數(shù)據(jù)x1，…，xn的泛化值，對(duì)泛化數(shù)據(jù)集的挖掘得到的關(guān)聯(lián)規(guī)則數(shù)與所有xi（i∈ ［1，n］）可以得到的敏感信息數(shù)相等，而與n無(wú)關(guān)。

由引理2的證明可知，對(duì)任一敏感信息Y，如果存在xi（i∈ ［1，n］）＝＞Y 的規(guī)則，則不管有幾個(gè)xi可以推導(dǎo)出Y，都會(huì)有規(guī)則X＝＞Y，所以，最終泛化值得到的規(guī)則數(shù)與敏感信息數(shù)相等。

引理4 假定X是確定數(shù)據(jù)x1，…，xn的泛化值，若存在X＝＞M，則對(duì)任意xi（i∈ ［1，n］），至少存在一條規(guī)則xi＝＞M，即對(duì)泛化數(shù)據(jù)挖掘得到的規(guī)則集可以完全反推出所有的原始確定規(guī)則集。

由數(shù)據(jù)集的泛化過(guò)程和UFI-DM算法的執(zhí)行過(guò)程可知，泛化后數(shù)據(jù)集的記錄數(shù)不變，但關(guān)聯(lián)規(guī)則數(shù)減少了，對(duì)任意xi（i∈ ［1，n］），如果有規(guī)則xi＝＞M，則對(duì)泛化數(shù)據(jù)挖掘后一定存在規(guī)則X＝＞M，且由引理2可知，該規(guī)則的置信度為xi（i∈ ［1，n］）中所有能推導(dǎo)xi＝＞M 規(guī)則的置信度的中間值。根據(jù)上述性質(zhì)1～性質(zhì)3，我們可以將X得到的規(guī)則還原到某一具體的xi（i∈［1，n］），所以將泛化數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘后的查詢(xún)結(jié)果與原始數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘后的查詢(xún)結(jié)果相比，后者能得到的規(guī)則前者都可以得到，并且前者還可以得到額外的有效但不一定正確的規(guī)則集。

由上述三個(gè)引理可知，對(duì)不確定數(shù)據(jù)集挖掘可以得到完整的關(guān)聯(lián)規(guī)則信息，并通過(guò)應(yīng)用上述性質(zhì)1～性質(zhì)4，將規(guī)則粒度完整地轉(zhuǎn)換到確定的關(guān)聯(lián)規(guī)則，且不確定數(shù)據(jù)集挖掘得到的規(guī)則數(shù)要少于確定數(shù)據(jù)集挖掘得到的規(guī)則數(shù)，很好地壓縮了規(guī)則庫(kù)大小。

4.4 查詢(xún)算法

查詢(xún)是滿(mǎn)足用戶(hù)需求的一個(gè)重要步驟，本節(jié)將介紹如何通過(guò)U-ARS查詢(xún)算法，結(jié)合上述性質(zhì)1～性質(zhì)4，實(shí)現(xiàn)對(duì)用戶(hù)的查詢(xún)透明化以滿(mǎn)足不同用戶(hù)的請(qǐng)求。這里只考慮從規(guī)則體的左邊或右邊屬性查詢(xún)的情況，對(duì)于兩邊都有約束條件的查詢(xún)，只需對(duì)單邊查詢(xún)結(jié)果集再應(yīng)用一次該算法。另外，為加快查詢(xún)速度，對(duì)泛化標(biāo)識(shí)符和敏感屬性分別構(gòu)建Hilbert packed R樹(shù)索引，具體構(gòu)造算法詳見(jiàn)文獻(xiàn)［2］，不再贅述。

算法1 不確定關(guān)聯(lián)規(guī)則查詢(xún)算法 U-ARS（query on association rules from uncertain data）

輸入：查詢(xún)條件和最小置信度。

輸出：符合要求的關(guān)聯(lián)規(guī)則。

1 if（查詢(xún)條件為精確值）｛

2 通過(guò)索引樹(shù)判斷查詢(xún)條件屬于哪個(gè)EGI區(qū)間χEGI；

3 if（χEGI只包含一個(gè)原始區(qū)間）｛

4 應(yīng)用性質(zhì)1得到所有的關(guān)聯(lián)規(guī)則結(jié)果；

5 ｝else｛

6 foreach規(guī)則inχEGI包含的原始區(qū)間對(duì)應(yīng)的所有關(guān)聯(lián)規(guī)則｛

7 應(yīng)用性質(zhì)2或性質(zhì)3得到相應(yīng)的關(guān)聯(lián)規(guī)則結(jié)果；

8 ｝

9 ｝

10 ｝else if（查詢(xún)條件為區(qū)間值）｛

11 通過(guò)索引樹(shù)判斷查詢(xún)條件包含于哪些EGI區(qū)間arrEGI；

12 if（arrEGI只包含一個(gè)EGI區(qū)間）｛

13 判斷查詢(xún)條件包含于arrEGI［0］中哪些原始區(qū)間arrGI；

14 if（arrGI只包含一個(gè)原始區(qū)間）｛

15 應(yīng)用性質(zhì)1得到所有的關(guān)聯(lián)規(guī)則結(jié)果；

16 ｝else｛

17 foreach規(guī)則inarrGI包含的原始區(qū)間對(duì)應(yīng)的所有關(guān)聯(lián)規(guī)則｛

18 應(yīng)用性質(zhì)4得到相應(yīng)的關(guān)聯(lián)規(guī)則結(jié)果；

19 ｝

20 ｝

21 ｝else｛

22 得到arrEGI中每個(gè)EGI區(qū)間對(duì)應(yīng)的所有原始區(qū)間，并去除和查詢(xún)條件沒(méi)有交集的原始區(qū)間，記為arrGI；

23 foreach規(guī)則in arrGI包含的原始區(qū)間對(duì)應(yīng)的所有關(guān)聯(lián)規(guī)則｛

24 應(yīng)用性質(zhì)4得到相應(yīng)的關(guān)聯(lián)規(guī)則結(jié)果；

25 ｝

26 ｝

27 ｝

從查詢(xún)算法的執(zhí)行過(guò)程看，每次查詢(xún)處理前都通過(guò)索引樹(shù)查找包含查詢(xún)條件的最小范圍，可以快速找到與查詢(xún)條件相關(guān)的所有規(guī)則集，再對(duì)查詢(xún)條件做具體分析，根據(jù)不同的情況，對(duì)相應(yīng)的關(guān)聯(lián)規(guī)則進(jìn)行變粒度計(jì)算，只需掃描一遍關(guān)聯(lián)規(guī)則庫(kù)。當(dāng)關(guān)聯(lián)規(guī)則庫(kù)很大時(shí)，可將查詢(xún)請(qǐng)求分配到不同的計(jì)算節(jié)點(diǎn)上并行執(zhí)行算法1，再將各節(jié)點(diǎn)的結(jié)果匯總返回。

5 實(shí)驗(yàn)與分析

針對(duì)滿(mǎn)足均勻分布的不確定數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘后得到的規(guī)則集，目前還不存在對(duì)其進(jìn)行變粒度查詢(xún)的算法。為分析U-ARS查詢(xún)算法的性能，本文在模擬實(shí)驗(yàn)環(huán)境中實(shí)現(xiàn)了該算法，并分別構(gòu)造了確定數(shù)據(jù)得到的關(guān)聯(lián)規(guī)則庫(kù)和不確定數(shù)據(jù)得到的關(guān)聯(lián)規(guī)則庫(kù)。

5.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

U-ARS查詢(xún)算法運(yùn)行在單機(jī)環(huán)境下。該環(huán)境運(yùn)行 Windows XP操作系統(tǒng)，硬件參數(shù)為2GHz Intel?CoreTM2Duo CPU，3GB內(nèi)存。但是，在比較該算法在不同數(shù)量級(jí)數(shù)據(jù)下的穩(wěn)定性和響應(yīng)時(shí)間時(shí)，則運(yùn)行在由三個(gè)節(jié)點(diǎn)組成的hadoop云計(jì)算平臺(tái)中，其中一個(gè)節(jié)點(diǎn)的運(yùn)行環(huán)境與上述單機(jī)環(huán)境相同，另外兩個(gè)節(jié)點(diǎn)的運(yùn)行環(huán)境都為WIN7操作系統(tǒng)，硬件參數(shù)是2.4GHz Intel? CoreTMi3-2370MCPU，2GB內(nèi)存。查詢(xún)算法采用的編程語(yǔ)言為C＃。

實(shí)驗(yàn)中使用了兩個(gè)數(shù)據(jù)集，一個(gè)是來(lái)自UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)提供的Adult數(shù)據(jù)［19］，稱(chēng)為D1，包含14個(gè)字段48 842條記錄，當(dāng)支持度下降時(shí)，該數(shù)據(jù)集中頻繁項(xiàng)的個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)；另一個(gè)是使用IBM數(shù)據(jù)集生成器生成的數(shù)據(jù)，稱(chēng)為D2，該數(shù)據(jù)集中每條記錄平均包含10個(gè)項(xiàng)，平均包含的頻繁項(xiàng)數(shù)目為5，總記錄數(shù)為100萬(wàn)條。根據(jù)實(shí)驗(yàn)需要，通過(guò)泛化方法對(duì)Adult數(shù)據(jù)集中Age字段進(jìn)行了泛化生成粗粒度的不確定數(shù)據(jù)集。另外，對(duì)數(shù)據(jù)集D1和D2，它們有確定的數(shù)據(jù)集和對(duì)應(yīng)的泛化數(shù)據(jù)集分別用于構(gòu)造對(duì)應(yīng)的確定關(guān)聯(lián)規(guī)則庫(kù)和不確定關(guān)聯(lián)規(guī)則庫(kù)。

5.2 實(shí)驗(yàn)結(jié)果

對(duì)原始數(shù)據(jù)集加入泛化處理得到的不確定數(shù)據(jù)不能完全符合均勻分布特征，進(jìn)行粒度轉(zhuǎn)換時(shí)會(huì)出現(xiàn)少數(shù)異常點(diǎn)，將少數(shù)異常點(diǎn)去除后，可顯著降低通過(guò)粒度轉(zhuǎn)換計(jì)算得到的確定規(guī)則與精確規(guī)則間的置信度誤差。如圖5所示，在數(shù)據(jù)集D1上進(jìn)行關(guān)聯(lián)規(guī)則挖掘后，以敏感信息Private為例，依照確定的關(guān)聯(lián)規(guī)則，分別得到其置信度的精確值和計(jì)算值。

Figure 5 Confidence comparison of age’s sensitive ivate before and after removing abnormal on dataset D1圖5 數(shù)據(jù)集D1去異常前后age得到敏感信息Private的置信度比較

圖5中點(diǎn)線(xiàn)表示age對(duì)應(yīng)Private規(guī)則的計(jì)算置信度曲線(xiàn)，＋線(xiàn)表示age對(duì)應(yīng)Private規(guī)則的精確置信度曲線(xiàn)。

由圖5可以看出，去除少數(shù)異常點(diǎn)后的計(jì)算置信度與精確置信度最大誤差不超過(guò)3%。

在數(shù)據(jù)集D1上，研究age與六個(gè)不同敏感信息的關(guān)聯(lián)關(guān)系，得到計(jì)算置信度與精確置信度比較如圖6所示。

將數(shù)據(jù)集D1分成不同數(shù)量級(jí)的子數(shù)據(jù)集后，再次以Private為例，研究不同數(shù)量級(jí)下，age得到Private規(guī)則的計(jì)算置信度和精確置信度對(duì)比，如圖7所示。

由圖6和圖7可以看出，相對(duì)于確定數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘，對(duì)不確定數(shù)據(jù)挖掘后再進(jìn)行粒度轉(zhuǎn)換，得到的關(guān)聯(lián)規(guī)則置信度與精確置信度之間存在一定的誤差，且隨著原始數(shù)據(jù)記錄數(shù)的增加，誤差不斷降低。如圖8所示，隨著數(shù)據(jù)表數(shù)量級(jí)的增加，不同age得到六個(gè)敏感信息的最大誤差逐漸降低。

為測(cè)試關(guān)聯(lián)規(guī)則庫(kù)中數(shù)據(jù)量增加時(shí)查詢(xún)算法的擴(kuò)展性，分別對(duì)不同數(shù)據(jù)量下的關(guān)聯(lián)規(guī)則庫(kù)做多次查詢(xún)得到平均查詢(xún)時(shí)間，如圖9所示。

Figure 9 Query time for association rules under different order of magnitude圖9 不同數(shù)量級(jí)的關(guān)聯(lián)規(guī)則庫(kù)中查詢(xún)時(shí)間

由于區(qū)間查詢(xún)需要執(zhí)行很多計(jì)算，隨著數(shù)據(jù)量的增加，平均查詢(xún)時(shí)間增加顯著，而確定查詢(xún)的平均查詢(xún)時(shí)間增長(zhǎng)緩慢。針對(duì)確定查詢(xún)，不同數(shù)據(jù)量下在確定關(guān)聯(lián)規(guī)則庫(kù)和不確定關(guān)聯(lián)規(guī)則庫(kù)中的查詢(xún)時(shí)間比較如圖10所示，當(dāng)規(guī)則庫(kù)中的數(shù)據(jù)量較小時(shí)，兩種規(guī)則庫(kù)的查詢(xún)都表現(xiàn)優(yōu)異，隨著數(shù)據(jù)量的增加，不同規(guī)則庫(kù)查詢(xún)時(shí)間的差異越來(lái)越大。而云平臺(tái)的負(fù)載均衡和并行查詢(xún)功能使得其響應(yīng)時(shí)間小于上述單機(jī)查詢(xún)，并且隨著規(guī)則庫(kù)中數(shù)據(jù)量的增加，其響應(yīng)時(shí)間的增長(zhǎng)比率低于上述兩種情況。

6 結(jié)束語(yǔ)

針對(duì)均勻分布的不確定數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘并構(gòu)建關(guān)聯(lián)規(guī)則庫(kù)，本文提出了一種變粒度查詢(xún)算法，依托云平臺(tái)的強(qiáng)大存儲(chǔ)和計(jì)算能力，U-ARS算法實(shí)現(xiàn)了變粒度查詢(xún)，使得查詢(xún)過(guò)程對(duì)用戶(hù)透明，滿(mǎn)足不同的用戶(hù)需求。

Figure 10 Query time for different rules libraries圖10 不同規(guī)則庫(kù)的查詢(xún)時(shí)間比較

［1］ Wang Yi-hao，Li Xiao-yong，Qi Ya-fei，et al.Research of uncertain data query［J］.Computer Research and Development，2012，49（7）：1460-1466.（in Chinese）

［2］ Kamel I，F(xiàn)aloutsos C.Hilbert R-tree：An improved R-tree using fractals［C］∥Proc of the 20th International Conference on Very Large Data Bases，1994：500-509.

［3］ Borzsonyi S，Kossmann D，Stocker K.The skyline operator［C］∥Proc of the 17th International Conference on Data Engineering，2001：421-430.

［4］ Bai Mei，Xin Jun-chang，Wang Guo-ren.Probabilistic reverse skyline query processing over uncertain data stream［C］∥Proc of the 17th International Conference on Database Systems for Advanced Applications，2012：17-32.

［5］ Re C，Dalvi N，Suciu D.Efficient top-k query evaluation on probabilistic data［C］∥Proc of the 23rd International Conference on Data Engineering，2007：886-895.

［6］ Soliman M A，Ilays I F，Chang K-C.Top-kquery processing in uncertain database［C］∥Proc of the 23rd International Conference on Data Engineering，2007：896-905.

［7］ Cormode G，Li Fei-fei，Yi Ke.Semantics of ranking queries for probabilistic data and expected ranks［C］∥Proc of the 25th International Conference on Data Engineering，2009：305-316.

［8］ Hua Ming，Pei Jian，Zhang Wen-jie，et al.Ranking queries on uncertain data：A probabilistic threshold approach［C］∥Proc of the 2008ACM SIGMOD International Conference on Management of data，2008：673-686.

［9］ Hua Ming，Pei Jian，Zhang Wen-jie，et al.Efficiently answering probabilistic threshold top-kqueries on uncertain data［C］∥Proc of the 24th International Conference on Data Engineering，2008：1403-1405.

［10］ Hua Ming，Pei Jian，Lin Xue-min.Ranking queries on uncertain data［J］.VLDB，2011，20（1）：129-153.

［11］ Cheng R，Prabhakar S，Kalashnikov D.Querying imprecise data in moving object environments［J］.Knowledge and Da-ta Engineering，2004，16（9）：1112-1127.

［12］ Cheng R，Chen Jin-chuan，Mokbel M，et al.Probabilistic verifiers：Evaluating constrained nearest-neighbor queries over uncertain data［C］∥Proc of the 24th International Conference on Data Engineering，2008：973-982.

［13］ Thomas B，Emrich T，Kriegel H-P，et al.Efficient probabilistic reverse nearest neighbor query processing on uncertain data［J］.VLDB Endowment，2011，4（10）：669-680.

［14］ Li Jia-jia，Wang Bo-tao，Wang Guo-ren.Efficient probabilistic reverse k-nearest neighbors query processing on uncertain data［C］∥Proc of the 18th International Conference on Database Systems for Advanced Applications，2013：456-471.

［15］ Ross R，Subrahmanian V-S，Grant J.Aggregate operators in probabilistic databases［J］.Journal of the ACM，2005，52（1）：54-101.

［16］ Zhou Xun，Li Jian-zhong，Shi Sheng-fei.Distributed aggregations for two queries over uncertain data［J］.Computer Research and Development，2010，47（5）：762-771.（in Chinese）

［17］ Agrwal R，lmielinski T，Swami A.Mining association rules between sets of items in large database［C］∥Proc of the 1993ACM SIGMOD International Conference on Management of Data，1993：207-216.

［18］ Han Jia-wei，Pei Jian，Yin Yi-wen.Mining frequent patterns without candidate generation［C］∥Proc of the 2000 ACM SIGMOD International Conference on Management of Data，2000：1-12.

［19］ Blake C L，Newman D J，Hettich S，et al.UCI repository of machine learning databases［EB／OL］.［1998-01-01］.http：／／www.ics.uci.edu／～mlearn.

附中文參考文獻(xiàn)：

［1］ 王意浩，李小勇，祁亞斐，等.不確定數(shù)據(jù)查詢(xún)技術(shù)研究［J］.計(jì)算機(jī)研究與發(fā)展，2012，49（7）：1460-1466.

［16］ 周遜，李建中，石勝飛.不確定數(shù)據(jù)上兩種查詢(xún)的分布式聚集算法［J］.計(jì)算機(jī)研究與發(fā)展，2010，47（5）：762-771.