归档于 ‘互联网’ 分类
原文地址:http://aimotion.blogspot.com/2009/12/playing-with-twitter-data.html
玩转Twitter数据：根据好友的状态信息用python对好友进行聚类/分组
大家好，
正如我在我的上一帖最后说，我会开写一些文章, 内容是在twitter上寻找新用户的一些尝试（一个实时微博和社会化网络的服务, 用户在这里可以发布最多140字符的消息）。目标是建立一个推荐系统，可以找到和我拥有相同的口味和偏好的新用户。
这篇文章将介绍有关数据的聚类分析的一些基本概念 ，聚类分析可用于发现和可视化一组拥有紧密联系的事物, 人,以及观点。为此，文章将会介绍如何收集和准备Twitter提供的数据，以及一些使用常规距离度量的聚类算法。一些图表也将作为图形可视化工具，用于观察聚类算法生成的数据(簇)。实现这些聚类算法的过程, 帮助我了解了如何去设计一个推荐算法. 使用特定距离度量方法去衡量一个用户在社会化网络中的得分.
在探讨这个问题之前，需要先向读者阐述一下有监督学习和无监督学习之间的差异。有监督学习通过数据和预期结果(标注结果)，去“学习”如何处理新的数据. 通过当时已经”学”到的内容对新数据生成一个结果.不过，像聚类算法这样的无监督学习和神经网络或者决策树这类有监督学习是不一样的.这类的算法(无监督)不需要用预期的结果(标注数据)去训练。聚类的目的是发现目标数据集合的结构, 而不是去识别数据的模式。具体的说就是利用数据来发现其中存在的独立群组。在这篇和下篇文章中，我们将探讨一些无监督学习，如层次聚类和K-means算法。
现在，先从twitter的用户资料入手, 看看当用户的状态更新时(文本消息), 如何将他们进行分组, 并且可以分到同他们的状态(文字)和用词相匹配的小组中。
下面，我会介绍我是如何获取数据，处理和聚类这些数据, 最终得到一些有意思的结果。
第1步：获取Twitter的数据
第一步是获取所有twitter的数据。对于本文，我决定分析我自己的twitter社会网络。所以我只关注我的资料和我的朋友(我follow的)的资料。我们的目标是确定我和我的朋友如何进行分组。因此，预期的结果是，同我写类似内容的朋友应该获得和我较近的距离，反之写不同类型内容的朋友应该距离远一点。为了获取数据 我用了python-twitter库。它是一个twtter api的开源python接口, 可以非常方便的获取twitter数据。进一步的资料可以查看其官方 项目首页。
在这个实验中，我从twitter中随机选出100个朋友. 把他们twitter中出现的一些特定词的频率作为聚类的数据.现。下表展示了其中的一个子集。
表01 - ， 用户用词的频率
通过用词频率来聚类用户信息，它可能把用户划分成不同的组，在这些组里面用户经常写类似的问题或者风格（如英文或葡萄牙文）。要生成此数据集，你需要下载twitter的用户状态数据，从其中提取出文本，并建立一个词频表。
为了下载Twitter数据，我开发了一个自定义版本的Python-twitter库。在模块里面，我开发了一些新函数，用于获取我的朋友在Twitter中的信息。我建议你下载这个模块，并使用它。要下载 twitterT.py点击这里 。
之后，我已经用Twitter的API，获取了twitter上我的和朋友的状态数据。函数 getFriendsIds 是用来得到包括我在内的Twitter的用户ID。你可以看下面的代码片段。
下一步是创建一个函数，将提取所有用户状态信息中的词。在实验中, 我下载了100个用户的最新100条状态信息。下一个片段显示了如何去完成这件事。
下一步是统计每条微博中每个词使用的次数, 并汇总成词表。因为象’the’这样的词将在几乎到处出现，你可以只选择词表中你认为有实际意义的词, 来减少词汇总量。我创建了一个英语/葡萄牙语的停用词表，包括了那些可以从你的词表里去掉的词。为了获得更好的效果，这步预处理很重要。你可以下载我的停用词列表 在这里 。要使用它只需要像这样导入程序： import stopwords。
最后一步是使用的单词列表和状态列表，创建一个文本文件，包含了一个大矩阵, 其中是每个用户状态的词频。我使用的模块 pickle 来存储这些表。这样做的好处是，你可以很容易地读和写数据，而不会失去对象的类型和避免进一步分析和处理数据。
第2步：聚类算法
本文中的类聚算法选择了层次聚类。它的主要思想是通过不断合并两个最相似的组建立一个有层次结构的组集合。每个组初始状态下只有一个单一的元素，在本实验中，就是一个用户的信息数据。这个方法在每次计算中先计算每两个组之间的距离，最近的合并在一起，形成一个新的小组。不断重复，直到只有一个组。图1显示了这一过程。
图01 - 层次聚类算法在过程
如图，元素的相对位置代表了他们之间的相似程度，两个元素越接近，他们就越类似。你可以看到每两个组（最接近一起）合并组成新的小组，新小组的位置用他们之间的中点来表示。在形成和合并小组的过程中，最后一步将最后剩下的两个小组合并到一块。
下一步是定义紧密度 。在本文中 ， 我将使用 Pearson correlation(皮尔逊关联系数) ， 以确定两个用户数据的相似程度。由于一些twitter状态信息含有较多的条目或比其他更长的条目，因此将在总体上包含更多的单词，Pearson关联系数就是用来解决这个问题的. 试图确定两组数据在之间的线性距离。请记住，pearson关联系数为1.0时表示两个元素匹配程度完美，接近0.0时表示两者没有任何关系。在这里，我们决定使用1减去Pearson关联系数，因为我们想用小的距离来表示两个元素相似。
对于层次聚类算法, 首先创建一个组群，每个原始元素就是一个组。函数的主循环中, 通过尝试每两个组和计算他们之间的关联程度, 找出最匹配的两个组。最好的两个组被合并到一个单一组当中。这一新组的数据是两个原先组中数据的平均值。这个过程重复进行，直到只剩下一个组。您可以在函数 hcluster 中找到全部层次聚类算法的的代码 。
步骤3：显示结果
树状图可以帮助我们更清楚的解读聚类得到的分组。层次聚类的结果通常都采用树状图，因为树状图可以在一个相对较小的空间内包含大量的信息。树状图是将节点按层次进行组织。对于上面例子的树状图显示在图02。
图02 - 可视化的树状图
树状图不仅利用连接来显示元素最终属于哪个分组，而且也用距离来表示元素之间的差异大小。你可以看到了AB簇距离A和B元素要比DE簇到D,E元素的距离近得多。对图的解读可以可以帮助你确定一个分组中各个元素的相似程度，可以认为是一个分组的紧密度。
在这篇文章中 ， [...]
原文地址: http://nathanmarz.com/blog/hadoop-mathematics/
我希望我在一年前就知道这些。现在，通过一些简单的数学我终于可以回答下面的问题：
当机器的处理能力加快一倍, 为什么整个系统运行的速度没有增加一倍?
如果故障率增加10%,为什么整体的运行时间增加了300%?
为了得到最优的性能和容错表现, 一个计算机群应该部署多少机器？
一个简单的数学公式可以巧妙的回答所有这些问题:
运行时间=系统开销/（1 - （1小时数据量的处理时间) ）
我们将在稍后证明这个等式。首先，让我们简要地讨论一下“Hadoop为基础的系统。(分布式系统)”1 Hadoop的一个常规应用是处理一个连续输入的数据流。这种工作流运行在一个“while(true)”循环当中，每一次处理的数据是上一次的运行结果。
接下来的分析可以归纳为一个简单的例子。假设你有一个工作流程需要12小时运行，因此，它每运行一次需要处理数据12小时。现在让我们假设需要做一些额外的计算工作，估计将在现有的工作流上增加两小时处理时间。问题来了。整个系统的运行增加的时间可能会远远多于两小时。它可能会增加10个小时，几百个小时，或者可能失去控制并且每一轮运行越来越慢。
为啥呢？
关键是你将系统需要12小时处理的数据运行时间增加到了14小时。这意味着下一次运行的工作流程，将有14小时的数据需要处理。由于下一个迭代有更多的数据，将需要更长的时间运行。这意味着下一次迭代会有更多的数据，等等。
要确定怎么让运行稳定，让我们做一些简单的数学。首先，让我们写了一个系统运行一次的公式：
运行时间=系统开销+（单机处理1小时数据的运行时间）*（总数据量/单击处理1小时的数据量）
系统开销是指任何常数时间的消耗。例如，启动一个程序的开销。任何运行时间同数据量无关的开销将属于这个“系统开销”这个类别。
“单击处理1小时数据的运行时间”指的是系统中的动态处理数据时间 。这是处理的实际数据量花费的时间，去掉了固定的系统时间开销。如果每个小时数据在系统中需要运行半小时，这个值为0.5。如果每个小时数据需要运行两小时，这个值为2。
一. 先来说说什么是”左”和”右”
1. 左翼(left-wing)和右翼(right-wing)的历史
以左右来划分政治派别, 起源于法国大革命. 在那个叫路易XX为国王的波旁王朝最后掌权的年代, 法国议会的右边坐着保皇党人, 而左边则是激进改革派. 从那时候起, 为政治派别首先划分开了阵营, 便于扎堆和排队, 区分敌友.
2. 传统意义上的”左””右”二元区分
先来看看, 左右翼阵营划分之初, 两边的区分
左翼
右翼
更多的经济干预
更多的经济自由
以消除不平等为目的
承认不平等的存在
绝对意义上的平等
获得机会的平等
自由主义
保守主义
无神论政府
宗教政府
法律支配文化
文化支配法律
从这个最基本的分歧上, 后续产生了分居两边的各种主义和体系, 社会主义/共产主义/资本主义, 大陆法系/英美法系等等
但”左””右”的划分和阵营不是一个绝对的划分, 而是相对的概念
当法国大革命轮到罗伯斯比尔和雅各宾派上台的时候, 自由主义的左派在砍了国王的脑袋以后, 也开始为了维护自己的政权疯狂的砍其他异见者的脑袋.这一点上讲, “左”和”右”都可能成为保守派, 只要在他们掌权以后; 同时也都可能是改革派, 那是他们在野的时候.
7年前的7月14日，一条名为“淇淇”的白鳍豚在武汉白鳍豚馆度过了22个春秋之后，在这一天孤独的离开了世界。
淇淇是人类见过的最后一条活着的白鳍豚。虽曾于2004年发现过白鳍豚的尸体，然而之后数次大规模的监测活动中却再也没能找到它们的身影。两年前的8月8日，这种我们从小熟知的“长江女神”，“水中大熊猫”，终于被宣告灭绝。
在白鳍豚馆里的22年中，淇淇虽然有过短暂的伴侣，绝大部分时间都是在孤独中度过的。设想一下，如果你是世间幸存的最后一个人，对于你这意味着什 么？是不是旷世的孤独、绝望与无助？这样不幸的事情正发生在它的身上。再也找不到谁与它结伴而游，喜欢结群的它只能在池中独自游弋；任凭它引吭高唱，这世 界上已没有谁能理解它的声音。
假如你有1000万要办一个网站。下面两种方案：
1，用800万买性能高的服务器，200万雇专业能力一般的技术人员；
2，用200万买性能一般的服务器，800万雇专业能力优秀的技术人员。
哪种更划算呢？
之前想了几次这个问题，但一直没得到一个简便的答案。后来突然想到，这个事情在算法教科书里经常提到。大意就是，假如你的程序使用的算法的复杂度是高于线性的，那么你买一个性能提高了N倍 的机器，你的程序单位时间内处理的数据量并不会提高N倍。
那么机器与人的区别就是，更贵的机器为你的程序带来的性能提升是线性的；而一个优秀的技术人员，通过设计时间复杂度更低的算法，则可能帮你将一个性能较差的程序的性能以平方、立方甚至指数级别提升。如果这样想的话，第2种方案更为划算。
这是一个很开放的问题。这里只是从性能这个角度去考虑，而且纯粹是理论上的。实际中需要考虑的因素更多。大家有何想法呢？
互联网从信息饥渴到信息过载, 几乎是瞬间完成的. web 2.0的普及更是带来了一个信息爆炸的时代.
对于海量数据的网络, 人们有哪些需求?
一种是”找”, 用户知道自己想要什么, 就像从杂物间里面找硬币一样. 另一种是”听”, 我不知道我要什么, 你来告诉我这里有什么好玩的东西, 也许我会感些兴趣.
十几年前, 有种叫搜索引擎的东西被造出来替人们去做第一件事情.但对于第二件事情, 却很难有个聪明的机器去替我们做, 因为机器还没智能到可以在没有任何人类提示的情况下, 从一堆一堆垃圾里面找到精华.
这里面唯一值得一提的就是新闻聚合, 把新闻网站的内容聚出焦点来. 这是一个好的开始, 但还不够.如果我怀着一颗好奇的心, 那么我该去”听”谁的呢? 网络时代之前的做法被沿用了下来.
1) 相信专业: 媒体编辑的职业就是干这活的, 天天看, 天天选. 他先替你一层一层选一遍, 你跟着他混就行了.这招准确率还行, 覆盖率不够. 同时严重依赖编辑的水平和操守, 最可怕的是遇到新闻联播型的媒体.
2) 相信大众: 别人都说好的, 咱也别错过. 这个依赖于群体智慧的整体水平.
3) 相信自己: 把所有东西看一遍, 自己来筛选精华. 这个方法好, 但似乎代价太大了……