最好理解的贝叶斯分类——朴素贝叶斯分类器

《机器学习》里说的是贝叶斯学习。不过其实数据挖掘的Classification本质就是一种机器学习。这里参考《数据挖掘》一书居多。
贝叶斯分类基于概率论中与条件概率相关的贝叶斯定理，根据条件概率的计算方法：

贝叶斯定理的公式通过两个事件相互间的条件概率消去了依赖于时间独立性的难以计算的：

 

这样一来，如果我们定义B是我们已知的一系列属性，视为“证据”。我们要计算带有这系列属性的记录的分类结果，可以先算出每个可能分类在已知条件（即这些证据）下的后验概率（Posterior Probability）。
贝叶斯定理提供了根据一系列已知概率来计算后验概率的方法。一系列已知概率，根据大数定理，我们可以用已有的统计样本（训练集）的频率来估计。因此准确性其实有赖于训练集的规模和代表性。

朴素之处
假设每条记录（元组）用一个n维向量表示其属性，假设所有可能分类为，则我们需要对所有分类，为这个元组计算其属于某一分类的概率：

最后我们选择有最高后验概率的类，作为这个元组的分类预测。也就是其概率比其他分类都高的分类。
朴素贝叶斯分类之所以被称为朴素（Naive，幼稚的），是因为它对于很难计算的后验概率，它作了以下假设：所有属性之间都是条件独立的，也就是说，一个议员在财政议题上的态度，与他在外交政策上的态度（没错还是用美国国会数据的例子）是无关的。这个假设简化了该后验概率的计算。之所以说后验概率难算，是因为我们很难在训练集中找到和待分类元组的属性完全吻合的记录，特别是当训练集规模不够大的时候（很难找到分类为，且属性向量为的记录）。当我们假设属性间条件独立的时候，便有：

一个属性向量的后验概率是其各维的乘积。
这种假设有其局限性，因为属性之间条件独立是很不可能的，比如议员在议题A上的取态不太可能和议题B的无关（当然其中往往没有直接的逻辑关系，但数学上定义的条件独立要求两个事件共同发生的概率等于两者概率的乘积）。因此这个假设虽然方便，但带来误差，但这不影响这种“幼稚”的方法的实用性。

先验概率估算
如果不存在可用的训练集，最好的方法是遵循信息论中的熵最小原则，假设所有的类是等概率的。但其实我们往往都有办法得到训练元组，前面说过，离散属性的概率可以通过其频率获得，而对于连续属性，我们进行一个比较依靠经验法则的假设，我们假设连续属性都满足正态分布，根据训练集作为统计样本得到均值和标准差，定义出该属性的分布公式：

那么我们只需将待分类元组的连续属性值根据公式算出其概率。
只要掌握了上述的思想，我们可以发现贝叶斯分类的数学模型是非常简洁好懂的。

拉普拉斯估计
根据类条件独立的假设，某属性向量的概率由其各维乘积得到，但如果遇到其中一个维的概率为0，那么估算出来的后验概率都会为0。如此一来该类的估算概率便为零。但这很可能只是因为训练集的局限性所致（因为规模不够大，或是不够全面）。这时我们引入另外一个假设，假设训练集很大，以致对每个计数结果加上1不会对估计概率产生不可忽略的影响，我们就可以用这种方法来避免零概率值的出现。
当然，在对k个技术结果都加一后，计算频率的分母应该加上k。
另，我们如果只是需要分类结果，因为我们是找具有最大后验概率的分类，而对于某个特定的属性向量X，其概率P(X)只是起到了归一化因子的作用，因此计算时只需要计算分子然后进行排序即可。（不对浮点数归一化同时可以避免精度丧失）

测试
以下是对美国国会数据集进行朴素贝叶斯分类的代码：

import random
class instance():
    def __init__(self, party, votes):
        self.party = party
        self.votes = votes
dataFile = open('dataset.txt', 'r')
datas = dataFile.readlines()
database = []
for line in datas:
    line = line[:-2]
    attrs = line.split(',')
    member = instance(attrs[0], attrs[1:])
    database.append(member)
partyName = ['democrat', 'republican']
trainset = []
checkset = []
for i in range(len(database)):
    if random.random() > 0.9:
        checkset.append(database[i])
    else:
        trainset.append(database[i])
stats = {}
for name in partyName:
    stats[name] = {"number" : 0, "votes" : []}
for k in stats:
    for i in range(len(database[0].votes)):
        stats[k]['votes'].append({"y" : 0, "?" : 0, "n" : 0})
for record in trainset:
    stats[record.party]['number'] += 1
    for i in range(len(record.votes)):
        stats[record.party]['votes'][i][record.votes[i]] += 1
wrong = 0.0
for record in checkset:
    probability = {}
    for name in partyName:
        probability[name] = 0.0
    for k in probability:
        p = 1.0
        for i in range(len(record.votes)):
            p *= (float(stats[k]['votes'][i][record.votes[i]]) / float(stats[k]['number']))
        probability[k] = p    
    if probability['democrat'] > probability['republican']:
        predict = "democrat"
    else:
        predict = "republican"
    print record.party + " , " + predict
    if record.party != predict:
        wrong += 1.0
print "correct rate: " + str(1 - wrong / len(checkset))

每条记录有90%的可能选作训练集，剩余用于检验分类正确性，最后打印出正确率

无耻地选了难得的全对结果，实际的正确率大约稳定在85%以上。
以下观点摘自《数据挖掘》：
理论上贝叶斯分类具有最小的错误率，但实践中容易因缺乏可用的概率数据和其假定的不确定性影响。

女孩，当他们说爱你的时候——读《牧师的女儿》

奥威尔的六部小说中有两部他认为烂到不应该再版，《牧师的女儿》是其中一本。两部都是在生活窘迫时为了赚钱而出版的实验性书稿（这部书的第三章干脆直接用戏剧的形式来写）。作者不成熟地描写了一个女主角，故事也讲得很蹩脚，很大程度就照搬他结束流浪后在英国的不同职业的生活经历作为素材。
Dorothy是个失去自由的女孩。在这个单亲家庭，她的父亲是个骨子里懒惰而又爱面子的大男人。千篇一律的生活和疲惫不堪的劳动，令她几乎感受不到任何的乐趣和幸福。而她坚守自己从不质疑的信仰，甚至通过自我体罚的方式。失忆后的流浪令这个女孩得到了前所未有的自由，尽管正因为失忆使她无法感受这种自由的变化。流浪的代价是艰苦的生活。而当她恢复记忆后，又面对着对自己名声被毁以及突然发现自己无依无靠的两重恐惧。她艰难地坚持着亲戚介绍的教书的临时工作，一边寻找新的可依赖人物——为了不丢掉工作而依赖苛刻的校长Mrs.Creevy，为了能回家依赖来接她的Mr.Warburton。Dorothy是个不幸的女孩，甚至我觉得她失忆时的流浪生活几乎可以说是她一生最难得的快乐时光。

奥威尔在描写流浪和打短工摘啤酒花（作者曾经做过这种工作并记下大量日记）的时候，也许有意强调了这种生活苦中作乐的一面。恰恰是这种贫困生活下的自由反衬出Dorothy之前禁锢式生活的可怕。但我们又都知道，当你身无分文时，你是不可能自由的。因为你只能利用自己的劳动力来获得维持生计的必需品。从这个角度看她的这段经历又是乏善可陈。即使在她这个阶段，这个流浪界的新人还是一直依赖着身边经验丰富的流浪者才得以顺利度过难关。不过这种依赖更多的是因一个群体对弱者很自然的关照。
人如果缺乏独立的能力而对别人产生了依赖，也就一直处于了被动的位置。这也是争取性别平等的人们主张女性要能经济独立的原因。不仅性别上，其他方面的问题实际也是相同道理。实际上我快看到结局的时候是以为Dorothy会答应Warburton的求婚请求的。如果如此，其实Dorothy也不过是换了一个依赖的对象继续过无法自己把握的生活罢了。但作者并没有这样写。经历了太多的Dorothy始终不愿再面临生活的大变化，失去了原来本就不坚定，毫无基础的信仰后的她，很恐惧再次的变化。她更愿意选择回自己尽管已经毫无感觉，但却能给她安全感和稳定感的最原本的生活，回到父亲身边继续打理繁杂的事务。
神父和Warbuton几乎是男权社会中的两类经典负面男性形象。神父虽为鳏夫，却没有尽自己作为一个父亲的责任给与女儿足够的关爱，反而因为他的大男子主义给女儿承受更多的压力，而这一切他亦视为理所当然。Warbuton则是玩世不恭的中年男人，不认真对待感情而又对此很享受。
作者借这本书指出了好几点，一是经济不平等所产生的贫困的可怕，正如他很多作品反映的那样；二是教育制度的问题，这点大概是作者在下三烂的学校当教师的时候所深深感受的，通过Dorothy做教师的经历反应；三是基督教保守传统下女性受到的压迫，尽管作者可能并没有打算局限在第三点。
Dorothy的不幸源于她一直处于无法主宰自己的命运的被动位置。我们不知道Dorothy回到家后的故事。也许神父会在数年后急切地想将Dorothy嫁出去，这个女孩的一生也就完成了所谓“女儿”到“妻子”的角色转变，而后是“母亲”。人需要有安全感，无论这种安全感是来源自己还是他人。产生依赖也只是因为自己给自己的安全感不够。即使到了最后，也没人和这个女孩说过“我爱你”，即使是要求婚的Warbuton。但为什么她非得屈就自己，去依赖甚至对她没有关怀的人？因为不够强大。
所以我始终同意无论性别或是家庭背景，人总要通过独立而获得自由。这只是这本书能够带出的思考。总体来说这本小说虽说不好，还是有看点的。
Extrations：

"Think of life as it really is, think of the details of life; and then think that there is no meaning in it, no purpose, no goal except the grave. Surely only fools or self-deceivers, or those whose lives are exceptionally fortunate, can face that thought without flinching?"

Chap II

“试着想想生活的真实状态，想想生活的细节；然后试想生活没有任何意义，没有目的，除了进入坟墓没有任何目标。也只有傻子或者是自欺的人，或者是那些生来就特别幸运的人，才能做到在面对这些想法的时候没有任何退缩？”

"For the rest, she grew used to the life that she was leading - used to the enormous sleepless nights, the cold, the dirt, the boredom, and the horrible communism of the Square. After a day or two she had ceased to feel even a flicker of surprise at her situation. She had come, like everyone about her, to accept this monstrous existence almost as though it were normal. "

Chap III

“至于其他，她已经习惯了她现在过的生活——习惯了漫长的无眠夜晚，那种寒冷，那种肮脏，那种乏味，和广场那种可怕的公共生活。一两天后她已经不再对自己的出境有即使那么一点的惊讶。她向其他人一样，像这很正常一样接受了这种可怕的生存。”

"It is a mysterious thing, the loss of faith-as mysterious as faith itself. Like faith, it is ultimately not rooted in logic; it is a change in the climate of the mind."

Chap V

“这是神秘的，丢失信仰——正如信仰本身一样神秘。像信仰一样，它终究不是植根于逻辑；它是你思想氛围的改变。”

基于SVG矢量格式的世界地图染色工具

想写这个是因为在美赛期间做D题的时候，为国家的数据进行聚类分析后，我们想插入一幅世界地图作为插图，为不同聚簇的国家染上不同的颜色。因为对维基百科上的SVG格式世界地图印象比较深，所以我通过下载原始素材，然后用SVG格式的编辑器Inkscape手工染色。实际上网上有一些利用数据绘制地图的工具网站，功能很齐全，只是创建出的图片是带水印的。

SVG格式
SVG（Scalable Vector Graphics）乃可缩放矢量图形。以前学Flash的时候看教程书了解过矢量图和位图的差异。位图（Bitmap）是比较普遍的图片表示形式，通过像素（每个位置的色彩点）的集合来表示一幅图像，因此位图的清晰度受其分辨率（Resolution）的限制。矢量图则通过存储图像的图形学特征来表示一幅图，比如矩形，折线，曲线的各个关键点的特征，因此矢量图的质量不会因放缩受影响，其相较下的缺点便是存储的复杂性。

位图与矢量图的放缩效果对比，这幅示例图是SVG格式的（源自维基百科）

SVG格式通过XML（eXtensible Markup Language，可扩展标记语言）定义，XML和HTML同属SGML（Standard Generalized Markup Language，标准通用标记语言）这一大类的标记语言。有趣的是这种格式的标准是有W3C制定的Web标准。因此，当我们用浏览器打开一幅SVG图像时，我们可以用其开发者工具查看它的每个元素。

用文本编辑工具打开一个SVG文件同样能查看它的文件结构，实际上它很像一个HTML页面，只不过标签不同。正因为SVG的文件结构特点，往往对其操作最方便的就是利用Javascript这一门前端语言。

SVG基本标签
SVG 代码以<svg>元素开始，用开启标签<svg>和关闭标签</svg>包括。<svg>是SVG XML的根元素，如同HTML的<html></html>。<svg>标签的width 和 height 属性设置SVG文件的宽度和高度。
SVG的形状通过<rect>（矩形）、<circle>（圆形）、<ellipse>（椭圆）、<line>（线）、<polyline>（折线）、<polygon>（多边形）和<path>（路径）这些标签定义。打开维基开放媒体提供的世界地图素材后，可以发现上面的国家都是通过<path>标签定义的。
文字通过<text>标签插入。上面那幅示例图即通过这种方式插入文字。
<g>标签指定元素的组，在同个<g>标签内的元素位于同一组（这一点可以在用编辑器打开时体会）。比如地图素材中的美国由于有多个不相连的块组成，就体现了建组的作用。
SVG标签的样式同样是由CSS定义的，这为绘图提供大大的方便，标签的style属性就是用来指定CSS属性的。比如通过指定fill属性即可指定图形的填充颜色。
示例：

<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="100%" height="100%" version="1.1" xmlns="http://www.w3.org/2000/svg">
    <line x1="0" y1="0" x2="300" y2="300" style="stroke:rgb(99,99,99);stroke-width:2"/>
</svg>

这段SVG XML代码定义了一幅从图片左上角画到左下角的直线。
世界地图的XML代码非常复杂，因为都是一堆<path>标签对国界线的定义，这种图形是通过编辑器画出来的。
关于SVG的更多标准可以查看W3C的官方文档。

代码

import re
def getPaintedMap(classification, colorScheme, filename="untitled.svg"):
    f = open('test.svg', 'r')
    content = f.read()
    stylePattern = re.compile(r'<style id="style_css_sheet" type="text/css">([\s\S]+?)</style>')
    styleText = stylePattern.search(content).group(1)
    newStyle = styleText
    for country in classification:
        selectorStr = "." + country + " \n{\n\tfill: " + colorScheme[classification[country]] + "\n}\n"
        newStyle += selectorStr
    content = content.replace(styleText, newStyle)
    f.close()
    f = open(filename, "w")
    f.write(content)
    f.close()

实际上代码的函数只是很简单的在原SVG文件的style标签中加上对应的css fill属性。素材中的每个国家都通过其对应的ISO 3166-2标准的国家代号（中国是cn，加拿大是ca等等）进行了标记。只需要用CSS选择器选择即可。
函数接受三个参数，classification是一个从ISO 3166-2国家代号字符串映射到分组号的字典，colorScheme定义着色方案，是分组号映射到颜色号的字典，filename定义输出的文件名。

简单应用
根据Opennet组织对73国的网络自由度评估，从组织整理的四项参数（的五级评分中，先做K-均值聚类而后绘制出这些国家的网络自由度程度评级，地图效果如下：

颜色越深的代表审查程度越严苛，灰色是原素材默认颜色，表示没有包括在数据内的国家。聚类结果比较符合预期，而画图的代码很直观地表示出分析信息。Python有一个第三方的pycountry模块，其源码中有很充足的ISO标准数据库，以xml格式存储。可以直接使用模块的函数或是自己抓出国家代号的信息。而Opennet官方也提供.csv格式的自由度评分数据。

题外话，Opennet的评估局限性在哪？除了其国家数量不足以外，更重要的一点是其评估的公允性。根据维基百科综合Opennet，无国界记者等的评估，结果如下：

无国界记者组织2014年列出的“互联网公敌”名单（图中粉色）新增了数个国家，包括美国和英国，很大程度即因为棱镜门丑闻的爆发。

躺在香榭丽舍大街的杂牌饭店——读《巴黎伦敦落魄记》

“奥威尔式”（Orwellian）这个词伴随着《一九八四》和《动物农场》的主题，被人们用来代指一个极权制度的管制手段。人们会联想到“电幕”、“老大哥”和“新话”。但我同意张佳玮在《代表作和被代表作》里指出的：

如是，连作品带人一起被误读，简直是一个创作者的义务。因为世界贪图方便，人们才需要标签和流派，用以给伟大的创作者分门别类。夸张的时候，他们还会用一两个名字或词语，统摄整个时代。比如，一个身处媒体标签时代的中国青年，如果试图去深入一下马尔克斯，必然眼界大开：首先，他会发现此人除了《百年孤独》，还写过那么浩繁的作品；其次，他会发现此人绝大多数的作品，都毫无媒体拼命标签的“魔幻现实主义”色彩。

所以对我来说，“奥威尔式”如果要成为一个标签，更像是奥威尔叙事叙理的那种Plain Fact的平实风格和冷静触感。他思想转折点间的不同时期讲述着不同主题的内容，又都很真切地反应着自己对所见所闻的思考和感受。犹如香港时评人李怡的经历转折给人带来的感觉，“我回顾过去一生，我觉得我冇试过不忠于自己”。在这里并没有否定两大名作的突破性，只是觉得人们太习惯忽略一个作家的思想历程和人生经历对其作品的影响。

企鹅出版社现代经典系列的封面

这部非虚构作品可以说是对这个作者的形象的一大补充。他放弃尚得体面的稳定生活而投身两个欧洲大国首都的不堪入目的核心。在这里有形形色色的三教九流，讲着荒诞的故事。作者会选择投身于此不是因为他疯了，这个在缅甸当过警察却又放弃殖民地生活回到英伦三岛的年轻作家，抱着对建制的反感抵触和质疑，想去寻找自己内心问题的答案。
他终究是个英国佬，因此他的绅士性格和英式幽默贯穿着整个经历。这段堂吉诃德式的探险不是一场带着猎奇的心态的计划旅行，而是一连串偶然下的体验。遭遇偷窃，典当身物，流浪街头，食不果腹。巴黎的X宾馆令人想起“猪龙城寨”。在Jehan客栈做洗碗工像是如获新生。在伦敦的收容所之间每日不断迁徙似是见证陆地上的吉普赛生活。向一群流浪汉取“伦敦东区露宿攻略”的经，而后各奔东西的很像某部江湖电影的脉络，只不过游走的江湖一点也不潇洒而已。
Boris是这本书中花比较大笔墨写的人。这个沙俄的红潮难民却又在镜头转向伦敦的时候完全从文中消失，甚至没有交代去处，尽管他和作者在巴黎几乎是整个落魄过程中共患难共悲喜的同伴。不知道是不是每个跑龙套的俄国人的名字都会是Boris，Ivan或是Yuri。无常的流浪生活就是这样，与作者相遇的人都挣扎在底层，谁又有兴趣和这个虽形象和他们一样但口音和举止都怪怪的人深交。所有人都是过客，但他们的出镜却都不是轻轻带过。这样一幅一直延续到终章的众生像，在作者回顾整理的时候又是不是像一场蒙太奇般的梦？
1930s的英法两国和很多国家一样面临着大萧条，欧洲大陆的右翼化开始抬头。深度的贫困摧毁人的生活至于摧毁人的希望，乃至摧毁人的思考。可以说作者所描写的就是这种程度的贫乏——人们不仅过得很糟糕，还没有改变现状的希望，更加地，也许幸运也许不幸，人们并没有改变现状的想法。书中所写的这种致人麻木的贫困和其中穿插的思考，几乎是解构极权主义的前奏。
“贫穷是一种专制，它培养自己的奴隶。”，正因我同意这句话，我不认为奥威尔在回到欧洲后到二战爆发这一大阶段的作品与战后他的两大反乌托邦作品脱节。Victory Mansions惨淡的形象，怎么看都像是圣·塞浦里安学校（见《如此欢乐童年》）或是巴黎金鸡街贫民窟糟糕的住宿环境在1984那个时空的折射。也正是有作者在各国丰富经过真诚体验得到的经历，才沉淀出在虚构时空下的那种真实笔触。奥威尔的反极权思想习惯性地被西方在冷战中用作对抗苏联邪恶帝国的意识形态武器，他的民主社会主义追求和对殖民主义、垄断资本主义的批判和解构却被有意无意地忽略。如果没有缅甸的经历，他不会到巴黎伦敦流浪。如果没有巴黎伦敦的流浪，他不会走上维冈码头的“朝圣之路”。如果没有维冈对他的冲击，他不会参与西班牙内战。而最后，也正是西班牙的经历令他转折。唯一不变的是这位作家始终没有放弃自己“圣徒”般的追求。

摘录：

"At present I do not feel that I have seen more than the fringe of poverty. Still, I can point to one or two things I have definitely learned by being hard up. I shall never again think that all tramps are drunken scoundrels, nor expect a beggar to be grateful when I give him a penny, nor be surprised if men out of work lack energy, nor subscribe to the Salvation Army, nor pawn my clothes, nor refuse a handbill, nor enjoy a meal at a smart restaurant. That is a beginning."

——Chap XXXVIII

“目前我并不觉得我看到了比贫困的冰山一角更多的部分。但我还是能指出在艰辛时日中实实在在学到的一两样东西。我不会在觉得流浪汉就是醉醺醺的恶棍，不会期望乞丐会因为我给他一便士而感激涕零，不会为失业的人的萎靡不振而吃惊，不会再向救世军捐款，不会再典当衣服，不会再拒绝传单，不会在高档餐厅吃饭。这就是开始。”

"Within certain limits, it is actually true that the less money you have, the less you worry."

——Chap III

“在一定程度下，你的钱越少你所担心的就越少，这是真的。”

"Hunger reduces one to an utterly spineless, brainless condition, more like the after-effects of influenza than anything else. It is as though all one's blood had been pumped out and lukewarm water substituted. "

——Chap VII

“饥饿使人进入全身瘫软，大脑空白的状态，像是流感之类的病的后作用。就像一个人的血都被抽空，用微温的水代替了。”

"Fate seemed to be playing a series of extraordinarily unamusing jokes."

——Chap VII

“命运像是给人开了一连串特别不好笑的玩笑。”

"Beggars do not work, it is said; but then, what is work? A navvy works by swinging a pick. An accountant works by adding up figures. A beggar works by standing out of doors in all weathers and getting varicose veins, bronchitis etc. It is a trade like any other; quite useless, of course — but, then, many reputable trades are quite useless."

——Chap XXXI

“人们说乞丐并不工作；但是，什么是工作呢？工人的工作是挥动镐。会计的工作是计算数据。乞丐的工作是无论天气在户外站着，从而患上血脉肿胀、支气管炎等等病。这和其他的工作没什么两样；很无用，当然——但，很多体面的工作也都是无用的。”

"He was an embittered atheist (the sort of atheist who does not so much disbelieve in God as personally dislike Him), and took a sort of pleasure in thinking that human affairs would never improve."

——Chap XXX

“他是那种怨恨的无神论者（那种不太相信上帝，个人来说厌恶上帝的），他相信人类不会有改善，并为此感觉优越和欣慰。”

Twitter实时同步到新浪微博

寒假写的这个程序。一开始天真地打算通过纯Python来实现，或者说不借助Twitter和新浪微博的官方API。整个程序的机理可以解释为，每隔一定时间间隔，从Twitter上爬取新的推文（Tweets），筛选出这一段时间内新发的推文，在新浪微博上发送。一开始因为我不打算用官方的API，所以用的是模拟新浪微博登录后调用发送的请求。

新浪微博模拟登录
微博有三个登录的站点，一般的网页版（weibo.com），智能手机访问的网页版（m.weibo.cn）和传统手机版式（weibo.cn），通过Chrome的开发者工具，我们会知道这三个机制在登录时浏览器向新浪发送的报文内容不尽相同。PC端网页版的登录最复杂，其密码和用户名均经过加密，而且在搜解决办法的时候，一些以前可行的方法都失效了，原因是新浪会改变密码的加密方式，目前使用的是RSA方式。
相比之下另外两个站点的登录方式则更简单，因为密码和用户名是不通过加密直接POST请求的，用urllib组织好报文发送即可。响应报文的Cookie可以用来后续的操作（发微博，点赞等等）。
如果只是一段时间的任务，最简单的方法是在发送报文的header中直接设置你的Cookie字段，只要用开发者工具查看你登录或是其他和浏览器交互的报文，就可以看到你的Cookie。因为要让其持久工作，有生存时间的Cookie不在考虑范围。
weibo.cn登录后只能发送文字，而m.weibo.cn支持六张图片的发送，其机制是先调用上传图片的请求，将文件上传到新浪的服务器，上传图片的请求会返回包含图片pid（或pid列表）的响应报文。微博在正式发送时连同正文和pid发送。
上面所述的办法我最终都没采用，因为模拟登录有时需要验证码（验证码的作用就是挡住我们这些机器人程序），我们需要一个能“长治久安”的办法，终究得用新浪微博提供的API。

新浪微博API
看《挖掘社交网络》这本书的时候，里面在Twitter等网站上做信息获取也是直接使用官方的API。官方API优势很明显，在于方便，但也有很明显的缺点，比如频次限制，这里便有新浪微博对API频次的说明，微博的API还有等级限制，你要有获得更多数据的权限，或是增加你的频次上限，都需要通过增加认证信息或是付费的方式（一如SAE的风格）。我同步的NBA的Twitter帐号便因为发送频率过高（NBA的更新频率的确很高）而被帐号冻结。
这里讲一下一个很好的应用IFTTT。新浪微博是第一个与其建立连接的国内社交网络，它支持很多样的社交应用网络，用户可以自定义自己的Recipe（其最喜欢举的例子便是“如果明天下雨，发我一条短信”，利用天气预报的信息）。不少牛人，诸如BYvoid和禅叔伍嘉贤等等利用它来同步自己的Twitter到新浪微博。IFTTT的功能还可以很多样。
IFTTT的帐号可以很高频地发送信息，原因就是因为他们申请了较高的API级别。
新浪微博没有官方提供Python的SDK，而是推荐了廖雪峰所写的SDK。SDK的作用是进一步提供基于API的接口，这样一来程序可以更好写。转换短链接的接口很简易，只需要提供你的appkey和要转换的url即可，因此我将这部分放到了Twitter预处理的那部分。
sdk的weibo.py定义的一个很有用的类是APIClient，新浪微博的读写API均需要通过OAuth2的方式，也就是不能通过简单的用户名和密码。我们在微博授权应用访问我们的帐号时，都会出现一个认证页面，实际上就是OAuth机制的其中一环。
正因如此，我为了让程序能自动发送微博，也基于SDK进行了改进，因为SDK仍然需要一个认证页面授权的过程，我的程序则通过爬虫实现自动授权。
关于OAuth及其细节可以看阮一峰的这篇博文。

Twitter这边
Twitter的信息获取实质很自由，因为不需要登录就可以访问一个人的主页。在本地测试时使用urllib2模块设置代理的函数，使程序通过GoAgent进行爬虫。

proxies = {'http': '127.0.0.1:8087', "https" : "https://127.0.0.1:8087"}
proxy_support = urllib2.ProxyHandler(proxies)
opener = urllib2.build_opener(proxy_support, urllib2.HTTPHandler)
urllib2.install_opener(opener)

Twitter的开发者帐号我无法申请，因为发现他们无法向中移动的号码发送验证码。无法使用Twitter API中的user_timeline获取推文的方式带来一个问题，如果是从首页进行爬虫，一条转发的推文（Retweet）并不包含转发的时间。如果更新间隔是五分钟，那么一条三分钟前转发的几天前的推文将被判断为几天前的内容而被筛掉，我最终没有解决这个问题的打算。（Retweet和新浪微博的转发很不相同，你不能附加任何信息，新浪微博一条转发可以相当于两条——你转发所说的话和原微博的内容）

部署
代码部署在Google App Engine上，利用GAE的cron服务可以很方便地实现定时执行，这里便引入另一个问题，GAE的cron服务，每一次的计时是在一次任务执行完毕后才开始计算的，也就是说间隔N分钟的任务，如果执行用了K分钟，那么下次检查更新将会跳过前面的时间间隔空隙。而IFTTT的同步频率比较快，却会出现一条动态被发送两次的问题。因此我的选择仍然是不理会这个误差。
这个程序的源代码可以在我的Github上看到。

这个是我同步的Techmeme帐号：
http://weibo.com/u/5521000534

在Heroku为墙外博客搭建墙内可访的爬虫代理

计算机网络课程在讲HTTP协议的时候介绍了Web Proxy（代理）的原理，可以用这幅图解释

这里要讲的代理工作原理和Proxy是一样的，不同之处在于不涉及任何的缓存。Client访问我们所搭建的Proxy服务器的时候，Proxy通过爬虫到我们的墙外博客爬下HTML页面直接返回。

Django域名转换
Django是一个很好的Python后台框架。在MVC框架下，Django通过定义视图模块（通用命名是views.py）来为网页指定view部分，可以结合模块使用。

Django通过根目录下的manage.py文件来与服务器进行交互，例如我们在本地启动一个Django服务器，使用的是命令

python manage.py runserver

我们可以修改manage.py内定义的默认模块来指定初始的模块，例如我们将项目主体的文件都放到了gettingstarted的目录，修改manage.py的设置：

os.environ.setdefault("DJANGO_SETTINGS_MODULE", "gettingstarted.settings")

向其指定设置文件为gettingstarted目录下的settings模块。
Django的url配置用于定义项目中url模式与其对应视图，定义在urls.py中
默认的urls.py是这样的：

from django.conf.urls.defaults import *

# Uncomment the next two lines to enable the admin:
# from django.contrib import admin
# admin.autodiscover()

urlpatterns = patterns('',
    # Example:
    # (r'^mysite/', include('mysite.foo.urls')),

    # Uncomment the admin/doc line below and add 'django.contrib.admindocs'
    # to INSTALLED_APPS to enable admin documentation:
    # (r'^admin/doc/', include('django.contrib.admindocs.urls')),

    # Uncomment the next line to enable the admin:
    # (r'^admin/', include(admin.site.urls)),
)

urls.py文件中的urlpatterns是一个元组，通过正则表达式匹配url，然后指定其映射到的视图模块。这个代理的urls.py很简单。

urlpatterns = patterns('',
    url(r'^(.*)$', 'gettingstarted.views.getPageContent', name='getPageContent'),
)

我在这里定义一个会捕捉整个url后缀的正则表达式，在映射时，Django会将正则内捕捉到的组作为参数传给你定义的模块，例如我在views.py内定义的getPageContent函数：

def getPageContent(request, postfix="/"):
 url = 'https://zhengsuizhan.blogspot.com/' + postfix + "?m=1"
 content = urllib2.urlopen(url).read()
 content = content.replace("http://zhengsuizhan.blogspot.com/", "http://zhengsuizhan-blogspot.herokuapp.com/")
 content = content.replace("?m=1", "")
 return HttpResponse(content)

这个函数将后缀拼接成url后通过urllib2模块进行访问，因为我没有做特别处理，直接通过Django的HttpResponse函数转换为Http响应信息返回。这样以来，访问云平台上的一个形如
http://zhengsuizhan-blogspot.herokuapp.com/xxxx的url，代理服务器先通过url映射规则，将正则捕捉到的组内容"xxxx"传参给getPageContent函数，getPageContent访问blogspot上对应页面http://zhengsuizhan.blogspot.com/xxxx，处理成响应报文返回。这样便能实现访问代理时url的格式和原网站上的格式一致。（我在这里让代理访问手机版页面）
urls.py的作用很像PHP项目中的.httaccess，不过感觉写起来更顺手。
关于Django的更多，请参考Django Book或官方文档。

选择云平台
现在人们能够申请的云平台很多。但因为我是为自己的Google Blog搭，Blogspot自从零八零九后的互联网寒冬后就一直被GFW封禁，所以我并没有考虑国内企业的云平台BAE或是SAE，一来怕我的应用受到审查，二来不了解新浪或是百度的服务器能不能翻墙。这使得选择空间变小。
最早用过的云平台是新浪的Sina App Engine（SAE）。SAE限制流量，当你注册初始的云豆用尽后就不能被访问，需要通过金钱购买，百度的BAE相比之下功能更好。
从Instagram在上年九月阵亡开始，我意识到墙选择目标的逻辑其实很简单：“不听我话的就是目标”。我在红帽子（Red Hat）的云平台Openshift上给这个博客搭建了代理站，才发现Openshift上搭建应用对应的域名rhcloud早就进了黑名单。同理的还有Sourceforge旗下对应的用户自建站域名。GAE更不用说了。有境外网站选择使用亚马逊的云服务为自己的网站搭建镜像。他们认为寄生在外企的基础服务上，GFW要墙掉整个站点的成本太大（亚马逊的云服务有一定的国内用户量）。但既然GFW能做到墙掉维基百科的某条词条，或是阮一峰博客的某篇博文，他们就能在不影响AWS整体业务的情况下卡掉某个不和谐的应用，因此我仍认为这种依附的自由是伪命题。
回到GFW逻辑的话题，为什么sourceforge和github这类看似人畜无害的程序猿社群网站都会被盯上（Github在2013年曾被下手，后因受到IT业人士广泛关注而解除，sourceforge早在2002始就被多次下手）？很直接的一个原因就是因为这类网站里没有直接听命的审查员，因此就有可能被用于发布他们Undesired的内容（巨火一直通过Github公布他们设置的最新镜像地址）。这个逻辑实际上能解释很大部分境外网站进入黑名单的原因（Instagram，Flickr，Wordpress等等）
我最后选择了墙内尚能访问的Heroku云平台，这家创业公司已被Salesforce收购。据说名字来源于Hero和Haiku（俳句，一种日本诗）的拼接。有趣的是Ruby的发明者松本行弘也加入了这个公司。

源代码
这个小程序的源代码在我的Github上可以看到。

题外话，一些墙外网站的用户，在他们使用的网站阵亡后认为在这些网站上发布不和谐内容的人要负责任，有时甚至是骂。不知道大家怎么看。记得以前中学玩一款被封禁的游戏《命令与征服：将军》，贴吧上一些用户会骂发布不和谐内容的用户怕他们导致封吧，当然吧主会很快删帖。

政治坐标，可视化的政见表示

无论政见如何，又或者关心政治与否，我想一个无法改变的事实是，生活在社会上的任何人无法摆脱政治对他/她的影响。或者如奥威尔在《政治与英语》所说的：

我们这个时代，是不存在所谓“超然于政治之外”的事情的。

政治上左与右两个概念，在不同的国家话语和意识形态中有不同的意思，有时甚至可以很荒诞地完全相反。因为本篇只想集中介绍政治指南针这一网站和测试，在这里只梳理在当今西方传统话语下的划分。
首先需要说明的是，很多情况下，人的思维惰性导致问题事物的简单二元化。左与右就是一种二元化衡量。在极权制度下，一个负面的二元标签代表着政治不正确。在当今的中国，“反动”是其中一个这类标签。
即使没有标签化，我们也可以发现，左与右用来判断一个人的政治立场，实在是太不足够。支持非暴力的甘地主义者，和支持高度中央集权的斯大林主义者，都是左派。认为国家应该最小限度干预经济的自由放任主义的弗里德曼支持者和追求专制的纳粹主义者，都是右派。但我们都会觉得弗里德曼支持者和甘地主义者的共同点多一些，而纳粹和斯大林主义更像是一丘之貉。同属极端保守的原教旨主义者的基督徒和穆斯林相遇，不会坐下来好好谈谈而是干脆互相扔炸弹。
因此如果要比较准确地描述一个人的立场，更好的办法是用政治流派的名词，比如“民主社会主义”、“古保守主义”，“马克思主义”等等。这样做只是一种必要的具体化。

财富分配上的分野
左右之分起源于法国大革命时期。巴士底狱被攻陷后，1791年的法国制宪议会上，温和派的保王党人都坐在议场的右边，而激进的革命党人都坐在左边。这个时候法国的左右是以旧君主政权的态度来区分的。大部分中国人从中学历史课本中所了解的左右定义——左是激进，右是保守（在这里这两个词均无感情价值评判），实际也起源于此。
但单凭“激进”与“保守”，或者说凭借对现政权或前政权的态度来界定，太有局限性。宗教原教旨恐怖主义的支持者，比如伊斯兰教的ISIS和基督教的3K党，他们主张无疑是激进的，但动机却是基于要保护他们眼中教义的纯洁性，从这个意义上又是保守的。用保守、激进两个名词区分缺乏普适性。事实上西方语境下左右的概念经过演变，大体可以概括成：

左派：支持社会平等，反对阶级分化

右派：认为社会分层有其自然性和不可避免性

可以说这个意义上的左右，围绕的是经济议题，或者更具体：财富的分配问题。

斯大林主张公社经济，不允许私人拥有财产，国家的经济通过计划来发展而不是市场，并对沙俄时的富农等阶层进行改造或肉体消灭。而甘地在反对英帝国殖民的同时，主张印度的经济地方自理，反对诸如食盐的专营导致贫富悬殊。他们的共同点是主张财富的更平等分配。希特勒的社会达尔文主义倾向认为弱的阶层不应该受保护，打压自治工会的存在，甚至将这种对弱者的伤害到种族层面，即消灭劣等种族。弗里德曼的自由放任主张则是认为不应该由政府来进行福利政策去补助贫弱，或是通过限制工商的政策限制企业的经济自由。他们的共同点是认为财富分配的不平等是自然或应当提倡的。

政府权力上的分野
前面提到的四个用以比较的例子，斯大林主义和甘地主义的区别，与纳粹主义和自由放任主义的区别实际是类似的。区别在于其所认同的国家（State）的理想权力范围。斯大林和希特勒这两个臭名昭著的极权统治者自然都是追求权力的最大化，而弗里德曼和甘地都反对这样的权力。我们只要在上面的横坐标基础上加一个纵坐标，即可衡量这一维度上的分野。

有了这一轴，便成为一个二维的坐标系。启蒙时代的不少著名思想家，比如洛克，孟德斯鸠，潘恩等等都是倾向于自由主义的。

至此为止，我介绍的都是政治指南针这一网站的测试。关于这个测试的更详细说明，我在译言网上翻译了这一网站的分析部分。上两幅图也是译自网站的图解。完整的翻译版问卷在中国政治坐标系这一测试上有翻译。想测试的话建议对照着翻译在原网站上完成。

第三维，文化态度的分野
中国政治坐标系这一测试最早在北大未名上出现。它的问题是基于中国的语境下的。与政治指南针不同，这个测试引入了第三个维度，也就是文化上的维度，因此你会见到一些关于传统文化，如中医，周易上的问题。在政治指南针中，虽然没有添加第三维，但仍有属于文化意义上的问题，比如测试者在占星学、堕胎、同性恋的看法。我想政治指南针的设计者实质是将这一类问题（文化上的开放与保守）也归结到了两个坐标轴上。在美国，文化上的开放（LGBT平权，大麻合法化等等）伴随着七十年代反越战运动的记忆，多少和左派的社会主义主张挂钩。但简单地将支持财富公平分配或是自由主义和支持文化开放做正相关，也许是一种简单化处理，个人倾向于用三个维度的衡量。恰恰是一些左派国家或人士，比如前苏联和甘地，主张文化上保守的禁欲（关于这点可以看看李银河的文章《共产党为什么会反性禁欲》）
之所以两个测试在文化上采用不同的问题，也跟传统文化有关。美国的基督教传统下，自然在堕胎和同性恋问题上有更多的争议（有基督徒根据教义主张堕胎是杀害生命，同性恋违反了男女结合的原则）。而这两个问题在中国往往不是争论的核心（堕胎与否在计划生育下已经不是主流的伦理争议，同性恋平权在中国仍然不是主流问题）。我想这就是中国政治坐标系的设计者选择了中医，国学教育等等问题的原因。实质上两者的问题都是区分文化上的开放和保守主张。

“没有真正的苏格兰人”——诉诸纯洁的谬误
没有真正的苏格兰人（No true Scotsman）或诉诸纯洁（appeal to purity）是一种非形式谬误。当原来的普遍宣称遇到反例时，这种谬误提出一个理想的标准以为其辩护的论证方式。比如一些希望人们不因为恐怖主义而歧视穆斯林的人会说，ISIS不是真正的穆斯林。又或者像美国的共和党中，茶党（Tea Party）运动的支持者会说某某共和党人只是名义上的共和党（RINO，Republicans In Name Only），从而展开他们的批判。
如果你隶属于某某政党，出于对你自己看法的坚持，你也许在感情上真的会认为某某党员不配做党员。如果你是一个教徒，这种捍卫你教派的纯洁性的冲动往往会更强烈。最近被一些舆论集中批判的贺卫方因为是中共党员，其针对点也直指他的党员身份。
在党国的话语体系下，“社会主义”已经特指马克思所主张的“科学社会主义”，因此现存的“社会主义国家”只有5个。政治正确地说，其他国家都实行着资本主义。讽刺的是，印度的宪法序言中，第一句便是：

我们印度人民已庄严决定，将印度建成为主权的社会主义的非宗教性的民主共和国。

或是卡扎菲时期的利比亚国名：

大阿拉伯利比亚人民社会主义民众国（Great Socialist People's Libyan Arab Jamahiriya） 

又或纳粹党的全称：

国家社会主义德国工人党（德语：Nationalsozialistische Deutsche Arbeiterpartei）

简单将社会主义限定为马克思主义，实质也是一种诉诸纯洁的谬误。当今现存国家，存在国名中有“社会主义”一词的（如斯里兰卡），有将“社会主义”写入宪法的（如印度、叙利亚），也有社会主义政党甚至马列主义政党成功通过选举成为执政党或执政联盟成员的。社会主义这一个政治学名词，其表达的准确性很低。上图中在红色，蓝色和绿色象限都能找到自称社会主义的思想（马克思主义及其众多分支可以归于红色象限，民主社会主义和社会民主主义可以归于绿色象限，国家社会主义（纳粹）和第三世界独立浪潮后一些国家的民族社会主义可以归到红色与蓝色象限的中间地带）。很多中国人局限于“社会主义”和“资本主义”之分，实际也是过于简单的二元化错误。（关于这点，举所谓“一国两制”的例子足矣）
同样地，“资本主义”作为一种经济形式，也不能准确地描述一种意识形态。美国现任民主党总统奥巴马从竞选至今都被不少保守主义和共和党对手标签为“社会主义”过。

宣传海报，将奥巴马与希特勒和列宁并列

将奥巴马丑化为共产党

丑化为纳粹支持者

奥巴马不可能在是一个共产主义/纳粹主义者的情况下还收到那么多的竞选经费。如此标签的人认为奥巴马不是“真正的”资本主义支持者，恰恰犯了诉诸纯洁的谬误。 题外话，上面的海报体现出了美国传统保守主义对“社会主义”一词的警惕和反感。至于为何奥巴马会被说成社会主义者，我想和奥氏医改以及他竞选时承诺的富人增税等亲基层主张有关。

个人倾向
我在这个测试的结果是这样的：

我最喜欢的作家英国人乔治·奥威尔自认是一个民主社会主义者。在政治学上我所阅读过的著作很少，所以我不认为可以宣称自己是什么主义，但我想可以说是自由意志社会主义与古典自由主义的混合。

最后附上一些我很认同的语录：

Those who expect to reap the blessings of freedom must, like men, undergo the fatigue of supporting it.

那些想收获自由所带来的美好的人，必须像真正的人那样，要承受支撑自由价值的艰辛。

托马斯·潘恩, 《美国危机》

That government is best which governs least.

管得最少的政府是最好的政府。

亨利·梭罗, 《论公民的不服从》

Power tends to corrupt and absolute power corrupts absolutely.

权力总倾向于腐败，绝对的权力绝对地腐败。

阿克顿勋爵

It is the fundamental duty of the citizen to resist and to restrain the violence of the state.

反抗与限制国家的暴力是公民的基本义务。

诺姆·乔姆斯基

基于划分的聚类——基于形心的K均值，K众数和K中值

前面提到分类（Classification）和聚类（Clustering）的区别。作为无监督学习，聚类在生成聚簇（Cluster）的时候，其聚簇数甚至是不能确定的。在做美赛D题的时候，我们最后使用了K均值的算法来为国家进行聚类，我写的是Python的代码。
一组属性组成的数据记录可以用一个N维向量表示。我们假若用这样一幅二维图像表示数据集，聚类便是努力使相邻的样本聚合到同一个簇。

图中所示的情况当然是很理想的，样本很明显地分成四个聚合。实际情况很可能是这样的

这幅图的样本分布就没那么明显了

《数据挖掘》一书介绍了在聚类分析中的四类方法。这里要讲的三种都属于基于划分（Partition）的方法，对于要生成的簇数k，划分会生成k个簇（不排除空簇），使得同簇内的对象相似，而不同簇的相异。

形心
我们用一个簇的形心，类似一个抽象几何体的中心点来表示一个簇，则属于该簇的所有点与其形心都有一个距离值，一个簇的质量（类似物理上的质量概念）可以用它的簇内变差（每个样例点与形心的欧几里德距离）度量，定义：

E即是对每个簇求其质量后各簇的质量总和。基于这一概念的划分方法不同之处其实在于如何定义形心这一概念。一个好的聚簇方案，其质量一定是尽可能小的，也就是说，每一个样例点到其簇的形心都尽可能小，以确保其被分配到最优的簇。然而枚举这些方案的复杂度是很高的，我们需要采用贪心策略的做法。

K-均值
K均值（K-Means）的算法把簇的形心定义为簇内点的均值。伪代码如下：

function K-Means-Clustering(examples, k)
returns a set of k clusters
    select k initial centroids from examples randomly //选取初始点
    do
        for instance in examples
            instance.cluster = cluster with argmin(dist(ci, instance)) //选择最近形心
        for c in clusters
            c.ci = average(for e in c) //更新形心
    while nothing change any more
    return clusters

这个过程是迭代的，首先随机选出k个样例作为k个簇的起始中心点，然后为每个对象分配到最近（最相似）的簇。这个算法循环地努力优化簇内变差，每一次的迭代，中心点都会被重新计算，然后下一次分配。
这个算法很有启发性，但也有很明显的局限。因为其起始点的随机性，比如说第一幅图中四个明显区分开的聚簇，如果我们初始选择的中心点有几个都在同一个聚簇，那结果会很难看。又或者如下图的例子：

左边是理想的方案，但若随机选取的初始中心在两个簇的边界处，最终结果有可能会出现部分边界交叉的情况（交叉是相对于理想方案来讲的）。正因K均值的方法受其初始点的随机性影响，所以往往在运行时会在多次结果中取折衷的方案，又或者是利用一些先验知识选择中心点以替代随机。美赛时我们对国家的数据进行聚簇的最终方案，也是先选择了几类国家作为初始中心点。看到一篇有趣的博客是对亚洲杯各国的数据进行聚簇的，有兴趣的可以看看。【哈哈哈哈哈哈哈国足
编程细节上如何结束迭代？我们都知道计算机在浮点数运算的时候精度是一个很大的问题，什么条件下判断聚簇方案在经过一次迭代后没有发生变化从而结束循环？《集体智慧编程》一书中给出的方案是为每个样例记录其上一次分到的类，若一次迭代中没有任何样例的聚簇发生变化，则终止。在赛时我还没看这本书，用的是记录每次中心点的位置，当中心点没有发生变化（具体表现是前后的改变距离小于一个很小的浮点数）时结束。现在看来是前一个方法准确。
对象总数为n，k是簇数，t为迭代次数，则K均值的复杂度是。局限性很明显，K均值对离群点和噪声敏感。因为是计算均值，也就是说考虑中心点的时候，离群点和其他点有着同等的贡献率。过分的离群值会严重扭曲理想的均值。

K众数
当我们用向量表示一个样例，其每个维我们假定为连续值。那么当我们需要面对离散值，或者说标称属性呢？离散的情况使得均值无法计算，这时候我们采用计算众数作为中心点。同时欧几里德距离要换成标称距离，也就是转换离散值为连续值。通过统计频率的方法来更新。决策树分类时美国国会投票的例子就可以用这个方法。我的转换方法是yes和no对应正负一，unknown对应0。

K众数对美国国会数据聚类代码：

#K-mode
import random
import copy
from math import *
class instance():
    def __init__(self, party, votes):
        self.party = party
        self.votes = votes
        self.classification = None
dataFile = open('dataset.txt', 'r')
datas = dataFile.readlines()
database = []
for line in datas:
    line = line[:-2]
    attrs = line.split(',')
    member = instance(attrs[0], attrs[1:])
    database.append(member)
def normDistance(vector1, vector2):
    total = 0
    normDict = {"y" : 1, "?" : 0, "n" : -1}
    for i in range(0, len(vector1.votes)):
        total += pow(normDict[vector1.votes[i]] - normDict[vector2.votes[i]], 2)
    return sqrt(total)
def kMode(dataSet, k):
    selectIndex = [2, 8]
    centroids = []
    for i in selectIndex:
        cent = copy.deepcopy(dataSet[i])
        centroids.append(cent)
    clusterChanged = True
    times = 0
    while clusterChanged:
        clusterChanged = False
        times += 1
        for record in dataSet:
            minIndex = 0
            minDist = 1000000000000
            for i in range(k):
                dist = normDistance(centroids[i], record)
                if dist < minDist:
                    minDist = dist
                    minIndex = i
            if record.classification != minIndex:
                record.classification = minIndex
                clusterChanged = True
        counter = []
        for i in range(k):
            init = []
            for j in range(len(centroids[0].votes)):
                init.append({"y" : 0, "?" : 0, "n" : 0})
            counter.append(init)
        for record in dataSet:
            for i in range(len(record.votes)):
                counter[record.classification][i][record.votes[i]] += 1
        for i in range(k):
            for j in range(len(centroids[i].votes)):
                maxVote = 0
                for op in counter[i][j]:
                    if counter[i][j][op] > maxVote:
                        maxVote = counter[i][j][op]
                        maxOption = op
                centroids[i].votes[j] = maxOption
    print "iteration time: %d" % times
    return centroids
cen = kMode(database, 2)
for i in range(2):
    print "cluster %d" % i
    stat = {"democrat" : 0, "republican" : 0}
    for record in database:
        if record.classification == i:
            stat[record.party] += 1
    print stat
    print ""

聚类结果还是说得过去的。。。=-=

K众数（K-modes）实际只是K均值的一个变体，其思路是一致的。在混合数值和标称值的数据中，两种方法实际可以结合使用。

K中值
不要和基于代表对象的K中心点混淆。K中值这个算法虽然《数据挖掘》一书中没提到，但大家在发现前面的问题后其实很容易可以想到。在数字图像处理中，类似的情况是椒盐噪声的去除，椒盐噪声一定程度上可以类比成离群值。如果我们使用均值滤波来去除，其效果一定没有中值滤波好，正是因为均值滤波中噪声会对最终结果有一定贡献率，而中值则是直接从样本中选取样例。
K中值在重新计算中心点的时候，使用的是曼哈顿中值，即

新中心点的每一维的值，都是其簇内样例中对应维的中值。K中值能够减少K均值的敏感性。

密集恐惧症者表示完全受不了某些聚类的效果图。。。。。。。。。。

关于决策树的更多——CART

上篇讲了ID3的后继C4.5，这篇讲讲有略大不同的（Classification and Regreession Tree，分类回归树）。它的特点是二分递归，产生真正的二叉树（这才是真正的Dichotomiser.。。。。=-=），也就是说无论是连续属性还是有两个值以上的离散属性，CART都只会把它们分成两个分支。

基尼指数
CART不使用熵的思路来衡量属性划分度量，而是使用了基尼指数（Gini Index）。一开始以为这是从经济学上拿来利用的概念，后来看来大概只是两者来自同一思路。维基百科上对CART的这一种度量称为基尼不纯度（Gini Impurity）。
经济学上，基尼系数用来衡量地区的收入不平等程度。在CART中它用来衡量训练集在某属性上的不纯度，定义：

划分连续属性称为二值属性的方法在讲C4.5时已经说过，这里只说如何划分离散属性。对于一个离散属性A，假设其值域为集合, 其幂集包含了它的所有子集。不考虑空集和其本身的情况，一共有个子集，又因为划分时，知道其中一个子集，另一个就是它的补集，划分方案有个，枚举划分方案有随集合大小指数增长的复杂度。
对于枚举出的对离散或是连续值的划分方案，我们计算其基尼系数：

我们选择基尼系数最小的划分方案来将非二值属性二值化，然后通过比较基尼系数，选择最小基尼系数的属性，也即分化程度最小的属性。

选用熵和基尼系数有何不同，我想这样一幅图能给出答案：

两者都在二值属性均分的时候达到最大值，但它们逼近最大值的速度变化不同，但在应用上有何区别上不得知。

代价复杂度
在剪枝问题上CART也是不同的，CART后剪枝使用的是代价复杂度（Cost Complexity）这一概念，对于一棵子树，其代价复杂度是这棵子树的错误率和叶子节点数的函数，有时表示成。类似悲观错误率，比较剪枝前后的代价复杂度，若复杂度变小，则剪去子树。剪枝的方法是自底向上对内部节点进行判断。

决策树的局限
前剪枝和后剪枝的结合使用能减少过拟合的现象，但在数据量大时还是难免防止树过大的情况，我们经常能遇到重复或是复制的问题。
重复（Repetition）即是从根节点开始的一条路径中，连续出现好几个对同一属性进行判断的节点。比如连续属性A的选择度量很大，那么我们经过第一次分裂分成了两个区间后，很有可能接下来的属性选择仍然选择的是A。
复制（Replication）是书中存在重复的子树，例如根据属性A划出两个子树，这两个子树又都按照B属性划分，便有了一毛一样的两个分支。
上面的两种情况在作业中也的确遇到了，也就是我们还没引入熵阈值的时候，树的深度不堪入目，那么可想而知更大的数据集这类问题大概更严重。
CART的一个解决办法是考虑多元划分，基于属性元组，而不是单个属性来划分，相当于构造出了新的属性。虽然教材上没提到，但我想到的一个思路是先将属性用类似机器学习中主成份分析（PCA，Principal Component Analysis，这个算法也是通过美赛第一天想思路时知道的）的方法，将多维的向量在不大量减少其信息值的前提下降维。
教材中提到的另一决策树局限是当数据集大到无法由内存装载的情况，如果只能从存储中分页读取训练集，那么我们无法同时掌握整体数据集的信息。两个思路能帮助解决，一是离散化连续属性，从而减少编码的空间，而是对数据进行抽样，而不利用全部的数据，当然，这就涉及到了抽样的代表性。这两个思路都很容易想到。还有诸如雨林（Rainforest）和树构造自助乐观（BOAT）等更厉害的算法，不过也是to be study了。

分类作为一个经典问题不止决策树一种方法，下一个想看的是贝叶斯分类。

关于决策树的更多——C4.5

在写前面关于AI作业的决策树笔记的时候接触了CART及C4.5两个决策树算法的名称，最近在《数据挖掘》这本教材上看到了它们的介绍。今年的ICM D题也让我更多地了解了数据挖掘中分类（Classification）和聚类（Clustering）的知识，虽然我们队最后没用上决策树的算法
数据挖掘中的分类和聚类的区别可以大体概括为有监督（Superised）学习和无监督（Unsuperised）学习的区别。虽然它们都是对数据进行划分（partition）的算法，但分类在学习阶段（也就是接受训练集训练）的时候，其数据库是包含了类标号（class label）的，用以指定某一条数据记录属于哪一个分类，而聚类的数据是不包括类标号的。好比前篇中的例子，用于训练判断党派的模型的原始数据中，包含了每一个议员的实际所属党，我们根据这些来得到我们要的模型。但若过原始数据中并不包括每个议员的党派，而只是他们在各个议题上的取态，我们要根据这些数据来为他们分类，这就是个聚类问题。说到这里的确有打算试一下在数据集上试一下聚类。【题外话，最近看美剧《新闻编辑室》，对美国的党派之争有了点兴趣】
前篇已经写过决策树算法的总体算法，不同的决策树算法实际是对总体思路的不断改进，因此不再冗述通用的过程。

信息增益率
ID3，C4.5和CART使用的均是贪心，不回溯的方法。C4.5作为ID3之后继，在选择属性的时候使用的度量标准是信息的增益率而非信息增益。其定义如下：

代表的是数据集D根据属性A进行划分后的“分裂信息（Split Information）”，与ID3的信息增益不同的是，它考虑该输出的元组数相对D中元组总数的比例。
为什么需要引入这个？细心的人会发现，基于信息增益的选择时，我们会倾向于选择那些具有大量可能值的属性，比如说数据库中每条记录有其唯一的ID，若数据集中包含着ID这一属性，根据ID划分，我们能得到N（N为数据记录数）个分支，其中分出来的每个子节点只包含该ID对应的那条记录，数据集大小为1，其信息纯度为最高。根据公式，有：

id这一属性的增益值是最大的可能值。之所以根据id划分的Remainder值会为0，是因为根据id划分出来的每个数据集都有最高的集中度（纯度），但实际上这样的划分显然很无意义。增益率中对增益的归一便能解决这一问题。GainRate计算的便是属性A的信息增益和分裂信息量的比。

悲观剪枝
What's more difference? C4.5的另一大不同是其剪枝方式。
之前作业中引入的减少过拟合的剪枝方法，若数据的增益小于某个阈值视为划分停止，取其大多数值结束划分，这其实是一种前剪枝（Prepruning）。后剪枝（Postpruning）则是在整棵原始树构建出来后，在根据算法砍去其冗余枝，而不是在构建时根据算法避免冗余枝产生。
C4.5的悲观剪枝（Pessimistic Pruning）利用对一棵子树的错误率评估来判断要不要把该子树砍除。因为原始错误率是用训练集的测试结果，既然树是训练集训练出的，其错误率往往很小，因此估算时使用了悲观的方法。
设子树有S个叶子节点（决策节点），划分到这一子树的有N个测试集样例，其中错误的例子共有E个，则其乐观错误率为。根据概率论中用正态分布拟合二项分布，p的置信区间为,我们的悲观错误率便是这一区间的上界，的取值可以是0.25。
当计算得剪枝后的错误率比剪枝前低的时候，我们就用子树的叶子节点中的多数值替换整棵子树。

连续值属性
如何划分那些连续值的属性，如果将数据集中的连续值属性看作是离散值，那也将是一场灾难，因为有多少个值就会划出多少个分支。很自然我们会想到，如果要划分连续值A，其决策过程应该是这样的：

也就是我们选择一个分裂点去对连续值进行二元划分。C4.5对连续属性的处理正是基于此。假设某节点的数据集中，连续属性A的所有取值排序后为, 任意相邻的一对值的中点均有可能成为分裂点。v个值将有v-1个划分方案。 我们对于每个划分方案，计算其Remainder，则Remainder最小的是我们需要的分裂方案（还是那句，因为这样分裂两边的集中度最高）。按照分裂点分成两个区间后，连续值的问题便成为了二值问题，我们便可将这个二值化后的属性与其他属性进行比较，从而确定要拿来划分的属性。

最后一句话，这篇东西应该加“机器学习”标签还是“数据挖掘”。。。。=-=