一墙杯、聚類算法
聚類屬于無(wú)監(jiān)督學(xué)習(xí)，是數(shù)據(jù)挖掘十大經(jīng)典算法之一 括荡。
二高镐、k-means聚類算法簡(jiǎn)介
1、k-means聚類算法的邏輯
- a. 給定一組數(shù)據(jù)集畸冲，先確定好需要分類個(gè)數(shù)k嫉髓，最大歸類迭代次數(shù)maxit，分類點(diǎn)最小移動(dòng)值cutoff召夹；
-
b. 對(duì)數(shù)據(jù)集進(jìn)行歸一化處理岩喷；
歸一化公式 - c. 初始化一個(gè)k行 X n列的矩陣centroid，n為分類數(shù)據(jù)集的特征個(gè)數(shù)监憎，隨機(jī)在數(shù)據(jù)集中抽取k組數(shù)據(jù)特征填入其中
- d. 遍歷整個(gè)數(shù)據(jù)集纱意，計(jì)算其與每個(gè)矩陣centroid的歐式距離，并將其賦值給距離最短的一個(gè)
- e. 一輪遍歷之后重新計(jì)算每個(gè)類的中心鲸阔，中心點(diǎn)的值為同一類所有點(diǎn)的平均值偷霉。并與原矩陣centroid計(jì)算歐式距離，若中心點(diǎn)偏移不超過(guò)cutoff值，則聚類結(jié)束，最終的centroid為每個(gè)類的中心點(diǎn)昭雌。否則用重新計(jì)算的中心循環(huán)過(guò)程d、e硫狞，直到maxit歸0。
python實(shí)現(xiàn)代碼如下：
# -*- coding: utf-8 -*-
"""
Created on Tue May 29 14:27:54 2018
@author: junzhu
"""
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
#import data
def import_data():
with pd.ExcelFile('users.xlsx') as x:
df = pd.read_excel(x,sheetname = 'Sheet1')
return df
#data standardization
def data_standardization(dataset):
min_col = np.amin(dataset[:,1:],axis = 0)
# max_col = np.amax(dataset[:,1:],axis = 0)
ptp_col = np.ptp(dataset[:,1:],axis = 0)
dataset[:,1:] = (dataset[:,1:]-min_col) / ptp_col
return dataset
#add one column to the end
def add_column(dataset):
add_col = np.zeros((len(dataset),1))
added_dataset = np.concatenate((dataset,add_col),axis = 1)
return added_dataset
#calculate,classify,update
def kmeans(k,maxit,cutoff,dataset_fin,centroid):
old_centroid = np.array([])
while not stop_signal(old_centroid,centroid,cutoff,maxit):
#calculate distance and classify
maxit -= 1
row_num = dataset_fin.shape[0]
for i in range(row_num):
mindis = np.inf
sample_data = dataset_fin[i,1:-1]
for j in range(k):
centroid_data = centroid[j,:-1]
distance = o_distance(sample_data,centroid_data)
if distance < mindis:
mindis = distance
dataset_fin[i,-1] = j + 1
#update centroid
old_centroid = centroid.copy()
for n in range(1,k+1):
new_tempt = dataset_fin[np.nonzero(dataset_fin[:,-1] == n)[0],1:-1]
centroid[np.nonzero(centroid[:,-1] == n)[0],:-1] = np.mean(new_tempt,axis = 0)
return dataset_fin,centroid
def o_distance(x1,x2):
distance = np.sqrt(np.sum(np.power((x1-x2),2)))
return distance
def stop_signal(old_centroid,centroid,cutoff,maxit = 20):
if len(old_centroid) == 0:
return False
elif (o_distance(old_centroid[:,:-1],centroid[:,:-1]) < cutoff):
return True
elif maxit == 0:
return True
else:
return False
#################################################################
def run_main():
#set-up k,cutoff,maxiteration
k = 3
cutoff = 0.02
maxit = 10
#import data
dataset = import_data()
row_num,column_num = dataset.shape
#data standardization
dataset = dataset.as_matrix()
dataset_std = data_standardization(dataset)
#add one column to the end
dataset_fin = add_column(dataset_std)
#initialize k-matrix
centroid = np.zeros((k,column_num))
centroid[:,-1] = np.arange(1,k+1)
for i in range(k):
centroid[i,:-1] = dataset_fin[np.random.choice(np.arange(row_num)),1:-1]
#finally result
dataset_kmeans , centroid_kmeans = kmeans(k,maxit,cutoff,dataset_fin,centroid)
print('dataset_kmeans:\n',dataset_kmeans)
if __name__ == '__main__':
run_main()
以上是k-means聚類的思路和代碼。
2残吩、k-means聚類的優(yōu)點(diǎn)是：
1）原理比較簡(jiǎn)單财忽，實(shí)現(xiàn)也是很容易，收斂速度快泣侮。
2）聚類效果較優(yōu)即彪。
3）算法的可解釋度比較強(qiáng)。
4）主要需要調(diào)參的參數(shù)僅僅是簇?cái)?shù)k活尊。
3隶校、k-means聚類的缺點(diǎn)有：
1）K值的選取不好把握。
2）如果各隱含類別的數(shù)據(jù)不平衡蛹锰，比如各隱含類別的數(shù)據(jù)量嚴(yán)重失衡深胳，或者各隱含類別的方差不同，則聚類效果不佳宁仔。
3）采用迭代方法稠屠，得到的結(jié)果只是局部最優(yōu)。
4）對(duì)噪音和異常點(diǎn)比較的敏感翎苫。(改進(jìn)1：離群點(diǎn)檢測(cè)的LOF算法，通過(guò)去除離群點(diǎn)后再聚類榨了，可以減少離群點(diǎn)和孤立點(diǎn)對(duì)于聚類效果的影響煎谍；改進(jìn)2：改成求點(diǎn)的中位數(shù)，這種聚類方式即K-Mediods聚類（K中值）)龙屉。
針對(duì)k-means聚類的缺點(diǎn)呐粘，有一個(gè)改進(jìn)的方法是采用二分k-means聚類。
三转捕、二分k-means聚類
二分k-means是一種層次聚類方法作岖，簡(jiǎn)單說(shuō)就是一個(gè)不斷分裂,擇優(yōu)錄用的過(guò)程。
它的一個(gè)原則是：因?yàn)榫垲惖恼`差平方和能夠衡量聚類性能五芝，該值越小表示數(shù)據(jù)點(diǎn)月接近于它們的質(zhì)心痘儡，聚類效果就越好。所以我們就需要對(duì)誤差平方和最大的簇進(jìn)行再一次的劃分枢步，因?yàn)檎`差平方和越大沉删，表示該簇聚類越不好，越有可能是多個(gè)簇被當(dāng)成一個(gè)簇了醉途，所以我們首先需要對(duì)這個(gè)簇進(jìn)行劃分矾瑰。
1、二分k-means聚類的邏輯
- a. 給定一組數(shù)據(jù)集隘擎，先確定好需要分類個(gè)數(shù)k殴穴；
-
b. 對(duì)數(shù)據(jù)集進(jìn)行歸一化處理；
歸一化公式 - c. 初始化一個(gè)m行 X 2列的矩陣clusterAssment，m為待分類數(shù)據(jù)集的樣本個(gè)數(shù)采幌。clusterAssment[0]存放分類編號(hào)恍涂，clusterAssment[1]存放距離差的平方和
- d. 初始化列表centList，用于存放中心點(diǎn)值
- e. 首先利用k-means法將原數(shù)據(jù)分成2部分：A,B植榕，并記錄
- f. 然后將A,B再利用k-means法各分成2部分：A1,A2,B1,B2再沧，計(jì)算A1,A2,B的距離差平方x和計(jì)算B1,B2,A的距離差平方y(tǒng)，選擇x尊残，y中小的那個(gè)值炒瘸，例如x最小，則本輪后的分類為A1,A2,B三類寝衫，并記錄
- g. 重復(fù)f步驟顷扩， 利用k-means法將A1,A2,B各分成2部分，并擇優(yōu)錄用慰毅，直到最終分類個(gè)數(shù)達(dá)到k則停止隘截。
python實(shí)現(xiàn)代碼如下：
#encoding=utf-8
from numpy import*
import matplotlib.pyplot as plt
def getDistance(vecA,vecB):
'''
本函數(shù)用于計(jì)算歐氏距離
:param vecA: 向量A
:param vecB: 向量B
:return:歐氏距離
'''
return sqrt(sum(power(vecA-vecB,2)))
def randCent(dataSet,k):
'''
本函數(shù)用于生成k個(gè)隨機(jī)質(zhì)心
:param dataSet: 數(shù)據(jù)集，具有矩陣形式
:param k:指定的質(zhì)心個(gè)數(shù)
:return:隨機(jī)質(zhì)心汹胃，具有矩陣形式
'''
n = shape(dataSet)[1] # 獲取特征數(shù)目
centRoids = mat(zeros((k,n)))
for j in range(n):
minJ = min(dataSet[:,j]) # 獲取每個(gè)特征的最小值
rangeJ = float(max(dataSet[:,j]-minJ)) # 獲取每個(gè)特征的范圍
centRoids[:,j] = minJ + rangeJ*random.rand(k,1) # numpy下的rand表示隨機(jī)生成k*1的隨機(jī)數(shù)矩陣婶芭，范圍0-1
return centRoids
#k-means算法，同上面的k-means算法在代碼上略有不同
def kMeans(dataSet,k,disMens = getDistance,createCent = randCent):
'''
本函數(shù)用于k均值聚類
:param dataSet: 數(shù)據(jù)集着饥，要求有矩陣形式
:param k: 指定聚類的個(gè)數(shù)
:param disMens: 求解距離的方式犀农，除歐式距離還可以定義其他距離計(jì)算方式
:param createCent: 生成隨機(jī)質(zhì)心方式
:return:隨機(jī)質(zhì)心，簇索引和誤差距離矩陣
'''
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m,2))) # 要為每個(gè)樣本建立一個(gè)簇索引和相對(duì)的誤差宰掉，所以需要m行的矩陣呵哨，m就是樣本數(shù)
centRoids = createCent(dataSet,k) # 生成隨機(jī)質(zhì)心
clusterChanged = True
while clusterChanged:
clusterChanged = False
for i in range(m): # 遍歷所有樣本
minDist = inf;minIndex = -1 # 初始化最小值
for j in range(k): # 遍歷所有質(zhì)心
disJI = disMens(centRoids[j,:],dataSet[i,:])
if disJI < minDist:
minDist = disJI;minIndex = j # 找出距離當(dāng)前樣本最近的那個(gè)質(zhì)心
if clusterAssment[i,0] != minIndex: # 更新當(dāng)前樣本點(diǎn)所屬于的質(zhì)心
clusterChanged = True # 如果當(dāng)前樣本點(diǎn)不屬于當(dāng)前與之距離最小的質(zhì)心，則說(shuō)明簇分配結(jié)果仍需要改變
clusterAssment[i,:] = minIndex,minDist**2
for cent in range(k):
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A == cent)[0]]
# nonzero 返回的是矩陣中所有非零元素的坐標(biāo)轨奄，坐標(biāo)的行數(shù)與列數(shù)個(gè)存在一個(gè)數(shù)組或矩陣當(dāng)中
# 矩陣支持檢查元素的操作孟害，所有可以寫成matrix == int這種形式，返回的一個(gè)布爾型矩陣挪拟，代表矩陣相應(yīng)位置有無(wú)此元素
# 這里指尋找當(dāng)前質(zhì)心下所聚類的樣本
centRoids[cent,:] = mean(ptsInClust,axis = 0) # 更新當(dāng)前的質(zhì)心為所有樣本的平均值挨务，axis = 0代表對(duì)列求平均值
return centRoids,clusterAssment
def binKMeans(dataSet, k, distMeas = getDistance):
'''
本函數(shù)用于二分k均值算法
:param dataSet: 數(shù)據(jù)集，要求有矩陣形式
:param k: 指定聚類個(gè)數(shù)
:param distMeas: 求解距離的方式
:return:質(zhì)心舞丛，簇索引和誤差距離矩陣
'''
m = shape(dataSet)[0]
clusterAssment = mat(zeros((m,2)))
centRoids0 = mean(dataSet,axis = 0).tolist()[0] # 初始化一個(gè)簇耘子，只有一個(gè)質(zhì)心，分量就是就是所有特征的均值
# 注意球切，tolist函數(shù)用于將矩陣轉(zhuǎn)化為一個(gè)列表谷誓，此列表為嵌套列表
centList = [centRoids0]
for j in range(m): # 遍歷所有樣本，計(jì)算所有樣本與當(dāng)前質(zhì)心的距離作為誤差
clusterAssment[j,1] = distMeas(mat(centRoids0),dataSet[j,:])**2
while (len(centList) < k): # 循環(huán)條件為當(dāng)前質(zhì)心數(shù)目還不夠指定數(shù)目
lowestSSE = inf #初始化距離差平方和為一個(gè)無(wú)限大的數(shù)
for i in range(len(centList)): # 遍歷所有質(zhì)心
ptsCurrCluster = dataSet[nonzero(clusterAssment[:,0].A == i)[0],:] # 搜索到當(dāng)前質(zhì)心所聚類的樣本
centroidsMat,splitClusterAss = kMeans(ptsCurrCluster,2,distMeas) # 將當(dāng)前分割成兩個(gè)簇
sseSplit = sum(splitClusterAss[:,1]) # 計(jì)算分裂簇后的SSE
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:,0].A != i)[0],1])
# 計(jì)算分裂之前的SSE
if (sseSplit + sseNotSplit) < lowestSSE: # 如果分裂之后的SSE小吨凑，則更新
bestCent2Split = i
bestNewCents = centroidsMat
bestClustAss = splitClusterAss.copy()
lowestSSE = sseSplit + sseNotSplit
#重新編制簇的編號(hào)捍歪，凡是分裂后編號(hào)為1的簇户辱，編號(hào)為質(zhì)心列表長(zhǎng)度，編號(hào)為0的簇糙臼，編號(hào)為最佳分裂質(zhì)心的編號(hào)庐镐，以此更新
bestClustAss[nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList)
bestClustAss[nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCent2Split
centList[bestCent2Split] = bestNewCents[0,:].tolist()[0] # 添加分裂的質(zhì)心到質(zhì)心列表中
centList.append(bestNewCents[1,:].tolist()[0])
clusterAssment[nonzero(clusterAssment[:,0].A == bestCent2Split)[0],:] = bestClustAss
return mat(centList),clusterAssment
dataSet = random.randint(10,high = 20,size = (30,3))
k = 3
centList,clusterAssment = binKMeans(dataSet, k, distMeas=getDistance)
四、密度DBscan聚類
和傳統(tǒng)的K-Means算法相比变逃，DBSCAN最大的不同就是不需要輸入類別數(shù)k必逆，當(dāng)然它最大的優(yōu)勢(shì)是可以發(fā)現(xiàn)任意形狀的聚類簇，而不是像K-Means揽乱，一般僅僅使用于凸的樣本集聚類名眉。同時(shí)它在聚類的同時(shí)還可以找出異常點(diǎn)，這點(diǎn)和BIRCH算法類似凰棉。
一般來(lái)說(shuō)损拢，如果數(shù)據(jù)集是稠密的，并且數(shù)據(jù)集不是凸的撒犀，那么用DBSCAN會(huì)比K-Means聚類效果好很多福压。
如果數(shù)據(jù)集不是稠密的，則不推薦用DBSCAN來(lái)聚類或舞。
1荆姆、密度DBscan聚類的邏輯
- a. 定義鄰域半徑e和樣本數(shù)量閾值Minpts（在領(lǐng)域半徑內(nèi)的最少點(diǎn)數(shù)量）；
- b. 找到滿足條件a的點(diǎn)集合嚷那，稱為核心對(duì)象x胞枕；
- c. 選取其中1個(gè)核心對(duì)象x：
- 查找其核心對(duì)象x領(lǐng)域半徑內(nèi)的點(diǎn)y
- 對(duì)每一個(gè)y，檢查其是否也是核心對(duì)象魏宽，如果yes，對(duì)新的核心對(duì)象查找其領(lǐng)域半徑內(nèi)的點(diǎn)z
- 循環(huán)1决乎、2队询，直到找到所有的核心對(duì)象及其領(lǐng)域半徑內(nèi)的點(diǎn)，所有找到的核心對(duì)象和點(diǎn)都標(biāo)注為同一類构诚。（類似于不斷發(fā)展下線）
- d. 在原始樣本集中去掉過(guò)程c的結(jié)果蚌斩，
- e. 對(duì)剩余的核心對(duì)象重復(fù)過(guò)程c
2、密度DBscan聚類的優(yōu)點(diǎn)：
1） 可以對(duì)任意形狀的稠密數(shù)據(jù)集進(jìn)行聚類范嘱，相對(duì)的送膳，K-Means之類的聚類算法一般只適用于凸數(shù)據(jù)集。
2） 可以在聚類的同時(shí)發(fā)現(xiàn)異常點(diǎn)丑蛤，對(duì)數(shù)據(jù)集中的異常點(diǎn)不敏感叠聋。
3） 聚類結(jié)果沒(méi)有偏倚，相對(duì)的受裹，K-Means之類的聚類算法初始值對(duì)聚類結(jié)果有很大影響碌补。
3虏束、密度DBscan聚類的缺點(diǎn)：
1）如果樣本集的密度不均勻、聚類間距差相差很大時(shí)厦章，聚類質(zhì)量較差镇匀，這時(shí)用DBSCAN聚類一般不適合。
2） 如果樣本集較大時(shí)袜啃，聚類收斂時(shí)間較長(zhǎng)汗侵，此時(shí)可以對(duì)搜索最近鄰時(shí)建立的KD樹或者球樹進(jìn)行規(guī)模限制來(lái)改進(jìn)。
3） 調(diào)參相對(duì)于傳統(tǒng)的K-Means之類的聚類算法稍復(fù)雜群发，主要需要對(duì)距離閾值?晰韵，鄰域樣本數(shù)閾值MinPts聯(lián)合調(diào)參，不同的參數(shù)組合對(duì)最后的聚類效果有較大影響也物。
python實(shí)現(xiàn)代碼如下：
import math
import numpy as np
import pylab as pl
#數(shù)據(jù)集：每三個(gè)是一組分別是西瓜的編號(hào)宫屠，密度，含糖量
data = """
1,0.697,0.46,2,0.774,0.376,3,0.634,0.264,4,0.608,0.318,5,0.556,0.215,
6,0.403,0.237,7,0.481,0.149,8,0.437,0.211,9,0.666,0.091,10,0.243,0.267,
11,0.245,0.057,12,0.343,0.099,13,0.639,0.161,14,0.657,0.198,15,0.36,0.37,
16,0.593,0.042,17,0.719,0.103,18,0.359,0.188,19,0.339,0.241,20,0.282,0.257,
21,0.748,0.232,22,0.714,0.346,23,0.483,0.312,24,0.478,0.437,25,0.525,0.369,
26,0.751,0.489,27,0.532,0.472,28,0.473,0.376,29,0.725,0.445,30,0.446,0.459"""
#數(shù)據(jù)處理 dataset是30個(gè)樣本（密度滑蚯，含糖量）的列表
a = data.split(',')
dataset = [(float(a[i]), float(a[i+1])) for i in range(1, len(a)-1, 3)]
#計(jì)算歐幾里得距離,a,b分別為兩個(gè)元組
def dist(a, b):
return math.sqrt(math.pow(a[0]-b[0], 2)+math.pow(a[1]-b[1], 2))
#算法模型
def DBSCAN(D, e, Minpts):
#初始化核心對(duì)象集合T,聚類個(gè)數(shù)k,聚類集合C, 未訪問(wèn)集合P,
T = set(); k = 0; C = []; P = set(D)
#遍歷樣本集浪蹂，尋找核心對(duì)象：
#核心對(duì)象：某點(diǎn)x，在x周圍e范圍內(nèi)有不少于Minpts個(gè)點(diǎn)告材，則x是核心對(duì)象
for d in D:
if len([ i for i in D if dist(d, i) <= e]) >= Minpts:
T.add(d)
#開始聚類
while len(T):
P_old = P
#隨機(jī)選擇1個(gè)核心對(duì)象賦給o
o = list(T)[np.random.randint(0, len(T))]
#在原數(shù)據(jù)集中刪除選中的核心對(duì)象o
P = P - set(o)
Q = []
Q.append(o)
while len(Q):
q = Q[0]
#在原數(shù)據(jù)集中收集核心對(duì)象周圍滿足e條件的點(diǎn)
Nq = [i for i in D if dist(q, i) <= e]
#如果滿足條件的點(diǎn)數(shù)量大于等于Minpts
if len(Nq) >= Minpts:
# S是P和Nq的交集
S = P & set(Nq)
# 把S添加到Q中坤次，目的是循環(huán)S中所有點(diǎn)，看其中是否也有核心對(duì)象
# 如果也有核心對(duì)象斥赋，則所有找到的核心對(duì)象及其周圍點(diǎn)都是一類的
Q += (list(S))
P = P - S
Q.remove(q)
k += 1
Ck = list(P_old - P)
T = T - set(Ck)
C.append(Ck)
return C
# 畫圖
def draw(C):
colValue = ['r', 'y', 'g', 'b', 'c', 'k', 'm']
for i in range(len(C)):
coo_X = [] #x坐標(biāo)列表
coo_Y = [] #y坐標(biāo)列表
for j in range(len(C[i])):
coo_X.append(C[i][j][0])
coo_Y.append(C[i][j][1])
pl.scatter(coo_X, coo_Y, marker='x', color=colValue[i%len(colValue)], label=i)
pl.legend(loc='upper right')
pl.show()
C = DBSCAN(dataset, 0.11, 5)
draw(C)
以上內(nèi)容參考缰猴、借鑒了以下資料:
1、簡(jiǎn)單聚類方法K-means方法的實(shí)現(xiàn)
2疤剑、《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》二分-kMeans算法（二分K均值聚類）
3滑绒、DBSCAN密度聚類算法
