基于Skyline的建筑設計數據挖掘方法

李曉飛

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

0 引 言

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

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

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

基于上述問題以及建筑設計案例的特點，提出一種基于Skyline算法的建筑設計數據挖掘方法，針對數據庫查詢特點進行了索引結構的構建，并優化了Skyline算法。實驗結果表明，該方法提升了建筑設計數據挖掘的執行效率。

1 索引結構構建

針對建筑設計數據挖掘中多關鍵詞匹配效率低的問題，文中構建了一種關鍵詞索引結構KeyTree，如圖1所示。

圖1 KeyTree索引結構圖

KeyTree分為兩層：

1)上層索引:在R-Tree索引結構的基礎上，對關鍵詞進行了簽名設置，將簽名信息加入到節點中，從而找到關鍵詞信息與挖掘對象的空間區域關系；

2)下層索引：構建了倒排表的結構，能夠反映關鍵詞和挖掘對象信息的映射關系。

上層索引中，為節點的存儲結構，其中，CoPair為數據信息位置坐標對，表示數據的區域位置信息；nextpt是一個指針，指向下一節點；signtag為當前位置的簽名信息。葉子節點中的id表示位置的原子編號。其中位置的簽名信息用8位的二進制碼表示，通過Hash函數將關鍵詞信息轉換為二進制碼。下層倒排索引中，每個節點中存儲了關鍵詞信息、位向量信息。其中位向量的每一個bit對應了區域的內部編號。

該索引結構關鍵詞簽名信息的構建降低了檢索過沖中的位沖突概率，此外還可以通過簽名信息過濾與關鍵詞無關的檢索區域，將無關的信息點進行剪枝。采用倒排索引結構相比于傳統倒排結構，很大程度上降低了大數據環境下索引的空間存儲容量依賴性。

2 Skyline建筑設計數據挖掘方法

在構建KeyTree索引結構的基礎上，提出了基于Skyline算法的建筑設計數據挖掘方法，包括Skyline數據挖掘算法、過濾策略和關鍵詞挖掘判定算法。

2.1 Skyline數據挖掘算法

為了解決多關鍵詞Skyline檢索效率問題，基于KeyTree索引結構，提出了Skyline數據挖掘算法----KTSL算法。

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

在下層索引中，對葉子節點進行遍歷，通過位之間的快速運算獲取滿足檢索關鍵詞的數據，從而獲得相關區域的候選集。基于KeyTree索引的Skyline數據挖掘算法如下：

KTSL算法:

輸入：檢索點p,檢索關鍵詞p.k，檢索范圍W，數據信息集S，KeyTree索

輸出：結果集OT

過程：

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

2. While !Node.isEmpty() do

3. NS←Node.pop( )

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

//檢索關鍵詞p.k與檢索范圍W匹配

5. if NS.isLeaf() then

6. TS←getSet(p.k)

//獲得滿足檢索關鍵詞的集合TS

7. for ts in TS

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

9. else

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

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

2.2 過濾策略

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

通過驗證發現：

①s1，s2為區域關鍵詞對象，對?s1，s2∈TS，若s1，s2之間不能構成支配關系，則s1，s2必定不構成區域關鍵詞信息支配。

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

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

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

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

(1)

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

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

2.3 關鍵詞挖掘判定算法

通過上述優化，得到的關鍵詞挖掘判定算法CSkyline算法如下：

輸入：中間結果集TempS，候選對象ts，檢索關鍵詞p.k，檢索范圍W

輸出：中間結果集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//不構成文本支配

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過濾法判定關鍵詞對象的支配關系；10～11行主要對中間結果集中被支配對象進行刪除操作。

3 實驗結果及分析

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

3.1 數據集

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

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

3.2 數據集大小對算法性能的影響

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

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

圖2 數據集大小對算法性能的影響

結果集的大小隨數據集大小的變化，實驗結果如圖3所示。

圖3 數據集大小對結果集的影響

CSkyline算法產生的結果集中元組數量較少，可以減少額外元組的數量。

3.3 關鍵詞數量對算法性能的影響

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

圖4 關鍵詞數量對算法性能的影響

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

3.4 數據集維度對算法性能的影響

數據集維度對算法性能的影響驗證采用獨立的數據集，數量為200 K，維度為2～8維，查詢關鍵詞數量為4，檢索區域坐標隨機產生。

數據集維度對算法性能的影響如圖5所示。

圖5 數據集維度對算法性能的影響

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

4 結 語

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