机器学习 — 发现群组
TobyTraugot
8年前
<h2>聚类</h2> <p>属于无监督学习</p> <p>目的：找到数据集中的不同群组</p> <h3>分级聚类</h3> <p>主要思想是：</p> <ol> <li>在数据集中找出两个最相似的节点</li> <li>根据这两个节点生成一个新的聚类节点，这个节点的数据为两个子节点的数据的平均值,</li> <li>将两个子节点从数据集中去除，将新的聚类节点加入数据</li> <li>回到1，直至数据集中只剩一个节点</li> </ol> <h3>K-means聚类</h3> <p>使用分级聚类的时候，因为得计算所有数据的两两之间的距离，形成新的聚类之后还得重新计算，所以在数据集较大的时候计算量会很大。</p> <p>除了分级聚类之外还有一种K-均值聚类方法，主要思想为：</p> <ol> <li>随机创建（给定）k个点作为中心点</li> <li>遍历数据集中每个点，找到距离最近的中心点，将该点划分在该中心点下</li> <li>遍历并划分完成后，将各个中心点移到自己组下所有点的中心位置</li> <li>回到2，直到移动之后的结果（不变）和上次一样</li> </ol> <p>结果展示：使用树状图来展现聚类之后的结果</p> <pre> <code class="language-python">import feedparser import re # test error_list = [] # 返回一个RSS订阅源的标题和包含单词计数情况的字典 def get_word_counts(url): # 解析订阅源 doc = feedparser.parse(url) # 单词计数 wc = {} # 遍历所有文章条目，统计所有单词出现次数 for entry in doc.entries: if 'summary' in entry: summary = entry.summary else: summary = entry.description # 提取出所有单词 words = get_words(entry.title + ' ' + summary) # 统计所有单词出现的次数 for word in words: wc.setdefault(word, 0) wc[word] += 1 print url if hasattr(doc.feed, 'title'): return doc.feed.title, wc error_list.append(url) return '', wc # 分割出html中的所有单词 def get_words(html): # 取出所有html标记 txt = re.compile(r'<[^.]>').sub('', html) # 利用所有非字母字符拆分出单词 words = re.compile(r'[^A-Z^a-z]').split(txt) # 转换为小写返回 return [word.lower() for word in words] apcount = {} word_counts = {} feed_list = [line for line in file('feedlist.txt')] # 读取每一个url并统计单词在每篇博客中出现的次数 for feed_url in feed_list: title, wc = get_word_counts(feed_url) if title == '': continue if title in word_counts: title += '1' print title word_counts[title] = wc # 统计单词词频 for word, count in wc.items(): apcount.setdefault(word, 0) if count > 1: apcount[word] += 1 # 设定词频边界，去除常见无用词 word_list = [] for w, bc in apcount.items(): frac = float(bc) / len(feed_list) if frac > 0.1 and frac < 0.5: word_list.append(w) out = file('blogdata.txt', 'w') # 输出表头 out.write('Blog') for word in word_list: out.write('\t%s' % word) out.write('\n') # 输出表格内容 for blog, wc in word_counts.items(): out.write(blog) for word in word_list: if word in wc: out.write('\t%d' % wc[word]) else: out.write('\t0') out.write('\n') print error_list</code></pre> <pre> <code class="language-python">http://feeds.feedburner.com/37signals/beMH http://feeds.feedburner.com/blogspot/bRuz http://blog.outer-court.com/rss.xml Google Blogoscoped http://gizmodo.com/index.xml http://googleblog.blogspot.com/rss.xml http://feeds.feedburner.com/GoogleOperatingSystem http://feeds.feedburner.com/Mashable</code></pre> <h3>上面的代码遇到的问题</h3> <ol> <li>有些博客rss失效，导致doc.feed.title为空，需要判断title是否为空，如果是则跳过该url</li> <li>列表和元组的区别，元组是不可变的相当于Java中的数组，放在一个圆括号中()；列表是可变的，相当于Java中的List，方法一个方括号中[]，有python内置的方法和列表自己的方法，比如添加append</li> <li>字典是使用大括号{}，遍历key和value使用items()方法，直接对字典遍历得到的是keySet</li> </ol> <p>分级聚类：通过连续不断的将最为相似的群组两两合并。其中每个群组都是从一个单一元素开始的。在这里这个单一元素就是blog。</p> <p>下面对blog进行聚类，先加载数据文件，按主题进行分组</p> <pre> <code class="language-python">def readfile(filename): lines = [line for line in file(filename)] colnames = line[0].strip().split('\t')[1:] rownames = [] data = [] for row in lines[1:]: p = row.strip().split('\t') rownames.append(p[0]) data.append(p[1:]) return rownames, colnames, data</code></pre> <pre> <code class="language-python">from math import sqrt def pearson(v1, v2): """ pearson算法计算两个向量之间的相似度 """ # 简单求和 sum1 = sum(v1) sum2 = sum(v2) # 求平方和 sum1_sqrt = sum([pow(v, 2) for v in v1]) sum2_sqrt = sum([pow(v, 2) for v in v2]) # 求乘积之和 multi_sum = sum([v1[i] * v2[i] for i in range(len(v1))]) # 计算pearson score num = multi_sum - (sum1 * sum2 / len(v1)) den = sqrt((sum1_sqrt - pow(sum1, 2) / len(v1)) * (sum2_sqrt - pow(sum2, 2) / len(v1))) if den == 0: return 0 # 相关度越大den越大，这里为了表示相似度越大，两个元素之间的距离的更小 return 1.0 - num/den</code></pre> <pre> <code class="language-python"># 定义一个聚类的类型 class bicluster: def __init__(self, vec, left=None, right=None, distance=0.0, id=None): # 该blog的每个单词的频率 self.vec = vec # 左子节点 self.left = left # 右子节点 self.right = right # 当前聚合类的相似度 self.distance = distance # 标识该聚类 self.id = id</code></pre> <pre> <code class="language-python">def hcluster(rows, distance=pearson): """ 进行聚类运算:遍历所有数据集，每次都找出距离最近的两个聚类， 然后生成一个新的聚类，将新生成的聚类添加到列表末尾，并删除找到的两个聚类，形成新的数据集，重复以上步骤 """ # 缓存两个cluster之间的距离 distances = {} current_cluster_id = -1 # 刚开始的聚类 cluster = [bicluster(rows[i], id = i) for i in range(len(rows))] # 开始聚类，直到数据集中只剩一个数据，表明聚类完成 while len(cluster) > 1: lowestpair = (0, 1) closest = distance(cluster[0].vec, cluster[1].vec) # 遍历每一个配置，寻找最相似的两个blog for i in range(len(cluster)): for j in range(i+1, len(cluster)): # 缓存距离 if (cluster[i].id, cluster[j].id) not in distances: distances[cluster[i].id, cluster[j].id] = distance(cluster[i].vec, cluster[j].vec) d = distances[cluster[i].id, cluster[j].id] if d < closest: closest = d lowestpair = (i, j) # 计算两个聚类的平均值 merfevec = [(cluster[lowestpair[0]].vec[i] + cluster[lowestpair[1]].vec[i]) / 2.0 for i in range(len(cluster[0].vec))] # 建立新的聚类 newcluster = bicluster(merfevec, left=cluster[lowestpair[0]], right=cluster[lowestpair[1]], distance=closest, id=current_cluster_id) # 不在原始集合中的聚类，使用id为负数表示 current_cluster_id -= 1 # 注意删除顺序，每次删除之后index都会发生变化，先删除index大的，即从后往前删除 del cluster[lowestpair[1]] del cluster[lowestpair[0]] cluster.append(newcluster) return cluster[0]</code></pre> <p>进行聚类运算，找出最终的聚合类</p> <pre> <code class="language-python">blognames, words, data = readfile('blogdata.txt') # 字符串转换为int int_data = [] for row in data: temp_row = [] for num in row: temp_row.append(int(num)) int_data.append(temp_row) cluster = hcluster(int_data) print cluster</code></pre> <pre> <code class="language-python"><__main__.bicluster instance at 0x7f978c07ca70></code></pre> <pre> <code class="language-python"># 将聚类后的cluster以树的形式打印出来 def print_cluster(cluster, labels=None, n=0): for i in range(n): print ' ', # 如果是分支，负数表示一个分支 if cluster.id < 0: print '-' else: if labels == None: print cluster.id else: print labels[cluster.id] # 打印左右分支 if cluster.left != None: print_cluster(cluster.left, labels, n=n+1) if cluster.right != None: print_cluster(cluster.right, labels, n=n+1)</code></pre> <pre> <code class="language-python">print_cluster(cluster, labels=blognames)</code></pre> <p>在python2中print是默认换行的，如果想print不换行：</p> <p>在python2中：print 'hello',</p> <p>在python3中：print ('hello', end='')</p> <p>上面是使用缩进对整个聚类结构进行排版，可以绘制树状图更加直观</p> <pre> <code class="language-python">from PIL import Image, ImageDraw # 计算每个节点的高度 def getheight(clust): # 如果是叶子节点，高度为1 if clust.left == None and clust.right == None: return 1 # 如果是树枝节点，高度为所有分支高度之和 return getheight(clust.right) + getheight(clust.left) # 计算两个节点之间的线段长度 def getdepth(clust): # 叶子节点的距离为0 if clust.left == None and clust.right == None: return 0 # 枝节点的距离为两个子节点的距离较大值加上枝节点自身的距离 return max(getdepth(clust.left), getdepth(clust.right)) + clust.distance # 绘制树状图，每个节点高度为20像素，宽度固定的jpg图片 def drawdendrogram(clust, labels, jpeg='clusters.jpg'): # 图片高度 h = getheight(clust) * 20 w = 1200 depth = getdepth(clust) # 由于宽度固定，需要对距离进行缩放，150为左右空白 scaling = float(w-150) / depth # 新建一张白色背景图片 img = Image.new('RGB', (w, h), (255, 255, 255)) draw = ImageDraw.Draw(img) # 绘制中间根节点的线 draw.line((0, h/2, 10, h/2), fill=(255, 0, 0)) drawnode(draw, clust, 10, h/2, scaling, labels) img.save(jpeg, 'JPEG') # 递归绘制节点自身以及两个子节点 def drawnode(draw, clust, x, y, scaling, labels): # 如果是枝节点，则只负责绘制两个子节点 if clust.id < 0: h1 = getheight(clust.left) * 20 h2 = getheight(clust.right) * 20 top = y - (h1 + h2) / 2 bottom = y + (h1 +h2) / 2 # 当前节点线的长度 line_len = clust.distance * scaling #print scaling, line_len # 聚类到子节点的垂直线 draw.line((x, top + h1/2, x, bottom - h2/2), fill=(255, 0, 0)) # 聚类到左子节点的垂直线 draw.line((x, top + h1/2, x + line_len, top + h1/2), fill=(255, 0, 0)) # 聚类到右子节点的垂直线 draw.line((x + line_len, bottom - h2/2, x, bottom - h2/2), fill=(255, 0, 0)) # 绘制左右子节点 drawnode(draw, clust.left, x + line_len, top + h1/2, scaling, labels) drawnode(draw, clust.right, x + line_len, bottom - h2/2, scaling, labels) else: # 如果是叶子节点，绘制blogname draw.text((x + 5, y - 5), labels[clust.id], (0, 0, 0))</code></pre> <pre> <code class="language-python">drawdendrogram(cluster, blognames)</code></pre> <h2>K-均值法</h2> <p>使用分级聚类的时候，因为得计算所有数据的两两之间的距离，形成新的聚类之后还得重新计算，所以在数据集较大的时候计算量会很大。</p> <p>除了分级聚类之外还有一种K-均值聚类方法，主要思想为：</p> <ol> <li>随机创建（给定）k个点作为中心点</li> <li>遍历数据集中每个点，找到距离最近的中心点，将该点划分在该中心点下</li> <li>遍历并划分完成后，将各个中心点移到自己组下所有点的中心位置</li> <li>回到2，直到移动之后的结果（不变）和上次一样</li> </ol> <pre> <code class="language-python">import random # k均值法进行聚类 def kcluster(rows, distance=pearson, k=4): # 确定每个点的最大值和最小值，便于控制随机生成值的范围 ranges = [(min(row[i] for row in rows), max(row[i] for row in rows)) for i in range(len(rows[0]))] # 随机生成k个点 clusters = [[random.random() * (ranges[i][1] - ranges[i][0]) + ranges[i][0] for i in range(len(rows[0]))] for j in range(k)] lastmatches = None for t in range(100): print 'Iterator %d' % t bestmatches = [[] for i in range(k)] for j in range(len(rows)): bestmatch = 0 for i in range(k): d = distance(rows[j], clusters[i]) if d < distance(rows[j], clusters[bestmatch]): bestmatch = i bestmatches[bestmatch].append(j) # 和上一次结果比较 if bestmatches == lastmatches: break lastmatches = bestmatches # 把中心点移到其所有成员的平均位置处 # 每个中心点都要移动 for i in range(k): avgs = [0.0] * len(rows[0]) if(len(bestmatches[i]) > 0): # 对其所有成员求和 for rowid in bestmatches[i]: for m in range(len(rows[rowid])): avgs[m] += rows[rowid][m] # 求平均值 for j in range(len(avgs)): avgs[j] /= len(bestmatches[i]) # 作为新的中心点 clusters[i] = avgs return bestmatches</code></pre> <pre> <code class="language-python">kclust = kcluster(int_data, k=5) print kclust</code></pre> <pre> <code class="language-python">Iterator 0 Iterator 1 Iterator 2 Iterator 3 Iterator 4 Iterator 5 Iterator 6 Iterator 7 [[5, 8, 10, 11, 17, 21, 29, 34, 48, 55, 62, 63, 66, 67, 68, 70, 73, 75, 84, 97], [2, 7, 13, 16, 23, 24, 25, 30, 36, 40, 44, 49, 56, 65, 69, 79, 80, 85, 91, 94], [4, 41, 42, 45, 46, 81], [6, 26, 27, 32, 33, 35, 37, 51, 53, 54, 57, 59, 64, 71, 76, 78, 82, 87, 88, 89, 90, 92, 95, 96], [0, 1, 3, 9, 12, 14, 15, 18, 19, 20, 22, 28, 31, 38, 39, 43, 47, 50, 52, 58, 60, 61, 72, 74, 77, 83, 86, 93, 98]]</code></pre> <p>使用分级聚类和k-均值聚类的方法，分析的数据是连续的，而对于偏好的数据，更好的是使用Tanimoto系数计算两者之间的距离，分析两个人在拥有物品重叠度的大小</p> <p>tanimoto系数计算：</p> <p>使用A和B的交集除以A和B的并集</p> <p><img src="https://simg.open-open.com/show/b9b7ace33c7700af9f181aadebf1c60a.jpg"></p> <pre> <code class="language-python"># 计算Tanimoto系数 def tanimoto(v1, v2): c1, c2, shr = 0, 0, 0 for i in range(len(v1)): # 出现在v1中 if v1[i] != 0: c1 += 1 # 出现在v2中 if v2[i] != 0: c2 += 1 # 在v1、v2中均出现 if v1[i] != 0 and v2[i] != 0: shr += 1 return 1.0 - (float(shr) / (c1 + c2 - shr))</code></pre> <p> </p> <p>来自：http://www.cnblogs.com/sunshine-2015/p/6545641.html</p> <p> </p>