導(dǎo)語(yǔ)：空間同位規(guī)則算法的改革論文一文來(lái)源于網(wǎng)友上傳，不代表本站觀點(diǎn)，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要：空間關(guān)聯(lián)規(guī)則是空間數(shù)據(jù)挖掘所要發(fā)現(xiàn)的一種重要知識(shí)。一般的空間關(guān)聯(lián)規(guī)則研究是基于傳統(tǒng)的關(guān)聯(lián)規(guī)則，然而這些方法在處理空間關(guān)系時(shí)是不適用的。同位規(guī)則問(wèn)題的提出，很好的解決了挖掘正確有效的空間關(guān)聯(lián)規(guī)則的需要。在介紹空間多維分類數(shù)據(jù)同位規(guī)則挖掘算法的基礎(chǔ)上，對(duì)該算法進(jìn)行了一點(diǎn)改進(jìn)，使其能更好的針對(duì)不同的實(shí)際數(shù)據(jù)進(jìn)行處理。

關(guān)鍵詞：空間關(guān)聯(lián)規(guī)則；空間同位規(guī)則；多維分類數(shù)據(jù)

1空間同位規(guī)則算法概述

參照特征中心模型（Referencefeaturecentricmodel）是基于參照空間特征的選擇，是與應(yīng)用領(lǐng)域特定的布爾型空間特征相關(guān)的。該模型的缺點(diǎn)有：1.1不能發(fā)現(xiàn)所有的關(guān)聯(lián)規(guī)則：由于使用了參照特征，而無(wú)法發(fā)現(xiàn)包含參照特征與相關(guān)特征的關(guān)聯(lián)模式；1.2因?yàn)樗怯脜⒖继卣髦車泥従幼鳛閷?shí)例這些鄰居在下一個(gè)參考特征的統(tǒng)計(jì)中可能被再次計(jì)數(shù)，于是產(chǎn)生重復(fù)計(jì)數(shù)的現(xiàn)象。

ad-hoc數(shù)據(jù)分割算法通過(guò)將空間數(shù)據(jù)集分割到互不相關(guān)的區(qū)域來(lái)定義傳統(tǒng)關(guān)聯(lián)規(guī)則挖掘中的事務(wù)。然而，這種強(qiáng)制分割忽略了邊界之間的關(guān)系，會(huì)導(dǎo)致忽略或重復(fù)計(jì)算具有交疊邊界的事務(wù)實(shí)例。此外，可能存在許多種數(shù)據(jù)分割的方法，每種方法都會(huì)產(chǎn)生不同的事務(wù)集，因此對(duì)于一個(gè)特定的空間關(guān)聯(lián)模式會(huì)得到不同的支持度。

2多維分類數(shù)據(jù)的空間同位規(guī)則挖掘算法研究

2.1相關(guān)定義

定義1R-鄰近關(guān)系

R-鄰近關(guān)系是事件中心模型的重要概念。對(duì)于給定的實(shí)例集S，R-鄰近關(guān)系定義為在鄰域關(guān)系R下形成的區(qū)域內(nèi)的實(shí)例集I，I!S。鄰域關(guān)系R的定義是基于所應(yīng)用的領(lǐng)域，由算法的輸入給定。鄰域關(guān)系R可以是空間關(guān)系（如連接的，鄰近的），距離關(guān)系（如歐幾里德距離）或以上二者的結(jié)合（如公路地圖上的最短路徑）。R-鄰近關(guān)系不同于拓?fù)鋵W(xué)中的鄰近概念，因?yàn)镽-鄰近關(guān)系的超集不一定也是符合限定的R-鄰近關(guān)系。

定義2行實(shí)例

假定存在同位模式c，如果一個(gè)R-鄰近關(guān)系I包含了c的所有特征實(shí)例且不存在I的子集包含c的所有特征實(shí)例，則稱這個(gè)R-鄰近關(guān)系為行實(shí)例，用row_instance(c)表示。定義3參與概率

在長(zhǎng)度為k的同位模式c={f1，⋯，fk}中，特征類型fi的參與概率pr（c，fi）表示發(fā)生空間特征fi的地點(diǎn)，發(fā)現(xiàn)空間特征c的可能性為pr（c，fi），其值用fi的實(shí)例在搜索到的行實(shí)例中出現(xiàn)的次數(shù)與fi的所有實(shí)例數(shù)之比表示。其中，!是用來(lái)剔除重復(fù)的實(shí)例的映射操作符。

定義4參與索引參與索引pi（c）是同位模式普遍性的度量值，它表示發(fā)現(xiàn)空間特征fi的地方，能夠發(fā)現(xiàn)空間特征c的可能性至少為pi（c）。

2.2算法描述

同位規(guī)則挖掘算法是在給定即參與索引閥值min_prevalence的基礎(chǔ)上，發(fā)現(xiàn)存在的所有同位規(guī)則。該掘算法也是采用自頂向下，逐層搜索的思想，過(guò)程中借鑒了Apriori算法的連接的步驟。以下是算法的具體流程。

算法1同位規(guī)則挖掘算法輸入：

2.2.1K個(gè)布爾型空間特征類型以及它們的實(shí)例集：

2.2.2針對(duì)特定的應(yīng)用制定的鄰域關(guān)系R；

2.2.3全局參與索引閥值min_prevalence；步驟：

a.初始化長(zhǎng)度為1的同位模式，此時(shí)所有的參與索引pi=1；

b.for長(zhǎng)度do

c.用apriori_gen方法生成侯選同位模式；

d.搜索滿足鄰域關(guān)系的空間實(shí)例，生成表實(shí)例；

e.根據(jù)min_prevalence進(jìn)行裁剪；f.生成同位規(guī)則；

g.end。

步驟b～g通過(guò)循環(huán)逐層搜索同位規(guī)則，當(dāng)不存在同位規(guī)則時(shí)算法結(jié)束。參照3.2.1小節(jié)的范例，用apriori_gen方法生成侯選同位模式，實(shí)現(xiàn)上是采用表連接，具體做法是：為每一維的每個(gè)候選同位模式建立一個(gè)表，高一維的表由低一維的同位模式表進(jìn)行表連接生成。然后是剪枝步驟，對(duì)生成的表進(jìn)行裁剪。對(duì)所有屬于候選同位模式集Ck的候選同位模式c，判斷其k-1個(gè)元素的子集是否存在于同位模式集Lk-1，若不是，則將之刪除。

步驟d是為每個(gè)表搜索空間中滿足鄰域關(guān)系的實(shí)例，生成表實(shí)例，計(jì)算該表中每個(gè)空間特征的參與概率，進(jìn)而得到參與索引。步驟e則根據(jù)給定的參與索引閥值裁剪侯選同位模式，生成k-項(xiàng)同位模式Lk。

3算法的改進(jìn)

我們發(fā)現(xiàn)，參與索引閥值的設(shè)定是根據(jù)實(shí)際情況和需要。對(duì)不同的空間數(shù)據(jù)集，人們無(wú)法預(yù)先知道數(shù)據(jù)的分布相關(guān)情況，參與索引閥值就難以確定。需要一種能夠根據(jù)具體的應(yīng)用而自動(dòng)選擇和調(diào)節(jié)參與索引閥值的方法。本文提出的做法是：從二維開(kāi)始，計(jì)算該維所有候選同位模式的參與索引的均值，以均值作為該維的參與索引閥值。同時(shí)，設(shè)定一個(gè)全局參與索引閥值，當(dāng)某個(gè)維度的參與索引均值小于全局參與索引閥值，則以全局參與索引閥值作為該維度的參與索引閥值。當(dāng)某個(gè)維度下所有候選同位模式的參與索引均小于全局參與索引閥值，算法結(jié)束，不產(chǎn)生該維度及更高維度的同位模式。公務(wù)員之家

算法2改進(jìn)的空間多維分類數(shù)據(jù)的同位規(guī)則挖掘算法輸入：

3.1空間特征類型以及它們的實(shí)例集，即有m個(gè)屬性，每個(gè)屬性有n個(gè)值；

3.2針對(duì)特定的應(yīng)用制定的鄰域關(guān)系R；

3.3全局參與索引閥值min_prevalence；步驟：

a.初始化長(zhǎng)度為1的同位模式，此時(shí)所有的參與索引pi=1；b.搜索空間鄰域關(guān)系，建立長(zhǎng)度為2的候選同位模式的屬性表；

c.for長(zhǎng)度do

d.根據(jù)改進(jìn)1的方法，生成長(zhǎng)度為l的侯選同位模式；

e.搜索滿足鄰域關(guān)系的空間實(shí)例，生成表實(shí)例；

f.計(jì)算參與索引均值average_prevalence；

g.if（average_prevalence>min_prevalence）根據(jù)average_prevalence進(jìn)行裁剪；

h.else根據(jù)min_prevalence進(jìn)行裁剪；

i.生成同位規(guī)則。

4小結(jié)

空間同位規(guī)則是有別于傳統(tǒng)的空間關(guān)聯(lián)規(guī)則方法的發(fā)現(xiàn)空間特征在分布上的聯(lián)系性的新方法，目前國(guó)內(nèi)外的相關(guān)研究較少。本文在多維分類數(shù)據(jù)的空間同位規(guī)則算法的基礎(chǔ)上，提出多層參與索引閥值的思想，采用各層參與索引均值和全局參與索引閥值，由數(shù)據(jù)本身的特性決定同位模式的判定，能有效的防止生成參與索引太小、不具實(shí)際意義的同位規(guī)則。

參考文獻(xiàn)

[1]王占全,王申康,華成.空間分類數(shù)據(jù)同位規(guī)則挖掘算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，10.

[2]黃添強(qiáng),秦小麟,葉水生等.一種新的空間多維關(guān)聯(lián)規(guī)則模型與算法[J].南京航空航天大學(xué)學(xué)報(bào)，2005，6.

[3]R.Agrawal,R.Srikant.FastAlgorithmsforMiningAssociationRules[C].InProceedingsof20thInternationalConferenceVeryLargeDataBases,MorganKaufmann1994:487-499.