數(shù)據(jù)挖掘及實驗報告

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

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

解壓后得到dblp.*ml文件。用vim翻開dblp.*ml發(fā)現(xiàn)所有的作者信息分布在以下這些屬性中：'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文件，將其中不同的人名按照人名出現(xiàn)的次序編碼，存儲到文件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步，首先掃描數(shù)據(jù)庫得到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后發(fā)現(xiàn)，得到的結果非常多，總共2000多，為了分析的方便，進一步提高頻繁度閾值為100，此時得到了111條記錄，按照合作者的共同支持度排序，局部截圖如下：統(tǒng)計滿足支持度條件的合作者個數(shù)可以發(fā)現(xiàn)，經(jīng)常一起合作的作者數(shù)目最多為3，故在輸出文件中輸出了authorA，authorB，authorC〔當合作者數(shù)目為2時，authorC為空，其對應支持度和置信度為0〕，Sup〔A,B,C〕為A,B,C共同合作的次數(shù)，Sup〔A〕Sup〔B〕Sup〔C〕分別為A,B,C各自的寫作次數(shù)，Con〔A〕、Con〔B〕、Con〔C〕分別表示A,B,C的置信度〔即合作次數(shù)除以寫作總次數(shù)〕MinCon和Ma*Con分別統(tǒng)計Con〔A〕、Con〔B〕、Con〔C〕的最小值和最大值〔注意，當authorC為空時，其對應的置信度不參加最大最小值的統(tǒng)計〕。從結果中可以看出，經(jīng)常在一起發(fā)表論文的大多數(shù)是兩個人，少數(shù)是三個人。合作者之間的關系是雙向性的，也就是說，A與B的合作程度與B與A合作的程度是一致的，因此可以直接考慮置信度。如果A和B之間的置信度相差較大有可能存在誤差，即A和B合作發(fā)表論文對B來說是偶然的對A來說是經(jīng)常的。實驗三聚類實驗一實驗內容本實驗研究如何評估K-means聚類算法中的最優(yōu)K值，主要理論依據(jù)是?數(shù)據(jù)挖掘導論?介紹的SSE和SilhouetteCoefficient系數(shù)的方法評估最優(yōu)K。實驗步驟概述：〔1〕實現(xiàn)K-means聚類算法〔2〕K值優(yōu)化：取k值*圍，計算出SSE，并繪制出曲線圖，觀察規(guī)律。取步驟2同樣的*圍，計算出SilhouetteCoefficient，并繪制出曲線圖，觀察規(guī)律。根據(jù)步驟2，3觀察的規(guī)律，評估出最優(yōu)K值，驗證最優(yōu)聚類?！?〕采用K-means++算法，設置同樣K值，比照聚類效果二實驗要求〔1〕獨立完成聚類實驗，根本實現(xiàn)最優(yōu)聚簇〔2〕實驗報告三實驗步驟〔1〕Kmeans算法原理①從D中隨機取k個元素，作為k個簇的各自的中心。②分別計算剩下的元素到k個簇中心的相異度，將這些元素分別劃歸到相異度最低的簇。③根據(jù)聚類結果，重新計算K各簇各自的中心，計算方法是取各自簇所有元素各維的平均數(shù)④將D中所有元素按照新的中心重新聚類⑤重復第四步，知道結果不再發(fā)生變化將結果輸出〔2〕Kmeans算法實現(xiàn)首先將要進展分類的數(shù)據(jù)源預處理，將其中的數(shù)據(jù)寫入到矩陣中，具體代碼如下：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ù)進展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的根本思想就是：初始的聚類中心之間的相互距離要盡可能的遠。具體步驟如下：從輸入的數(shù)據(jù)點集合中隨機選擇一個點作為第一個聚類中心對于數(shù)據(jù)集中的每一個點*，計算它與最近聚類中心(指已選擇的聚類中心)的距離D(*)選擇一個新的數(shù)據(jù)點作為新的聚類中心，選擇的原則是：D(*)較大的點，被選取作為聚類中心的概率較大重復2和3直到k個聚類中心被選出來利用這k個初始的聚類中心來運行標準的k-means算法〔4〕Kmeans++算法實現(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,