kmeans演算法的缺點

㈠ 大數據十大經典演算法之k-means

大數據十大經典演算法之k-means
k均值演算法基本思想：
K均值演算法是基於質心的技術。它以K為輸入參數，把n個對象集合分為k個簇，使得簇內的相似度高，簇間的相似度低。
處理流程：
1、為每個聚類確定一個初始聚類中心，這樣就有k個初始聚類中心；
2、將樣本按照最小距離原則分配到最鄰近聚類
3、使用每個聚類中的樣本均值作為新的聚類中心
4、重復步驟2直到聚類中心不再變化
5、結束，得到K個聚類
劃分聚類方法對數據集進行聚類時的要點：
1、選定某種距離作為數據樣本間的相似性度量，通常選擇歐氏距離。
2、選擇平價聚類性能的准則函數
用誤差平方和准則函數來評價聚類性能。
3、相似度的計算分局一個簇中對象的平均值來進行
K均值演算法的優點：
如果變數很大，K均值比層次聚類的計算速度較快（如果K很小）；
與層次聚類相比，K均值可以得到更緊密的簇，尤其是對於球狀簇；
對於大數據集，是可伸縮和高效率的；
演算法嘗試找出使平方誤差函數值最小的k個劃分。當結果簇是密集的，而簇與簇之間區別明顯的時候，效果較好。
K均值演算法缺點：
最後結果受初始值的影響。解決辦法是多次嘗試取不同的初始值。
可能發生距離簇中心m最近的樣本集為空的情況，因此m得不到更新。這是一個必須處理的問題，但我們忽略該問題。
不適合發現非凸面形狀的簇，並對雜訊和離群點數據較敏感，因為少量的這類數據能夠對均值產生較大的影響。
K均值演算法的改進：
樣本預處理。計算樣本對象量量之間的距離，篩掉與其他所有樣本那的距離和最大的m個對象。
初始聚類中心的選擇。選用簇中位置最靠近中心的對象，這樣可以避免孤立點的影響。
K均值演算法的變種：
K眾數（k-modes）演算法，針對分類屬性的度量和更新質心的問題而改進。
EM（期望最大化）演算法
k-prototype演算法
這種演算法不適合處理離散型屬性，但是對於連續型具有較好的聚類效果。
k均值演算法用途：
圖像分割；
衡量足球隊的水平；
下面給出代碼：
#include <iostream>
#include <vector>
//auther archersc
//JLU
namespace CS_LIB
{
using namespace std;
class Kmean
{
public:
//輸入格式
//數據數量N 維度D
//以下N行，每行D個數據
istream& loadData(istream& in);
//輸出格式
//聚類的數量CN
//中心維度CD
//CN行，每行CD個數據
//數據數量DN
//數據維度DD
//以下DN組，每組的第一行兩個數值DB, DDis
//第二行DD個數值
//DB表示改數據屬於一類，DDis表示距離改類的中心的距離
ostream& saveData(ostream& out);
//設置中心的數量
void setCenterCount(const size_t count);
size_t getCenterCount() const;
//times最大迭代次數， maxE ,E(t)表示第t次迭代後的平方誤差和，當|E(t+1) - E(t)| < maxE時終止
void clustering(size_t times, double maxE);

private:
double calDistance(vector<double>& v1, vector<double>& v2);

private:
vector< vector<double> > m_Data;
vector< vector<double> > m_Center;
vector<double> m_Distance;
vector<size_t> m_DataBelong;
vector<size_t> m_DataBelongCount;
};
}
#include "kmean.h"

#include <ctime>
#include <cmath>
#include <cstdlib>
//auther archersc
//JLU

namespace CS_LIB
{
template<class T>
void swap(T& a, T& b)
{
T c = a;
a = b;
b = c;
}

istream& Kmean::loadData(istream& in)
{
if (!in){
cout << "input error" << endl;
return in;
}
size_t dCount, dDim;
in >> dCount >> dDim;
m_Data.resize(dCount);
m_DataBelong.resize(dCount);
m_Distance.resize(dCount);
for (size_t i = 0; i < dCount; ++i){
m_Data[i].resize(dDim);
for (size_t j = 0; j < dDim; ++j){
in >> m_Data[i][j];
}
}
return in;
}
ostream& Kmean::saveData(ostream& out)
{
if (!out){
cout << "output error" << endl;
return out;
}
out << m_Center.size();
if (m_Center.size() > 0)
out << << m_Center[0].size();
else
out << << 0;
out << endl << endl;
for (size_t i = 0; i < m_Center.size(); ++i){
for (size_t j = 0; j < m_Center[i].size(); ++j){
out << m_Center[i][j] << ;
}
out << endl;
}
out << endl;
out << m_Data.size();
if (m_Data.size() > 0)
out << << m_Data[0].size();
else
out << << 0;
out << endl << endl;
for (size_t i = 0; i < m_Data.size(); ++i){
out << m_DataBelong[i] << << m_Distance[i] << endl;
for (size_t j = 0; j < m_Data[i].size(); ++j){
out << m_Data[i][j] << ;
}
out << endl << endl;
}
return out;
}
void Kmean::setCenterCount(const size_t count)
{
m_Center.resize(count);
m_DataBelongCount.resize(count);
}
size_t Kmean::getCenterCount() const
{
return m_Center.size();
}
void Kmean::clustering(size_t times, double maxE)
{
srand((unsigned int)time(NULL));
//隨機從m_Data中選取m_Center.size()個不同的樣本點作為初始中心。
size_t *pos = new size_t[m_Data.size()];
size_t i, j, t;
for (i = 0; i < m_Data.size(); ++i){
pos[i] = i;
}
for (i = 0; i < (m_Data.size() << 1); ++i){
size_t s1 = rand() % m_Data.size();
size_t s2 = rand() % m_Data.size();
swap(pos[s1], pos[s2]);
}
for (i = 0; i < m_Center.size(); ++i){
m_Center[i].resize(m_Data[pos[i]].size());
for (j = 0; j < m_Data[pos[i]].size(); ++j){
m_Center[i][j] = m_Data[pos[i]][j];
}
}
delete []pos;
double currE, lastE;
for (t = 0; t < times; ++t){
for (i = 0; i < m_Distance.size(); ++i)
m_Distance[i] = LONG_MAX;
for (i = 0; i < m_DataBelongCount.size(); ++i)
m_DataBelongCount[i] = 0;
currE = 0.0;
for (i = 0; i < m_Data.size(); ++i){
for (j = 0; j < m_Center.size(); ++j){
double dis = calDistance(m_Data[i], m_Center[j]);
if (dis < m_Distance[i]){
m_Distance[i] = dis;
m_DataBelong[i] = j;
}
}
currE += m_Distance[i];
m_DataBelongCount[m_DataBelong[i]]++;
}
cout << currE << endl;
if (t == 0 || fabs(currE - lastE) > maxE)
lastE = currE;
else
break;
for (i = 0; i < m_Center.size(); ++i){
for (j = 0; j < m_Center[i].size(); ++j)
m_Center[i][j] = 0.0;

}
for (i = 0; i < m_DataBelong.size(); ++i){
for (j = 0; j < m_Data[i].size(); ++j){
m_Center[m_DataBelong[i]][j] += m_Data[i][j] / m_DataBelongCount[m_DataBelong[i]];
}
}
}
}
double Kmean::calDistance(vector<double>& v1, vector<double>& v2)
{
double result = 0.0;
for (size_t i = 0; i < v1.size(); ++i){
result += (v1[i] - v2[i]) * (v1[i] - v2[i]);
}
return pow(result, 1.0 / v1.size());
//return sqrt(result);
}
}
#include <iostream>
#include <fstream>
#include "kmean.h"
using namespace std;
using namespace CS_LIB;

int main()
{
ifstream in("in.txt");
ofstream out("out.txt");
Kmean kmean;
kmean.loadData(in);
kmean.setCenterCount(4);
kmean.clustering(1000, 0.000001);
kmean.saveData(out);

return 0;
}

㈡ k均值聚類演算法存在哪些困難和局限

1、初始化選取各簇中心時，是隨機的，影響聚類結果。canopy演算法可以改進這點。
2、聚類結果是圓形狀，對條狀和線狀支持不好
3、要事先指定K值

㈢ 對比傳統K-Means等聚類演算法，LDA主題模型在文本聚類上有何優缺點

K-MEANS演算法:k-means演算法接受輸入量k；然後將n個數據對象劃分為k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。k-means演算法的工作過程說明如下：首先從n個數據對象任意選擇k個對象作為初始聚類中心；而對於所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然後再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數.k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。具體如下：輸入：k,data[n];（1）選擇k個初始中心點，例如c[0]=data[0],…c[k-1]=data[k-1];（2）對於data[0]….data[n],分別與c[0]…c[n-1]比較，假定與c[i]差值最少，就標記為i;（3）對於所有標記為i點，重新計算c[i]=/標記為i的個數；（4）重復(2)(3),直到所有c[i]值的變化小於給定閾值。演算法實現起來應該很容易，就不幫你編寫代碼了。

㈣ K-means的存在問題

存在的問題
K-means 演算法的特點——採用兩階段反復循環過程演算法，結束的條件是不再有數據元素被重新分配： 優點：本演算法確定的K 個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區別明顯時，效果較好。對於處理大數據集，這個演算法是相對可伸縮和高效的，計算的復雜度為O(NKt)，其中N是數據對象的數目，t是迭代的次數。一般來說，K<<N，t<<N 。

㈤ k-means演算法怎麼為對稱矩陣進行聚類

幾種典型的聚類融合演算法：
1.基於超圖劃分的聚類融合演算法
(1)Cluster-based Similarity Partitioning Algorithm(GSPA)
(2)Hyper Graph-Partitioning Algorithm(HGPA)
(3)Meta-Clustering Algorithm(MCLA)
2.基於關聯矩陣的聚類融合演算法
Voting-K-Means演算法。
3.基於投票策略的聚類融合演算法
w-vote是一種典型的基於加權投票的聚類融合演算法。
同時還有基於互信息的聚類融合演算法和基於有限混合模型的聚類融合演算法。
二、基於關聯矩陣的聚類融合演算法——Voting-K-Means演算法
Voting-K-Means演算法是一種基於關聯矩陣的聚類融合演算法，關聯矩陣的每一行和每一列代表一個數據點，關聯矩陣的元素表示數據集中數據點對共同出現在同一個簇中的概率。
演算法過程：
1.在一個數據集上得到若干個聚類成員；
2.依次掃描這些聚類成員，如果數據點i和j在某個聚類成員中被劃分到同一個簇中，那麼就在關聯矩陣對應的位置計數加1；關聯矩陣中的元素值越大，說明該元素對應的兩個數據點被劃分到同一個簇中的概率越大；
3.得到關聯矩陣之後，Voting-K-Means演算法依次檢查關聯矩陣中的每個元素，如果它的值大於演算法預先設定的閥值，就把這個元素對應的兩個數據點劃分到同一個簇中。

Voting-K-Means演算法的優缺點：
Voting-K-Means演算法不需要設置任何參數，在聚類融合的過程中可以自動地的選擇簇的個數 並且可以處理任意形狀的簇。因為Voting-K-Means演算法在聚類融合過程中是根據兩個數據點共同出現在同一個簇中的可能性大小對它們進行劃分的，所以只要兩個數據點距離足夠近，它們就會被劃分到一個簇中。
Voting-K-Means演算法的缺點是時間復雜度較高，它的時間復雜度是O(n^2);需要較多的聚類成員，如果聚類成員達不到一定規模，那麼關聯矩陣就不能准確反映出兩個數據點出現在同一個簇的概率。

package clustering;import java.io.FileWriter;import weka.clusterers.ClusterEvaluation;import weka.clusterers.SimpleKMeans;import weka.core.DistanceFunction;import weka.core.EuclideanDistance;import weka.core.Instances;import weka.core.converters.ConverterUtils.DataSource;import weka.filters.unsupervised.attribute.Remove;public class Votingkmeans2 extends SimpleKMeans { /** 生成的序列號 */ private static final long serialVersionUID = 1557181390469997876L; /** 劃分的簇數 */ private int m_NumClusters; /** 每個劃分的簇中的實例的數量 */ public int[] m_ClusterSizes; /** 使用的距離函數，這里是歐幾里德距離 */ protected DistanceFunction m_DistanceFunction = new EuclideanDistance(); /** 實例的簇號賦值 */ protected int[] m_Assignments; /** 設定聚類成員融合閥值 */ private final static double THREASOD = 0.5; /** 生成一個聚類器 */ public void buildClusterer(Instances data) throws Exception{ final int numinst = data.numInstances(); // 數據集的大小 double [][]association = new double[numinst][numinst]; // 定義並初始化一個關聯矩陣 int numIteration = 40; // 設置生成的聚類成員數 final int k = (int)Math.sqrt(numinst); // 設置K-Means聚類演算法參數——簇數 for(int i = 0; i < numIteration; i++) { if(data.classIndex() == -1) data.setClassIndex(data.numAttributes() - 1); // 索引是從0開始 String[] filteroption = new String[2]; filteroption[0] = "-R"; filteroption[1] = String.valueOf(data.classIndex() + 1);// 索引是從1開始 Remove remove = new Remove(); remove.setOptions(filteroption); remove.setInputFormat(data); /* 使用過濾器模式生成新的數據集；新數據集是去掉類標簽之後的數據集 */ Instances newdata = weka.filters.Filter.useFilter(data, remove); /* 生成一個K-Means聚類器 */ SimpleKMeans sm = new SimpleKMeans(); sm.setNumClusters(k); sm.setPreserveInstancesOrder(true); // 保持數據集實例的原始順序 sm.setSeed(i); // 通過設置不同的種子，設置不同的簇初始中心點，從而得到不同的聚類結果 sm.buildClusterer(newdata); int[] assigm = sm.getAssignments(); // 得到數據集各個實例的賦值 /* 建立關聯矩陣 */ for(int j = 0; j < numinst; j++) { for(int m = j; m < numinst; m++) { if(assigm[j] == assigm[m]) { association[j][m] = association[j][m] + 1.0 / numIteration ; } } } } System.out.println(); /* 將生成的關聯矩陣寫入.txt文件（註：生成的txt文本文件在e:/result.txt中） */ FileWriter fw = new FileWriter("e://result.txt"); for(int j = 0; j < numinst; j++) { for(int m = j; m < numinst; m++) { //由於關聯矩陣是對稱的，為了改進演算法的效率，只計算矩陣的上三角 String number = String.format("%8.2f", association[j][m]); fw.write(number); } fw.write("\n"); } /* 處理關聯矩陣，分別考慮了兩種情況 ：1.關聯矩陣中某個元素對應的兩個數據點已經被劃分到了不同的簇中 * 2.兩個數據點中有一個或者兩個都沒有被劃分到某個簇中。 */ int[] flag = new int[numinst]; int[] flagk = new int[k]; int[] finallabel = new int[numinst]; for(int m = 0; m < numinst; m++) { for(int n = m; n < numinst; n++) { if(association[m][n] > THREASOD) { if(flag[m] == 0 && flag[n] == 0) { // 兩個數據點都沒有被劃分到某個簇中， int i = 0; // 將他們劃分到同一個簇中即可 while (i < k && flagk[i] == 1) i = i + 1; finallabel[m] = i; finallabel[n] = i; flag[m] = 1; flag[n] = 1; flagk[i] = 1; } else if (flag[m] == 0 && flag[n] == 1) { // 兩個數據點中有一個沒有被劃分到某個簇中， finallabel[m] = finallabel[n]; // 將他們劃分到同一個簇中即可 flag[m] = 1; } else if (flag[m] == 1 && flag[n] == 0) { finallabel[n] = finallabel[m]; flag[n] = 1; } else if (flag[m] == 1 && flag[n] == 1 && finallabel[m] != finallabel[n]) { // 兩個數據點已被劃分到了不同的簇中， flagk[finallabel[n]] = 0; // 將它們所在的簇合並 int temp = finallabel[n]; for(int i = 0; i < numinst; i++) { if(finallabel[i] == temp) finallabel[i] = finallabel[m]; } } } } } m_Assignments = new int[numinst]; System.out.println("基於關聯矩陣的聚類融合演算法——Voting-K-Means演算法的最終聚類結果"); for(int i = 0; i < numinst; i++) { m_Assignments[i] = finallabel[i]; System.out.print(finallabel[i] + " "); if((i+1) % 50 == 0) System.out.println(); } for(int i = 0; i < k; i++) { if(flagk[i] == 1) m_NumClusters++; } } /** * return a string describing this clusterer * * @return a description of the clusterer as a string */ public String toString() { return "Voting-KMeans\n"; } public static void main(String []args) { try {String filename="e://weka-data//iris.arff"; Instances data = DataSource.read(filename); Votingkmeans2 vk = new Votingkmeans2(); vk.buildClusterer(data); /* 要生成Voting-K-Means的聚類評估結果包括准確率等需要覆蓋重寫toString()方法； * 因為沒有覆蓋重寫，所以這里生產的評估結果沒有具體內容。 */ ClusterEvaluation eval = new ClusterEvaluation(); eval.setClusterer(vk); eval.evaluateClusterer(new Instances(data)); System.out.println(eval.clusterResultsToString()); } catch (Exception e) { e.printStackTrace(); }}}

分析代碼時注意：得到的類成員變數m_Assignments就是最終Voting-K-Means聚類結果；由於是採用了開源機器學習軟體Weka中實現的SimpleKMeans聚類演算法，初始時要指定簇的個數，這里是數據集大小開根號向下取整；指定的閥值為0.5，即當關聯矩陣元素的值大於閥值時，才對該元素對應的兩個數據點進行融合，劃分到一個簇中，考慮兩種情況，代碼注釋已有，這里不再詳述。但聚類融合的實驗結果並不理想，鶯尾花數據集irsi.arff是數據挖掘實驗中最常用的數據集，原數據集共有三個類；但本實驗進行四十個聚類成員的融合，其最終聚類結果劃分成兩個簇；其原因可能有兩個：一是演算法本身的問題，需要使用其他更加優化的聚類融合演算法；二是實現上的問題，主要就在聚類結果的融合上，需要進行一步對照關聯矩陣進行邏輯上的分析，找出代碼中的問題。關聯矩陣文本文件http://download.csdn.net/detail/lhkaikai/7294323

---------------------

本文來自 Turingkk 的CSDN 博客 ，全文地址請點擊：https://blog.csdn.net/lhkaikai/article/details/25004823?utm_source=

㈥ 簡述K-means演算法的基本過程及其不足。《數據挖掘》作業題追分100

過程：
1、 從 n個數據對象任意選擇 k 個對象作為初始聚類中心；
2、 根據每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；並根據最小距離重新對相應對象進行劃分；
3、 重新計算每個（有變化）聚類的均值（中心對象）
4、循環步驟2和3，直到每個聚類不再發生變化為止

缺點：
1、聚類個數K需要自己決定，因此在不知道具體有多少類時需要從2開始多次嘗試，選擇最好的
2、當k確定時，聚類效果和初始中心選擇有關，所以演算法很不穩定
3、演算法在維數較多時，由於需要多次迭代，花費時間較長

㈦ 關於K-Means聚類演算法的,論文里都說：K-Means演算法對數據輸入順序敏感....

當然是敏感的,跟程序中如何處理數據有很大的關系.比如兩個中心點（-1,0）（1,0）,這時讀入數據（0,0）,那麼程序計算與所有中心點的距離,因為距離相同,程序會給其中一個,至於給哪個,都是由程序決定,一般按數據存儲的先後順序來給.而且結果不同不能代表聚類結果差,而是說明結果的多樣化,本身K的選取就是沒有一個約定的方法,所以結果有差別也是理所當然的.關鍵是你要如何體現你的演算法的優越性.就是要跟別的演算法作比較,比如從演算法的空間、時間復雜度,演算法的運行處理速度等等因素來做比較.

㈧ kmean演算法是干什麼的

聚類分析是一種靜態數據分析方法，常被用於機器學習，模式識別，數據挖掘等領域。通常認為，聚類是一種無監督式的機器學習方法，它的過程是這樣的：在未知樣本類別的情況下，通過計算樣本彼此間的距離（歐式距離,馬式距離，漢明距離，餘弦距離等）來估計樣本所屬類別。從結構性來劃分，聚類方法分為自上而下和自下而上兩種方法，前者的演算法是先把所有樣本視為一類，然後不斷從這個大類中分離出小類，直到不能再分為止；後者則相反，首先所有樣本自成一類，然後不斷兩兩合並，直到最終形成幾個大類。
常用的聚類方法主要有以下四種： //照搬的wiki，比較懶...
Connectivity based clustering（如hierarchical clustering 層次聚類法)
Centroid-based clustering(如kmeans)
Distribution-based clustering
Density-based clustering
Kmeans聚類是一種自下而上的聚類方法，它的優點是簡單、速度快；缺點是聚類結果與初始中心的選擇有關系，且必須提供聚類的數目。Kmeans的第二個缺點是致命的，因為在有些時候，我們不知道樣本集將要聚成多少個類別，這種時候kmeans是不適合的，推薦使用hierarchical 或meanshift來聚類。第一個缺點可以通過多次聚類取最佳結果來解決。
Kmeans的計算過程大概表示如下
隨機選擇k個聚類中心. 最終的類別個數<= k
計算每個樣本到各個中心的距離
每個樣本聚類到離它最近的中心
重新計算每個新類的中心
重復以上步驟直到滿足收斂要求。(通常就是中心點不再改變或滿足一定迭代次數).

㈨ K-means的演算法缺點

① 在 K-means 演算法中 K 是事先給定的，這個 K 值的選定是非常難以估計的。很多時候，事先並不知道給定的數據集應該分成多少個類別才最合適。這也是 K-means 演算法的一個不足。有的演算法是通過類的自動合並和分裂，得到較為合理的類型數目 K，例如 ISODATA 演算法。關於 K-means 演算法中聚類數目K 值的確定在文獻中，是根據方差分析理論，應用混合 F統計量來確定最佳分類數，並應用了模糊劃分熵來驗證最佳分類數的正確性。在文獻中，使用了一種結合全協方差矩陣的 RPCL 演算法，並逐步刪除那些只包含少量訓練數據的類。而文獻中使用的是一種稱為次勝者受罰的競爭學習規則，來自動決定類的適當數目。它的思想是：對每個輸入而言，不僅競爭獲勝單元的權值被修正以適應輸入值，而且對次勝單元採用懲罰的方法使之遠離輸入值。
② 在 K-means 演算法中，首先需要根據初始聚類中心來確定一個初始劃分，然後對初始劃分進行優化。這個初始聚類中心的選擇對聚類結果有較大的影響，一旦初始值選擇的不好，可能無法得到有效的聚類結果，這也成為 K-means演算法的一個主要問題。對於該問題的解決，許多演算法採用遺傳演算法（GA），例如文獻 中採用遺傳演算法（GA）進行初始化，以內部聚類准則作為評價指標。
③ 從 K-means 演算法框架可以看出，該演算法需要不斷地進行樣本分類調整，不斷地計算調整後的新的聚類中心，因此當數據量非常大時，演算法的時間開銷是非常大的。所以需要對演算法的時間復雜度進行分析、改進，提高演算法應用范圍。在文獻中從該演算法的時間復雜度進行分析考慮，通過一定的相似性准則來去掉聚類中心的侯選集。而在文獻中，使用的 K-means 演算法是對樣本數據進行聚類，無論是初始點的選擇還是一次迭代完成時對數據的調整，都是建立在隨機選取的樣本數據的基礎之上，這樣可以提高演算法的收斂速度。