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

有效

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

1.一種基于GACUC和Delaunay三角網的空間聚類方法，其特征在于包括如下步驟：?

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

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

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

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

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

2.根據權利要求1所述的一種基于GACUC和Delaunay三角網的空間聚類方法，其特征在于所述的步驟1)包括：?

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

2.2隨機選擇k個初始聚類中心，計算分類效用函數CU的值，得到new?CU，i增加1；?

2.3比較分類效用函數CU的值new?CU和best?CU，如果new?CU>best?CU，則將這k個初始中心設置為初始聚類中心，并且best?CU＝new?CU，否則初始中心保持不變；?

2.4比較i和m，如果i<m，返回步驟2.2；否則，循環結束，返回k個屬性聚類的初始中心。?

3.根據權利要求1所述的一種基于GACUC和Delaunay三角網的空間聚類方法，其特征在于所述的步驟2)包括：?

3.1遍歷所有空間要素，選擇尚未進行聚類的空間要素a；?

3.2判斷空間要素a是否存在，如果存在，使用公式(1)，計算該空間要素歸入每個聚類簇后的分類效用函數CU的值，比較這k個分類效用函數CU的值，將該空間要素歸入產生最大分類效用函數CU值的聚類簇中，返回步驟3.1；否則，進入步驟3.3；?

3.3得到初始聚類結果。?

4.根據權利要求1所述的一種基于GACUC和Delaunay三角網的空間聚類方法，其特征在于所述的步驟3)包括：?

4.1設置循環次數為n；?

4.2在任一聚類簇A中，隨機選擇一個空間要素b；?

4.3隨機選擇不同于聚類簇A的聚類簇B，將空間要素b置換到聚類簇B，使用公式(1)，計算置換后的分類效用函數CU的值，得到new?CU，如果new?CU>old?CU，則保留本次置換，否則，撤銷本次置換，返回原來的聚類簇中；?

4.4循環n次步驟4.1和步驟4.2，最終生成k個聚類簇：cluster1、cluster2、……、clusterX、……、clusterk，X＝1、2、……、k。?