《数据挖掘实验地报告材料.doc》由会员分享，可在线阅读，更多相关《数据挖掘实验地报告材料.doc（23页珍藏版）》请在课桌文档上搜索。
1、实验一 K邻近算法实验一 实验内容使用k近邻算法改良约会的配对效果。海伦使用约会寻找适合自己的约会对象，约会会推荐不 同的人选。她将曾经交往过的的人总结为三种类型：（1） 不喜欢的人（2） 魅力一般的人（3） 极具魅力的人尽管发现了规律，但依然无法将约会提供的人归入恰当的分类。使用KNN算法，更好的帮助她将匹配对 象划分到确切的分类中。二 实验要求 1 独立完成kNN实验，根本实现可的效果2 实验报告3 开放性：可以自己增加数据或修改算法，实 现更好的分类效果三 实验步骤1数据源说明实验给出的数据源为datingTestSet.txt，共有4列，每一列的属性分别为： percentage of
2、 time spenting playing vedio games； frequent flied miles earned per year； liters of ice cream consumed per year； your attitude towars this people。通过分析数据源中的数据，得到规律，从而判断一个人的前三项属性来得出划分海伦对他的态度。2KNN算法原理对未知属性的某数据集中的每个点一次执行以下操作 计算类别数据集中的每一个点和当前点的距离 按照距离递增依次排序 选取与当前点距离最小的k个点 确定k个点所在类别的出现频率 返回k个点出现频率最高的点作为当前
3、点的分类3KNN算法实现 利用python实现构造分类器首先计算欧式距离然后选取距离最小的K个点代码如下：def classify(inMat,dataSet,labels,k):dataSetSize=dataSet.shape0#KNN的算法核心就是欧式距离的计算，一下三行是计算待分类的点和训练集中的任一点的欧式距离diffMat=tile(inMat,(dataSetSize,1)-dataSetsqDiffMat=diffMat*2distance=sqDiffMat.sum(axis=1)*0.5#接下来是一些统计工作sortedDistIndicies=distance.argso
4、rt()classCount=for i in range(k):labelName=labelssortedDistIndiciesiclassCountlabelName=classCount.get(labelName,0)+1;sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)return sortedClassCount00 解析数据输入文件名，将文件中的数据转化为样本矩阵，方便处理代码如下：def file2Mat(testFileName,parammterNumb
5、er):fr=open(testFileName)lines=fr.readlines()lineNums=len(lines)resultMat=zeros(lineNums,parammterNumber)classLabelVector=for i in range(lineNums):line=linesi.strip()itemMat=line.split(t)resultMati,:=itemMat0:parammterNumberclassLabelVector.append(itemMat-1)fr.close()return resultMat,classLabelVecto
6、r;返回值为前三列属性被写入到resultMat二维数组中，第四列属性作为标签写入到classLableVector中 归一化数据不同评价指标往往具有不同的量纲和量纲单位，这样的情况会影 响到数据分析的结果，为了消除指标之间的量纲影响，需要进展 数据标准化处理，使各指标处于同一数量级。处理过程如下：def autoNorm(dataSet):minVals=dataSet.min(0)maxVals=dataSet.max(0)ranges=maxVals-minValsnormMat=zeros(shape(dataSet)size=normMat.shape0normMat=dataSet
7、-tile(minVals,(size,1)normMat=normMat/tile(ranges,(size,1)return normMat,minVals,ranges 测试数据在利用KNN算法之前，通常只提供已有数据的90%作为训练样本，使用其余的10%数据去测试分类器。注意10%测试数据是随机选择的，采用错误率来检测分类器的性能。错误率太高说明数据源出现问题，此时需要重新考虑数据源的合理性。def test(trainigSetFileName,testFileName):trianingMat,classLabel=file2Mat(trainigSetFileName,3)tri
8、aningMat,minVals,ranges=autoNorm(trianingMat)testMat,testLabel=file2Mat(testFileName,3)testSize=testMat.shape0errorCount=0.0for i in range(testSize):result=classify(testMati-minVals)/ranges,trianingMat,classLabel,3)if(result!=testLabeli):errorCount+=1.0errorRate=errorCount/(float)(len(testLabel)retu
9、rn errorRate; 使用KNN算法进展如果第四步中的错误率在课承受X围内，表示可以利用此数据源进展。输入前三项属性之后较为准确的了分类。代码如下：def classifyPerson(): input a person , decide like or not, then update the DB resultlist = not at all,little doses,large doses percentTats = float(raw_input(input the person percentage of time playing video games:) ffMiles
10、= float(raw_input(flier miles in a year:) iceCream = float(raw_input(amount of iceCream consumed per year:) datingDataMat,datingLabels = file2matrix(datingTestSet.txt) normMat, ranges, minVals = autoNorm(datingDataMat) normPerson = (array(ffMiles,percentTats,iceCream)-minVals)/ranges result = classi
11、fy0(normPerson, normMat, datingLabels, 3) print you will probably like this guy in: ,result#resultlistresult -1 #update the datingTestSet print update dating DB tmp = t.join(repr(ffMiles),repr(percentTats),repr(iceCream),repr(result)+n with open(datingTestSet2.txt,a) as fr: fr.write(tmp)四 实验结果与分析本次实
12、验结果截图如下：从实验结果来看，本数据集的一共检测的数据有200个，其中的和实际不相符的有16个，错误率为8%，在可承受X围之内。由于检测的数据集是随机选取的，因此该数据比拟可信。当输入数据分别为900，40，80时，分类结果为didntlike，与数据集中给出的类似数据的分类一致。实验二 分组实验一 实验内容本次实验的实验内容为利用数据挖掘的聚类算法实现对DBLP合作者的数据挖掘。DBLP收录了国内外学者发表的绝大多数论文，其收录的论文按照文章类型等分类存储在DBLP.xml文件中。通过聚类算法发现频繁项集就可以很好的开掘出有哪些作者经常在一起发表论文。二实验要求1 完成对DBLP数据集的采
13、集和预处理，能从中提取出作者以与合作者的某某2 利用聚类算法完成对合作者的挖掘3 实验报告三 实验步骤1 从DBLP数据集中提取作者信息解压后得到dblp.xml文件。用vim打开dblp.xml发现所有的作者信息分布在以下属性中：article,inproceedings,proceedings,book,incollection,phdthesis,mastersthesis,。在这里使用python自带的xml分析器解析该文件。代码如下：其核心思想为，分析器在进入上面那些属性中的某一个时，标记flag=1，然后将author属性的内容输出到文件，退出时再标记flag=0,最后得到auth
14、ors.txt文件Getauthor.pyimport codecs from xml.sax import handler, make_parser paper_tag = (article,inproceedings,proceedings,book, incollection,phdthesis,mastersthesis,) class mHandler(handler.ContentHandler): def _init_(self,result): self.result = result self.flag = 0 def startDocument(self): print D
15、ocument Start def endDocument(self): print Document End def startElement(self, name, attrs): if name = author: self.flag = 1 def endElement(self, name): if name = author: self.flag = 0 if (name in paper_tag) : def characters(self, chrs): if self.flag: def parserDblpXml(source,result): handler = mHan
16、dler(result) parser = make_parser() parser.setContentHandler(handler) parser.parse(source) if _name_ = _main_: source = codecs.open(dblp.xml,r,utf-8) result = codecs.open(authors.txt,w,utf-8) parserDblpXml(source,result) result.close() source.close()2 建立索引作者ID读取步骤1中得到的authors.txt文件，将其中不同的人名按照人名出现的次序
17、编码，存储到文件authors_index.txt中，同时将编码后的合作者列表写入authors_encoded.txt文件。代码如下：encoded.pyimport codecs source = codecs.open(authors.txt,r,utf-8) result = codecs.open(authors_encoded.txt,w,utf-8) index = codecs.open(authors_index.txt,w,utf-8) index_dic = name_id = 0 # build an index_dic, key - authorName value
18、= id, count for line in source: name_list = line.split(,) for name in name_list: if not (name = rn): if name in index_dic: index_dicname1 +=1 else: index_dicname = name_id,1 index.write(name + urn) name_id += 1 result.write(str(index_dicname0) + u,) result.write(rn) source.close() result.close() ind
19、ex.close()3 构建FP-Tree并得到频繁项集FP-Tree算法的原理在这里不展开讲了，其核心思想分为2步，首先扫描数据库得到FP-Tree,然后再从树上递归生成条件模式树并上溯找到频繁项集。代码如下：def createTree(dataSet, minSup=1): #create FP-tree from dataset but dont mine freqDic = #go over dataSet twice for trans in dataSet:#first pass counts frequency of occurance for item in trans: f
20、reqDicitem = freqDic.get(item, 0) + dataSettrans headerTable = k:v for (k,v) in freqDic.iteritems() if v = minSup if len(headerTable) = 0: return None, None #if no items meet min support -get out for k in headerTable: headerTablek = headerTablek, None #reformat headerTable to use Node link #print he
21、aderTable: ,headerTable retTree = treeNode(Null Set, 1, None) #create tree for tranSet, count in dataSet.items(): #go through dataset 2nd time localD = for item in tranSet: #put transaction items in order if headerTable.get(item,0): localDitem = headerTableitem0 if len(localD) 0: orderedItems = v0 f
22、or v in sorted(localD.items(), key=lambda p: p1, reverse=True) updateTree(orderedItems, retTree, headerTable, count)#populate tree with ordered freq itemset return retTree, headerTable #return tree and header table def updateTree(items, inTree, headerTable, count): if items0 in inTree.children:#chec
23、k if orderedItems0 in retTree.children inTree.childrenitems0.inc(count) #incrament count else: #add items0 to inTree.children inTree.childrenitems0 = treeNode(items0, count, inTree) if headerTableitems01 = None: #update header table headerTableitems01 = inTree.childrenitems0 else: updateHeader(heade
24、rTableitems01, inTree.childrenitems0) if len(items) 1:#call updateTree() with remaining ordered items updateTree(items1:, inTree.childrenitems0, headerTable, count) def updateHeader(nodeToTest, targetNode): #this version does not use recursion while (nodeToTest.nodeLink != None): #Do not use recursi
25、on to traverse a linked list! nodeToTest = nodeToTest.nodeLink nodeToTest.nodeLink = targetNodedef mineTree(inTree, headerTable, minSup, preFix, freqItemList): bigL = v0 for v in sorted(headerTable.items(), key=lambda p: p1)#(sort header table) for basePat in bigL: #start from bottom of header table
26、 newFreqSet = preFix.copy() newFreqSet.add(basePat) #print finalFrequent Item: ,newFreqSet #append to set if len(newFreqSet) 1: freqItemListfrozenset(newFreqSet) = headerTablebasePat0 condPattBases = findPrefixPath(basePat, headerTablebasePat1) myCondTree, myHead = createTree(condPattBases, minSup)
27、#print head from conditional tree: , myHead if myHead != None: #3. mine cond. FP-tree #print conditional tree for: ,newFreqSet #myCondTree.disp(1) mineTree(myCondTree, myHead, minSup, newFreqSet, freqItemList)四 实验结果与分析在选取频繁度为40后发现，得到的结果非常多，总共2000多，为了分析的方便，进一步提高频繁度阈值为100，此时得到了111条记录，按照合作者的共同支持度排序，局部截
28、图如下：统计满足支持度条件的合作者个数可以发现，经常一起合作的作者数目最多为3，故在输出文件中输出了authorA，authorB，authorC当合作者数目为2时，authorC为空，其对应支持度和置信度为0，SupA,B,C为A,B,C共同合作的次数，SupASupBSupC分别为A,B,C各自的写作次数，ConA、ConB、ConC分别表示A,B,C的置信度即合作次数除以写作总次数MinCon和MaxCon分别统计ConA、ConB、ConC的最小值和最大值注意，当authorC为空时，其对应的置信度不参加最大最小值的统计。 从结果中可以看出，经常在一起发表论文的大多数是两个人，少数是三
29、个人。合作者之间的关系是双向性的，也就是说，A与B的合作程度与B与A合作的程度是一致的，因此可以直接考虑置信度。如果A和B之间的置信度相差较大有可能存在误差，即A和B合作发表论文对B来说是偶然的对A来说是经常的。实验三 聚类实验一 实验内容本实验研究如何评估K-means聚类算法中的最优K值，主要理论依据是数据挖掘导论介绍的SSE和Silhouette Coefficient系数的方法评估最优K。实验步骤概述：1 实现K-means聚类算法2 K值优化：取k值X围，计算出SSE，并绘制出曲线图，观察规律。取步骤2同样的X围，计算出Silhouette Coefficient，并绘制出曲线图，观
30、察规律。根据步骤2，3观察的规律，评估出最优K值，验证最优聚类。3 采用K-means+算法，设置同样K值，比照聚类效果二 实验要求1 独立完成聚类实验，根本实现最优聚簇2 实验报告三 实验步骤1 Kmeans算法原理 从D中随机取k个元素，作为k个簇的各自的中心。 分别计算剩下的元素到k个簇中心的相异度，将元素分别划归到相异度最低的簇。 根据聚类结果，重新计算K各簇各自的中心，计算方法是取各自簇所有元素各维的平均数 将D中所有元素按照新的中心重新聚类 重复第四步，知道结果不再发生变化 将结果输出2 Kmeans算法实现首先将要进展分类的数据源预处理，将其中的数据写入到矩阵中，具体代码如下：d
31、ef file2matrix(filename): fr = open(filename) fr.readline() # Read the first line lines = fr.readlines() data = for line in lines: numlist = int(i) for i in line.split(t) data.append(numlist1:) return data然后，将得到的数据进展Kmeans聚类，代码如下：def kmeans(data, mincluster, maxcluster): x = ssey = scy = datarandom
32、= data: fresult = open(resultfile1, wb) for i in range(mincluster, maxcluster + 1): print nk = %d % i ssetempold = 0 ssetemp = 0 numgroupold = x.append(i) fresult.write(str(i) + :n) # Write to the file for k in range(0, kcount):# random.shuffle(datarandom) # group = numgroup = for j in range(0, i):
33、g = group.append(g) g = numgroup.append(g) ssetemp = cal(data, datarandom0: i, group, numgroup) if(k = 0): ssetempold = ssetemp numgroupold = numgroup elif(ssetempold ssetemp): ssetempold = ssetemp numgroupold = numgroup print -, # Write to the file # count = 0 for groupmember in numgroupold: count
34、+= 1 fresult.write(n) fresult.write(-*500) fresult.write(nGroup-%d(%d) % (count, len(groupmember) for num in groupmember: fresult.write( %s % str(num) fresult.write(n) fresult.write(-*500) fresult.write(n) fresult.write(n) ssey.append(ssetempold) # Calculate silhouette coefficient for i in range(0,
35、len(numgroupold): s = for j in range(0, len(numgroupoldi): temp = for k in range(0, len(numgroupold): temp.append(caldistancefromarray(numgroupoldij, numgroupoldk) a = tempi / len(numgroupoldi) sorted = tile(temp, 1).argsort() if(sorted0 = i): d = 1 else: d = 0 while(d 0): b = tempsortedd / len(numg
36、roupoldsortedd) break else: d += 1 if(d = len(sorted): s.append(0) continue c = (b-a)/max(a, b) # print size1 = %d i = %d j = %d sorted0=%d sorted1=%d a = %s b = %s c = %s % (len(numgroupi),i, j, sorted0, sorted1, str(a), str(b), str(c) s.append(c) scy.append(tile(s, 1).sum(axis=0)/len(s) fresult.cl
37、ose() plt.subplot(211) plt.plot(x, ssey) plt.ylabel(SSE) # plt.show() plt.subplot(212) plt.ylabel(SC) plt.xlabel(k) plt.plot(x, scy) plt.show()3Kmeans+算法原理k-means+算法选择初始seeds的根本思想就是：初始的聚类中心之间的相互距离要尽可能的远。具体步骤如下：从输入的数据点集合中随机选择一个点作为第一个聚类中心对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)选择一个新的数据点作为新的聚类中心，选择的原如
38、此是：D(x)较大的点，被选取作为聚类中心的概率较大重复2和3直到k个聚类中心被选出来利用这k个初始的聚类中心来运行标准的k-means算法4Kmeans+算法实现代码如下：def kmeansplus(data,mincluster,maxcluster):x = ssey = scy = fresult = open(resultfile2,wb)for i in range(mincluster, maxcluster+1):print nk = %d % issetempold = 0ssetemp = 0numgroupold = x.append(i)fresult.write(str(i) + :n)group = numgroup = masslist = getmasslist(data,i)for j in range(0, i):g = group.append(g)g = numgroup.append(g)ssetemp = cal(data, masslist, group, numgroup)numgroupold = numgroupcount = 0for groupmember in numgroupold:count += 1fresult.write(n)fresult.wri
