IS為砥孟干虎

HenanUniversityofUrbanConstruction

《數據挖掘與數據倉庫》課程

實驗指導書

2020年

計算機與數據科學學院

實驗1Apriori算法實現

一'實驗目的

1、掌握Apriori算法對于關聯規則挖掘中頻繁集的產生以及關聯規則集合的產生過程；

2、根據算法描述編程實現算法，調試運行。并結合相關實驗數據進行應用，得到分析結果。

數據和刪除數據的操作。

實驗類型：綜合

計劃課間：3學時

二'實驗內容

1、頻繁項集的生成與Apriori算法實現；

2、關聯規則的生成過程與規則算法實現；

3、結合樣例對算法進行分析；

三'實驗步驟

編寫程序完成下列算法：

1、Apriori算法

輸入：數據集D；最小支持數minsupcount；

輸出：頻繁項目集L

Ll={large1-itemsets)

For(k=2;LkT#①；k++)

Ck=apriori-gen(Lk-1);//Ck是k個元素的候選集

Foralltransactionst^Ddo

beginCt二subset(Ck,t);〃Ct是所有t包含的候選集元素

forallcandidatescwCtdoc.count++;

end

Lk={cGCk|c.count工minsupcount}

End

L=ULk;

2、apriori-gen(Lk-1)候選集產生算法

輸入：（kT）-頻繁項目集LkT

輸出：k-頻繁項目集Ck

Forallitemsetp￡LkTdo

ForallitemsetqGLk-1do

Ifp.iteml=q.iteml,p.item2=q.item2,p.itemk-2=q.itemk-2,

p.itemk-Kq.itemk-1

then

beginc=p0°q

ifhasinfrequentsubset(c,Lk-l)

thendeletec

elseaddctoCk

End

ReturnCk

3、has_infrequent_subset(c,Lk-l)

功能：判斷候選集的元素

輸入：一個k-頻繁項目集LkT,8-1)-頻繁項目集1^-1

輸出：c是否從候選集中刪除的布爾判斷

Forall(k-l)-subsetsofcdo

IfNot(SeLk-l)THENreturnTRUE;

ReturnFALSE;

4、Rule-generate(L,minconf)

輸入：頻繁項目集；最小信任度

輸出：強關聯規則

算法：

FOReachfrequentitemsetIkinL

generules(Ik,Ik);

5、Genrules遞歸算法：

Genrules(Ik:frequentk-itemset,xm:frequentm-itemset)

X={(m-1)-itemsetsxm-1xm-linxm);

Foreachxm-1inX

BEGINconf=support(Ik)/support(xm-1);

IF(conf=minconf)THEN

BEGIN

輸出規則：xmT->(lk-xmT),support,confidence;

IF(m-l)>1)THENgenrules(Ik,xm-1);

END;

END;

結合相關樣例數據對算法進行調試，并根據相關實驗結果對數據進行分析，

四、實驗報告要求

1、用java語言實現上述相關算法。

2、改造參考代碼，添加最小置信度約束條件，并實現算法

3、在報告中詳細寫出實驗操作步驟和實驗結果，實驗中出現的問題和解決方法。

五、注意事項

1、集合的表示及相關操作的實現；

2、項目集的數據結構描述；

參考核心代碼如下：(相關的測試main函數可以自己書寫。根據頻繁k項集生成關聯規則相

對簡單，只通過最小支持度從頻繁K項集中找到所有的滿足條件的關聯規則。)

publicclassApriori

(

privatestaticfinaldoubleMIN_SUPPROT=0.2;〃最小支持度

privatestaticbooleanendTag=false;〃循環狀態

staticList<List<String>>record=newArrayList<List〈String>>();〃數據集

/**

*讀取txt數據

*/

publicstaticList<List<String>>getRecordO

(

List<List<String?record=newArrayList<List<String?();

try

Stringencoding二〃GBK〃；//字符編碼(可解決中文亂碼問題)

=newFile(z，E:\\eclipse-workspace\\Apriori\\simple.txt，z);

if(0&&0)

(

InputStreamReaderread=newInputStreamReader(

new(file),encoding);

BufferedReaderbufferedReader=newBufferedReader(read);

StringlineTXT=null;

while((lineTXT=bufferedReader.readLineO)!=null)

{〃讀一行文件

String[]lineString=lineTXT.split(z，〃)；

List<String>lineList=newArrayList<String>();

for(inti=0;i<lineString.length;i++)

{〃處理矩陣中的T、F、YES、NO

if(lineString[i].endsWith(〃T〃)||

lineString[i].endsWith("YES"))

lineList.add(record,get(0).get(i));

elseif(lineString[iJ.endsWith(，，F，z)||

lineString[i].endsWith("NO"))

;//F,NO記錄不保存

else

lineList.add(lineString[i]);

)

record.add(lineList);

}

read,close();

}else{

System.out.printin(〃找不到指定的文件！”);

)

)

catch(Exceptione)

(

System.out.printin(〃讀取文件內容操作出錯”)；

e.printStackTrace();

)

returnrecord;

)

/**

*有當前頻繁項集自連接求下一次候選集

*?paramFrequentltemset

*/

privatestaticList<List<String>>getNextCandidate(List<List<String?

Frequentltemset)

List<List<String>>nextCandidateltemset=newArrayList<List<String>>();

for(inti=0;i<FrequentItemset.size();i++)

HashSet<String>hsSet=newHashSet<String>();

HashSet<String>hsSettemp=newHashSet<String>();

for(intk=0;k<Frequentltemset.get(i).size();k++)〃獲得頻繁集第i

行

hsSet.add(Frequentltemset.get(i).get(k));

inthsLengthbefore=hsSet.size。；〃添加前長度

hsSettemp=(HashSet<String>)hsSet.clone();

for(inth=i+l;h<FrequentItemset.size();h++)

{〃頻繁集第i行與第j行(j>i)連接每次添加且添加一個元素組成新的

頻繁項集的某一行，

hsSet=(HashSet<String>)hsSettemp.clone();//!!!做連接的hasSet

保持不變

for(intj=0;j<Frequentltemset.get(h).size();j++)

hsSet.add(Frequentltemset.get(h).get(j));

inthsLength_after=hsSet.size();

if(hsLength_before+l==hsLength_after&&

isSubsetOf(hsSet,record)==1&&isnotHave(hsSet,nextCandidateltemset))

{〃如果不相等，表示添加了1個新的元素，再判斷其是否為「“ord某一行

的子集，若是則其為候選集中的一項

Iterator<String>itr=hsSet.iterator();

List<String>tempList=newArrayList<String>();

while(itr.hasNext())

(

StringItem=(String)itr.next();

tempList.add(Item);

)

nextCandidateltemset.add(tempList);

)

)

returnnextCandidateltemset;

)

/**

*判斷新添加元素形成的候選集是否在新的候選集中

*?paramhsSet

*@paramnextCandidateltemset

*/

privatestaticbooleanisnotHave(HashSet<String>hsSet,

List<List<String>>nextCandidateitemset)

(

//TODOAuto-generatedmethodstub

List<String>tempList=newArrayList<String>();

Iterator<String>itr=hsSet.iterator0;

while(itr.hasNext())

(

StringItem=(String)itr.next();

tempList.add(Item);

)

for(inti=0;i<nextCandidateItemset.size();i++)

if(tempList.equals(nextCandidateltemset.get(i)))

returnfalse;

returntrue;

)

/**

*判斷hsSet是不是record2中的某一記錄子集

*?paramhsSet

*?paramrecord2

*/

privatestaticintisSubsetOf(HashSet<String>hsSet,

List<List<String>>record2)

(

〃115521轉換成員51

List<String>tempList=newArrayList<String>();

Iterator<String>itr=hsSet.iterator();

while(itr.hasNext())

(

StringItem=(String)itr.next();

tempList.add(Item);

)

for(inti=l;i<record.size();i++)

(

List<String>tempListRecord=newArrayList<String>();

for(intj=l;j<record.get(i).size();j++)

tempListRecord.add(record,get(i).get(j));

if(tempListRecord.containsAll(tempList))

return1;

return0;

/**

*由k項候選集剪枝得到k項頻繁集

*?paramCandidateitemset

*/

privatestaticList<List<String>>getSupprotedltemset(List<List<String?

Candidateitemset)

(

//TODOAuto-generatedmethodstub

booleanend=true;

List<List<String?supportedltemset=newArrayList<List<String?();

intk=0;

for(inti=0;i<Candidateltemset.size();i++)

(

intcount=countFrequent(Candidateitemset.get⑴)；〃統計記錄數

if(count>=MINSUPPROT*(record.size()-l))

(

supportedltemset.add(Candidateitemset.get(i));

end=false;

)

}

endTag二end;〃存在頻繁項集則不會結束

if(endTag==true)

System.out.printin(〃無滿足支持度項集,結束連接〃)；

returnsupportedltemset;

)

/**

*統計record中出現list集合的個數

*?paramlist

*/

privatestaticintcountFrequent(List<String>list)

(

//TODOAuto-generatedmethodstub

intcount=0;

for(inti=1;i<record.size();i++)

(

booleannotllaveThisList=false;

for(intk=0;k<list.size();k++)

{〃判斷record,get(i)是否包含list

booleanthisRecordHave=false;

for(intj=1;j<record.get(i).size();j++)

if(list,get(k).equals(record,get(i).get(j)))//listoget(k)

在record。get(i)中能找到

thisRecordHave=true;

}

if(!thisRecordHave){〃只要有一個list元素找不到，則退出其余元素比

較，進行下一個record。get(i)比較

notHaveThisList=true;

break;

)

)

if(notHaveThisList==false)

count++;

)

returncount;

)

/**

*獲得一項候選集

*/

privatestaticList<List<String>>findFirstCandidate()

(

//TODOAuto-generatedmethodstub

List<List<String?tableList=newArrayList<List<String?();

HashSet<String>hs=newHashSet<String>();

for(inti=1;i<record.size();i++)

(〃第一行為商品信息

for(intj=l;j<record.get(i).size();j++){

hs.add(record,get(i).get(j));

)

)

Iterator<String>itr=hs.iterator();

while(itr.hasNext())

(

List<String>tempList=newArrayList<String>();

StringItem=(String)itr.next();

tempList.add(Item);

tableList.add(tempList);

}

returntableList;

實驗2貝葉斯算法實現

一、實驗目的

通過對貝葉斯算法的編程實現，加深對貝葉斯算法的理解，同時利用貝葉斯算法對簡單

應用實現預測分類

二'實驗內容

1、分析貝葉斯算法；

2、計算條件概率；

3、預測精度的計算與評估；

4、編程實現貝葉斯分類算法，并對簡單應用樣本數據實現預測分類

5.參考實驗數據

三'實驗方法

1、實現貝葉斯算法

2、利用實驗數據對貝葉斯算法進行檢測

3、求解精確度計算

4、調試程序

四'實驗步驟

4.1算法過程描述：

1）輸入訓練數據，將數據保存在DataBase二維數組中（數組的最后一個屬性對應類別

標號）

2）設定訓練數據集與測試數據集大小（指定從數組下標0開始到TrainSetSizeT所對應

的數據為訓練數據，其余為測試數據）；

3）計算訓練數據集數據中各屬性在各類中的概率分布情況；

4）利用測試數據計算貝葉斯算法的分類精度；

5）輸出分類結果；

4.2數據處理

A、實驗數據

RIDageincomestudentCredit_ratingBuyComputer

1W30HighNoFairNo

2W30HighNoExcellentNo

33:40HighNoFairYes

4>40medNoFairYes

5>40LowYesFairYes

6>40LowYesExcellentNo

731~40LowYesExcellentYes

8至30MedNoFairNo

9W30LowYesFairYes

10>40MedYesFairYes

11W30MedYesExcellentYes

1231~40MedNoExcellentYes

133「40HighYesFairYes

14>40medNoExcellentNo

B、對數據中的枚舉類型數據進行轉換以便于數據處理：

0123ClassNo

100000

200010

310001

421001

522101

622110

712111

801000

902101

1021101

1101111

1211011

1310101

1421010

4.3計算訓練數據集數據中各屬性在各類中的概率分布情況如圖27所示

4.4利用測試數據計算貝葉斯算法的分類精度如圖2-2所示

Yes

圖2-1訓練數據集各屬性的概率分布計算

申請ClassSize*ClassSize個空間Precise

圖2-2貝葉斯算法的分類精度計算

五、實驗要求

1、用java語言實現上述相關算法。

2、改造參考代碼，添加準確度度計算函數，并實現

3、在報告中詳細寫出實驗操作步驟和實驗結果，實驗中出現的問題和解決方法。

參考代碼

importjava.io.BufferedReader;

importjava.io.File;

importjava.io.;

importjava.io.lOException;

importjava.util.ArrayList;

importjava.util.HashMap;

importjava.util.Map;

/**

*樸素貝葉斯算法工具類

*/

publicclassNaiveBayesTool{

//類標記符，這里分為2類，YES和NO

privateStringYES=〃Yes〃；

privateStringNO=〃No〃；

//已分類訓練數據集文件路徑

privateString;

//屬性名稱數組

privateString[]attrNames;

//訓練數據集

privateString口□data;

//每個屬性的值所有類型

privateHashMap<String,ArrayList<String?attrValue;

publicNaiveBayesTool(String){

this.=;

readDataFileO;

initAttrValueO;

}

/**

*從文件中讀取數據

*/

privatevoidreadDataFileO{

=newFileO;

ArrayList<String[]>dataArray=newArrayList<String[]>();

try(

BufferedReaderin=newBufferedReader(new(file));

Stringstr;

String口tempArray;

while((str=in.readLine())!=null){

tempArray=str.splitC〃)；

dataArray.add(tempArray);

)

in.close();

}catch(lOExceptione){

e.getStackTrace();

data=newString[dataArray.sizeO][];

dataArray.toArray(data);

attrNames=data[0];

/*

*for(inti=0;i<data.length;i++){for(intj=0;j<data[0].length;j++){

*System,out.print(，z"+data[i][j]);}

*

*System,out.print(〃\n〃)；}

*/

)

/**

*首先初始化每種屬性的值的所有類型，用于后面的子類烯的計算時用

*/

privatevoidinitAttrValue(){

attrValue=newHashMapOO;

ArrayList<String>tempValues;

//按照列的方式，從左往右找

for(intj=1;j<attrNames.length;j++){

//從一列中的上往下開始尋找值

tempValues=newArrayListO();

for(inti=1;i<data,length;i++){

if(!tempValues.contains(data[i][j])){

//如果這個屬性的值沒有添加過，則添加

tempValues.add(data[i][j]);

)

)

//一列屬性的值已經遍歷完畢，復制到map屬性表中

attrValue.put(data[0][j],tempValues);

)

}

/**

*在classType的情況下，發生condition條件的概率

*

*?paramcondition

*屬性條件

*@paramclassType

*分類的類型

*?return

*/

privatedoublecomputeConditionProbably(Stringcondition,StringclassType){

//條件計數器

intcount=0;

//條件屬性的索引列

intattrlndex=1;

//yes類標記符數據

ArrayList<String[]>yClassData=newArrayListO();

//no類標記符數據

ArrayList<String[]>nClassData=newArrayListO();

ArrayList<String[]>classData;

for(inti=1;i<data,length;i++){

//data數據按照yes和no分類

if(data[i][attrNames.length-1].equals(YES)){

yClassData.add(data[i]);

}else{

nClassData.add(data[i]);

)

)

if(classType.equals(YES)){

classData=yClassData;

}else{

classData=nClassData;

)

//如果沒有設置條件則，計算的是純粹的類事件概率

if(condition==null){

return1.0*classData.size()/(data,length-1);

)

//尋找此條件的屬性列

attrlndex=getConditionAttrName(condition);

for(String[]s:classData){

if(s[attrlndex].equals(condition)){

count++;

)

)

return1.0*count/classData.size();

/**

*根據條件值返回條件所屬屬性的列值

*

*?paramcondition

*條件

*?return

*/

privateintgetConditionAttrName(Stringcondition){

//條件所屬屬性名

StringattrName=〃〃；

//條件所在屬性列索引

intattrlndex=1;

〃臨時屬性值類型

ArrayList<String[]>valueTypes;

for(Map.Entryentry:attrValue.entrySet()){

valueTypes=(ArrayList<String[]>)entry.getValueO;

if(valueTypes.contains(condition)

&,&!((String)entry.getKeyO).equals(，，BuysComputer，z))

attrName=(String)entry.getKeyO;

)

)

for(inti=0;i<attrNames.length-1;i++){

if(attrNames[i].equals(attrName)){

attrlndex=i;

break;

}

)

returnattrlndex;

)

/**

*進行樸素貝葉斯分類

*

*?paramdata

*待分類數據

*/

publicStringnaiveBayesClassificate(Stringdata){

//測試數據的屬性值特征

String[]dataFeatures;

//在yes的條件下，x事件發生的概率

doublexWhenYes=1.0;

//在no的條件下，x事件發生的概率

doublexWhenNo=1.0;

//最后也是yes和no分類的總概率，用P(X|Ci)*P(Ci)的公式計算

doublepYes=1;

doublepNo=1;

dataFeatures=data,split(z，〃)；

for(inti=0;i<dataFeatures.length;i++){

//因為樸素貝葉斯算法是類條件獨立的，所以可以進行累積的計算

xWhenYes*二computeConditionProbably(dataFeatures[i],YES);

xWhenNo*=computeConditionProbably(dataFeatures[i],NO);

}

pYes=xWhenYes*computeConditionProbably(nul1,YES);

pNo=xWhenNo*computeConditionProbab1y(nu11,NO);

return(pYes>pNo?YES:NO);

)

)

實驗3K-Means聚類算法實現

一、實驗目的

通過分析K-Means聚類算法的聚類原理，利用JAVA編程工具（或者其他編程工具）實現

K-Means聚類算法，并通過對樣本數據的聚類過程，加深對該聚類算法的理解與應用過程。

二、實驗內容

1、分析K-Means聚類算法；

2、分析距離計算方法；

3、分析聚類的評價準則；

4、編程完成K-Means聚類算法，并基于相關實驗數據實現聚類過程；

三'實驗方法

1、K-means聚類算法原理

K-means聚類算法以K為參數，把n個對象分為K個簇，以使簇內的具有較高的相似度。相

似度的計算根據一個簇中對象的平均值來進行。

算法描述：

輸入：簇的數目K和包含n個對象的數據庫

輸出：使平方誤差準則最小的C個簇

過程：

任選K個對象作為初始的簇中心；

Repeat

forj=ltonDO

根據簇中對象的平均值，將每個對象賦給最類似的簇

fori=ltoKDO

更新簇的平均值

計算E

Unit!E不再發生變化

按簇輸出相應的對象

2、聚類評價準則：

E的計算為：E=

i=lxeCj

四、實驗步驟

4.1實驗數據

請自行下載Wine和Iris數據中的一種做為訓練樣本集，完成實驗。

4.2初始簇中心的選擇

選擇k個樣本作為簇中心

For(i=0;i<k;i++)

For(j=0;j<AttSetSize;j++)

ClusterCenter[i][j]=DataBase[i][j]

4.3數據對象的重新分配

Sim二某一較大數；ClusterNo=-l;

For(i=0;i<k;i++)

If(Distance(DataBase[j],ClusterCenter[i])<Sim)

{Sim=Distance(DataBase[j],ClusterCenter[i]);

ClusterNo=i;}

ObjectCluster[j]=ClusterNo;

4.4簇的更新

For(i=0;i<k;i++)

{Temp=0;Num=0;

For(j=0;j<n;j++)

If(ObjectCluster[j]==i){Num++;Temp+=DataBase[j];}

If(ClusterCenter[i]!=Temp)HasChanged=TRUE;

ClusterCenter[i]=Temp;

)

4.5結果的輸出

For(i=0;i<k;i++)

|

Printf("輸出第%d個簇的對象：”，i);

For(j=0;j<n;j++)

If(ObjectCluster[j]==i)printf(a%d”，j);

Printf("\n”);

Printf(^\t\t\t簇平均值為觥d,%d)\n"，ClusterCenter[i][0],

ClusterCenter[i][1]);

)

五'注意事項

（1）K如何確定

K-menas算法首先選擇K個初始質心，其中K是用戶指定的參數，即所期望

的簇的個數。這樣做的前提是我們己經知道數據集中包含多少個簇，但很多情況

下，我們并不知道數據的分布情況，實際上聚類就是我們發現數據分布的一種手

段，這就陷入了雞和蛋的矛盾。如何有效的確定K值，這里大致提供幾種方法,

以供參考。

1.與層次聚類結合

經常會產生較好的聚類結果的一個有趣策略是，首先采用層次凝聚算法決定

結果粗的數目，并找到一個初始聚類，然后用迭代重定位來改進該聚類。

2.穩定性方法

穩定性方法對一個數據集進行2次重采樣產生2個數據子集，再用相同的聚

類算法對2個數據子集進行聚類，產生2個具有k個聚類的聚類結果，計算2

個聚類結果的相似度的分布情況。2個聚類結果具有高的相似度說明k個聚類反

映了穩定的聚類結構，其相似度可以用來估計聚類個數。采用此方法試探多個k,

找到合適的k值。

3.系統演化方法[3]

系統演化方法將一個數據集視為偽熱力學系統，當數據集被劃分為K個聚類

時稱系統處于狀態K。系統由初始狀態K=1出發，經過分裂過程和合并過程，系

統將演化到它的穩定平衡狀態Ki,其所對應的聚類結構決定了最優類數Ki。系

統演化方法能提供關于所有聚類之間的相對邊界距離或可分程度，它適用于明顯

分離的聚類結構和輕微重疊的聚類結構。

4.使用canopy算法進行初始劃分[4]

基于CanopyMethod的聚類算法將聚類過程分為兩個階段：

Stagel、聚類最耗費計算的地方是計算對象相似性的時候，CanopyMethod

在第一階段選擇簡單、計算代價較低的方法計算對象相似性，將相似的對象放在

一個子集中，這個子集被叫做Canopy,通過一系列計算得到若干Canopy,Canopy

之間可以是重疊的，但不會存在某個對象不屬于任何Canopy的情況，可以把這

一階段看做數據預處理；

Stage2＞在各個Canopy內使用傳統的聚類方法（如K-means）,不屬于同一

Canopy的對象之間不進行相似性計算。

從這個方法起碼可以看出兩點好處：首先，Canopy不要太大且Canopy之

間重疊的不要太多的話會大大減少后續需要計算相似性的對象的個數；其次，類

似于K-means這樣的聚類方法是需要人為指出K的值的，通過Stagel得到的

Canopy個數完全可以作為這個K值，一定程度上減少了選擇K的盲目性。

（2）初始質心的選取

選擇適當的初始質心是基本kmeans算法的關鍵步驟。常見的方法是隨機的

選取初始質心，但是這樣簇的質量常常很差。處理選取初始質心問題的一種常用

技術是：多次運行，每次使用一組不同的隨機初始質心，然后選取具有最小SSE

（誤差的平方和）的簇集。這種策略簡單，但是效果可能不好，這取決于數據集

和尋找的簇的個數。

第二種有效的方法是，取一個樣本，并使用層次聚類技術對它聚類。從層次

聚類中提取K個簇，并用這些簇的質心作為初始質心。該方法通常很有效，但僅

對下列情況有效：（1）樣本相對較小，例如數百到數千（層次聚類開銷較大）；

（2）K相對于樣本大小較小。

第三種選擇初始質心的方法，隨機地選擇第一個點，或取所有點的質心作為

第一個點。然后，對于每個后繼初始質心，選擇離已經選取過的初始質心最遠的

點。使用這種方法，確保了選擇的初始質心不僅是隨機的，而且是散開的。但是，

這種方法可能選中離群點。此外，求離當前初始質心集最遠的點開銷也非常大。

為了克服這個問題，通常該方法用于點樣本。由于離群點很少（多了就不是離群

點了），它們多半不會在隨機樣本中出現。計算量也大幅減少。

第四種方法就是上面提到的canopy算法。

（3）距離的度量

常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評定個體

間差異的大小的。歐幾里得距離度量會受指標不同單位刻度的影響，所以一般需

要先進行標準化，同時距離越大，個體間差異越大；空間向量余弦夾角的相似度

度量不會受指標刻度的影響，余弦值落于區間值越大，差異越小。但是

針對具體應用，什么情況下使用歐氏距離，什么情況下使用余弦相似度？

從幾何意義上來說，n維向量空間的一條線段作為底邊和原點組成的三角形,

其頂角大小是不確定的。也就是說對于兩條空間向量，即使兩點距離一定，他們

的夾角余弦值也可以隨意變化。感性的認識，當兩用戶評分趨勢一致時，但是評

分值差距很大，余弦相似度傾向給出更優解。舉個極端的例子，兩用戶只對兩件

商品評分，向量分別為（3,3）和（5,5）,這兩位用戶的認知其實是一樣的，但是歐

式距離給出的解顯然沒有余弦值合理。

（4）質心的計算

對于距離度量不管是采用歐式距離還是采用余弦相似度，簇的質心都是其均

值，即向量各維取平均即可。

(5)算法停止條件

一般是目標函數達到最優或者達到最大的迭代次數即可終止。對于不同的距

離度量，目標函數往往不同。當采用歐式距離時，目標函數一般為最小化對象到

其簇質心的距離的平方和，如下：

minXXdisl

/=1xeC'i

當采用余弦相似度時，目標函數一般為最大化對象到其簇質心的余弦相似度

和，如下：

K

max￡Xcosine(q,x)

/=1xeCt

(6)空聚類的處理

如果所有的點在指派步驟都未分配到某個簇，就會得到空簇。如果這種情況

發生，則需要某種策略來選擇一個替補質心，否則的話，平方誤差將會偏大。一

種方法是選擇一個距離當前任何質心最遠的點。這將消除當前對總平方誤差影響

最大的點。另一種方法是從具有最大SSE的簇中選擇一個替補的質心。這將分裂

簇并降低聚類的總SSE。如果有多個空簇，則該過程重復多次。另外，編程實現

時，要注意空簇可能導致的程序bug。

3.適用范圍及缺陷

K-menas算法試圖找到使平凡誤差準則函數最小的簇。當潛在的簇形狀是凸

面的，簇與簇之間區別較明顯，且簇大小相近時，其聚類結果較理想。前面提到，

該算法時間復雜度為O(tKmn),與樣本數量線性相關，所以，對于處理大數據集

合，該算法非常高效，且伸縮性較好。但該算法除了要事先確定簇數K和對初始

聚類中心敏感外，經常以局部最優結束，同時對“噪聲”和孤立點敏感，并且該

方法不適于發現非凸面形狀的簇或大小差別很大的簇。

參考代碼：

K-means類定義：

publicclassKMeans{

privateintkNum;〃族的個數

privateintiterNum=10;〃迭代次數

privateintiterMaxTimes=100000;〃單次迭代最大運行次數

privateintiterRunTimes=0;〃單次迭代實際運行次數

privatefloatdisDiff=(float)0.01;〃單次迭代終止條件，兩次運行中

類中心的距離差

privateList<float[]>original_data=null;〃用于存放，原始數據集

privatestaticList<Point>pointList=null;〃用于存放，原始數據集所構建

的點集

privateDistanceComputedisc=newDistanceCompute();

privateintlen=0;〃用于記錄每個數據點的維度

publicKMeansRun(intk,List<float[]>original_data){

this.kNum=k;

this.original_data=original_data;

this.len=original_data.get(0).length;

〃檢查規范

check();

〃初始化點集。

init();

}

/**

*檢查規范

*/

privatevoidcheck(){

if(kNum==0){

thrownewIllegalArgumentException("kmustbethenumber>0");

}

if(original__data==null){

thrownewIllegalArgumentException("programcan'tgetrealdata");

)

)

/**

*初始化數據集，把數組轉化為Point類型。

*/

privatevoidinit(){

pointList=newArrayList<Point>();

for(inti=0,j=original_data.size();i<j;i++){

pointList.add(newPoint(i,original_data.get(i)));

}

}

分類初始化：

publicclassCluster

privateintid;//標識

privatePointcenter;//中心

privateList<Point>members=newArrayList<Point>();//成員

publicCluster(intid.Pointcenter)

{

this.id=id;

this.center=center;

}

publicCluster(intid.Pointcenter,List<Point>members)

{

this.id=id;

this.center=center;

this.members=members;

}

publicvoidaddPoint(PointnewPoint)

{

if(!members.contains(newPoint))

{

members.add(newPoint);

}else(

System.out.printin("樣本數據點{"+newPoint.toString()+")己經存在!

")；

}

}

publicintgetld()

{

returnid;

)

publicPointgetCenter()

{

returncenter;

)

publicvoidsetCenter(Pointcenter)

{

this.center=center;

}

publicList<Point>getMembers()

{

returnmembers;

}

publicStringtoString(){

StringtoString="Cluster\n"+"Cluster__id="+this.id+:center:{

+this.center.toString()+")";

for(Pointpoint:members){

toString+="\n"+point.toString();

}

returntoString+"\n";

}

)

初始中心點設置：

privateSet<Cluster>chooseCenterCluster(){

Set<Cluster>clusterSet=newHashSet<Cluster>();

Randomrandom=newRandom();

for(intid=0;id<kNum;){

Pointpoint=pointList.get(random.nextInt(point/.ist.size()));

//用于標記是否已經選擇過該數據。

booleanflag=true;

for(Clustercluster:clusterSet){

if(cluster.getCenter(