李曉飛

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

0 引 言

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

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

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

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

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

針對建筑設(shè)計(jì)數(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)鍵詞進(jìn)行了簽名設(shè)置，將簽名信息加入到節(jié)點(diǎn)中，從而找到關(guān)鍵詞信息與挖掘?qū)ο蟮目臻g區(qū)域關(guān)系；

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

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

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

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

在構(gòu)建KeyTree索引結(jié)構(gòu)的基礎(chǔ)上，提出了基于Skyline算法的建筑設(shè)計(jì)數(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ù)信息文本集合進(jìn)行過濾。

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

KTSL算法:

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

2.2 過濾策略

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

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

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

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

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

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

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

(1)

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

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

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支配的點(diǎn)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過濾法對集合對象進(jìn)行剪枝，6～9行采用Sum過濾法判定關(guān)鍵詞對象的支配關(guān)系；10～11行主要對中間結(jié)果集中被支配對象進(jìn)行刪除操作。

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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