趣味数据挖掘系列5：听妈妈讲过去的故事，分房与分类

中老年回顾歌曲集中有这样一首歌：“月亮在白莲花般的云朵里穿行，晚风吹来一阵阵欢乐的歌声，我们坐在高高的谷堆旁边，听妈妈讲那过去的事情……”歌词美，旋律也美，每当听到它，就仿佛回到了那如歌的岁月。

此故事的主人公小梅，在上周末也听她母亲讲了的故事。故事中没有月亮、云朵和晚风，却有关于数据挖掘中的分类技术的启示;虽然，现在不再分福利房了，但此故事既回顾历史，也解释了分类技术若干要点，有参考价值。

1 乔迁之喜引出的故事

上周末，去贺朋友女儿小梅乔迁之喜，漂亮的新房引起小梅之母一阵阵感叹唏嘘，说，当年小梅都两岁了，还带着她住集体宿舍，每逢有人探亲，同室姐妹们自动到仓库暂住几天….

　　梁山英雄排座次

后来，厂里修了一栋两层的砖楼，共18个一套三，厂里搬家动静可大了，搬动了18X6=108家，好像梁山泊英雄排座次：厂级干部搬新房，处长搬厂干之旧房，科长搬处长之旧房，副科长搬科长之旧房，老师傅搬副科长旧房，小梅家以优秀技术员的资格，比水浒传中扈三娘座次略低，从集体宿舍搬到老师傅腾出的旧房。仍令未搬家的群众眼馋，好事者按《水浒传》取外号，编排了36天罡，72地煞,有些天罡年年岁岁搬新房，难怪有些地煞月月天天想升版本。

　　半导体PN结之填空运动

雅一点的牢骚来自技术员，有人说，好像半导体三极管的“发射极-基极”PN结上电荷空穴的填充运动，其放大后输出的舆论暗流，在口耳相传中，涌动了半年。

后来，有了分房委员会，实行公开民主评议分房，才有所改观。

小梅问母亲，分房委员会是怎样分房的呢小梅母亲的故事细且长:细致中见舆情，罗嗦中有感叹，既忆苦思甜，又鞭笞时弊。故事触动了我的灵感，正好用来解释分类概念与技术，现将故事与术语混合，夹叙夹议，演绎于下。

2 分房样板：训练集与测试集

当年有句话：榜样的力量是无穷的。厂长秘书起草了一个分房样板，交给工会分房委员会，征求意见，旨在修改成一个群众满意，领导认可的样板;用数据挖掘的行话描述，要构造一个正确的、用于分类的训练数据集和测试数据集，格式如表1。

据小梅母亲回忆，当年的样板较大，列数较多，每个车间，科室，不同层次都有，还考虑了贡献、民族、党派、工种，单身，离异，…。下面是示意性格式和数据。其中有些属性(列)与分房关系不大，似有其它意图，为突出问题，这里做了一点夸张，用“身高”和“体重”来代表这类属性。

表1 职工分房计分样板（训练数据和测试数据）格式

上述表中的每一行是一个申请住房的记录，简单地用住房面积为类标签，当然，标签也可用序号，如1、2、3…等，来等价地代替。

其中，一部分作为训练集(例如 1—50号)，另一部分作测试集(例如51–150号)。

3训练集相当于教练，训练出的分类公式相当于学生

样板比较直观，但不便于推广使用，要从训练数据中挖掘出一个分房(分类)公式，数据挖掘假定真理就在训练集之中，尽管到现在还不知道它将表达陈什么摸样。

在分类过程中，训练集相当于教练，训练出的公式相当于学生, 如果教师不公正，训练出的公式就不公正。

4教考分离，测试集必须独立

如今学校都实行教考分离，同理，由训练数据训练出来的公式，要在另外一批、独立的测试数据上测试。

有时候，一个不公正的训练集和训练集会复杂得让人看不懂而暗藏玄机，委员会会举手通过，直到最后分房揭晓时，才知道某列某加权因子是为了照顾某某人。

经过认真核实讨论，能在很大程度上简明化、公正化，使训练数据和测试集基本符合群众利益，自然也会符合好领导的意图。

5第一个训练结果，删除无用的列–属性选择

　　4.1 分房委员会看出了冗余属性问题

分房委员会对这个样板初稿，提出了意见。

(a)“身高”和“体重”，以及类似的若干列，和分房没有大的关系，应该删去。

(b)“姓名”和分房没有关系，制定分房标准对事不对人，没有姓名，才好讨论。

人看出了问题，计算机能吗 能。

　　4.2 计算机程序向训练数据学习，也能看出冗余属性问题

删去这些无关列，行话称为属性选择，旨在选留那些“区分度大”、对分类贡献大的属性。事实上，包含真理的训练数据中就暗含了“哪些列应该删去”的信息.

例如，属性精简程序会比较张三与张C ，李四与李D ，王五与王E，发现身高、体重与住房无关;

计算过程是：计算身高(或体重)的分布，发现相同的身高(或体重)比较均匀地分布在不同类，说明身高(或体重)的熵比较大，或者，对住房分类的贡献不大，用行话，身高(或体重)的信息增益低。根据信息熵原理，写一道到几十行的程序，以训练数据为输入，训练数据训练机器(对称地，机器向数据学习)，使之可把信息增益低于指定阈值的属性删去。

数据挖掘中，属性选择所依据的“信息增益”(Info Gain)公式如下(较难，阅读时可跳过)。

它与列属性A的信息熵相关，依赖于训练集中的记录的分布状态。

精简属性能减少无关属性干扰，既节省时间，又保证分类精度。

6第二个训练结果，训练一个分房(分类)公式

分房委员会反复讨论，旨在生成一个加权公式：

　　Total =∑PiFi

　　其中，Pi为加权值，总分Total为应住面积。而Fi为各条件之量化值，例如，曾经有一个学校的真实的分数：工龄一年算一分，副教授算3分，教授算5分，等等;

注意，复杂的分类规则不一定能用简单的公式表达，但总可用一组形如“If….then….”的规则来表示。

经委员会反复讨论，(在计算机中，则表现为反复迭代)，当把训练集中每一行代入分房公式，得到的分房总分Total都与训练数据中对应房型基本匹配。训练过程就完成了。

计算机能模拟这一手工的、交互的过程，自动地生成加权公式，或形如“If….Then…”的规则 ，例如用决策树、回归、用遗传算法、用基因表达式编程，等等，对分房这种小规模问题，现在的数据挖掘系统几秒钟就出结果。

6 测试数据与测试

　　6.1 讨论与迭代中的校正

交互过程中，分房委员会的委员们会暗自把自己的数据代入公式， 看自己能分到哪一类。如果发现吃亏了，会大呼上当，提出反对意见。

如果分房委员会有足够的代表性，每一个委员都维护自己所代表的那一类人的利益，在讨论或计算机的迭代过程中，缩小误差，最后推出的分房(分类)公式是基本正确的。

　　6.2 测试

用独立的测试数据(本文中，第51-150号记录)，代入公式，得到的结果应该与测试数据中所分类型基本一致，否则，要重新修订公式、各项分值和加权等，在计算机中表现为继续迭代计算。

8 应用于大规模的分类

公示通过了测试的分房公式，用其计算全厂申请住房者的分类标号(等价于住房面积数)，公示。

9商品房时代的购房与分类有关吗

福利分房用了表1 那样的多属性表，如今的商品房的法则，也可视为是上述方法的特例，即用一个属性取代表1中所有属性，这个属性就叫金钱，出第n等的钱，就住第n等的房。

设有一个映射：

• f: 对社会的贡献–>收入

如果这个映射f很完整、很公平，则金钱法则相当于多劳多得，按劳分配。但是，社会太复杂，这个映射f 不太完整，还有漏洞(如贷款炒房)，也不太公平，情况就复杂了。

此外，如今一些在本单位土地上建设的商品房，对本单位职工比较优惠，因僧多粥少，还需排队，排队时，还是用类似于如表1描述的传统方式计算分类，分出排队次序。

需要说明，真正的分类技术并不像这篇科普文章这么简单。事实上，在数据挖掘中，分类是比关联规则更复杂的技术，计算机专业的硕士生、博士生也要花好几周，甚至更长时间才学得扎实。

分类还有那些重要情节它与预测又怎样联系且看下篇分解。

作者：唐常杰，四川大学，计算机学院，教授