基本介紹
- 中文名：聚類搜尋算法
- 外文名：Clustering search algorithm
- 學科：計算機科學與技術
- 定義：結合聚類的特點和搜尋的要求
- 有關術語：聚類分析
- 領域：搜尋引擎、市場分析
定義,聚類算法分類,劃分法,層次法,密度算法,圖論聚類法,格線算法,模型算法,增廣鏈修復下大數據並行搜尋聚類算法,背景,方案,
定義
聚類分析（Cluster analysis，亦稱為群集分析）是對於統計數據分析的一門技術，在許多領域受到廣泛套用，包括機器學習，數據挖掘，模式識別，圖像分析以及生物信息。聚類分析是根據事物本身的特性研究個體的一種方法，目的在於將相似的事物歸類。它的原則是同一類中的個體有較大的相似性，不同類的個體差異性很大。這種方法有三個特徵：
（1）適用於沒有先驗知識的分類。如果沒有這些事先的經驗或一些國際標準、國內標準、行業標準，分類便會顯得隨意和主觀。這時只要設定比較完善的分類變數，就可以通過聚類分析法得到較為科學合理的類別；
（2）可以處理多個變數決定的分類。例如，要根據消費者購買量的大小進行分類比較容易，但如果在進行數據挖掘時，要求根據消費者的購買量、家庭收入、家庭支出、年齡等多個指標進行分類通常比較複雜，而聚類分析法可以解決這類問題；
（3）聚類分析法是一種探索性分析方法，能夠分析事物的內在特點和規律，並根據相似性原則對事物進行分組，是數據挖掘中常用的一種技術。
搜尋是人工智慧的基本技術之一，指計算機找出從初始狀態轉化到目標狀態的途徑，根據給定條件求解一個問題正確答案的過程。一個有趣的例子是：3個馴獸員帶著3隻熊和1條船在左岸(初始狀態)，要把人、熊、船都渡到右岸去(目標狀態)，給定條件是人或熊都會划船、但船每次最多只能裝載或兩人或兩熊或一人一熊、而且無論左岸或右岸都不允許出現熊多於人的情況(否則熊會傷人)，為順利到達右岸而尋找正確解決這個問題的可靠方法的過程就叫搜尋。
搜尋要講究策略方法，一個最佳搜尋的標準是：
(1)在問題有解的場合下能保證成功；
(2)必須花的搜尋工作量最少；
(3) 找到的途徑是最短的 (捷徑)；
(4)沿著找到的途徑進行實際操作的費用最小。
針對一個實際分類搜尋問題時，一個好的聚類搜尋算法設計一般要考慮聚類的特點以及搜尋的要求。儘量使算法性能在各個方面達到最佳或者最佳。
聚類算法分類
很難對聚類方法提出一個簡潔的分類，因為這些類別可能重疊，從而使得一種方法具有幾類的特徵，儘管如此，對於各種不同的聚類方法提供一個相對有組織的描述依然是有用的，為聚類分析計算方法主要有如下幾種：
劃分法
劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。而且這K個分組滿足下列條件：
（1） 每一個分組至少包含一個數據紀錄；
（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類算法中可以放寬）；
對於給定的K，算法首先給出一個初始的分組方法，以後通過反覆疊代的方法改變分組，使得每一次改進之後的分組方案都較前一次好，而所謂好的標準就是：同一分組中的記錄越近越好，而不同分組中的紀錄越遠越好。
大部分劃分方法是基於距離的。給定要構建的分區數k，劃分方法首先創建一個初始化劃分。然後，它採用一種疊代的重定位技術，通過把對象從一個組移動到另一個組來進行劃分。一個好的劃分的一般準備是：同一個簇中的對象儘可能相互接近或相關，而不同的簇中的對象儘可能遠離或不同。還有許多評判劃分質量的其他準則。傳統的劃分方法可以擴展到子空間聚類，而不是搜尋整個數據空間。當存在很多屬性並且數據稀疏時，這是有用的。為了達到全局最優，基於劃分的聚類可能需要窮舉所有可能的劃分，計算量極大。實際上，大多數套用都採用了流行的啟發式方法，如k-均值和k-中心算法，漸近的提高聚類質量，逼近局部最優解。這些啟發式聚類方法很適合發現中小規模的資料庫中小規模的資料庫中的球狀簇。為了發現具有複雜形狀的簇和對超大型數據集進行聚類，需要進一步擴展基於劃分的方法。[1]
使用這個基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法；
層次法
層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為“自底向上”和“自頂向下”兩種方案。
例如，在“自底向上”方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的疊代中，它把那些相互鄰近的組合併成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。
層次聚類方法可以是基於距離的或基於密度或連通性的。層次聚類方法的一些擴展也考慮了子空間聚類。層次方法的缺陷在於，一旦一個步驟（合併或分裂）完成，它就不能被撤銷。這個嚴格規定是有用的，因為不用擔心不同選擇的組合數目，它將產生較小的計算開銷。然而這種技術不能更正錯誤的決定。已經提出了一些提高層次聚類質量的方法。[1]
代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等；
密度算法
基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的算法只能發現“類圓形”的聚類的缺點。
這個方法的指導思想就是，只要一個區域中的點的密度大過某個閾值，就把它加到與之相近的聚類中去。
代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等；
圖論聚類法
圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連線特徵作為聚類的主要信息源，因而其主要優點是易於處理局部數據的特性。
格線算法
基於格線的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的格線結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。
代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；
模型算法
基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函式或者其它。它的一個潛在的假定就是：目標數據集是由一系列的機率分布所決定的。
增廣鏈修復下大數據並行搜尋聚類算法
背景
數據聚類在工程設計、計算機網路及信息處理、機械故障診斷、雷達目標識別、資料庫建立、人工智慧等許多領域具有廣泛的套用前景。通過設計有效的聚類算法，通過計算機軟體處理，對數據和信息進行聚類處理再作之後的研究和處理，既是信號與信息處理的關鍵一步，也是提高效率，減少運算開支的根本途徑。多源語義特徵分層資料庫是構建數位化信息系統的基礎，多源語義特徵分層資料庫將大量網路計算資源、存儲資源與軟體資源等多源信息資源進行多層次的虛擬化和抽象，統一調度，以網路服務的方式向用戶提供按需服務的IT服務模式，多源語義特徵分層資料庫進行大數據聚類，實現數據的分類識別。
方案
多源語義特徵分層資料庫中由於路由衝突，在鏈路負載較大的情況下，不能有效實現對大數據語義特徵的並行搜尋。提出一種基於增廣鏈同態解析的鏈路分流方法避免路由衝突，實現增廣鏈修復下大數據並行搜尋聚類。構建大數據聚類的語義相似度融合模型，基於跨層鏈路分流算法實現增廣鏈路分流，進行語義本體模型構建，選擇採用高階貝塞爾函式累積量作為增廣鏈修復檢驗統計量，確定節點數據包的置信度，確立置信區間，在進行緩衝區溢出修復時，進行功率譜幅度特徵提取，實現大數據的並行搜尋聚類，進行語義本體模型構建，為離群點新建一個簇，依次對每個文檔的主題詞集進行處理，將每個主題詞自動添加入形式背景的屬性集中，採用並行搜尋算法實現對語義大數據的最佳化聚類算法改進。仿真實驗進行了性能驗證，研究結果表明，採用本文算法能有效提高大數據聚類性能，聚類的切合度較好，誤分率較低。
