[發明專利]一種基于GACUC和Delaunay三角網的空間聚類方法

有效

• 申請號: 201410299160.0
• 申請日: 2014-06-27
• 公開（公告）號: CN104036024B
• 公開（公告）日: 2017-03-29
• 發明（設計）人: 劉仁義;杜震洪;張豐;張逸然;徐聰
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州求是專利事務所有限公司33200
• 代理人: 張法高

技術領域

本發明屬于空間數據挖掘研究領域。尤其涉及一種基于GACUC和Delaunay三角網的空間聚類方法。?

背景技術

空間聚類方法是空間數據挖掘研究領域一種最為活躍的技術方法，目前已被廣泛應用于地理信息科學、傳染病學、生物學以及經濟學等諸多研究領域，并產生了良好的社會效益和經濟效益。?

空間聚類就是根據一定的劃分規則，將空間數據庫中的空間要素劃分為若干個具有現實意義的聚類簇，使得每一個聚類簇內的空間要素之間具有最大的相似度，而聚類簇之間具有最大的區別。目前，常用的聚類方法包括基于劃分的聚類方法、基于層次的聚類方法、基于密度的聚類方法、基于網格的聚類方法以及基于模型的聚類方法。對上述幾種空間聚類方法分析可知，這些方法基本都只采用空間屬性之間的歐式距離或非空間屬性之間的閔氏距離進行相似度計算。前者忽略了空間要素之間非空間屬性的相似性，而后者則忽略了空間要素之間的空間可達性。近年來，為了克服上述聚類方法的不足，也有不少學者從空間要素的空間屬性和非空間屬性進行綜合考慮，提出了不同的聚類方法。李光強等學者從空間要素之間空間歐式距離和非空間閔氏距離的可達性這兩個方面對聚類進行約束，提出了一種基于雙重距離的空間聚類方法，方法雖然解決了上述聚類方法的不足，但該方法只能支持屬性值為數字類型非空間屬性，實際應用范圍不大。焦利民等學者對空間和屬性雙重約束下的空間要素聚類進行了研究，通過設置屬性距離和空間距離的閾值來對空間要素進行劃分，但不同的閾值對聚類結果將產生重要的影響，且該方法也無法對聚類結果的聚類效用進行評價，因此，該方法可應用性不強。?

在此背景下，面對當前海量的空間數據，現有的空間聚類方法不僅沒有有效的聚類效用評價方法，而且應用范圍受到屬性值的約束，因此，目前常用的聚類方法均不能很好解決空間數據的聚類問題，而且聚類效果不佳。?

發明內容

本發明的目的是克服現有技術的不足，提供了一種基于GACUC和Delaunay三角網的空間聚類方法。?

本發明的技術方案如下：?

基于GACUC和Delaunay三角網的空間聚類方法包括如下步驟：?

1)設置分類效用函數CU，初始化屬性聚類的個數為k；多次重復選擇k個初始中心，分別計算分類效用函數CU的值，根據“分類效用函數CU的值越大，聚類效果越好”的原則，確定k個屬性聚類初始中心；?

2)計算每個空間要素歸入各個屬性聚類初始中心時其分類效用函數CU的值，對這些分類效用函數CU的值進行比較，將該空間要素與分類效用函數CU值最大的初始中心聚為一類；遍歷所有待聚類的空間要素，直至每個空間要素都完成聚類；?

3)優化步驟2)的屬性聚類結果，對聚類簇中的空間要素進行調整，使得最終形成的空間要素屬性聚類結果其分類效用函數CU的值最大；?

4)根據聚類簇中每一個空間要素的空間坐標位置，利用逐點插入法構建Delaunay三角網，并生成每一個空間要素的空間可達性關系表；根據各個空間要素的空間可達性關系表確定空間要素之間的空間可達性和連續空間可達性；?

5)基于深度優先算法對步驟3)生成的每個聚類簇進行遍歷，將每個聚類簇中具有連續空間可達性的空間要素聚為一類，即完成屬性聚類基礎上的二次空間聚類，確保最終生成的每一個聚類簇中各個空間要素之間均具有最大屬性相似性和空間可達性。?

所述的步驟1)包括：?

2.1設置屬性聚類的個數為k，循環次數為m，初始化索引i＝0；設置分類效用函數CU，并初始化best?CU＝0.0；?