數(shù)據(jù)挖掘及實(shí)驗(yàn)報(bào)告

-.z中科大數(shù)據(jù)挖掘?qū)嶒?yàn)報(bào)告**樊濤聲班級(jí)軟設(shè)一班**SA15226248實(shí)驗(yàn)一K鄰近算法實(shí)驗(yàn)一實(shí)驗(yàn)內(nèi)容使用k近鄰算法改進(jìn)約會(huì)的配對(duì)效果。海倫使用約會(huì)網(wǎng)址尋找適合自己的約會(huì)對(duì)象，約會(huì)會(huì)推薦不同的人選。她將曾經(jīng)交往過(guò)的的人總結(jié)為三種類(lèi)型：不喜歡的人魅力一般的人極具魅力的人盡管發(fā)現(xiàn)了這些規(guī)律，但依然無(wú)法將約會(huì)提供的人歸入恰當(dāng)?shù)姆诸?lèi)。使用KNN算法，更好的幫助她將匹配對(duì)象劃分到確切的分類(lèi)中。二實(shí)驗(yàn)要求〔1〕獨(dú)立完成kNN實(shí)驗(yàn)，根本實(shí)現(xiàn)可預(yù)測(cè)的效果〔2〕實(shí)驗(yàn)報(bào)告〔3〕開(kāi)放性：可以自己增加數(shù)據(jù)或修改算法，實(shí)現(xiàn)更好的分類(lèi)效果三實(shí)驗(yàn)步驟〔1〕數(shù)據(jù)源說(shuō)明實(shí)驗(yàn)給出的數(shù)據(jù)源為datingTestSet.t*t，共有4列，每一列的屬性分別為：①percentageoftimespentingplayingvediogames；②frequentfliedmilesearnedperyear；③litersoficecreamconsumedperyear；④yourattitudetowarsthispeople。通過(guò)分析數(shù)據(jù)源中的數(shù)據(jù)，得到規(guī)律，從而判斷一個(gè)人的前三項(xiàng)屬性來(lái)得出劃分海倫對(duì)他的態(tài)度?！?〕KNN算法原理對(duì)未知屬性的*數(shù)據(jù)集中的每個(gè)點(diǎn)一次執(zhí)行以下操作計(jì)算類(lèi)別數(shù)據(jù)集中的每一個(gè)點(diǎn)和當(dāng)前點(diǎn)的距離按照距離遞增依次排序選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)確定k個(gè)點(diǎn)所在類(lèi)別的出現(xiàn)頻率返回k個(gè)點(diǎn)出現(xiàn)頻率最高的點(diǎn)作為當(dāng)前點(diǎn)的分類(lèi)〔3〕KNN算法實(shí)現(xiàn)①利用python實(shí)現(xiàn)構(gòu)造分類(lèi)器首先計(jì)算歐式距離然后選取距離最小的K個(gè)點(diǎn)代碼如下：defclassify(inMat,dataSet,labels,k):

dataSetSize=dataSet.shape[0]

*KNN的算法核心就是歐式距離的計(jì)算，一下三行是計(jì)算待分類(lèi)的點(diǎn)和訓(xùn)練集中的任一點(diǎn)的歐式距離diffMat=tile(inMat,(dataSetSize,1))-dataSet

sqDiffMat=diffMat**2

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

*接下來(lái)是一些統(tǒng)計(jì)工作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]②解析數(shù)據(jù)輸入文件名，將文件中的數(shù)據(jù)轉(zhuǎn)化為樣本矩陣，方便處理代碼如下：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;返回值為前三列屬性被寫(xiě)入到resultMat二維數(shù)組中，第四列屬性作為標(biāo)簽寫(xiě)入到classLableVector中③歸一化數(shù)據(jù)不同評(píng)價(jià)指標(biāo)往往具有不同的量綱和量綱單位，這樣的情況會(huì)影響到數(shù)據(jù)分析的結(jié)果，為了消除指標(biāo)之間的量綱影響，需要進(jìn)展數(shù)據(jù)標(biāo)準(zhǔn)化處理，使各指標(biāo)處于同一數(shù)量級(jí)。處理過(guò)程如下：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④測(cè)試數(shù)據(jù)在利用KNN算法預(yù)測(cè)之前，通常只提供已有數(shù)據(jù)的90%作為訓(xùn)練樣本，使用其余的10%數(shù)據(jù)去測(cè)試分類(lèi)器。注意10%測(cè)試數(shù)據(jù)是隨機(jī)選擇的，采用錯(cuò)誤率來(lái)檢測(cè)分類(lèi)器的性能。錯(cuò)誤率太高說(shuō)明數(shù)據(jù)源出現(xiàn)問(wèn)題，此時(shí)需要重新考慮數(shù)據(jù)源的合理性。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算法進(jìn)展預(yù)測(cè)如果第四步中的錯(cuò)誤率在課承受*圍內(nèi)，表示可以利用此數(shù)據(jù)源進(jìn)展預(yù)測(cè)。輸入前三項(xiàng)屬性之后較為準(zhǔn)確的預(yù)測(cè)了分類(lèi)。代碼如下：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)四實(shí)驗(yàn)結(jié)果及分析本次實(shí)驗(yàn)結(jié)果截圖如下：在終端輸入pythonKNN.py命令開(kāi)場(chǎng)執(zhí)行KNN.py，分別得到了樣本測(cè)試的錯(cuò)誤率以及輸入數(shù)據(jù)后KNN算法的預(yù)測(cè)結(jié)果：從實(shí)驗(yàn)結(jié)果來(lái)看，本數(shù)據(jù)集的一共檢測(cè)的數(shù)據(jù)有200個(gè)，其中預(yù)測(cè)的和實(shí)際不相符的有16個(gè)，錯(cuò)誤率為8%，在可承受*圍之內(nèi)。由于檢測(cè)的數(shù)據(jù)集是隨機(jī)選取的，因此該數(shù)據(jù)比較可信。當(dāng)輸入數(shù)據(jù)分別為900，40，80時(shí)，分類(lèi)結(jié)果為didntlike，與數(shù)據(jù)集中給出的類(lèi)似數(shù)據(jù)的分類(lèi)一致。實(shí)驗(yàn)二分組實(shí)驗(yàn)一實(shí)驗(yàn)內(nèi)容本次實(shí)驗(yàn)的實(shí)驗(yàn)內(nèi)容為利用數(shù)據(jù)挖掘的聚類(lèi)算法實(shí)現(xiàn)對(duì)DBLP合作者的數(shù)據(jù)挖掘。DBLP收錄了國(guó)內(nèi)外學(xué)者發(fā)表的絕大多數(shù)論文，其收錄的論文按照文章類(lèi)型等分類(lèi)存儲(chǔ)在DBLP.*ml文件中。通過(guò)聚類(lèi)算法發(fā)現(xiàn)頻繁項(xiàng)集就可以很好的開(kāi)掘出有哪些作者經(jīng)常在一起發(fā)表論文。二實(shí)驗(yàn)要求〔1〕完成對(duì)DBLP數(shù)據(jù)集的采集和預(yù)處理，能從中提取出作者以及合作者的**〔2〕利用聚類(lèi)算法完成對(duì)合作者的挖掘〔3〕實(shí)驗(yàn)報(bào)告三實(shí)驗(yàn)步驟〔1〕從DBLP數(shù)據(jù)集中提取作者信息首先從官網(wǎng)下載DBLP數(shù)據(jù)集dblp.*ml.gz

解壓后得到dblp.*ml文件。用vim翻開(kāi)dblp.*ml發(fā)現(xiàn)所有的作者信息分布在以下這些屬性中：'article','inproceedings','proceedings','book','incollection','phdthesis','mastersthesis',''。在這里使用python自帶的*ml分析器解析該文件。代碼如下：〔其核心思想為，分析器在進(jìn)入上面那些屬性中的*一個(gè)時(shí)，標(biāo)記flag=1，然后將author屬性的內(nèi)容輸出到文件，退出時(shí)再標(biāo)記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文件，將其中不同的人名按照人名出現(xiàn)的次序編碼，存儲(chǔ)到文件authors_inde*.t*t中，同時(shí)將編碼后的合作者列表寫(xiě)入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〕構(gòu)建FP-Tree并得到頻繁項(xiàng)集FP-Tree算法的原理在這里不展開(kāi)講了，其核心思想分為2步，首先掃描數(shù)據(jù)庫(kù)得到FP-Tree,然后再?gòu)臉?shù)上遞歸生成條件模式樹(shù)并上溯找到頻繁項(xiàng)集。代碼如下：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)四實(shí)驗(yàn)結(jié)果及分析在選取頻繁度為40后發(fā)現(xiàn)，得到的結(jié)果非常多，總共2000多，為了分析的方便，進(jìn)一步提高頻繁度閾值為100，此時(shí)得到了111條記錄，按照合作者的共同支持度排序，局部截圖如下：統(tǒng)計(jì)滿(mǎn)足支持度條件的合作者個(gè)數(shù)可以發(fā)現(xiàn)，經(jīng)常一起合作的作者數(shù)目最多為3，故在輸出文件中輸出了authorA，authorB，authorC〔當(dāng)合作者數(shù)目為2時(shí)，authorC為空，其對(duì)應(yīng)支持度和置信度為0〕，Sup〔A,B,C〕為A,B,C共同合作的次數(shù)，Sup〔A〕Sup〔B〕Sup〔C〕分別為A,B,C各自的寫(xiě)作次數(shù)，Con〔A〕、Con〔B〕、Con〔C〕分別表示A,B,C的置信度〔即合作次數(shù)除以寫(xiě)作總次數(shù)〕MinCon和Ma*Con分別統(tǒng)計(jì)Con〔A〕、Con〔B〕、Con〔C〕的最小值和最大值〔注意，當(dāng)authorC為空時(shí)，其對(duì)應(yīng)的置信度不參加最大最小值的統(tǒng)計(jì)〕。從結(jié)果中可以看出，經(jīng)常在一起發(fā)表論文的大多數(shù)是兩個(gè)人，少數(shù)是三個(gè)人。合作者之間的關(guān)系是雙向性的，也就是說(shuō)，A與B的合作程度與B與A合作的程度是一致的，因此可以直接考慮置信度。如果A和B之間的置信度相差較大有可能存在誤差，即A和B合作發(fā)表論文對(duì)B來(lái)說(shuō)是偶然的對(duì)A來(lái)說(shuō)是經(jīng)常的。實(shí)驗(yàn)三聚類(lèi)實(shí)驗(yàn)一實(shí)驗(yàn)內(nèi)容本實(shí)驗(yàn)研究如何評(píng)估K-means聚類(lèi)算法中的最優(yōu)K值，主要理論依據(jù)是?數(shù)據(jù)挖掘?qū)д?介紹的SSE和SilhouetteCoefficient系數(shù)的方法評(píng)估最優(yōu)K。實(shí)驗(yàn)步驟概述：〔1〕實(shí)現(xiàn)K-means聚類(lèi)算法〔2〕K值優(yōu)化：取k值*圍，計(jì)算出SSE，并繪制出曲線圖，觀察規(guī)律。取步驟2同樣的*圍，計(jì)算出SilhouetteCoefficient，并繪制出曲線圖，觀察規(guī)律。根據(jù)步驟2，3觀察的規(guī)律，評(píng)估出最優(yōu)K值，驗(yàn)證最優(yōu)聚類(lèi)。〔3〕采用K-means++算法，設(shè)置同樣K值，比照聚類(lèi)效果二實(shí)驗(yàn)要求〔1〕獨(dú)立完成聚類(lèi)實(shí)驗(yàn)，根本實(shí)現(xiàn)最優(yōu)聚簇〔2〕實(shí)驗(yàn)報(bào)告三實(shí)驗(yàn)步驟〔1〕Kmeans算法原理①?gòu)腄中隨機(jī)取k個(gè)元素，作為k個(gè)簇的各自的中心。②分別計(jì)算剩下的元素到k個(gè)簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。③根據(jù)聚類(lèi)結(jié)果，重新計(jì)算K各簇各自的中心，計(jì)算方法是取各自簇所有元素各維的平均數(shù)④將D中所有元素按照新的中心重新聚類(lèi)⑤重復(fù)第四步，知道結(jié)果不再發(fā)生變化將結(jié)果輸出〔2〕Kmeans算法實(shí)現(xiàn)首先將要進(jìn)展分類(lèi)的數(shù)據(jù)源預(yù)處理，將其中的數(shù)據(jù)寫(xiě)入到矩陣中，具體代碼如下：deffile2matri*(filename):fr=open(filename)fr.readline()*Readthefirstlinelines=fr.readlines()data=[]forlineinlines:numlist=[int(i)foriinline.split('\t')]data.append(numlist[1:])returndata然后，將得到的數(shù)據(jù)進(jìn)展Kmeans聚類(lèi)，代碼如下：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的根本思想就是：初始的聚類(lèi)中心之間的相互距離要盡可能的遠(yuǎn)。具體步驟如下：從輸入的數(shù)據(jù)點(diǎn)集合中隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)聚類(lèi)中心對(duì)于數(shù)據(jù)集中的每一個(gè)點(diǎn)*，計(jì)算它與最近聚類(lèi)中心(指已選擇的聚類(lèi)中心)的距離D(*)選擇一個(gè)新的數(shù)據(jù)點(diǎn)作為新的聚類(lèi)中心，選擇的原則是：D(*)較大的點(diǎn)，被選取作為聚類(lèi)中心的概率較大重復(fù)2和3直到k個(gè)聚類(lèi)中心被選出來(lái)利用這k個(gè)初始的聚類(lèi)中心來(lái)運(yùn)行標(biāo)準(zhǔn)的k-means算法〔4〕Kmeans++算法實(shí)現(xiàn)代碼如下：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,