kmeans演算法python
K-Means是常用的聚類演算法，與其他聚類演算法相比，其時間復雜度低，聚類的效果也還不錯，這里簡單介紹一下k-means演算法，下圖是一個手寫體數據集聚類的結果。
基本思想
k-means演算法需要事先指定簇的個數k，演算法開始隨機選擇k個記錄點作為中心點，然後遍歷整個數據集的各條記錄，將每條記錄歸到離它最近的中心點所在的簇中，之後以各個簇的記錄的均值中心點取代之前的中心點，然後不斷迭代，直到收斂，演算法描述如下：
上面說的收斂，可以看出兩方面，一是每條記錄所歸屬的簇不再變化，二是優化目標變化不大。演算法的時間復雜度是O(K*N*T)，k是中心點個數，N數據集的大小，T是迭代次數。
優化目標
k-means的損失函數是平方誤差：
RSSk=∑x∈ωk|x?u(ωk)|2
RSS=∑k=1KRSSk
其中$\omega _k$表示第k個簇，$u(\omega _k)$表示第k個簇的中心點，$RSS_k$是第k個簇的損失函數，$RSS$表示整體的損失函數。優化目標就是選擇恰當的記錄歸屬方案，使得整體的損失函數最小。
中心點的選擇
k-meams演算法的能夠保證收斂，但不能保證收斂於全局最優點，當初始中心點選取不好時，只能達到局部最優點，整個聚類的效果也會比較差。可以採用以下方法：k-means中心點
1、選擇彼此距離盡可能遠的那些點作為中心點；
2、先採用層次進行初步聚類輸出k個簇，以簇的中心點的作為k-means的中心點的輸入。
3、多次隨機選擇中心點訓練k-means，選擇效果最好的聚類結果
k值的選取
k-means的誤差函數有一個很大缺陷，就是隨著簇的個數增加，誤差函數趨近於0，最極端的情況是每個記錄各為一個單獨的簇，此時數據記錄的誤差為0，但是這樣聚類結果並不是我們想要的，可以引入結構風險對模型的復雜度進行懲罰：
K=mink[RSSmin(k)+λk]
$\lambda$是平衡訓練誤差與簇的個數的參數，但是現在的問題又變成了如何選取$\lambda$了，有研究[參考文獻1]指出，在數據集滿足高斯分布時，$\lambda=2m$，其中m是向量的維度。
另一種方法是按遞增的順序嘗試不同的k值，同時畫出其對應的誤差值，通過尋求拐點來找到一個較好的k值，詳情見下面的文本聚類的例子。
k-means文本聚類
我爬取了36KR的部分文章，共1456篇，分詞後使用sklearn進行k-means聚類。分詞後數據記錄如下：
使用TF-IDF進行特徵詞的選取，下圖是中心點的個數從3到80對應的誤差值的曲線：
從上圖中在k=10處出現一個較明顯的拐點，因此選擇k=10作為中心點的個數，下面是10個簇的數據集的個數。
{0: 152, 1: 239, 2: 142, 3: 61, 4: 119, 5: 44, 6: 71, 7: 394, 8: 141, 9: 93}
簇標簽生成
聚類完成後，我們需要一些標簽來描述簇，聚類完後，相當於每個類都用一個類標，這時候可以用TFIDF、互信息、卡方等方法來選取特徵詞作為標簽。關於卡方和互信息特徵提取可以看我之前的文章文本特徵選擇，下面是10個類的tfidf標簽結果。
Cluster 0: 商家 商品 物流 品牌 支付 導購 網站 購物 平台 訂單
Cluster 1: 投資 融資 美元 公司 資本 市場 獲得 國內 中國 去年
Cluster 2: 手機 智能 硬體 設備 電視 運動 數據 功能 健康 使用
Cluster 3: 數據 平台 市場 學生 app 移動 信息 公司 醫生 教育
Cluster 4: 企業 招聘 人才 平台 公司 it 移動 網站 安全 信息
Cluster 5: 社交 好友 交友 寵物 功能 活動 朋友 基於 分享 游戲
Cluster 6: 記賬 理財 貸款 銀行 金融 p2p 投資 互聯網 基金 公司
Cluster 7: 任務 協作 企業 銷售 溝通 工作 項目 管理 工具 成員
Cluster 8: 旅行 旅遊 酒店 預訂 信息 城市 投資 開放 app 需求
Cluster 9: 視頻 內容 游戲 音樂 圖片 照片 廣告 閱讀 分享 功能
實現代碼
#!--encoding=utf-8
from __future__ import print_function
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.feature_extraction.text import HashingVectorizer
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans, MiniBatchKMeans
def loadDataset():
'''導入文本數據集'''
f = open('36krout.txt','r')
dataset = []
lastPage = None
for line in f.readlines():
if '< title >' in line and '< / title >' in line:
if lastPage:
dataset.append(lastPage)
lastPage = line
else:
lastPage += line
if lastPage:
dataset.append(lastPage)
f.close()
return dataset
def transform(dataset,n_features=1000):
vectorizer = TfidfVectorizer(max_df=0.5, max_features=n_features, min_df=2,use_idf=True)
X = vectorizer.fit_transform(dataset)
return X,vectorizer
def train(X,vectorizer,true_k=10,minibatch = False,showLable = False):
#使用采樣數據還是原始數據訓練k-means，
if minibatch:
km = MiniBatchKMeans(n_clusters=true_k, init='k-means++', n_init=1,
init_size=1000, batch_size=1000, verbose=False)
else:
km = KMeans(n_clusters=true_k, init='k-means++', max_iter=300, n_init=1,
verbose=False)
km.fit(X)
if showLable:
print("Top terms per cluster:")
order_centroids = km.cluster_centers_.argsort()[:, ::-1]
terms = vectorizer.get_feature_names()
print (vectorizer.get_stop_words())
for i in range(true_k):
print("Cluster %d:" % i, end='')
for ind in order_centroids[i, :10]:
print(' %s' % terms[ind], end='')
print()
result = list(km.predict(X))
print ('Cluster distribution:')
print (dict([(i, result.count(i)) for i in result]))
return -km.score(X)
def test():
'''測試選擇最優參數'''
dataset = loadDataset()
print("%d documents" % len(dataset))
X,vectorizer = transform(dataset,n_features=500)
true_ks = []
scores = []
for i in xrange(3,80,1):
score = train(X,vectorizer,true_k=i)/len(dataset)
print (i,score)
true_ks.append(i)
scores.append(score)
plt.figure(figsize=(8,4))
plt.plot(true_ks,scores,label="error",color="red",linewidth=1)
plt.xlabel("n_features")
plt.ylabel("error")
plt.legend()
plt.show()
def out():
'''在最優參數下輸出聚類結果'''
dataset = loadDataset()
X,vectorizer = transform(dataset,n_features=500)
score = train(X,vectorizer,true_k=10,showLable=True)/len(dataset)
print (score)
#test()
out()
B. k-means聚類演算法python實現，導入的數據集有什麼要求
一，K-Means聚類演算法原理
k-means 演算法接受參數 k
；然後將事先輸入的n個數據對象劃分為
k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對
象」（引力中心）來進行計算的。
K-means演算法是最為經典的基於劃分的聚類方法，是十大經典數據挖掘演算法之一。K-means演算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。
C. python代碼如何應用系統聚類和K-means聚類法進行聚類分析 然後選擇變數，建立適當的模型
-Means聚類演算法
k-means演算法以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。
隨機選擇k個點作為初始的聚類中心。
對於剩下的點，根據其與聚類中心的距離，將其歸入最近的簇。
對每個簇，計算所有點的均值作為新的聚類中心。
重復2，3直到聚類中心不再發生改變
Figure 1
K-means的應用
數據介紹：
現有1999年全國31個省份城鎮居民家庭平均每人全年消費性支出的八大主要變數數據，這八大變數分別是：食品、衣著、家庭設備用品及服務、醫療保健、交通和通訊、娛樂教育文化服務、居住以及雜項商品和服務。利用已有數據，對31個省份進行聚類。
實驗目的：
通過聚類，了解1999年各個省份的消費水平在國內的情況。
技術路線：
sklearn.cluster.Kmeans
數據實例：
D. Python數據挖掘從哪些
一. 基於Python的數據挖掘 基本架構
1. matplotlib， 圖形化
2. pandas，數據挖掘的關鍵， 提供各種挖掘分析的演算法
3. numpy， 提供基本的統計
scipy， 提供各種數學公式
4. python common lib，python基本框架
二. 環境搭建
1. 安裝python
2. 安裝pip
pandas依賴的pip版本，最低是8.0.0。如果pip是8以下的版本，如7.2.1，需要升級pip.
命令是「python -m pip install -U pip」，這是windows版本。
Linux是」pip install -U pip「
通過命令「pip --version」， 可以查看pip版本號
3. 安裝pandas
命令「pip install pandas", 這是windows版本。
Linux平台可用
sudo apt-get install python-pandas
4. 安裝matplotlib
pip install matplotlib
三. 數據類型
pypython common type
string list tuple dict set
6鍾學列
list, tuple, string, unicode string, buffer object, xrange
pandas type
ndarray, series dateFrame
ndarray, 數組類型，新增原因：
list, tuple是基於指針+對象設計的。即list，tuple存儲的是void*指針，指針指向具體對象的數據。
因為是void*指針，所以二者可以存儲各種數據類型，即數據類型可以不統一。
雖然存儲豐富，但如果數據量過大時，即處理大數據時，有弊端。
1. 存儲空間大，浪費內存。因為存兩部分，指針+數據
2. 讀取慢，通過index，找到指針；基於指針，找到數據
所以在大數據處理時，新增ndarray，數字類型，類似C++ 數組。存儲相同，讀取、修改快捷。
別名：array, 有利於節省內存、提高CPU的計算時間，有豐富的處理函數
series，變長字典，
類似一維數組的對象；有數據和索引組成
新增原因：
dict是無序的，它的key和value存在映射關系。但key和value之間是不獨立的，存儲在一起。
如果需要對一項進行操作，會影響到另外一項。所以有了series， series的key和value是獨立的，獨立存儲。
series的key是定長有序的。通過series.key獲取整個索引， 通過series.values獲取所有values.
series的key,可以通過series.index.name，設置唯一的名稱。
series整體也可以設置唯一名稱，通過series.name
DataFrame:
1. 一個表格型的數據結構
2. 含有一組有序的列（類似於index)
3. 可以認為是，共享一個index的Series集合
data1={'name':['java', 'c', 'python'], 'year': [2,2,3]}
frame = pd.DataFrame(data1)
------------------------------------------------
四. 基本的數據分析流程：
1. 數據的獲取
2. 數據准備--規格化，建立各種索引index
3. 數據的顯示、描述，用於調試
如df.index, df.values， df.head(n), df.tail(n） df.describe
4. 數據的選擇
index獲取， 切片獲取, 行、列獲取， 矩形區域獲取
index獲取，df.row1 或者 df['row1']
行列，df.loc[行list, 列list], 如df.loc[0:1,['co1','col2'] ]
通過二位索引，取二維左上角，df.iloc[0,0],也可以列表 df.iloc[0:2,0:2]，取前2行。
5. 簡單的統計與處理
統計平均值、最大值等
6. Grouping 分組
df.groupby(df.row1)
7. Merge合並
append追加,
contact連接， 包含append功能，也可以兩個不同的二維數據結構合並
join連接， sql連接，基於相同欄位連接，如 sql的where, a.row1 = b.row1
------------------------------------------------
五. 高級的數據處理與可視化：
1. 聚類分析
聚類是數據挖掘描述性任務和預測性任務的一個重要組成部分，它以相似性為基礎，
把相似的對象通過靜態分類，分成不同的組別和子集。
在python中，有很多第三方庫提供了聚類演算法。
聚類演算法有很多， 其中K-均值演算法，因為其簡單、快捷的特點，被廣泛使用。
基本原理是，
1. 查找某數據集的中心，
2. 使用均方差，計算距離。使得每一個數據點都收斂在一個組內；各個組是完全隔離的
案例：
>>> from pylab import *
>>> from scipy.cluster.vq import *
>>>
>>> list1=[88,64,96,85]
>>> list2=[92,99,95,94]
>>> list3=[91,87,99,95]
>>> list4 = [78,99,97,81]
>>> list5=[88,78,98,84]
>>> list6=[100,95,100,92]
>>> tempdate = (list1, list2, list3, list4, list5, list6)
>>>
>>> tempdate
([88, 64, 96, 85], [92, 99, 95, 94], [91, 87, 99, 95], [78, 99, 97, 81], [88, 78
, 98, 84], [100, 95, 100, 92])
>>> date = vstack(tempdate)
>>>
>>> date
array([[ 88, 64, 96, 85],
[ 92, 99, 95, 94],
[ 91, 87, 99, 95],
[ 78, 99, 97, 81],
[ 88, 78, 98, 84],
[100, 95, 100, 92]])
>>> centroids,abc=kmeans(date,2) #查找聚類中心，第二個參數是設置分N類，如5類，則為5
>>> centroids # 基於每列查找的中心點，可能是平均值
array([[88, 71, 97, 84],
[90, 95, 97, 90]])
>>>
>>> result,cde=vq(date,centroids) #對數據集，基於聚類中心進行分類
>>> result
array([0, 1, 1, 1, 0, 1])
2. 繪圖基礎
python描繪庫，包含兩部分，
繪圖api, matplotlib提供各種描繪介面。
集成庫，pylab（包含numpy和matplotlib中的常用方法），描繪更快捷、方便。
import numpy as np
import matplotlib.pyplot as plt
t = np.arange(0,10)
plt.plot(t, t+2）
plt.plot(t,t, 'o', t,t+2, t,t**2, 'o') #（x,y)一組，默認是折線；『o'是散點，
plt.bar(t,t**2) # 柱狀圖
plt.show()
--------------------
import pylab as pl
t = np.arange(0,10)
plt.plot(t, t+2)
plt.show()
3. matplotlib圖像屬性控制
色彩、樣式
名稱： 圖、橫、縱軸,
plt.title('philip\'s python plot')
plt.xlabel('date')
plt.ylabel('value')
其他： pl.figure(figsize=(8,6),dpi=100)
pl.plot(x,y, color='red', linewidth=3, lable='line1')
pl.legend(loc='upper left')
子圖
pl.subplot(211) # 整體圖片，可以分為二維部分；
#第一個是圖的行，第二個是列；第三個是index, 從左上開始0遍歷 當前行，再下一行。
#如果是2位數，如11，需要『，』
axes(left, bottom, width, height) # 參數取值范圍是(0,1), left,是到左邊的距離，bottom是到下面的距離
4. pandas作圖
Series、DataFrame支持直接描繪，封裝了調用matplotlib的介面，如
series.close.plot()
df.close.plot() #具體參數類似matplotlib普通介面
屬性控制
類似matplotlib普通介面，修改各種圖片的類型，柱形圖、折線等
--------common-----------------
list, tuple, dict
--------numpy-----------------
ndarray, Series, DataFrame
E. kmeans演算法用Python怎麼實現
函數
loadDataSet(fileName)
從文件中讀取數據集
distEclud(vecA, vecB)
計算距離，這里用的是歐氏距離，當然其他合理的距離都是可以的
randCent(dataSet, k)
隨機生成初始的質心，這里是雖具選取數據范圍內的點
kMeans(dataSet, k, distMeas=distEclud, createCent=randCent)
kmeans演算法，輸入數據和k值。後面兩個事可選的距離計算方式和初始質心的選擇方式
show(dataSet, k, centroids, clusterAssment)
可視化結果
- 1 #coding=utf-8 2 from numpy import * 3 4 def loadDataSet(fileName): 5 dataMat = [] 6 fr = open(fileName) 7 for line in fr.readlines(): 8 curLine = line.strip().split(' ') 9 fltLine = map(float, curLine)10 dataMat.append(fltLine)11 return dataMat12 13 #計算兩個向量的距離，用的是歐幾里得距離14 def distEclud(vecA, vecB):15 return sqrt(sum(power(vecA - vecB, 2)))16 17 #隨機生成初始的質心（ng的課說的初始方式是隨機選K個點）
18 def randCent(dataSet, k):19 n = shape(dataSet)[1]20 centroids = mat(zeros((k,n)))21 for j in range(n):22 minJ = min(dataSet[:,j])23 rangeJ = float(max(array(dataSet)[:,j]) - minJ)24 centroids[:,j] = minJ + rangeJ * random.rand(k,1)25 return centroids26 27 def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):28 m = shape(dataSet)[0]29 clusterAssment = mat(zeros((m,2)))#create mat to assign data points
30 #to a centroid, also holds SE of each point31 centroids = createCent(dataSet, k)32 clusterChanged = True33 while clusterChanged:34 clusterChanged = False35 for i in range(m):#for each data point assign it to the closest centroid36 minDist = inf37 minIndex = -138 for j in range(k):39 distJI = distMeas(centroids[j,:],dataSet[i,:])40 if distJI < minDist:41 minDist = distJI; minIndex = j42 if clusterAssment[i,0] != minIndex:
43 clusterChanged = True44 clusterAssment[i,:] = minIndex,minDist**245 print centroids46 for cent in range(k):#recalculate centroids47 ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this cluster48 centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean
49 return centroids, clusterAssment50 51 def show(dataSet, k, centroids, clusterAssment):52 from matplotlib import pyplot as plt
53 numSamples, dim = dataSet.shape
54 mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
55 for i in xrange(numSamples):
56 markIndex = int(clusterAssment[i, 0])
57 plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])
58 mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
59 for i in range(k):
60 plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize = 12)
61 plt.show()62 63 def main():64 dataMat = mat(loadDataSet('testSet.txt'))65 myCentroids, clustAssing= kMeans(dataMat,4)66 print myCentroids67 show(dataMat, 4, myCentroids, clustAssing)
68 69 70 if __name__ == '__main__':71 main()
這里是聚類結果，還是很不錯的啦
F. 用python2.7做kmeans聚類演算法怎麼導入數據
指定文件名
問題描述：一堆二維數據，用kmeans演算法對其進行聚類，下面例子以分k=3為例。
原數據：
1.5,3.1
2.2,2.9
3,4
2,1
15,25
43,13
32,42
0,0
8,9
12,5
9,12
11,8
22,33
24,25
實現代碼：
[python] view plain
#coding:utf-8
from numpy import *
import string
import math
def loadDataSet(filename):
dataMat = []
fr = open(filename)
for line in fr.readlines():
element = line.strip('\n').split(',')
number = []
for i in range(len(element)):
number.append(string.atof(element[i]))
dataMat.append(number)
return dataMat
def distEclud(vecA, vecB):
count = len(vecA)
s = 0.0
for i in range(0, count):
s = s + power(vecA[i]-vecB[i], 2)
return sqrt(s)
def clusterOfElement(means, element):
min_dist = distEclud(means[0], element)
lable = 0
for index in range(1, len(means)):
dist = distEclud(means[index], element)
if(dist < min_dist):
min_dist = dist
lable = index
return lable
def getMean(cluster): #cluster=[[[1,2],[1,2],[1,2]....],[[2,1],[2,1],[2,1],[2,1]...]]
num = len(cluster) #1個簇的num，如上為3個
res = []
temp = 0
dim = len(cluster[0])
for i in range(0, dim):
for j in range(0, num):
temp = temp + cluster[j][i]
temp = temp / num
res.append(temp)
return res
def kMeans():
k = 3
data = loadDataSet('data.txt')
print "data is ", data
inite_mean = [[1.1, 1], [1, 1],[1,2]]
count = 0
while(count < 1000):
count = count + 1
clusters = []
means = []
for i in range(k):
clusters.append([])
means.append([])
for index in range(len(data)):
lable = clusterOfElement(inite_mean, data[index])
clusters[lable].append(data[index])
for cluster_index in range(k):
mea = getMean(clusters[cluster_index])
for mean_dim in range(len(mea)):
means[cluster_index].append(mea[mean_dim])
for mm in range(len(means)):
for mmm in range(len(means[mm])):
inite_mean[mm][mmm] = means[mm][mmm]
print "result cluster is ", clusters
print "result means is ", inite_mean
kMeans()