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

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

百度百科

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

分類和聚類算法一直以來都是數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)領(lǐng)域的熱門課題，因此產(chǎn)生了眾多的算法及改進(jìn)算法，以應(yīng)對現(xiàn)實(shí)世界中業(yè)務(wù)需求。正因?yàn)樗惴ǖ亩鄻有?，選擇一個(gè)合適的算法，就需要對常用的算法進(jìn)行了解，并進(jìn)行比較。最終選擇一個(gè)適合業(yè)務(wù)需求的算法模型。

1.     對聚類分析的要求

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

處理不同屬性類型：許多算法是為聚類數(shù)值的數(shù)據(jù)設(shè)計(jì)的。然而，應(yīng)用可能要求聚類其他類型的數(shù)據(jù)，如二元、標(biāo)稱、序數(shù)或者這些數(shù)據(jù)類型的混合。現(xiàn)在，越來越多的應(yīng)用需要對諸如圖、序列、圖像和文檔等復(fù)雜的數(shù)據(jù)類型進(jìn)行聚類分析。

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

對于確定輸入?yún)?shù)的領(lǐng)域知識的要求：許多聚類算法都要求用戶以輸入?yún)?shù)（如希望產(chǎn)生的簇?cái)?shù)）的形式提供領(lǐng)域知識。因此，聚類結(jié)果可能對這些參數(shù)十分敏感。通常，參數(shù)很難確定，對于高維數(shù)據(jù)集和用戶尚未深入理解的數(shù)據(jù)來說更是如此。

處理噪聲數(shù)據(jù)的能力：現(xiàn)實(shí)世界中的大部分?jǐn)?shù)據(jù)集都包含離群點(diǎn)/缺失數(shù)據(jù)、未知或錯(cuò)誤的數(shù)據(jù)。一些聚類算法可能對這樣的噪聲敏感，從而產(chǎn)生低質(zhì)量的聚類結(jié)果。

增量聚類和對輸入次序不敏感：在許多應(yīng)用中，增量更新可能是需要的。一些聚類算法不能將新插入的數(shù)據(jù)（如數(shù)據(jù)庫更新）合并到已有的聚類結(jié)構(gòu)中去，而是需要從頭開始聚類。一些算法還可能對輸入數(shù)據(jù)的次序敏感。也就是說，給定數(shù)據(jù)對象集合，當(dāng)以不同的次序提供時(shí)，算法可能產(chǎn)生差別很大的聚類結(jié)果。需要開發(fā)增量聚類算法和對數(shù)據(jù)輸入不敏感的算法。

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

基于約束的聚類：現(xiàn)實(shí)世界的應(yīng)用可能需要在各種約束條件下進(jìn)行聚類。找到既滿足特定的約束又具有良好聚類特性的數(shù)據(jù)分組是一項(xiàng)具有挑戰(zhàn)性的任務(wù)。

可解釋性和可用性：用戶希望聚類結(jié)果是可解釋的、可理解的和可用的。也就是說，聚類算法可能需要與特定的語義解釋和應(yīng)用相聯(lián)系。

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

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

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

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

以上內(nèi)容大多來自《數(shù)據(jù)挖掘-概念與技術(shù)》。總之，聚類算法具有多種要求。因此在開始選擇算法時(shí)，就需要根據(jù)實(shí)際業(yè)務(wù)需求確定聚類算法的要求。

2.     基本聚類方法

2.1      劃分方法

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

特點(diǎn)：

─發(fā)現(xiàn)球形互斥的簇；

─基于距離；

─可以用均值或中心點(diǎn)等代表簇中心；

─對中小規(guī)模數(shù)據(jù)集有效；

最常用劃分方法：

2.1.1        k-均值：

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

算法流程如下：

輸入：

    k：簇的數(shù)目

     D：包含n個(gè)對象的數(shù)據(jù)集

輸出：k個(gè)簇的集合

算法：

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

（2）    Repeat

（3）      根據(jù)簇中對象的均值，將每個(gè)對象分配到最相似的簇；

（4）      更新簇中心；

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

k-均值缺點(diǎn)：

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

（2）    當(dāng)涉及具有標(biāo)稱屬性的數(shù)據(jù)時(shí)，均值可能無定義，解決辦法：k-眾數(shù)（k-modes）方法，用簇眾數(shù)取代簇均值，采用基于頻率的方法來更新簇的眾數(shù)。可以集成k-均值和k-眾數(shù)方法。對混合類型的數(shù)據(jù)進(jìn)行聚類。

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

（4）    不適合發(fā)現(xiàn)非凸球形的簇，或大小差別很大的簇；

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

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

2.1.2            k-中心點(diǎn)：

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

算法流程如下：

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

輸入：

    k：簇的數(shù)目

             D：包含n個(gè)對象的數(shù)據(jù)集

  輸出：k個(gè)簇的集合

算法：

2.2      層次方法

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

2.2.1        層次凝聚方法

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

2.2.2        層次分裂方法

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

特點(diǎn)：

─聚類時(shí)一個(gè)層次分解（即多層）；

─不能糾正錯(cuò)誤的合并或劃分；

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

─凝聚方法遠(yuǎn)比分裂方法多。

    它們趨向?qū)﹄x群點(diǎn)和噪聲數(shù)據(jù)過分敏感。使用均值或平均距離是一種折中方法，可以克服離群點(diǎn)敏感性問題。平均距離既能夠處理數(shù)值數(shù)據(jù)又能處理分類數(shù)據(jù)。

2.3      實(shí)際應(yīng)用分析

由于本次實(shí)際應(yīng)用需求較簡單，上述常用算法能夠很好地運(yùn)用，并且原理簡單，實(shí)現(xiàn)方便。

2.1.3        問題簡述

    位置信息是基于GPS上傳的經(jīng)緯度信息，每個(gè)一定時(shí)間周期設(shè)備會上傳所在位置的經(jīng)緯度信息。如下圖所示，紅圈位置表示車輛停留聚集的地方，在定義上屬于異常點(diǎn)或離群點(diǎn)。因?yàn)檫@些點(diǎn)一般都比較固定，所以不需要每次都在整個(gè)數(shù)據(jù)集上進(jìn)行識別。不然不僅效率低，而且算法更加復(fù)雜。

圖3-1

圖3-2

圖3-3

圖3-4

1. 2.1.4        算法思路

問題關(guān)鍵：

（1）    位置信息24小時(shí)上傳，位置信息遍布于路段附近的整張路網(wǎng)，且有些目標(biāo)區(qū)域的密度并不比正常區(qū)域的密度大，因此基于密度的方法無效。

（2）    利用位置信息+時(shí)間信息。

（3）    由于簇?cái)?shù)量K未知，所以不建議使用劃分方法，本次采用層次方法。

（4）    采用距離度量來確定簇內(nèi)的相似性與簇間的相異性。且距離度量采用經(jīng)緯度計(jì)算，通常采用google的距離計(jì)算公司。

（5）    聚類完成后根據(jù)結(jié)果劃分區(qū)域，一般可劃分為矩形區(qū)域或圓形區(qū)域。

由于算法涉及實(shí)際項(xiàng)目，考慮到機(jī)密問題，具體算法不在此詳細(xì)描述。

1. 2.4      總結(jié)

本文檔介紹了最基本的聚類算法原理，及簡單應(yīng)用。聚類算法要較好的應(yīng)用實(shí)際項(xiàng)目，還有很多的算法可以比較。如基于密度的方法，基于概率的方法，模糊集聚類，網(wǎng)格聚類，基于高維空間的譜聚類，圖聚類。后續(xù)考慮進(jìn)一步補(bǔ)充完善。