基于Skyline的建筑設(shè)計數(shù)據(jù)挖掘方法

李曉飛

(吉林建筑科技學(xué)院 計算機科學(xué)與工程學(xué)院， 吉林 長春 130114)

0 引 言

建筑設(shè)計案例對建筑師具有非同尋常的重要價值。數(shù)據(jù)信息的迅速傳播，建筑網(wǎng)站的數(shù)量以及建筑設(shè)計案例的數(shù)量急劇增長，積累了海量的數(shù)據(jù)。大數(shù)據(jù)時代的到來，對于建筑設(shè)計師從互聯(lián)網(wǎng)中挖掘建筑案例，并獲取有價值的信息造成了一定障礙。如何準確快速地從海量建筑案例中找出建筑師需求的有價值的案例并實現(xiàn)設(shè)計創(chuàng)新，將會很大程度緩解建筑設(shè)計師數(shù)據(jù)挖掘困難的問題。

提高數(shù)據(jù)挖掘性能的關(guān)鍵技術(shù)之一是對檢索進行優(yōu)化。因此，對于數(shù)據(jù)挖掘問題來說，找到一個最優(yōu)挖掘計劃，成為數(shù)據(jù)挖掘研究中一個重要內(nèi)容[1-2]。

構(gòu)建一個多連接檢索樹是對一個數(shù)據(jù)庫進行最優(yōu)檢索成本最低的。為了解決對大型數(shù)據(jù)庫的檢索進行優(yōu)化的問題，國內(nèi)外學(xué)者提出了很多檢索優(yōu)化算法[3-6]。傳統(tǒng)的檢索優(yōu)化算法使用全搜索算法，該類算法只適用于數(shù)據(jù)庫中對象的連接關(guān)系數(shù)量較少時，當數(shù)量較大時，檢索速度和效率很低。而大數(shù)據(jù)環(huán)境下，數(shù)據(jù)庫中的檢索連接量都很大。為了解決此問題，相關(guān)學(xué)者提出了動態(tài)規(guī)劃算法進行優(yōu)化，但查詢效率依舊較低[7-8]。Chen Z等[9]提出R-Tree索引結(jié)構(gòu)，該結(jié)構(gòu)解決空間最近鄰問題，索引結(jié)構(gòu)利用MBR對空間進行了分割，使空間利用率達到50%。此后，Qusdtree索引[10]、R-Tree倒排索引[11-12]被陸續(xù)提出，對存在的問題進行優(yōu)化。

基于上述問題以及建筑設(shè)計案例的特點，提出一種基于Skyline算法的建筑設(shè)計數(shù)據(jù)挖掘方法，針對數(shù)據(jù)庫查詢特點進行了索引結(jié)構(gòu)的構(gòu)建，并優(yōu)化了Skyline算法。實驗結(jié)果表明，該方法提升了建筑設(shè)計數(shù)據(jù)挖掘的執(zhí)行效率。

1 索引結(jié)構(gòu)構(gòu)建

針對建筑設(shè)計數(shù)據(jù)挖掘中多關(guān)鍵詞匹配效率低的問題，文中構(gòu)建了一種關(guān)鍵詞索引結(jié)構(gòu)KeyTree，如圖1所示。

圖1 KeyTree索引結(jié)構(gòu)圖

KeyTree分為兩層：

1)上層索引:在R-Tree索引結(jié)構(gòu)的基礎(chǔ)上，對關(guān)鍵詞進行了簽名設(shè)置，將簽名信息加入到節(jié)點中，從而找到關(guān)鍵詞信息與挖掘?qū)ο蟮目臻g區(qū)域關(guān)系；

2)下層索引：構(gòu)建了倒排表的結(jié)構(gòu)，能夠反映關(guān)鍵詞和挖掘?qū)ο笮畔⒌挠成潢P(guān)系。

上層索引中，為節(jié)點的存儲結(jié)構(gòu)，其中，CoPair為數(shù)據(jù)信息位置坐標對，表示數(shù)據(jù)的區(qū)域位置信息；nextpt是一個指針，指向下一節(jié)點；signtag為當前位置的簽名信息。葉子節(jié)點中的id表示位置的原子編號。其中位置的簽名信息用8位的二進制碼表示，通過Hash函數(shù)將關(guān)鍵詞信息轉(zhuǎn)換為二進制碼。下層倒排索引中，每個節(jié)點中存儲了關(guān)鍵詞信息、位向量信息。其中位向量的每一個bit對應(yīng)了區(qū)域的內(nèi)部編號。

該索引結(jié)構(gòu)關(guān)鍵詞簽名信息的構(gòu)建降低了檢索過沖中的位沖突概率，此外還可以通過簽名信息過濾與關(guān)鍵詞無關(guān)的檢索區(qū)域，將無關(guān)的信息點進行剪枝。采用倒排索引結(jié)構(gòu)相比于傳統(tǒng)倒排結(jié)構(gòu)，很大程度上降低了大數(shù)據(jù)環(huán)境下索引的空間存儲容量依賴性。

2 Skyline建筑設(shè)計數(shù)據(jù)挖掘方法

在構(gòu)建KeyTree索引結(jié)構(gòu)的基礎(chǔ)上，提出了基于Skyline算法的建筑設(shè)計數(shù)據(jù)挖掘方法，包括Skyline數(shù)據(jù)挖掘算法、過濾策略和關(guān)鍵詞挖掘判定算法。

2.1 Skyline數(shù)據(jù)挖掘算法

為了解決多關(guān)鍵詞Skyline檢索效率問題，基于KeyTree索引結(jié)構(gòu)，提出了Skyline數(shù)據(jù)挖掘算法----KTSL算法。

KTSL算法在對KeyTree索引遍歷的過程中，上層索引通過比較關(guān)鍵詞位置信息與查詢關(guān)鍵詞信息，算法對數(shù)據(jù)信息文本集合進行過濾。

在下層索引中，對葉子節(jié)點進行遍歷，通過位之間的快速運算獲取滿足檢索關(guān)鍵詞的數(shù)據(jù)，從而獲得相關(guān)區(qū)域的候選集?；贙eyTree索引的Skyline數(shù)據(jù)挖掘算法如下：

KTSL算法:

輸入：檢索點p,檢索關(guān)鍵詞p.k，檢索范圍W，數(shù)據(jù)信息集S，KeyTree索

輸出：結(jié)果集OT

過程：

1. TempS←{ };TS←{ };

2. While !Node.isEmpty() do

3. NS←Node.pop( )

4. if NS.isInRange(p.k,W) then

//檢索關(guān)鍵詞p.k與檢索范圍W匹配

5. if NS.isLeaf() then

6. TS←getSet(p.k)

//獲得滿足檢索關(guān)鍵詞的集合TS

7. for ts in TS

8. TempS←CSkyline(TempS,TS,p.k,W)

9. else

10. Node.push(NS.getChild());

KTSL算法中，首先以棧的形式維護KeyTree上層索引節(jié)點中未被訪問的節(jié)點，然后判斷檢索區(qū)域，當檢索到葉子節(jié)點時，則采用倒排索引計算符合檢索條件的集合TS；最后，循環(huán)調(diào)用CSkyline(TempS,TS,p.k,W)方法，支配判定關(guān)鍵詞，生成新的中間結(jié)果集TempS。

2.2 過濾策略

由于中間結(jié)果集TempS和候選集合TS之間的關(guān)鍵詞支配判定的計算，導(dǎo)致CSkyline(TempS,TS,p.k,W)方法比較耗時且操作頻繁。為此，文中進行了空間優(yōu)化，通過過濾策略提高挖掘效率。

通過驗證發(fā)現(xiàn)：

①s1，s2為區(qū)域關(guān)鍵詞對象，對?s1，s2∈TS，若s1，s2之間不能構(gòu)成支配關(guān)系，則s1，s2必定不構(gòu)成區(qū)域關(guān)鍵詞信息支配。

②如果某個區(qū)域關(guān)鍵詞對象存在關(guān)系,si∈TS，并且關(guān)鍵詞對象的加權(quán)距離小于中間結(jié)果集TempS中距離檢索點最近的關(guān)鍵詞對象點，則si一定屬于TempS。

基于上述定義，采用如下過濾策略：

1)Min過濾法。設(shè)置一個小頂堆結(jié)構(gòu)，堆頂對象tp為中間結(jié)果集TempS中距離檢索點p加權(quán)距離最近的對象點。然后判斷候選對象點ts的加權(quán)距離，如果小于tp，根據(jù)②，則ts∈TempS。根據(jù)此規(guī)律，在后續(xù)計算中只需要判定關(guān)鍵詞支配關(guān)系，并且直接對中間結(jié)果集中未被ts支配的點刪除即可。

2)Sum過濾法。根據(jù)數(shù)值型對象的屬性，過濾的判定依據(jù)為關(guān)鍵詞的數(shù)值和。設(shè)s為關(guān)鍵詞對象點,?s在N維屬性上的過濾公式為

(1)

式中：G(s)----過濾值。

該方法的時間復(fù)雜度為O(1)，在算法開始執(zhí)行時，采用Sum過濾法對支配關(guān)系進行判定。對于?s1，?s2，若G(s1)G(s2)，則表明s2在N維屬性上不可能支配對象s1。因此，如果對象點s1與s2無關(guān)鍵詞支配關(guān)系，根據(jù)①可以得到s1和s2不存在支配關(guān)系，就不需要在循環(huán)中繼續(xù)進行計算，對其進行直接剪枝操作，算法的執(zhí)行效率得到有效提高。

2.3 關(guān)鍵詞挖掘判定算法

通過上述優(yōu)化，得到的關(guān)鍵詞挖掘判定算法CSkyline算法如下：

輸入：中間結(jié)果集TempS，候選對象ts，檢索關(guān)鍵詞p.k，檢索范圍W

輸出：中間結(jié)果集TempS

過程：

1.TempS←getHeapTop(TempS);

2.if dt(ts,s) < dt(tp,s) then

3. KeyDetele(TempS, ts); //刪除TempS中所有被ts支配的點

4. insert ts into TempS;

5.else

6. for tp in TempS from the Stack do

7. if G(ts)≤G(tp) then

8. if ts?Zhiper(TempS) then

9. continue;

10. else if dt(ts,s)

11. delele tp from TempS; //刪除SP中被c支配的點sp

12. else

13. if tp?Zhipei(ts) then//不構(gòu)成文本支配

14. continue;

15. else if dt(tp,s)

16. break;

17. if tp=NULL then

//指向堆末,表明遍歷完所有對象

18. insert ts into TempS;

在CSkyline算法中，前4行采用Min過濾法對集合對象進行剪枝，6～9行采用Sum過濾法判定關(guān)鍵詞對象的支配關(guān)系；10～11行主要對中間結(jié)果集中被支配對象進行刪除操作。

3 實驗結(jié)果及分析

為驗證該算法的可行性，主要從數(shù)據(jù)集大小、數(shù)據(jù)集維度、關(guān)鍵詞數(shù)量三個方面對算法性能影響進行了實驗驗證。

3.1 數(shù)據(jù)集

為了評估所提出方法的性能，數(shù)據(jù)集同時使用了合成數(shù)據(jù)集和真實數(shù)據(jù)集進行驗證。合成數(shù)據(jù)集是用標準數(shù)據(jù)生成工具，生成完整數(shù)據(jù)集，然后隨機生成不完整的數(shù)據(jù)集功能。真實數(shù)據(jù)集采用中外建筑案例形成的數(shù)據(jù)庫，主要包括公建和住宅兩大類建筑案例數(shù)據(jù)信息，每一條數(shù)據(jù)包括23個屬性，其中17個屬性是可比的，數(shù)據(jù)庫中共包含1 627個元組。

文中采用兩個指標評估算法的性能,響應(yīng)時間和結(jié)果集的大小。在建筑設(shè)計案例數(shù)據(jù)庫中設(shè)計了一個實驗,與INKS算法[13]和STD算法[14]進行比較，為建筑案例信息數(shù)據(jù)的每個維度設(shè)置了不同的權(quán)重，以獲得不同的Skyline算法結(jié)果。

3.2 數(shù)據(jù)集大小對算法性能的影響

實驗主要分析了執(zhí)行時間隨數(shù)據(jù)集大小的變化。數(shù)據(jù)集大小對算法性能的影響如圖2所示。

從圖2可以看出，隨著數(shù)據(jù)集中元組的增加，CSkyline算法的執(zhí)行時間近似呈指數(shù)增長，而INKS 算法和STD算法的執(zhí)行時間約占CSkyline算法的10%。STD算法的初始執(zhí)行時間與INKS算法相近，STD隨著數(shù)據(jù)集大小的增加，算法的執(zhí)行時間逐漸低于INKS算法的執(zhí)行時間。

圖2 數(shù)據(jù)集大小對算法性能的影響

結(jié)果集的大小隨數(shù)據(jù)集大小的變化，實驗結(jié)果如圖3所示。

圖3 數(shù)據(jù)集大小對結(jié)果集的影響

CSkyline算法產(chǎn)生的結(jié)果集中元組數(shù)量較少，可以減少額外元組的數(shù)量。

3.3 關(guān)鍵詞數(shù)量對算法性能的影響

為了驗證關(guān)鍵詞數(shù)量對算法性能的影響，實驗對建筑設(shè)計案例數(shù)據(jù)庫進行部分抽取，數(shù)據(jù)維度為4。在檢索點q區(qū)域坐標一致的情況下，關(guān)鍵詞數(shù)量由1增加到10的算法執(zhí)行時間的變化如圖4所示。

圖4 關(guān)鍵詞數(shù)量對算法性能的影響

可以看出，文中CSkyline算法在關(guān)鍵詞較高的時候，明顯優(yōu)于其他兩種算法，多關(guān)鍵詞匹配上采用簽名信息，并利用hash函數(shù)進行映射，有效提高了多關(guān)鍵詞時的挖掘速度。

3.4 數(shù)據(jù)集維度對算法性能的影響

數(shù)據(jù)集維度對算法性能的影響驗證采用獨立的數(shù)據(jù)集，數(shù)量為200 K，維度為2～8維，查詢關(guān)鍵詞數(shù)量為4，檢索區(qū)域坐標隨機產(chǎn)生。

數(shù)據(jù)集維度對算法性能的影響如圖5所示。

圖5 數(shù)據(jù)集維度對算法性能的影響

從圖5可以看出，STD算法和INKS算法隨著維度逐漸升高，算法的檢索時間逐漸變長，算法性能逐漸下降。CSkyline算法由于進行了剪枝操作，前期減少了無效對象點之間的匹配計算時間，所以隨著維度的逐漸增加，計算開銷沒有明顯增大。維度為8時，計算開銷約為STD算法的1/3。

4 結(jié) 語

針對大數(shù)據(jù)時代下建筑設(shè)計師從互聯(lián)網(wǎng)中挖掘建筑案例，并獲取有價值的信息效率低的問題，提出一種基于Skyline算法的建筑設(shè)計數(shù)據(jù)挖掘方法，針對數(shù)據(jù)庫查詢特點構(gòu)建了索引結(jié)構(gòu)KeyTree,加入了簽名信息，降低了檢索過沖中的位沖突概率，過濾了與關(guān)鍵詞無關(guān)的檢索區(qū)域，將無關(guān)的信息點進行剪枝。在索引結(jié)構(gòu)KeyTree的基礎(chǔ)上，提出了多關(guān)鍵詞挖掘算法CSkyline算法。實驗結(jié)果表明，該方法有效提升了建筑設(shè)計數(shù)據(jù)挖掘的執(zhí)行效率，并能夠有效解決建筑設(shè)計案例中多關(guān)鍵詞Skyline檢索問題。