導語：空間同位規則算法的改革論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要：空間關聯規則是空間數據挖掘所要發現的一種重要知識。一般的空間關聯規則研究是基于傳統的關聯規則，然而這些方法在處理空間關系時是不適用的。同位規則問題的提出，很好的解決了挖掘正確有效的空間關聯規則的需要。在介紹空間多維分類數據同位規則挖掘算法的基礎上，對該算法進行了一點改進，使其能更好的針對不同的實際數據進行處理。

關鍵詞：空間關聯規則；空間同位規則；多維分類數據

1空間同位規則算法概述

參照特征中心模型（Referencefeaturecentricmodel）是基于參照空間特征的選擇，是與應用領域特定的布爾型空間特征相關的。該模型的缺點有：1.1不能發現所有的關聯規則：由于使用了參照特征，而無法發現包含參照特征與相關特征的關聯模式；1.2因為它是用參考特征周圍的鄰居作為實例這些鄰居在下一個參考特征的統計中可能被再次計數，于是產生重復計數的現象。

ad-hoc數據分割算法通過將空間數據集分割到互不相關的區域來定義傳統關聯規則挖掘中的事務。然而，這種強制分割忽略了邊界之間的關系，會導致忽略或重復計算具有交疊邊界的事務實例。此外，可能存在許多種數據分割的方法，每種方法都會產生不同的事務集，因此對于一個特定的空間關聯模式會得到不同的支持度。

2多維分類數據的空間同位規則挖掘算法研究

2.1相關定義

定義1R-鄰近關系

R-鄰近關系是事件中心模型的重要概念。對于給定的實例集S，R-鄰近關系定義為在鄰域關系R下形成的區域內的實例集I，I!S。鄰域關系R的定義是基于所應用的領域，由算法的輸入給定。鄰域關系R可以是空間關系（如連接的，鄰近的），距離關系（如歐幾里德距離）或以上二者的結合（如公路地圖上的最短路徑）。R-鄰近關系不同于拓撲學中的鄰近概念，因為R-鄰近關系的超集不一定也是符合限定的R-鄰近關系。

定義2行實例

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

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

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

2.2算法描述

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

算法1同位規則挖掘算法輸入：

2.2.1K個布爾型空間特征類型以及它們的實例集：

2.2.2針對特定的應用制定的鄰域關系R；

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

a.初始化長度為1的同位模式，此時所有的參與索引pi=1；

b.for長度do

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

d.搜索滿足鄰域關系的空間實例，生成表實例；

e.根據min_prevalence進行裁剪；f.生成同位規則；

g.end。

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

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

3算法的改進

我們發現，參與索引閥值的設定是根據實際情況和需要。對不同的空間數據集，人們無法預先知道數據的分布相關情況，參與索引閥值就難以確定。需要一種能夠根據具體的應用而自動選擇和調節參與索引閥值的方法。本文提出的做法是：從二維開始，計算該維所有候選同位模式的參與索引的均值，以均值作為該維的參與索引閥值。同時，設定一個全局參與索引閥值，當某個維度的參與索引均值小于全局參與索引閥值，則以全局參與索引閥值作為該維度的參與索引閥值。當某個維度下所有候選同位模式的參與索引均小于全局參與索引閥值，算法結束，不產生該維度及更高維度的同位模式。公務員之家

算法2改進的空間多維分類數據的同位規則挖掘算法輸入：

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

3.2針對特定的應用制定的鄰域關系R；

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

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

c.for長度do

d.根據改進1的方法，生成長度為l的侯選同位模式；

e.搜索滿足鄰域關系的空間實例，生成表實例；

f.計算參與索引均值average_prevalence；

g.if（average_prevalence>min_prevalence）根據average_prevalence進行裁剪；

h.else根據min_prevalence進行裁剪；

i.生成同位規則。

4小結

空間同位規則是有別于傳統的空間關聯規則方法的發現空間特征在分布上的聯系性的新方法，目前國內外的相關研究較少。本文在多維分類數據的空間同位規則算法的基礎上，提出多層參與索引閥值的思想，采用各層參與索引均值和全局參與索引閥值，由數據本身的特性決定同位模式的判定，能有效的防止生成參與索引太小、不具實際意義的同位規則。

參考文獻

[1]王占全,王申康,華成.空間分類數據同位規則挖掘算法[J].計算機輔助設計與圖形學學報，2005，10.

[2]黃添強,秦小麟,葉水生等.一種新的空間多維關聯規則模型與算法[J].南京航空航天大學學報，2005，6.

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