第一次迭代下,除了a4點(diǎn),其他點(diǎn)都?xì)w為一類c1:(a1 a2 a3 a5);c2:(a4) 聚類中心：c1:(2,2);c2(5,4)（聚類中心的計(jì)算方式是平均類中所有點(diǎn)）
創(chuàng)新互聯(lián)建站長(zhǎng)期為1000+客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為三臺(tái)企業(yè)提供專業(yè)的網(wǎng)站設(shè)計(jì)制作、網(wǎng)站設(shè)計(jì)，三臺(tái)網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。
第二次迭代下,c1(a1 a2 a5);c2(a3 a4) 聚類中心c1:(4/3,5/3);c2(9/2 7/2)
第三次迭代下,c1(a1 a2 a5);c2(a3 a4) 聚類中心c1:(4/3,5/3);c2(9/2 7/2)結(jié)果已經(jīng)穩(wěn)定跳出循環(huán)
大數(shù)據(jù)分析之聚類算法
1. 什么是聚類算法
所謂聚類，就是比如給定一些元素或者對(duì)象，分散存儲(chǔ)在數(shù)據(jù)庫(kù)中，然后根據(jù)我們感興趣的對(duì)象屬性，對(duì)其進(jìn)行聚集，同類的對(duì)象之間相似度高，不同類之間差異較大。最大特點(diǎn)就是事先不確定類別。
這其中最經(jīng)典的算法就是KMeans算法，這是最常用的聚類算法，主要思想是:在給定K值和K個(gè)初始類簇中心點(diǎn)的情況下，把每個(gè)點(diǎn)(亦即數(shù)據(jù)記錄)分到離其最近的類簇中心點(diǎn)所代表的類簇中，所有點(diǎn)分配完畢之后，根據(jù)一個(gè)類簇內(nèi)的所有點(diǎn)重新計(jì)算該類簇的中心點(diǎn)(取平均值)，然后再迭代的進(jìn)行分配點(diǎn)和更新類簇中心點(diǎn)的步驟，直至類簇中心點(diǎn)的變化很小，或者達(dá)到指定的迭代次數(shù)。
KMeans算法本身思想比較簡(jiǎn)單，但是合理的確定K值和K個(gè)初始類簇中心點(diǎn)對(duì)于聚類效果的好壞有很大的影響。
聚類算法實(shí)現(xiàn)
假設(shè)對(duì)象集合為D，準(zhǔn)備劃分為k個(gè)簇。
基本算法步驟如下：
1、從D中隨機(jī)取k個(gè)元素，作為k個(gè)簇的各自的中心。
2、分別計(jì)算剩下的元素到k個(gè)簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。
3、根據(jù)聚類結(jié)果，重新計(jì)算k個(gè)簇各自的中心，計(jì)算方法是取簇中所有元素各自維度的算術(shù)平均數(shù)。
4、將D中全部元素按照新的中心重新聚類。
5、重復(fù)第4步，直到聚類結(jié)果不再變化。
6、將結(jié)果輸出。
核心Java代碼如下：
/**
* 迭代計(jì)算每個(gè)點(diǎn)到各個(gè)中心點(diǎn)的距離，選擇最小距離將該點(diǎn)劃入到合適的分組聚類中，反復(fù)進(jìn)行，直到
* 分組不再變化或者各個(gè)中心點(diǎn)不再變化為止。
* @return
*/
public List[] comput() {
List[] results = new ArrayList[k];//為k個(gè)分組，分別定義一個(gè)聚簇集合，未來(lái)放入元素。
boolean centerchange = true;//該變量存儲(chǔ)中心點(diǎn)是否發(fā)生變化
while (centerchange) {
iterCount++;//存儲(chǔ)迭代次數(shù)
centerchange = false;
for (int i = 0; i k; i++) {
results[i] = new ArrayListT();
}
for (int i = 0; i players.size(); i++) {
T p = players.get(i);
double[] dists = new double[k];
for (int j = 0; j initPlayers.size(); j++) {
T initP = initPlayers.get(j);
/* 計(jì)算距離 這里采用的公式是兩個(gè)對(duì)象相關(guān)屬性的平方和，最后求開(kāi)方*/
double dist = distance(initP, p);
dists[j] = dist;
}
int dist_index = computOrder(dists);//計(jì)算該點(diǎn)到各個(gè)質(zhì)心的距離的最小值，獲得下標(biāo)
results[dist_index].add(p);//劃分到對(duì)應(yīng)的分組。
}
/*
* 將點(diǎn)聚類之后，重新尋找每個(gè)簇的新的中心點(diǎn)，根據(jù)每個(gè)點(diǎn)的關(guān)注屬性的平均值確立新的質(zhì)心。
*/
for (int i = 0; i k; i++) {
T player_new = findNewCenter(results[i]);
System.out.println("第"+iterCount+"次迭代，中心點(diǎn)是："+player_new.toString());
T player_old = initPlayers.get(i);
if (!IsPlayerEqual(player_new, player_old)) {
centerchange = true;
initPlayers.set(i, player_new);
}
}
}
return results;
}
上面代碼是其中核心代碼，我們根據(jù)對(duì)象集合List和提前設(shè)定的k個(gè)聚集,最終完成聚類。我們測(cè)試一下，假設(shè)要測(cè)試根據(jù)NBA球員的場(chǎng)均得分情況，進(jìn)行得分高中低的聚集，很簡(jiǎn)單，高得分在一組，中等一組，低得分一組。
我們定義一個(gè)Player類，里面有屬性goal，并錄入數(shù)據(jù)。并設(shè)定分組數(shù)目為k=3。
測(cè)試代碼如下:
List listPlayers = new ArrayList();
Player p1 = new Player();
p1.setName(“mrchi1”);
p1.setGoal(1);
p1.setAssists(8);
listPlayers.add(p1);
Player p2 = new Player();
p2.setName("mrchi2");
p2.setGoal(2);
listPlayers.add(p2);
Player p3 = new Player();
p3.setName("mrchi3");
p3.setGoal(3);
listPlayers.add(p3);
//其他對(duì)象定義此處略。制造幾個(gè)球員的對(duì)象即可。
KmeansPlayer kmeans = new KmeansPlayer(listPlayers, 3);
ListPlayer[] results = kmeans.comput();
for (int i = 0; i results.length; i++) {
System.out.println("類別" + (i + 1) + "聚集了以下球員：");
ListPlayer list = results[i];
for (Player p : list) {
System.out.println(p.getName() + "---" + p.getGoal()
}
}
算法運(yùn)行結(jié)果：
可以看出中心點(diǎn)經(jīng)歷了四次迭代變化，最終分類結(jié)果也確實(shí)是相近得分的分到了一組。當(dāng)然這種算法有缺點(diǎn)，首先就是初始的k個(gè)中心點(diǎn)的確定非常重要，結(jié)果也有差異。可以選擇彼此距離盡可能遠(yuǎn)的K個(gè)點(diǎn)，也可以先對(duì)數(shù)據(jù)用層次聚類算法進(jìn)行聚類，得到K個(gè)簇之后，從每個(gè)類簇中選擇一個(gè)點(diǎn)，該點(diǎn)可以是該類簇的中心點(diǎn)，或者是距離類簇中心點(diǎn)最近的那個(gè)點(diǎn)。
以前做項(xiàng)目時(shí)候?qū)懙拇a，數(shù)據(jù)是一維的，多維的也一樣，把距離計(jì)算的改一改就行int?term?=?Math.abs(dotlist.get(centerIndex[j]).x-?dotlist.get(i).x);
[java]?view?plaincopy
package?uestc.dmlab.call;??
import?java.io.BufferedReader;??
import?java.io.FileReader;??
import?java.security.KeyStore.Entry;??
import?java.util.HashMap;??
import?java.util.HashSet;??
import?java.util.Iterator;??
import?java.util.LinkedList;??
import?java.util.List;??
import?java.util.Map;??
import?java.util.Random;??
import?java.util.Set;??
public?class?Clustering?{??
/**?
*??
*?@param?fileName?
*????????????文件中每個(gè)字段對(duì)應(yīng)一個(gè)概率?
*?@param?k?
*????????????聚成k個(gè)類?
*?@param?minDistance?
*????????????聚類中心位移小于minDistance時(shí)停止迭代?
*?@return?
*/??
public?static?HashMapString,?Integer?cluster(String?fileName,?int?k,??
int?minDistance)?{??
try?{??
BufferedReader?br?=?new?BufferedReader(new?FileReader(fileName));??
ListDot?dotlist?=?new?LinkedListDot();??
String?line;??
int?count?=?0;//?行數(shù)??
while?((line?=?br.readLine())?!=?null)?{??
String?s[]?=?line.split(",");??
Dot?dot?=?new?Dot();??
dot.isCenter?=?false;??
dot.isVirtual?=?false;??
dot.name?=?s[0];??
//?if(s.length4){??
//?System.out.println(line);??
//?}??
dot.x?=?Integer.parseInt(s[3]);??
dotlist.add(dot);??
count++;??
}??
if?(count??k)?{??
k?=?count;??
}??
//?隨機(jī)初始化k個(gè)聚類中心??
int?centerIndex[]?=?new?int[k];?//?存儲(chǔ)k個(gè)中心點(diǎn)在dotlist中的索引??
int?centerNum?=?k;??
while?(centerNum??0)?{??
int?index?=?new?Random().nextInt(count);??
if?(!dotlist.get(index).isCenter)?{??
centerNum--;??
dotlist.get(index).isCenter?=?true;??
centerIndex[centerNum]?=?index;??
}??
}??
//?K個(gè)聚類??
Cluster[]?clusers?=?new?Cluster[k];??
boolean?flag?=?true;??
while?(flag)?{??
flag?=?false;??
clusers?=?new?Cluster[k];??
for?(int?i?=?0;?i??clusers.length;?i++)?{??
clusers[i]?=?new?Cluster();??
}??
//System.out.println(clusers.length);??
//?找到離第i個(gè)點(diǎn)最近的聚類中心??
for?(int?i?=?0;?i??dotlist.size();?i++)?{??
//?該點(diǎn)不是中心點(diǎn)也不是虛擬點(diǎn)就計(jì)算它與所有中心點(diǎn)的距離并取最小值??
//?if(!dotlist.get(i).isCenter!dotlist.get(i).isVirtual){??
if?(!dotlist.get(i).isVirtual)?{??
int?distance?=?Integer.MAX_VALUE;??
int?c?=?0;//?記錄離該節(jié)點(diǎn)最近的中心點(diǎn)的索引??
for?(int?j?=?0;?j??k;?j++)?{??
int?term?=?Math.abs(dotlist.get(centerIndex[j]).x??
-?dotlist.get(i).x);??
if?(distance??term)?{??
distance?=?term;??
c?=?j;??
}??
}??
clusers[c].dots.add(i);??
}??
}??
//?重新計(jì)算聚類中心??
for?(int?i?=?0;?i??k;?i++)?{??
Cluster?cluster?=?clusers[i];??
if?(cluster.dots.size()??0)?{?//若該類中有點(diǎn)??
int?sum?=?0;??
for?(int?j?=?0;?j??cluster.dots.size();?j++)?{??
sum?+=?dotlist.get(cluster.dots.get(j)).x;??
}??
Dot?dot?=?new?Dot();??
dot.x?=?sum?/?cluster.dots.size();??
dot.isCenter?=?true;??
dot.isVirtual?=?true;??
//?新舊聚類中心的距離??
int?term?=?Math.abs(dotlist.get(centerIndex[i]).x??
-?dot.x);??
if?(term??minDistance)??
flag?=?true;??
dotlist.add(dot);??
centerIndex[i]?=?dotlist.indexOf(dot);?//?第i個(gè)聚類的中心改變??
}??
}??
}??
//?生成分類映射??
HashMapString,?Integer?map?=?new?HashMapString,?Integer();??
for?(Dot?dot?:?dotlist)?{??
if?(dot.isVirtual?==?false)?{??
int?className?=?-1;??
for?(int?i?=?0;?i??k;?i++)?{??
if?(clusers[i].dots.contains(dotlist.indexOf(dot)))??
className?=?i;??
}??
map.put(dot.name,?className);??
}??
}??
return?map;??
}?catch?(Exception?e)?{??
e.printStackTrace();??
}??
return?new?HashMapString,?Integer();??
}??
public?static?void?main(String[]?args)?{??
MapString,?Integer?map?=?Clustering.cluster(??
"C:/Documents?and?Settings/Administrator/桌面/123.txt",?2,?0);??
IteratorMap.EntryString,?Integer?it?=?map.entrySet().iterator();??
while(it.hasNext()){??
Map.EntryString,?Integer?entry?=?it.next();??
System.out.println(entry.getKey()+","+entry.getValue());??
}??
}??
}??
class?Dot?{??
String?name;??
int?x;??
boolean?isCenter;??
boolean?isVirtual;??
}??
class?Cluster?{??
//?記錄了該類中點(diǎn)的索引值??
LinkedListInteger?dots?=?new?LinkedListInteger();
重慶分公司
重慶分公司
