《数据挖掘与数据仓库》课程实验指导书

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(