網格聚類演算法

1. 用於數據挖掘的聚類演算法有哪些，各有何優勢

聚類方法的分類，主要分為層次化聚類演算法，劃分式聚類演算法，基於密度的聚類演算法，基於網格的聚類演算法，基於模型的聚類演算法等。

而衡量聚類演算法優劣的標准主要是這幾個方面：處理大的數據集的能力；處理任意形狀，包括有間隙的嵌套的數據的能力；演算法處理的結果與數據輸入的順序是否相關，也就是說演算法是否獨立於數據輸入順序；處理數據雜訊的能力；是否需要預先知道聚類個數，是否需要用戶給出領域知識；演算法處理有很多屬性數據的能力，也就是對數據維數是否敏感。

.聚類演算法主要有兩種演算法，一種是自下而上法（bottom-up），一種是自上而下法（top-down）。這兩種路徑本質上各有優勢，主要看實際應用的時候要根據數據適用於哪一種，Hierarchical methods中比較新的演算法有BIRCH主要是在數據體量很大的時候使用；ROCK優勢在於異常數據抗干擾性強……

關於數據挖掘的相關學習，推薦CDA數據師的相關課程，課程以項目調動學員數據挖掘實用能力的場景式教學為主，在講師設計的業務場景下由講師不斷提出業務問題，再由學員循序漸進思考並操作解決問題的過程中，幫助學員掌握真正過硬的解決業務問題的數據挖掘能力。這種教學方式能夠引發學員的獨立思考及主觀能動性，學員掌握的技能知識可以快速轉化為自身能夠靈活應用的技能，在面對不同場景時能夠自由發揮。點擊預約免費試聽課。

2. 聚類演算法有哪幾種

聚類分析計算方法主要有： 層次的方法(hierarchical method)、劃分方法(partitioning method)、基於密度的方法(density-based method)、基於網格的方法(grid-based method)、基於模型的方法(model-based method)等。其中，前兩種演算法是利用統計學定義的距離進行度量。

k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心;而對於所剩下其它對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然 後再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

其流程如下：

(1)從 n個數據對象任意選擇 k 個對象作為初始聚類中心;

(2)根據每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離;並根據最小距離重新對相應對象進行劃分;

(3)重新計算每個(有變化)聚類的均值(中心對象);

(4)循環(2)、(3)直到每個聚類不再發生變化為止(標准測量函數收斂)。

優點： 本演算法確定的K個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區別明顯時，效果較好。對於處理大數據集，這個演算法是相對可伸縮和高效的，計算的復雜度為 O(NKt)，其中N是數據對象的數目，t是迭代的次數。

缺點：

1. K 是事先給定的，但非常難以選定;

2. 初始聚類中心的選擇對聚類結果有較大的影響。

3. spark機器學習-聚類

spark機器學習-聚類
聚類演算法是一種無監督學習任務，用於將對象分到具有高度相似性的聚類中，聚類演算法的思想簡單的說就是物以類聚的思想，相同性質的點在空間中表現的較為緊密和接近，主要用於數據探索與異常檢測，最常用的一種聚類演算法是K均值(K-means)聚類演算法

演算法原理
kmeans的計算方法如下：
1 選取k個中心點
2 遍歷所有數據，將每個數據劃分到最近的中心點中
3 計算每個聚類的平均值，並作為新的中心點
4 重復2-3，直到這k個中線點不再變化（收斂了），或執行了足夠多的迭代
演算法的時間復雜度上界為O(n*k*t), 其中k為輸入的聚類個數，n為數據量，t為迭代次數。一般t,k,n均可認為是常量，時間和空間復雜度可以簡化為O(n)，即線性的
spark ml編碼實踐
可在spark-shell環境下修改參數調試以下代碼，可以用實際的業務數據做測試評估，業務數據一般是多列，可以把維度列用VectorAssembler組裝成向量列做為Kmeans演算法的輸入列，考慮現實的應用場景，比如做異常數據檢測，正常數據分為一類，異常數據分為幾類，分別統計正常數據與異常數據的數據量，求百分比等
<span style="font-size:18px;">import org.apache.spark.ml.clustering.KMeans
import org.apache.spark.mllib.linalg.Vectors

val dataset = sqlContext.createDataFrame(Seq(
(1, Vectors.dense(0.0, 0.0, 0.0)),
(2, Vectors.dense(0.1, 0.1, 0.1)),
(3, Vectors.dense(0.2, 0.2, 0.2)),
(4, Vectors.dense(9.0, 9.0, 9.0)),
(5, Vectors.dense(1.1, 1.1, 0.1)),
(6, Vectors.dense(12, 14, 100)),
(6, Vectors.dense(1.1, 0.1, 0.2)),
(6, Vectors.dense(-2, -3, -4)),
(6, Vectors.dense(1.6, 0.6, 0.2))
)).toDF("id", "features")

// Trains a k-means model
val kmeans = new KMeans().setK(3).setMaxIter(20).setFeaturesCol("features").setPredictionCol("prediction")
val model = kmeans.fit(dataset)

// Shows the result
println("Final Centers: ")
model.clusterCenters.foreach(println)
model.clusterCenters.zipWithIndex.foreach(println)

val myres = model.transform(dataset).select("features","prediction")
myres.show()</span>
聚類演算法是一類無監督式機器學習演算法，聚類效果怎麼評估，模型訓練參數怎麼調優，是否能用管道來訓練模型來比較各種不同組合的參數的效果，即網格搜索法(gridsearch),先設置好待測試的參數，MLLib就會自動完成這些參數的不同組合,管道搭建了一條工作流，一次性完成了整個模型的調優，而不是獨立對每個參數進行調優，這個還要再確認一下，查看SPARK-14516好像目前還沒有一個聚類效果通用的自動的度量方法
像這種代碼（不過現在這個代碼有問題）：
<span style="font-size:18px;">import org.apache.spark.ml.clustering.KMeans
import org.apache.spark.mllib.linalg.Vectors
import org.apache.spark.ml.tuning.{ ParamGridBuilder, CrossValidator }
import org.apache.spark.ml.{ Pipeline, PipelineStage }

val dataset = sqlContext.createDataFrame(Seq(
(1, Vectors.dense(0.0, 0.0, 0.0)),
(2, Vectors.dense(0.1, 0.1, 0.1)),
(3, Vectors.dense(0.2, 0.2, 0.2)),
(4, Vectors.dense(9.0, 9.0, 9.0)),
(5, Vectors.dense(1.1, 1.1, 0.1)),
(6, Vectors.dense(12, 14, 100)),
(6, Vectors.dense(1.1, 0.1, 0.2)),
(6, Vectors.dense(-2, -3, -4)),
(6, Vectors.dense(1.6, 0.6, 0.2))
)).toDF("id", "features")

val kmeans = new KMeans().setK(2).setMaxIter(20).setFeaturesCol("features").setPredictionCol("prediction")
//主要問題在這里，沒有可用的評估器與label列設置
val evaluator = new BinaryClassificationEvaluator().setLabelCol("prediction")
val paramGrid = new ParamGridBuilder().addGrid(kmeans.initMode, Array("random")).addGrid(kmeans.k, Array(3, 4)).addGrid(kmeans.maxIter, Array(20, 60)).addGrid(kmeans.seed, Array(1L, 2L)).build()
val steps: Array[PipelineStage] = Array(kmeans)
val pipeline = new Pipeline().setStages(steps)

val cv = new CrossValidator().setEstimator(pipeline).setEvaluator(evaluator).setEstimatorParamMaps(paramGrid).setNumFolds(10)
// Trains a model
val pipelineFittedModel = cv.fit(dataset)</span>

4. 分類和聚類的區別及各自的常見演算法

1、分類和聚類的區別：
Classification (分類)，對於一個classifier，通常需要你告訴它「這個東西被分為某某類」這樣一些例子，理想情況下，一個 classifier 會從它得到的訓練集中進行「學習」，從而具備對未知數據進行分類的能力，這種提供訓練數據的過程通常叫做supervised learning (監督學習)，
Clustering (聚類)，簡單地說就是把相似的東西分到一組，聚類的時候，我們並不關心某一類是什麼，我們需要實現的目標只是把相似的東西聚到一起。因此，一個聚類演算法通常只需要知道如何計算相似度就可以開始工作了，因此 clustering 通常並不需要使用訓練數據進行學習，這在Machine Learning中被稱作unsupervised learning (無監督學習).
2、常見的分類與聚類演算法
所謂分類，簡單來說，就是根據文本的特徵或屬性，劃分到已有的類別中。如在自然語言處理NLP中，我們經常提到的文本分類便就是一個分類問題，一般的模式分類方法都可用於文本分類研究。常用的分類演算法包括：決策樹分類法，樸素貝葉斯分類演算法(native Bayesian classifier)、基於支持向量機(SVM)的分類器，神經網路法，k-最近鄰法(k-nearestneighbor，kNN)，模糊分類法等等。
分類作為一種監督學習方法，要求必須事先明確知道各個類別的信息，並且斷言所有待分類項都有一個類別與之對應。但是很多時候上述條件得不到滿足，尤其是在處理海量數據的時候，如果通過預處理使得數據滿足分類演算法的要求，則代價非常大，這時候可以考慮使用聚類演算法。
而K均值(K-mensclustering)聚類則是最典型的聚類演算法(當然，除此之外，還有很多諸如屬於劃分法K中心點（K-MEDOIDS）演算法、CLARANS演算法；屬於層次法的BIRCH演算法、CURE演算法、CHAMELEON演算法等；基於密度的方法：DBSCAN演算法、OPTICS演算法、DENCLUE演算法等；基於網格的方法：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；基於模型的方法)。

5. 數據挖掘干貨總結（四）--聚類演算法

本文共計2680字，預計閱讀時長七分鍾

聚類演算法

 

一 、 本質

將數據劃分到不同的類里，使相似的數據在同一類里，不相似的數據在不同類里

 

二 、 分類演算法用來解決什麼問題

文本聚類、圖像聚類和商品聚類，便於發現規律，以解決數據稀疏問題

三 、 聚類演算法基礎知識

1. 層次聚類 vs 非層次聚類

– 不同類之間有無包含關系

2. 硬聚類 vs 軟聚類

– 硬聚類：每個對象只屬於一個類

– 軟聚類：每個對象以某個概率屬於每個類

3. 用向量表示對象

– 每個對象用一個向量表示，可以視為高維空間的一個點

– 所有對象形成數據空間（矩陣）

– 相似度計算：Cosine、點積、質心距離

4. 用矩陣列出對象之間的距離、相似度

5. 用字典保存上述矩陣（節省空間）

    D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}

6. 評價方法

– 內部評價法（Internal Evalution）：

• 沒有外部標准，非監督式

• 同類是否相似，跨類是否相異

DB值越小聚類效果越好，反之，越不好

– 外部評價法（External Evalution）：

• 准確度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)

• 精度（Precision）: C11 / (C11 + C21 )

• 召回（Recall）: C11 / (C11 + C12 )

• F值（F-measure）：

β表示對精度P的重視程度，越大越重視，默認設置為1，即變成了F值，F較高時則能說明聚類效果較好。

四 、 有哪些聚類演算法

主要分為 層次化聚類演算法 ， 劃分式聚類演算法 ， 基於密度的聚類演算法 ， 基於網格的聚類演算法 ， 基於模型的聚類演算法等 。

4.1 層次化聚類演算法

又稱樹聚類演算法，透過一種層次架構方式，反復將數據進行分裂或聚合。典型的有BIRCH演算法，CURE演算法，CHAMELEON演算法，Sequence data rough clustering演算法,Between groups average演算法,Furthest neighbor演算法,Neares neighbor演算法等。

凝聚型層次聚類 ：

先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。

演算法流程：

1. 將每個對象看作一類，計算兩兩之間的最小距離；

2. 將距離最小的兩個類合並成一個新類；

3. 重新計算新類與所有類之間的距離；

4. 重復2、3，直到所有類最後合並成一類。

特點：

1. 演算法簡單

2. 層次用於概念聚類（生成概念、文檔層次樹）

3. 聚類對象的兩種表示法都適用

4. 處理大小不同的簇

5. 簇選取步驟在樹狀圖生成之後

4.2 劃分式聚類演算法

預先指定聚類數目或聚類中心，反復迭代逐步降低目標函數誤差值直至收斂，得到最終結果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等

經典K-means：

演算法流程：

1. 隨機地選擇k個對象，每個對象初始地代表了一個簇的中心；

2. 對剩餘的每個對象，根據其與各簇中心的距離，將它賦給最近的簇；

3. 重新計算每個簇的平均值，更新為新的簇中心；

4. 不斷重復2、3，直到准則函數收斂。

特點：

1.K的選擇

2.中心點的選擇

– 隨機

– 多輪隨機：選擇最小的WCSS

3.優點

– 演算法簡單、有效

– 時間復雜度：O(nkt)

4.缺點

– 不適於處理球面數據

– 密度、大小不同的聚類，受K的限制，難於發現自然的聚類

4.3 基於模型的聚類演算法

為每簇假定了一個模型，尋找數據對給定模型的最佳擬合，同一」類「的數據屬於同一種概率分布，即假設數據是根據潛在的概率分布生成的。主要有基於統計學模型的方法和基於神經網路模型的方法，尤其以基於概率模型的方法居多。一個基於模型的演算法可能通過構建反應數據點空間分布的密度函數來定位聚類。基於模型的聚類試圖優化給定的數據和某些數據模型之間的適應性。

SOM 神經網路演算法 ：

該演算法假設在輸入對象中存在一些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特徵保持性質,與實際的大腦處理有很強的理論聯系。

SOM網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特徵。

演算法流程：

1. 網路初始化，對輸出層每個節點權重賦初值；

2. 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；

3. 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；

4. 提供新樣本、進行訓練；

5. 收縮鄰域半徑、減小學習率、重復，直到小於允許值，輸出聚類結果。

4.4 基於密度聚類演算法

只要鄰近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類，擅於解決不規則形狀的聚類問題，廣泛應用於空間信息處理,SGC,GCHL，DBSCAN演算法、OPTICS演算法、DENCLUE演算法。

DBSCAN：

對於集中區域效果較好，為了發現任意形狀的簇，這類方法將簇看做是數據空間中被低密度區域分割開的稠密對象區域；一種基於高密度連通區域的基於密度的聚類方法，該演算法將具有足夠高密度的區域劃分為簇，並在具有雜訊的空間數據中發現任意形狀的簇。

4.5 基於網格的聚類演算法

    基於網格的方法把對象空間量化為有限數目的單元，形成一個網格結構。所有的聚類操作都在這個網格結構（即量化空間）上進行。這種方法的主要優點是它的處理 速度很快，其處理速度獨立於數據對象的數目，只與量化空間中每一維的單元數目有關。但這種演算法效率的提高是以聚類結果的精確性為代價的。經常與基於密度的演算法結合使用。代表演算法有STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法等。 

6. 空間聚類演算法簡述

空間數據聚類演算法主要包括四大類：（1）給予劃分的聚類；（2）基於層次的聚類；（3）基於密度的聚類；（4）基於網格的聚類。時空數據聚類演算法是空間數據聚類演算法的驗身，它將時許維度納入聚類計算中。

1.1基於劃分的空間聚類演算法

k-means演算法 ：用戶定義k個簇的質心位置——將每個數據點聚合到與之最近的質心所在的簇——重新為每個簇計算質心所在位置——重復步驟二和三直到質心收斂。其計算復雜度為 ,T為步驟四中迭代次數，他對於用戶給定的簇中心點的初始位置和雜訊點非常敏感。同時，在處理海量數據的時候運行時間較長。

1.2基於層次的空間聚類演算法

層次聚的目的是將數據對象分配到一個層次結構中，它遵循兩種劇本策略：向上凝聚和向下分裂。向上凝聚方法將每一個對象看做獨立的簇，然後從整個層次結構的底層開始對具有相似特徵的簇聚合，逐層遞歸至頂層。相反，向下分裂方法把所有的數據對象看做同一個簇，然後從整個層次結構的頂層開始，對具有不同特徵的簇進行分裂，逐層遞歸至底層。其計算的事件復雜度是

1.3基於密度的空間聚類演算法

基於茄豎密度的聚類演算法在發現任意形狀和數據造成方面具有獨特的優勢，且不要求對簇的數量進行初始設置。其演算法包括：DBSCAN演算法，OPTICS演算法，DENCLUE演算法，CURD演算法，Incremental DBSCAN演算法，SDBDC演算法，ST-DBSCAN演算法等。DBSCAN是第一個被提出的基於密度的聚類演算法。而密度主要通過兩個基本參數進行定義：空間半徑 和密度閾值MinPts.

DBSCAN基本概念：

演算法的主要缺點是它的運算時間復 ,因此對海量空間數據的聚類過程需要經過一個無法忍受的耗時。它的另一個缺陷是無法支持多密度聚類埋枝、增量聚類和並行計算。許多工作針對這些問題進行了研究他們可以被概括為兩大類工彎納敏作：⑴演算法改進；（2）演算法並行化。傳統的改進方法採用空間索引技術來快速鎖定數據對象。GirDBSCAN被稱為最先進的DBSCAN演算法它基於網格劃分策略極大的減低了演算法的時間復雜度，且沒有計算精度損失。得益於網格的超規則空間結構，任意兩個格子之間的最短空間距離可以很容易被獲取。對於任意點 ，其關於 的近鄰點只存在於一個固定的格子集合范圍內；換言之，那些格子集合范圍外的點一定不是其的近鄰點，因此這些點與點 之間的距離計算可以被省略，從而提高DBSCAN演算法的計算效率。基於這個想法，Gunawan將整個網格劃分為以 為邊長的正方形格子，用於2維空間數據的基於密度聚類計算，使得每個正方格子內的最大空間距離為因此一旦格子內的點的數量達到或超過MinPts，則該格子里的所有點都是核心點，且屬於同一個簇。因此一個簇可以通過密度相連格子和密度可達格子的最大集合進行計算，從而省略了許多點與點之間的距離計算。同時採用了Voronoi圖技術，進一步改進了DBSCAN演算法的運算效率。但是，構建一個Voronoi圖本身需要消耗大量的時間。基於這個想法，Gan和Tao提出了一種關於p近似DBSCAN演算法來獲得近似精度的計算結果，但只需要關於N的線性計算時間，用於取代傳統的DBSCAN演算法。

1.4基於網格的聚類

基於網格聚類演算法將數據空間劃分為規則的互不相交的格子，再將所有的數據對象映射帶網格中基於格子進行聚類。總結一下就是：將對象空間量化為有限數目的單元，形成一個網狀結構，所有聚類都在這個網狀結構上進行。

我們將學習一下STING演算法以及CLIQUE演算法。

7. 聚類演算法有哪些分類

聚類演算法的分類有：

1、劃分法

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K小於N。而且這K個分組滿足下列條件：

（1） 每一個分組至少包含一個數據紀錄；

（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類演算法中可以放寬）；

2、層次法

層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。

例如，在「自底向上」方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合並成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。

3、密度演算法

基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類法

圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源，因而其主要優點是易於處理局部數據的特性。

5、網格演算法

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。

代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；

6、模型演算法

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。

通常有兩種嘗試方向：統計的方案和神經網路的方案。

(7)網格聚類演算法擴展閱讀：

聚類演算法的要求：

1、可伸縮性

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

我們需要具有高度可伸縮性的聚類演算法。

2、不同屬性

許多演算法被設計用來聚類數值類型的數據。但是，應用可能要求聚類其他類型的數據，如二元類型(binary)，分類/標稱類型（categorical/nominal），序數型（ordinal）數據，或者這些數據類型的混合。

3、任意形狀

許多聚類演算法基於歐幾里得或者曼哈頓距離度量來決定聚類。基於這樣的距離度量的演算法趨向於發現具有相近尺度和密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發現任意形狀簇的演算法是很重要的。

4、領域最小化

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

5、處理「雜訊」

絕大多數現實中的資料庫都包含了孤立點，缺失，或者錯誤的數據。一些聚類演算法對於這樣的數據敏感，可能導致低質量的聚類結果。

6、記錄順序

一些聚類演算法對於輸入數據的順序是敏感的。例如，同一個數據集合，當以不同的順序交給同一個演算法時，可能生成差別很大的聚類結果。開發對數據輸入順序不敏感的演算法具有重要的意義。