[發明專利]一種自適應的穩定高效的聚類方法和系統

有效

• 申請號: 201310082671.2
• 申請日: 2013-03-14
• 公開（公告）號: CN103207896B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 張蘭;劉云浩
• 申請（專利權）人: 無錫清華信息科學與技術國家實驗室物聯網技術中心
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京品源專利代理有限公司11332
• 代理人: 馬曉亞

技術領域

本發明涉及計算機信息處理技術領域,尤其涉及一種自適應的穩定高效的聚類方法和系統。?

背景技術

隨著計算機信息的快速增長，人們對各類計算機信息的處理需求越來越強烈。聚類算法作為信息處理中非常重要的一類算法，為各種數據管理、人工智能、機器學習提供了基礎的聚類功能，在各種信息處理中發揮著重要的角色，?

在智能移動終端應用普遍的今天，出現了各種各樣基于智能移動設備的信息服務，它們需要對各種智能終端提供高效穩定的服務，其中大量的服務都需要用到聚類算法，如移動社交網絡中對社交好友的聚類，購物應用中對商品的聚類等。目前大量移動設備終端通過GPS，基站，無線接入點等方式具備了定位能力，因此還產生了許多基于地理位置的服務，而聚類方法則可以為這類服務提供更加豐富和有用的功能，例如分類熱點地區聚類。簡單舉例，目前的電子地圖上往往由用戶添加了各類地理標簽，如購物、美食、景點等，這些地理標簽分散在整個電子地圖上。當一個智能手機用戶外出旅行或逛街時，他常常需要尋找自己感興趣的熱門商圈，即某一類標簽密集的地點，如購物集中的商圈，并獲取導航服務。但是通過目前的手機地圖查詢“購物”卻只能得到分散在整個地圖上的“購物”標簽，讓用戶難以抉擇路線了目標地址。然而通過將這些“購物”標簽的有效聚類，即將標簽劃分為多個密集的子區域（聚類），則能快速發現熱門的“購物”商圈。而通過對多個標簽，如“購物”和“美食”，的聚類結果進行整合，則能有效的幫助用戶發現滿足其多種要求的熱門商圈。聚類方法能為新?型移動設備帶來大量豐富的應用，但是移動終端的應用多樣化和計算資源受限的特點則對聚類方法的提出了自適應，穩定，高效的新需求。?

目前已有多種聚類方法，如常用的k-means和期望最大的方法，雖然它們實現簡單快速，但是它們需要預先設置最終分區的數目，這顯然使得這樣的方法無法適應廣泛的應用。因為在大多數應用中用戶無法預先獲知分區數目，如一個城市究竟有多少個美食聚集地。此外，這兩種方法都存在不穩定的現象，即多次運行得到的聚類結果可能不一致。而另一種叫做QT的方法雖然不需預先設置分區數目，并且能獲取到穩定的聚類結果，但是它卻需要o【(n】³)的計算開銷，面對龐大的信息量，對于計算資源受限的移動設備來說，這樣的開銷往往是難以承受的。?

發明內容

本發明的目的在于提出一種自適應的穩定高效的聚類方法和系統，以解決計算開銷大的問題。?

為達此目的，本發明采用以下技術方案：?

一種自適應的穩定高效的聚類方法，包括：?

a獲取輸入數據的集合為p＝{p₁,...p_n}，集合中包括n個輸入數據，獲取聚類半徑的閾值θ；?

b將p_i以及集合中的與輸入數據p_i的距離小于閾值θ的輸入數據都加入輸入數據p_i對應的候選聚類C_pi,輸入數據p_i表示集合中的第i個輸入數據；?

c令候選聚類C_pi中的輸入數據為m個,函數d(p_i,p_j)為兩個輸入數據p_i,p_j之?間距離，計算輸入數據p_i作為聚類中心的概率為??????????????????????????????????????????????????1≤j≤m；?

d從集合的輸入數據中，選出成為聚類中心概率最大的輸入數據，將該選出的輸入數據對應的候選聚類加入最終聚類。?

進一步的，所述將該選出的輸入數據對應的候選聚類加入最終聚類之后，進一步包括：?

e從輸入數據集合中刪除加入最終聚類的輸入數據，重新從當前輸入數據集合中選出成為聚類中心概率最大的輸入數據，將該選出的輸入數據對應的候選聚類加入最終聚類；?

判斷集合中的輸入數據的數量是否為零，如果是，則結束，否則，繼續步驟e。?

一種自適應的穩定高效的聚類系統，包括：?

初始化模塊，用于獲取輸入數據的集合為p＝{p₁,...p_n}，集合中包括n個輸入數據，獲取聚類半徑的閾值θ；?