数据挖掘及实验报告

-.z中科大数据挖掘实验报告**樊涛声班级软设一班**SA15226248实验一K邻近算法实验一实验内容使用k近邻算法改进约会的配对效果。海伦使用约会网址寻找适合自己的约会对象，约会会推荐不同的人选。她将曾经交往过的的人总结为三种类型：不喜欢的人魅力一般的人极具魅力的人尽管发现了这些规律，但依然无法将约会提供的人归入恰当的分类。使用KNN算法，更好的帮助她将匹配对象划分到确切的分类中。二实验要求〔1〕独立完成kNN实验，根本实现可预测的效果〔2〕实验报告〔3〕开放性：可以自己增加数据或修改算法，实现更好的分类效果三实验步骤〔1〕数据源说明实验给出的数据源为datingTestSet.t*t，共有4列，每一列的属性分别为：①percentageoftimespentingplayingvediogames；②frequentfliedmilesearnedperyear；③litersoficecreamconsumedperyear；④yourattitudetowarsthispeople。通过分析数据源中的数据，得到规律，从而判断一个人的前三项属性来得出划分海伦对他的态度。〔2〕KNN算法原理对未知属性的*数据集中的每个点一次执行以下操作计算类别数据集中的每一个点和当前点的距离按照距离递增依次排序选取与当前点距离最小的k个点确定k个点所在类别的出现频率返回k个点出现频率最高的点作为当前点的分类〔3〕KNN算法实现①利用python实现构造分类器首先计算欧式距离然后选取距离最小的K个点代码如下：defclassify(inMat,dataSet,labels,k):

dataSetSize=dataSet.shape[0]

*KNN的算法核心就是欧式距离的计算，一下三行是计算待分类的点和训练集中的任一点的欧式距离diffMat=tile(inMat,(dataSetSize,1))-dataSet

sqDiffMat=diffMat**2

distance=sqDiffMat.sum(a*is=1)**0.5

*接下来是一些统计工作sortedDistIndicies=distance.argsort()

classCount={}

foriinrange(k):

labelName=labels[sortedDistIndicies[i]]

classCount[labelName]=classCount.get(labelName,0)+1;

sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)

returnsortedClassCount[0][0]②解析数据输入文件名，将文件中的数据转化为样本矩阵，方便处理代码如下：deffile2Mat(testFileName,parammterNumber):

fr=open(testFileName)

lines=fr.readlines()

lineNums=len(lines)

resultMat=zeros((lineNums,parammterNumber))

classLabelVector=[]

foriinrange(lineNums):

line=lines[i].strip()

itemMat=line.split('\t')

resultMat[i,:]=itemMat[0:parammterNumber]

classLabelVector.append(itemMat[-1])

fr.close()

returnresultMat,classLabelVector;返回值为前三列属性被写入到resultMat二维数组中，第四列属性作为标签写入到classLableVector中③归一化数据不同评价指标往往具有不同的量纲和量纲单位，这样的情况会影响到数据分析的结果，为了消除指标之间的量纲影响，需要进展数据标准化处理，使各指标处于同一数量级。处理过程如下：defautoNorm(dataSet):

minVals=dataSet.min(0)

ma*Vals=dataSet.ma*(0)

ranges=ma*Vals-minVals

normMat=zeros(shape(dataSet))

size=normMat.shape[0]

normMat=dataSet-tile(minVals,(size,1))

normMat=normMat/tile(ranges,(size,1))

returnnormMat,minVals,ranges④测试数据在利用KNN算法预测之前，通常只提供已有数据的90%作为训练样本，使用其余的10%数据去测试分类器。注意10%测试数据是随机选择的，采用错误率来检测分类器的性能。错误率太高说明数据源出现问题，此时需要重新考虑数据源的合理性。deftest(trainigSetFileName,testFileName):

trianingMat,classLabel=file2Mat(trainigSetFileName,3)

trianingMat,minVals,ranges=autoNorm(trianingMat)

testMat,testLabel=file2Mat(testFileName,3)

testSize=testMat.shape[0]

errorCount=0.0

foriinrange(testSize):

result=classify((testMat[i]-minVals)/ranges,trianingMat,classLabel,3)

if(result!=testLabel[i]):

errorCount+=1.0

errorRate=errorCount/(float)(len(testLabel))

returnerrorRate;⑤使用KNN算法进展预测如果第四步中的错误率在课承受*围内，表示可以利用此数据源进展预测。输入前三项属性之后较为准确的预测了分类。代码如下：defclassifyPerson():inputaperson,decidelikeornot,thenupdatetheDBresultlist=['notatall','littledoses','largedoses']percentTats=float(raw_input('inputtheperson\'percentageoftimeplayingvideogames:'))ffMiles=float(raw_input('fliermilesinayear:'))iceCream=float(raw_input('amountoficeCreamconsumedperyear:'))datingDataMat,datingLabels=file2matri*('datingTestSet.t*t')normMat,ranges,minVals=autoNorm(datingDataMat)normPerson=(array([ffMiles,percentTats,iceCream])-minVals)/rangesresult=classify0(normPerson,normMat,datingLabels,3)print'youwillprobablylikethisguyin:',result*resultlist[result-1]*updatethedatingTestSetprint'updatedatingDB'tmp='\t'.join([repr(ffMiles),repr(percentTats),repr(iceCream),repr(result)])+'\n'withopen('datingTestSet2.t*t','a')asfr:fr.write(tmp)四实验结果及分析本次实验结果截图如下：在终端输入pythonKNN.py命令开场执行KNN.py，分别得到了样本测试的错误率以及输入数据后KNN算法的预测结果：从实验结果来看，本数据集的一共检测的数据有200个，其中预测的和实际不相符的有16个，错误率为8%，在可承受*围之内。由于检测的数据集是随机选取的，因此该数据比较可信。当输入数据分别为900，40，80时，分类结果为didntlike，与数据集中给出的类似数据的分类一致。实验二分组实验一实验内容本次实验的实验内容为利用数据挖掘的聚类算法实现对DBLP合作者的数据挖掘。DBLP收录了国内外学者发表的绝大多数论文，其收录的论文按照文章类型等分类存储在DBLP.*ml文件中。通过聚类算法发现频繁项集就可以很好的开掘出有哪些作者经常在一起发表论文。二实验要求〔1〕完成对DBLP数据集的采集和预处理，能从中提取出作者以及合作者的**〔2〕利用聚类算法完成对合作者的挖掘〔3〕实验报告三实验步骤〔1〕从DBLP数据集中提取作者信息首先从官网下载DBLP数据集dblp.*ml.gz

解压后得到dblp.*ml文件。用vim翻开dblp.*ml发现所有的作者信息分布在以下这些属性中：'article','inproceedings','proceedings','book','incollection','phdthesis','mastersthesis',''。在这里使用python自带的*ml分析器解析该文件。代码如下：〔其核心思想为，分析器在进入上面那些属性中的*一个时，标记flag=1，然后将author属性的内容输出到文件，退出时再标记flag

=

0,最后得到authors.t*t

文件〕‘’’Getauthor.pyimportcodecsfrom*ml.sa*importhandler,make_parserpaper_tag=('article','inproceedings','proceedings','book','incollection','phdthesis','mastersthesis','')classmHandler(handler.ContentHandler):def__init__(self,result):self.result=resultself.flag=0defstartDocument(self):print'DocumentStart'defendDocument(self):print'DocumentEnd'defstartElement(self,name,attrs):ifname=='author':self.flag=1defendElement(self,name):ifname=='author':self.result.write(',')self.flag=0if(nameinpaper_tag):self.result.write('\r\n')defcharacters(self,chrs):ifself.flag:self.result.write(chrs)defparserDblp*ml(source,result):handler=mHandler(result)parser=make_parser()parser.setContentHandler(handler)parser.parse(source)if__name__=='__main__':source=codecs.open('dblp.*ml','r','utf-8')result=codecs.open('authors.t*t','w','utf-8')parserDblp*ml(source,result)result.close()source.close()〔2〕建立索引作者ID读取步骤1中得到的authors.t*t文件，将其中不同的人名按照人名出现的次序编码，存储到文件authors_inde*.t*t中，同时将编码后的合作者列表写入authors_encoded.t*t文件。代码如下：‘’’encoded.pyimportcodecssource=codecs.open('authors.t*t','r','utf-8')result=codecs.open('authors_encoded.t*t','w','utf-8')inde*=codecs.open('authors_inde*.t*t','w','utf-8')inde*_dic={}name_id=0**buildaninde*_dic,key->authorNamevalue=>[id,count]forlineinsource:name_list=line.split(',')fornameinname_list:ifnot(name=='\r\n'):ifnameininde*_dic:inde*_dic[name][1]+=1else:inde*_dic[name]=[name_id,1]inde*.write(name+u'\r\n')name_id+=1result.write(str(inde*_dic[name][0])+u',')result.write('\r\n')source.close()result.close()inde*.close()〔3〕构建FP-Tree并得到频繁项集FP-Tree算法的原理在这里不展开讲了，其核心思想分为2步，首先扫描数据库得到FP-Tree,然后再从树上递归生成条件模式树并上溯找到频繁项集。代码如下：defcreateTree(dataSet,minSup=1):*createFP-treefromdatasetbutdon'tminefreqDic={}*gooverdataSettwicefortransindataSet:*firstpasscountsfrequencyofoccuranceforitemintrans:freqDic[item]=freqDic.get(item,0)+dataSet[trans]headerTable={k:vfor(k,v)infreqDic.iteritems()ifv>=minSup}iflen(headerTable)==0:returnNone,None*ifnoitemsmeetminsupport-->getoutforkinheaderTable:headerTable[k]=[headerTable[k],None]*reformatheaderTabletouseNodelink*print'headerTable:',headerTableretTree=treeNode('NullSet',1,None)*createtreefortranSet,countindataSet.items():*gothroughdataset2ndtimelocalD={}foritemintranSet:*puttransactionitemsinorderifheaderTable.get(item,0):localD[item]=headerTable[item][0]iflen(localD)>0:orderedItems=[v[0]forvinsorted(localD.items(),key=lambdap:p[1],reverse=True)]updateTree(orderedItems,retTree,headerTable,count)*populatetreewithorderedfreqitemsetreturnretTree,headerTable*returntreeandheadertabledefupdateTree(items,inTree,headerTable,count):ifitems[0]ininTree.children:*checkiforderedItems[0]inretTree.childreninTree.children[items[0]].inc(count)*incramentcountelse:*additems[0]toinTree.childreninTree.children[items[0]]=treeNode(items[0],count,inTree)ifheaderTable[items[0]][1]==None:*updateheadertableheaderTable[items[0]][1]=inTree.children[items[0]]else:updateHeader(headerTable[items[0]][1],inTree.children[items[0]])iflen(items)>1:*callupdateTree()withremainingordereditemsupdateTree(items[1::],inTree.children[items[0]],headerTable,count)defupdateHeader(nodeToTest,targetNode):*thisversiondoesnotuserecursionwhile(nodeToTest.nodeLink!=None):*Donotuserecursiontotraversealinkedlist!nodeToTest=nodeToTest.nodeLinknodeToTest.nodeLink=targetNodedefmineTree(inTree,headerTable,minSup,preFi*,freqItemList):bigL=[v[0]forvinsorted(headerTable.items(),key=lambdap:p[1])]*(sortheadertable)forbasePatinbigL:*startfrombottomofheadertablenewFreqSet=preFi*.copy()newFreqSet.add(basePat)*print'finalFrequentItem:',newFreqSet*appendtosetiflen(newFreqSet)>1:freqItemList[frozenset(newFreqSet)]=headerTable[basePat][0]condPattBases=findPrefi*Path(basePat,headerTable[basePat][1])myCondTree,myHead=createTree(condPattBases,minSup)*print'headfromconditionaltree:',myHeadifmyHead!=None:*3.minecond.FP-tree*print'conditionaltreefor:',newFreqSet*myCondTree.disp(1)mineTree(myCondTree,myHead,minSup,newFreqSet,freqItemList)四实验结果及分析在选取频繁度为40后发现，得到的结果非常多，总共2000多，为了分析的方便，进一步提高频繁度阈值为100，此时得到了111条记录，按照合作者的共同支持度排序，局部截图如下：统计满足支持度条件的合作者个数可以发现，经常一起合作的作者数目最多为3，故在输出文件中输出了authorA，authorB，authorC〔当合作者数目为2时，authorC为空，其对应支持度和置信度为0〕，Sup〔A,B,C〕为A,B,C共同合作的次数，Sup〔A〕Sup〔B〕Sup〔C〕分别为A,B,C各自的写作次数，Con〔A〕、Con〔B〕、Con〔C〕分别表示A,B,C的置信度〔即合作次数除以写作总次数〕MinCon和Ma*Con分别统计Con〔A〕、Con〔B〕、Con〔C〕的最小值和最大值〔注意，当authorC为空时，其对应的置信度不参加最大最小值的统计〕。从结果中可以看出，经常在一起发表论文的大多数是两个人，少数是三个人。合作者之间的关系是双向性的，也就是说，A与B的合作程度与B与A合作的程度是一致的，因此可以直接考虑置信度。如果A和B之间的置信度相差较大有可能存在误差，即A和B合作发表论文对B来说是偶然的对A来说是经常的。实验三聚类实验一实验内容本实验研究如何评估K-means聚类算法中的最优K值，主要理论依据是?数据挖掘导论?介绍的SSE和SilhouetteCoefficient系数的方法评估最优K。实验步骤概述：〔1〕实现K-means聚类算法〔2〕K值优化：取k值*围，计算出SSE，并绘制出曲线图，观察规律。取步骤2同样的*围，计算出SilhouetteCoefficient，并绘制出曲线图，观察规律。根据步骤2，3观察的规律，评估出最优K值，验证最优聚类。〔3〕采用K-means++算法，设置同样K值，比照聚类效果二实验要求〔1〕独立完成聚类实验，根本实现最优聚簇〔2〕实验报告三实验步骤〔1〕Kmeans算法原理①从D中随机取k个元素，作为k个簇的各自的中心。②分别计算剩下的元素到k个簇中心的相异度，将这些元素分别划归到相异度最低的簇。③根据聚类结果，重新计算K各簇各自的中心，计算方法是取各自簇所有元素各维的平均数④将D中所有元素按照新的中心重新聚类⑤重复第四步，知道结果不再发生变化将结果输出〔2〕Kmeans算法实现首先将要进展分类的数据源预处理，将其中的数据写入到矩阵中，具体代码如下：deffile2matri*(filename):fr=open(filename)fr.readline()*Readthefirstlinelines=fr.readlines()data=[]forlineinlines:numlist=[int(i)foriinline.split('\t')]data.append(numlist[1:])returndata然后，将得到的数据进展Kmeans聚类，代码如下：defkmeans(data,mincluster,ma*cluster):*=[]ssey=[]scy=[]datarandom=data[:]fresult=open(resultfile1,'wb')foriinrange(mincluster,ma*cluster+1):print"\nk=%d"%issetempold=0ssetemp=0numgroupold=[]*.append(i)fresult.write(str(i)+':\n')*Writetothefileforkinrange(0,kcount): *random.shuffle(datarandom)*group=[]numgroup=[]forjinrange(0,i):g=[]group.append(g)g=[]numgroup.append(g)ssetemp=cal(data,datarandom[0:i],group,numgroup)if(k==0):ssetempold=ssetempnumgroupold=numgroupelif(ssetempold>ssetemp):ssetempold=ssetempnumgroupold=numgroupprint"-",*Writetothefile*count=0forgroupmemberinnumgroupold:count+=1fresult.write("\n")fresult.write("-"*500)fresult.write("\nGroup-%d(%d)"%(count,len(groupmember)))fornumingroupmember:fresult.write("%s"%str(num))fresult.write("\n")fresult.write("-"*500)fresult.write("\n")fresult.write("\n")ssey.append(ssetempold)*Calculatesilhouettecoefficientforiinrange(0,len(numgroupold)):s=[]forjinrange(0,len(numgroupold[i])):temp=[]forkinrange(0,len(numgroupold)):temp.append(caldistancefromarray(numgroupold[i][j],numgroupold[k]))a=temp[i]/len(numgroupold[i])sorted=tile(temp,1).argsort()if(sorted[0]==i):d=1else:d=0while(d<len(sorted)):if(temp[sorted[d]]>0):b=temp[sorted[d]]/len(numgroupold[sorted[d]])breakelse:d+=1if(d==len(sorted)):s.append(0)continuec=(b-a)/ma*(a,b)*print"size1=%di=%dj=%dsorted[0]=%dsorted[1]=%da=%sb=%sc=%s"%(len(numgroup[i]),i,j,sorted[0],sorted[1],str(a),str(b),str(c))s.append(c)scy.append(tile(s,1).sum(a*is=0)/len(s))fresult.close()plt.subplot(211)plt.plot(*,ssey)plt.ylabel('SSE')*plt.show()plt.subplot(212)plt.ylabel('SC')plt.*label('k')plt.plot(*,scy)plt.show()〔3〕Kmeans++算法原理k-means++算法选择初始seeds的根本思想就是：初始的聚类中心之间的相互距离要尽可能的远。具体步骤如下：从输入的数据点集合中随机选择一个点作为第一个聚类中心对于数据集中的每一个点*，计算它与最近聚类中心(指已选择的聚类中心)的距离D(*)选择一个新的数据点作为新的聚类中心，选择的原则是：D(*)较大的点，被选取作为聚类中心的概率较大重复2和3直到k个聚类中心被选出来利用这k个初始的聚类中心来运行标准的k-means算法〔4〕Kmeans++算法实现代码如下：defkmeansplus(data,mincluster,ma*cluster): *=[] ssey=[] scy=[] fresult=open(resultfile2,'wb') foriinrange(mincluster,ma*cluster+1): print"\nk=%d"%i ssetempold=0 ssetemp=0 numgroupold=[] *.append(i) fresult.write(str(i)+':\n') group=[] numgroup=[] masslist=getmasslist(data,i) forjinrange(0,