基于位置信息的聚類算法介紹及模型選擇

基于位置信息的聚類算法介紹及模型選擇

百度百科

聚類：將物理或抽象對象的集合分成由類似的對象組成的多個類的過程被稱為聚類。由聚類所生成的簇是一組數據對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異。“物以類聚，人以群分”，在自然科學和社會科學中，存在著大量的分類問題。聚類分析又稱群分析，它是研究（樣品或指標）分類問題的一種統計分析方法。聚類分析起源于分類學，但是聚類不等于分類。聚類與分類的不同在于，聚類所要求劃分的類是未知的。

分類和聚類算法一直以來都是數據挖掘，機器學習領域的熱門課題，因此產生了眾多的算法及改進算法，以應對現實世界中業務需求。正因為算法的多樣性，選擇一個合適的算法，就需要對常用的算法進行了解，并進行比較。最終選擇一個適合業務需求的算法模型。

1.     對聚類分析的要求

可伸縮性：許多聚類算法在小數據集合上運行良好，然而在大型數據庫可能包含數百萬甚至數十億個對象。在大型數據集上進行聚類可能會導致有偏的結果，甚至程序在一定時間內根本無法計算出結果。因此需要高度可伸縮性的聚類算法。

處理不同屬性類型：許多算法是為聚類數值的數據設計的。然而，應用可能要求聚類其他類型的數據，如二元、標稱、序數或者這些數據類型的混合?，F在，越來越多的應用需要對諸如圖、序列、圖像和文檔等復雜的數據類型進行聚類分析。

發現任意形狀的簇：許多聚類算法基于歐幾里得或曼哈頓距離度量來確定簇?；谶@些距離度量的算法趨向于發現具有相近尺寸和密度的球狀簇。然而，一個簇可能是任意形狀的。

對于確定輸入參數的領域知識的要求：許多聚類算法都要求用戶以輸入參數（如希望產生的簇數）的形式提供領域知識。因此，聚類結果可能對這些參數十分敏感。通常，參數很難確定，對于高維數據集和用戶尚未深入理解的數據來說更是如此。

處理噪聲數據的能力：現實世界中的大部分數據集都包含離群點/缺失數據、未知或錯誤的數據。一些聚類算法可能對這樣的噪聲敏感，從而產生低質量的聚類結果。

增量聚類和對輸入次序不敏感：在許多應用中，增量更新可能是需要的。一些聚類算法不能將新插入的數據（如數據庫更新）合并到已有的聚類結構中去，而是需要從頭開始聚類。一些算法還可能對輸入數據的次序敏感。也就是說，給定數據對象集合，當以不同的次序提供時，算法可能產生差別很大的聚類結果。需要開發增量聚類算法和對數據輸入不敏感的算法。

聚類高維數據的能力：數據集可能包含大量的維。例如，在文檔聚類時，每個關鍵詞都可以看成一個維，并且常常有數以千計的關鍵詞。許多算法擅長處理低維數據，發現高維空閑中數據對象的簇是一個挑戰，特別是考慮這樣的數據可能非常稀疏，并且高度傾斜。

基于約束的聚類：現實世界的應用可能需要在各種約束條件下進行聚類。找到既滿足特定的約束又具有良好聚類特性的數據分組是一項具有挑戰性的任務。

可解釋性和可用性：用戶希望聚類結果是可解釋的、可理解的和可用的。也就是說，聚類算法可能需要與特定的語義解釋和應用相聯系。

劃分準則：在某些方法中，所有的對象都被劃分，使得簇之間不存在層次結。也就是說，在概念上，所有的簇都在相同的層。另外，其他方法利用分層的思想劃分數據對象，其中簇可以在不同語義層形成。

簇的分離性：有些聚類方法把數據分成互斥的簇。但在一些情況下，簇可以不是互斥的，即一個數據對象可以屬于多個簇。如在把文檔聚類到主題時，一個文檔可能與多個主題有關。因此作為簇的主題可能不是互斥的。

相似性度量：有些方法用對象之間的距離確定兩個對象之間的相似性。這種距離可以在歐式空間，公路網，向量空間或其他空間中定義。在其他方法中，相似性可以用基于密度的連接性和鄰近性定義，并且不依賴兩個對象之間的絕對距離。

聚類空間：許多聚類方法都在整個給定的數據空間中搜索簇。這些方法對于低維數據集是有用的。然而，對于高維數據，可能有許多不相關的屬性，使得相似性度量不可靠。因此，在整個空間中發現的簇常常是沒有意義的。最好在相同的數據集的不同子空間內搜索簇。子空間聚類發現揭示對象相似性的簇和子空間。

以上內容大多來自《數據挖掘-概念與技術》?？傊?，聚類算法具有多種要求。因此在開始選擇算法時，就需要根據實際業務需求確定聚類算法的要求。

2.     基本聚類方法

2.1      劃分方法

給定一個n個對象的集合，劃分方法構建數據的k個分區，其中每個分區表示一個簇。也就是說它把數據劃分為k個簇，使得每個簇至少包含一個對象。典型的，基本劃分方法采取互斥的簇劃分，這一要求，例如在模糊劃分技術中，可以放寬。

特點：

─發現球形互斥的簇；

─基于距離；

─可以用均值或中心點等代表簇中心；

─對中小規模數據集有效；

最常用劃分方法：

2.1.1        k-均值：

算法把簇的形心定義為簇內點的均值。它的處理流程如下。首先，在D中隨機地選擇k個對象，每個對象代表一個簇的初始均值（中心）。對剩下的每個對象，根據其與各個簇中心的歐式距離，將它分配到最相近的簇。然后，重新計算簇內對象的均值（中心），不斷迭代，直到各個簇內對象不再發生變化（或者滿足要求）。

算法流程如下：

輸入：

    k：簇的數目

     D：包含n個對象的數據集

輸出：k個簇的集合

算法：

（1）    從D中任意選擇k個對象作為初始簇中心；

（2）    Repeat

（3）      根據簇中對象的均值，將每個對象分配到最相似的簇；

（4）      更新簇中心；

（5）    Until不再發生變化（或者滿足要求）。

k-均值缺點：

（1）    聚類質量依賴于初始簇中心，解決辦法：以不同的初始簇中心，多次運行k-均值算法；二分k-均值算法，該算法對初始簇中心較不敏感。

（2）    當涉及具有標稱屬性的數據時，均值可能無定義，解決辦法：k-眾數（k-modes）方法，用簇眾數取代簇均值，采用基于頻率的方法來更新簇的眾數?？梢约?/span>k-均值和k-眾數方法。對混合類型的數據進行聚類。

（3）    K值的選擇：提供k值的近似范圍，通過比較不同k值得到的聚類結果，確定最佳的值；

（4）    不適合發現非凸球形的簇，或大小差別很大的簇；

（5）    對噪聲和離群點敏感：k-中心點算法；

（6）    可伸縮性有待提高：在聚類時使用合適規模的樣本；過濾方法，使用空間層次數據索引節省計算均值的開銷；利用微聚類的思想，首先把近鄰的對象劃分到一些“微簇”，然后對這些微簇使用k-均值算法進行聚類。

2.1.2            k-中心點：

不采用簇中對象的均值作為參照點，而是挑選實際對象來代表簇，每個簇使用一個代表對象。其余的每個對象被分配到與其最近的代表對象所在的簇中?；谧钚』袑ο?/span>p與其對應的代表之間的相異度之和的原則來進行劃分。

算法流程如下：

算法描述：k-中心點。圍繞中心點劃分（PAM），一種基于中心點或中心對象進行劃分的k-中心點算法。

輸入：

    k：簇的數目

             D：包含n個對象的數據集

  輸出：k個簇的集合

算法：

2.2      層次方法

盡管劃分方法滿足把對象劃分成一些互斥的組群的基本聚類要求，但是在某些情況下，我們想把數據劃分成不同層上的組群，如層次。層次聚類方法（hierarchical clustering method）將數據對象組成層次結構或簇的“樹”。

2.2.1        層次凝聚方法

使用自底向上的策略，令每個對象形成自己的簇開始，并且迭代地把簇合并成越來越大的簇，直到所有對象都在一個簇中，或者滿足某個終止條件。在合并過程中，找出兩個最接近的簇（根據某種相似性度量），并且合并它們，形成一個簇。因為每次迭代合并兩個簇，其中每個簇至少包含一個對象，因此凝聚方法最多需要n次迭代。

2.2.2        層次分裂方法

使用自頂向下的策略。它把所有對象置于一個簇中，該簇是層次結構的根。然后把根上的簇劃分成多個較小的子簇，并且遞歸地把這些簇劃分成更小的簇。直到最底層的簇都足夠凝聚，或者僅包含一個對象。

特點：

─聚類時一個層次分解（即多層）；

─不能糾正錯誤的合并或劃分；

─可以集成其他技術，如微聚類或考慮對象“連接”；

─凝聚方法遠比分裂方法多。

    它們趨向對離群點和噪聲數據過分敏感。使用均值或平均距離是一種折中方法，可以克服離群點敏感性問題。平均距離既能夠處理數值數據又能處理分類數據。

2.3      實際應用分析

由于本次實際應用需求較簡單，上述常用算法能夠很好地運用，并且原理簡單，實現方便。

2.1.3        問題簡述

    位置信息是基于GPS上傳的經緯度信息，每個一定時間周期設備會上傳所在位置的經緯度信息。如下圖所示，紅圈位置表示車輛停留聚集的地方，在定義上屬于異常點或離群點。因為這些點一般都比較固定，所以不需要每次都在整個數據集上進行識別。不然不僅效率低，而且算法更加復雜。

圖3-1

圖3-2

圖3-3

圖3-4

1. 2.1.4        算法思路

問題關鍵：

（1）    位置信息24小時上傳，位置信息遍布于路段附近的整張路網，且有些目標區域的密度并不比正常區域的密度大，因此基于密度的方法無效。

（2）    利用位置信息+時間信息。

（3）    由于簇數量K未知，所以不建議使用劃分方法，本次采用層次方法。

（4）    采用距離度量來確定簇內的相似性與簇間的相異性。且距離度量采用經緯度計算，通常采用google的距離計算公司。

（5）    聚類完成后根據結果劃分區域，一般可劃分為矩形區域或圓形區域。

由于算法涉及實際項目，考慮到機密問題，具體算法不在此詳細描述。

1. 2.4      總結

本文檔介紹了最基本的聚類算法原理，及簡單應用。聚類算法要較好的應用實際項目，還有很多的算法可以比較。如基于密度的方法，基于概率的方法，模糊集聚類，網格聚類，基于高維空間的譜聚類，圖聚類。后續考慮進一步補充完善。