《數(shù)據(jù)挖掘與數(shù)據(jù)倉(cāng)庫(kù)》課程實(shí)驗(yàn)指導(dǎo)書(shū)

IS為砥孟干虎

HenanUniversityofUrbanConstruction

《數(shù)據(jù)挖掘與數(shù)據(jù)倉(cāng)庫(kù)》課程

實(shí)驗(yàn)指導(dǎo)書(shū)

2020年

計(jì)算機(jī)與數(shù)據(jù)科學(xué)學(xué)院

實(shí)驗(yàn)1Apriori算法實(shí)現(xiàn)

一'實(shí)驗(yàn)?zāi)康?/p>

1、掌握Apriori算法對(duì)于關(guān)聯(lián)規(guī)則挖掘中頻繁集的產(chǎn)生以及關(guān)聯(lián)規(guī)則集合的產(chǎn)生過(guò)程；

2、根據(jù)算法描述編程實(shí)現(xiàn)算法，調(diào)試運(yùn)行。并結(jié)合相關(guān)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行應(yīng)用，得到分析結(jié)果。

數(shù)據(jù)和刪除數(shù)據(jù)的操作。

實(shí)驗(yàn)類型：綜合

計(jì)劃課間：3學(xué)時(shí)

二'實(shí)驗(yàn)內(nèi)容

1、頻繁項(xiàng)集的生成與Apriori算法實(shí)現(xiàn)；

2、關(guān)聯(lián)規(guī)則的生成過(guò)程與規(guī)則算法實(shí)現(xiàn)；

3、結(jié)合樣例對(duì)算法進(jìn)行分析；

三'實(shí)驗(yàn)步驟

編寫(xiě)程序完成下列算法：

1、Apriori算法

輸入：數(shù)據(jù)集D；最小支持?jǐn)?shù)minsupcount；

輸出：頻繁項(xiàng)目集L

Ll={large1-itemsets)

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

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

Foralltransactionst^Ddo

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

forallcandidatescwCtdoc.count++;

end

Lk={cGCk|c.count工minsupcount}

End

L=ULk;

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

輸入：（kT）-頻繁項(xiàng)目集LkT

輸出：k-頻繁項(xiàng)目集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)

功能：判斷候選集的元素

輸入：一個(gè)k-頻繁項(xiàng)目集LkT,8-1)-頻繁項(xiàng)目集1^-1

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

Forall(k-l)-subsetsofcdo

IfNot(SeLk-l)THENreturnTRUE;

ReturnFALSE;

4、Rule-generate(L,minconf)

輸入：頻繁項(xiàng)目集；最小信任度

輸出：強(qiáng)關(guān)聯(lián)規(guī)則

算法：

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

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

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

END;

END;

結(jié)合相關(guān)樣例數(shù)據(jù)對(duì)算法進(jìn)行調(diào)試，并根據(jù)相關(guān)實(shí)驗(yàn)結(jié)果對(duì)數(shù)據(jù)進(jìn)行分析，

四、實(shí)驗(yàn)報(bào)告要求

1、用java語(yǔ)言實(shí)現(xiàn)上述相關(guān)算法。

2、改造參考代碼，添加最小置信度約束條件，并實(shí)現(xiàn)算法

3、在報(bào)告中詳細(xì)寫(xiě)出實(shí)驗(yàn)操作步驟和實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)中出現(xiàn)的問(wèn)題和解決方法。

五、注意事項(xiàng)

1、集合的表示及相關(guān)操作的實(shí)現(xiàn)；

2、項(xiàng)目集的數(shù)據(jù)結(jié)構(gòu)描述；

參考核心代碼如下：(相關(guān)的測(cè)試main函數(shù)可以自己書(shū)寫(xiě)。根據(jù)頻繁k項(xiàng)集生成關(guān)聯(lián)規(guī)則相

對(duì)簡(jiǎn)單，只通過(guò)最小支持度從頻繁K項(xiàng)集中找到所有的滿足條件的關(guān)聯(lián)規(guī)則。)

publicclassApriori

(

privatestaticfinaldoubleMIN_SUPPROT=0.2;〃最小支持度

privatestaticbooleanendTag=false;〃循環(huán)狀態(tài)

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

/**

*讀取txt數(shù)據(jù)

*/

publicstaticList<List<String>>getRecordO

(

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

try

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

=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(xiàn)，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(〃讀取文件內(nèi)容操作出錯(cuò)”)；

e.printStackTrace();

)

returnrecord;

)

/**

*有當(dāng)前頻繁項(xiàng)集自連接求下一次候選集

*?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。；〃添加前長(zhǎng)度

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

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

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

頻繁項(xiàng)集的某一行，

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個(gè)新的元素，再判斷其是否為「“ord某一行

的子集，若是則其為候選集中的一項(xiàng)

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轉(zhuǎn)換成員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項(xiàng)候選集剪枝得到k項(xiàng)頻繁集

*?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⑴)；〃統(tǒng)計(jì)記錄數(shù)

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

(

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

end=false;

)

}

endTag二end;〃存在頻繁項(xiàng)集則不會(huì)結(jié)束

if(endTag==true)

System.out.printin(〃無(wú)滿足支持度項(xiàng)集,結(jié)束連接〃)；

returnsupportedltemset;

)

/**

*統(tǒng)計(jì)record中出現(xiàn)list集合的個(gè)數(shù)

*?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){〃只要有一個(gè)list元素找不到，則退出其余元素比

較，進(jìn)行下一個(gè)record。get(i)比較

notHaveThisList=true;

break;

)

)

if(notHaveThisList==false)

count++;

)

returncount;

)

/**

*獲得一項(xiàng)候選集

*/

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;

實(shí)驗(yàn)2貝葉斯算法實(shí)現(xiàn)

一、實(shí)驗(yàn)?zāi)康?/p>

通過(guò)對(duì)貝葉斯算法的編程實(shí)現(xiàn)，加深對(duì)貝葉斯算法的理解，同時(shí)利用貝葉斯算法對(duì)簡(jiǎn)單

應(yīng)用實(shí)現(xiàn)預(yù)測(cè)分類

二'實(shí)驗(yàn)內(nèi)容

1、分析貝葉斯算法；

2、計(jì)算條件概率；

3、預(yù)測(cè)精度的計(jì)算與評(píng)估；

4、編程實(shí)現(xiàn)貝葉斯分類算法，并對(duì)簡(jiǎn)單應(yīng)用樣本數(shù)據(jù)實(shí)現(xiàn)預(yù)測(cè)分類

5.參考實(shí)驗(yàn)數(shù)據(jù)

三'實(shí)驗(yàn)方法

1、實(shí)現(xiàn)貝葉斯算法

2、利用實(shí)驗(yàn)數(shù)據(jù)對(duì)貝葉斯算法進(jìn)行檢測(cè)

3、求解精確度計(jì)算

4、調(diào)試程序

四'實(shí)驗(yàn)步驟

4.1算法過(guò)程描述：

1）輸入訓(xùn)練數(shù)據(jù)，將數(shù)據(jù)保存在DataBase二維數(shù)組中（數(shù)組的最后一個(gè)屬性對(duì)應(yīng)類別

標(biāo)號(hào)）

2）設(shè)定訓(xùn)練數(shù)據(jù)集與測(cè)試數(shù)據(jù)集大?。ㄖ付◤臄?shù)組下標(biāo)0開(kāi)始到TrainSetSizeT所對(duì)應(yīng)

的數(shù)據(jù)為訓(xùn)練數(shù)據(jù)，其余為測(cè)試數(shù)據(jù)）；

3）計(jì)算訓(xùn)練數(shù)據(jù)集數(shù)據(jù)中各屬性在各類中的概率分布情況；

4）利用測(cè)試數(shù)據(jù)計(jì)算貝葉斯算法的分類精度；

5）輸出分類結(jié)果；

4.2數(shù)據(jù)處理

A、實(shí)驗(yàn)數(shù)據(jù)

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、對(duì)數(shù)據(jù)中的枚舉類型數(shù)據(jù)進(jìn)行轉(zhuǎn)換以便于數(shù)據(jù)處理：

0123ClassNo

100000

200010

310001

421001

522101

622110

712111

801000

902101

1021101

1101111

1211011

1310101

1421010

4.3計(jì)算訓(xùn)練數(shù)據(jù)集數(shù)據(jù)中各屬性在各類中的概率分布情況如圖27所示

4.4利用測(cè)試數(shù)據(jù)計(jì)算貝葉斯算法的分類精度如圖2-2所示

Yes

圖2-1訓(xùn)練數(shù)據(jù)集各屬性的概率分布計(jì)算

申請(qǐng)ClassSize*ClassSize個(gè)空間Precise

圖2-2貝葉斯算法的分類精度計(jì)算

五、實(shí)驗(yàn)要求

1、用java語(yǔ)言實(shí)現(xiàn)上述相關(guān)算法。

2、改造參考代碼，添加準(zhǔn)確度度計(jì)算函數(shù)，并實(shí)現(xiàn)

3、在報(bào)告中詳細(xì)寫(xiě)出實(shí)驗(yàn)操作步驟和實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)中出現(xiàn)的問(wèn)題和解決方法。

參考代碼

importjava.io.BufferedReader;

importjava.io.File;

importjava.io.;

importjava.io.lOException;

importjava.util.ArrayList;

importjava.util.HashMap;

importjava.util.Map;

/**

*樸素貝葉斯算法工具類

*/

publicclassNaiveBayesTool{

//類標(biāo)記符，這里分為2類，YES和NO

privateStringYES=〃Yes〃；

privateStringNO=〃No〃；

//已分類訓(xùn)練數(shù)據(jù)集文件路徑

privateString;

//屬性名稱數(shù)組

privateString[]attrNames;

//訓(xùn)練數(shù)據(jù)集

privateString口□data;

//每個(gè)屬性的值所有類型

privateHashMap<String,ArrayList<String?attrValue;

publicNaiveBayesTool(String){

this.=;

readDataFileO;

initAttrValueO;

}

/**

*從文件中讀取數(shù)據(jù)

*/

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〃)；}

*/

)

/**

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

*/

privatevoidinitAttrValue(){

attrValue=newHashMapOO;

ArrayList<String>tempValues;

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

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

//從一列中的上往下開(kāi)始尋找值

tempValues=newArrayListO();

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

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

//如果這個(gè)屬性的值沒(méi)有添加過(guò)，則添加

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

)

)

//一列屬性的值已經(jīng)遍歷完畢，復(fù)制到map屬性表中

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

)

}

/**

*在classType的情況下，發(fā)生condition條件的概率

*

*?paramcondition

*屬性條件

*@paramclassType

*分類的類型

*?return

*/

privatedoublecomputeConditionProbably(Stringcondition,StringclassType){

//條件計(jì)數(shù)器

intcount=0;

//條件屬性的索引列

intattrlndex=1;

//yes類標(biāo)記符數(shù)據(jù)

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

//no類標(biāo)記符數(shù)據(jù)

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

ArrayList<String[]>classData;

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

//data數(shù)據(jù)按照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;

)

//如果沒(méi)有設(shè)置條件則，計(jì)算的是純粹的類事件概率

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();

/**

*根據(jù)條件值返回條件所屬屬性的列值

*

*?paramcondition

*條件

*?return

*/

privateintgetConditionAttrName(Stringcondition){

//條件所屬屬性名

StringattrName=〃〃；

//條件所在屬性列索引

intattrlndex=1;

〃臨時(shí)屬性值類型

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;

)

/**

*進(jìn)行樸素貝葉斯分類

*

*?paramdata

*待分類數(shù)據(jù)

*/

publicStringnaiveBayesClassificate(Stringdata){

//測(cè)試數(shù)據(jù)的屬性值特征

String[]dataFeatures;

//在yes的條件下，x事件發(fā)生的概率

doublexWhenYes=1.0;

//在no的條件下，x事件發(fā)生的概率

doublexWhenNo=1.0;

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

doublepYes=1;

doublepNo=1;

dataFeatures=data,split(z，〃)；

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

//因?yàn)闃闼刎惾~斯算法是類條件獨(dú)立的，所以可以進(jìn)行累積的計(jì)算

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);

)

)

實(shí)驗(yàn)3K-Means聚類算法實(shí)現(xiàn)

一、實(shí)驗(yàn)?zāi)康?/p>

通過(guò)分析K-Means聚類算法的聚類原理，利用JAVA編程工具（或者其他編程工具）實(shí)現(xiàn)

K-Means聚類算法，并通過(guò)對(duì)樣本數(shù)據(jù)的聚類過(guò)程，加深對(duì)該聚類算法的理解與應(yīng)用過(guò)程。

二、實(shí)驗(yàn)內(nèi)容

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

2、分析距離計(jì)算方法；

3、分析聚類的評(píng)價(jià)準(zhǔn)則；

4、編程完成K-Means聚類算法，并基于相關(guān)實(shí)驗(yàn)數(shù)據(jù)實(shí)現(xiàn)聚類過(guò)程；

三'實(shí)驗(yàn)方法

1、K-means聚類算法原理

K-means聚類算法以K為參數(shù)，把n個(gè)對(duì)象分為K個(gè)簇，以使簇內(nèi)的具有較高的相似度。相

似度的計(jì)算根據(jù)一個(gè)簇中對(duì)象的平均值來(lái)進(jìn)行。

算法描述：

輸入：簇的數(shù)目K和包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)

輸出：使平方誤差準(zhǔn)則最小的C個(gè)簇

過(guò)程：

任選K個(gè)對(duì)象作為初始的簇中心；

Repeat

forj=ltonDO

根據(jù)簇中對(duì)象的平均值，將每個(gè)對(duì)象賦給最類似的簇

fori=ltoKDO

更新簇的平均值

計(jì)算E

Unit!E不再發(fā)生變化

按簇輸出相應(yīng)的對(duì)象

2、聚類評(píng)價(jià)準(zhǔn)則：

E的計(jì)算為：E=

i=lxeCj

四、實(shí)驗(yàn)步驟

4.1實(shí)驗(yàn)數(shù)據(jù)

請(qǐng)自行下載Wine和Iris數(shù)據(jù)中的一種做為訓(xùn)練樣本集，完成實(shí)驗(yàn)。

4.2初始簇中心的選擇

選擇k個(gè)樣本作為簇中心

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

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

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

4.3數(shù)據(jù)對(duì)象的重新分配

Sim二某一較大數(shù)；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結(jié)果的輸出

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

|

Printf("輸出第%d個(gè)簇的對(duì)象：”，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]);

)

五'注意事項(xiàng)

（1）K如何確定

K-menas算法首先選擇K個(gè)初始質(zhì)心，其中K是用戶指定的參數(shù)，即所期望

的簇的個(gè)數(shù)。這樣做的前提是我們己經(jīng)知道數(shù)據(jù)集中包含多少個(gè)簇，但很多情況

下，我們并不知道數(shù)據(jù)的分布情況，實(shí)際上聚類就是我們發(fā)現(xiàn)數(shù)據(jù)分布的一種手

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

以供參考。

1.與層次聚類結(jié)合

經(jīng)常會(huì)產(chǎn)生較好的聚類結(jié)果的一個(gè)有趣策略是，首先采用層次凝聚算法決定

結(jié)果粗的數(shù)目，并找到一個(gè)初始聚類，然后用迭代重定位來(lái)改進(jìn)該聚類。

2.穩(wěn)定性方法

穩(wěn)定性方法對(duì)一個(gè)數(shù)據(jù)集進(jìn)行2次重采樣產(chǎn)生2個(gè)數(shù)據(jù)子集，再用相同的聚

類算法對(duì)2個(gè)數(shù)據(jù)子集進(jìn)行聚類，產(chǎn)生2個(gè)具有k個(gè)聚類的聚類結(jié)果，計(jì)算2

個(gè)聚類結(jié)果的相似度的分布情況。2個(gè)聚類結(jié)果具有高的相似度說(shuō)明k個(gè)聚類反

映了穩(wěn)定的聚類結(jié)構(gòu)，其相似度可以用來(lái)估計(jì)聚類個(gè)數(shù)。采用此方法試探多個(gè)k,

找到合適的k值。

3.系統(tǒng)演化方法[3]

系統(tǒng)演化方法將一個(gè)數(shù)據(jù)集視為偽熱力學(xué)系統(tǒng)，當(dāng)數(shù)據(jù)集被劃分為K個(gè)聚類

時(shí)稱系統(tǒng)處于狀態(tài)K。系統(tǒng)由初始狀態(tài)K=1出發(fā)，經(jīng)過(guò)分裂過(guò)程和合并過(guò)程，系

統(tǒng)將演化到它的穩(wěn)定平衡狀態(tài)Ki,其所對(duì)應(yīng)的聚類結(jié)構(gòu)決定了最優(yōu)類數(shù)Ki。系

統(tǒng)演化方法能提供關(guān)于所有聚類之間的相對(duì)邊界距離或可分程度，它適用于明顯

分離的聚類結(jié)構(gòu)和輕微重疊的聚類結(jié)構(gòu)。

4.使用canopy算法進(jìn)行初始劃分[4]

基于CanopyMethod的聚類算法將聚類過(guò)程分為兩個(gè)階段：

Stagel、聚類最耗費(fèi)計(jì)算的地方是計(jì)算對(duì)象相似性的時(shí)候，CanopyMethod

在第一階段選擇簡(jiǎn)單、計(jì)算代價(jià)較低的方法計(jì)算對(duì)象相似性，將相似的對(duì)象放在

一個(gè)子集中，這個(gè)子集被叫做Canopy,通過(guò)一系列計(jì)算得到若干Canopy,Canopy

之間可以是重疊的，但不會(huì)存在某個(gè)對(duì)象不屬于任何Canopy的情況，可以把這

一階段看做數(shù)據(jù)預(yù)處理；

Stage2＞在各個(gè)Canopy內(nèi)使用傳統(tǒng)的聚類方法（如K-means）,不屬于同一

Canopy的對(duì)象之間不進(jìn)行相似性計(jì)算。

從這個(gè)方法起碼可以看出兩點(diǎn)好處：首先，Canopy不要太大且Canopy之

間重疊的不要太多的話會(huì)大大減少后續(xù)需要計(jì)算相似性的對(duì)象的個(gè)數(shù)；其次，類

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

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

（2）初始質(zhì)心的選取

選擇適當(dāng)?shù)某跏假|(zhì)心是基本kmeans算法的關(guān)鍵步驟。常見(jiàn)的方法是隨機(jī)的

選取初始質(zhì)心，但是這樣簇的質(zhì)量常常很差。處理選取初始質(zhì)心問(wèn)題的一種常用

技術(shù)是：多次運(yùn)行，每次使用一組不同的隨機(jī)初始質(zhì)心，然后選取具有最小SSE

（誤差的平方和）的簇集。這種策略簡(jiǎn)單，但是效果可能不好，這取決于數(shù)據(jù)集

和尋找的簇的個(gè)數(shù)。

第二種有效的方法是，取一個(gè)樣本，并使用層次聚類技術(shù)對(duì)它聚類。從層次

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

對(duì)下列情況有效：（1）樣本相對(duì)較小，例如數(shù)百到數(shù)千（層次聚類開(kāi)銷較大）；

（2）K相對(duì)于樣本大小較小。

第三種選擇初始質(zhì)心的方法，隨機(jī)地選擇第一個(gè)點(diǎn)，或取所有點(diǎn)的質(zhì)心作為

第一個(gè)點(diǎn)。然后，對(duì)于每個(gè)后繼初始質(zhì)心，選擇離已經(jīng)選取過(guò)的初始質(zhì)心最遠(yuǎn)的

點(diǎn)。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機(jī)的，而且是散開(kāi)的。但是，

這種方法可能選中離群點(diǎn)。此外，求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點(diǎn)開(kāi)銷也非常大。

為了克服這個(gè)問(wèn)題，通常該方法用于點(diǎn)樣本。由于離群點(diǎn)很少（多了就不是離群

點(diǎn)了），它們多半不會(huì)在隨機(jī)樣本中出現(xiàn)。計(jì)算量也大幅減少。

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

（3）距離的度量

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

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

要先進(jìn)行標(biāo)準(zhǔn)化，同時(shí)距離越大，個(gè)體間差異越大；空間向量余弦?jiàn)A角的相似度

度量不會(huì)受指標(biāo)刻度的影響，余弦值落于區(qū)間值越大，差異越小。但是

針對(duì)具體應(yīng)用，什么情況下使用歐氏距離，什么情況下使用余弦相似度？

從幾何意義上來(lái)說(shuō)，n維向量空間的一條線段作為底邊和原點(diǎn)組成的三角形,

其頂角大小是不確定的。也就是說(shuō)對(duì)于兩條空間向量，即使兩點(diǎn)距離一定，他們

的夾角余弦值也可以隨意變化。感性的認(rèn)識(shí)，當(dāng)兩用戶評(píng)分趨勢(shì)一致時(shí)，但是評(píng)

分值差距很大，余弦相似度傾向給出更優(yōu)解。舉個(gè)極端的例子，兩用戶只對(duì)兩件

商品評(píng)分，向量分別為（3,3）和（5,5）,這兩位用戶的認(rèn)知其實(shí)是一樣的，但是歐

式距離給出的解顯然沒(méi)有余弦值合理。

（4）質(zhì)心的計(jì)算

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

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

(5)算法停止條件

一般是目標(biāo)函數(shù)達(dá)到最優(yōu)或者達(dá)到最大的迭代次數(shù)即可終止。對(duì)于不同的距

離度量，目標(biāo)函數(shù)往往不同。當(dāng)采用歐式距離時(shí)，目標(biāo)函數(shù)一般為最小化對(duì)象到

其簇質(zhì)心的距離的平方和，如下：

minXXdisl

/=1xeC'i

當(dāng)采用余弦相似度時(shí)，目標(biāo)函數(shù)一般為最大化對(duì)象到其簇質(zhì)心的余弦相似度

和，如下：

K

max￡Xcosine(q,x)

/=1xeCt

(6)空聚類的處理

如果所有的點(diǎn)在指派步驟都未分配到某個(gè)簇，就會(huì)得到空簇。如果這種情況

發(fā)生，則需要某種策略來(lái)選擇一個(gè)替補(bǔ)質(zhì)心，否則的話，平方誤差將會(huì)偏大。一

種方法是選擇一個(gè)距離當(dāng)前任何質(zhì)心最遠(yuǎn)的點(diǎn)。這將消除當(dāng)前對(duì)總平方誤差影響

最大的點(diǎn)。另一種方法是從具有最大SSE的簇中選擇一個(gè)替補(bǔ)的質(zhì)心。這將分裂

簇并降低聚類的總SSE。如果有多個(gè)空簇，則該過(guò)程重復(fù)多次。另外，編程實(shí)現(xiàn)

時(shí)，要注意空簇可能導(dǎo)致的程序bug。

3.適用范圍及缺陷

K-menas算法試圖找到使平凡誤差準(zhǔn)則函數(shù)最小的簇。當(dāng)潛在的簇形狀是凸

面的，簇與簇之間區(qū)別較明顯，且簇大小相近時(shí)，其聚類結(jié)果較理想。前面提到，

該算法時(shí)間復(fù)雜度為O(tKmn),與樣本數(shù)量線性相關(guān)，所以，對(duì)于處理大數(shù)據(jù)集

合，該算法非常高效，且伸縮性較好。但該算法除了要事先確定簇?cái)?shù)K和對(duì)初始

聚類中心敏感外，經(jīng)常以局部最優(yōu)結(jié)束，同時(shí)對(duì)“噪聲”和孤立點(diǎn)敏感，并且該

方法不適于發(fā)現(xiàn)非凸面形狀的簇或大小差別很大的簇。

參考代碼：

K-means類定義：

publicclassKMeans{

privateintkNum;〃族的個(gè)數(shù)

privateintiterNum=10;〃迭代次數(shù)

privateintiterMaxTimes=100000;〃單次迭代最大運(yùn)行次數(shù)

privateintiterRunTimes=0;〃單次迭代實(shí)際運(yùn)行次數(shù)

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

類中心的距離差

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

privatestaticList<Point>pointList=null;〃用于存放，原始數(shù)據(jù)集所構(gòu)建

的點(diǎn)集

privateDistanceComputedisc=newDistanceCompute();

privateintlen=0;〃用于記錄每個(gè)數(shù)據(jù)點(diǎn)的維度

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

this.kNum=k;

this.original_data=original_data;

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

〃檢查規(guī)范

check();

〃初始化點(diǎn)集。

init();

}

/**

*檢查規(guī)范

*/

privatevoidcheck(){

if(kNum==0){

thrownewIllegalArgumentException("kmustbethenumber>0");

}

if(original__data==null){

thrownewIllegalArgumentException("programcan'tgetrealdata");

)

)

/**

*初始化數(shù)據(jù)集，把數(shù)組轉(zhuǎn)化為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;//標(biāo)識(shí)

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("樣本數(shù)據(jù)點(diǎn){"+newPoint.toString()+")己經(jīng)存在!

")；

}

}

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";

}

)

初始中心點(diǎn)設(shè)置：

privateSet<Cluster>chooseCenterCluster(){

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

Randomrandom=newRandom();

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

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

//用于標(biāo)記是否已經(jīng)選擇過(guò)該數(shù)據(jù)。

booleanflag=true;

for(Clustercluster:clusterSet){

if(cluster.getCenter(