马太效应和幂律分布是怎么回事？终于有人讲明白了
导读：描述“富者愈富，穷者愈穷”的马太效应，以及经济学中的帕累托法则，其背后的数学模型是什么？在统计学中，它们可以被抽象成幂律分布。
作者：帕诺斯·卢里达斯（Panos Louridas）
来源：大数据DT（ID：hzdashuju）
我们在城市规模中看到的模式：大多数人类居住地区的规模达不到以百万来计数，但少数地区能达到数百万人规模。在数字王国里，大多数网站的访问量很低，但少数网站的访问量非常庞大。在文学领域，大多数书籍几乎无人阅读，但少数书籍畅销异常。
所有这些都让我们回忆起“富者愈富，穷者愈穷”的现象。
在语言学中，这种现象被称为Zipf定律，以哈佛的语言学家George Kingsley Zipf的名字命名，他观察到在一种语言中第i位最常见的单词出现的频率正比于1/i。Zipf定律指出，在一个n个单词的语料库中，遇到第i位最常见单词的概率为
其中
数Hn在数学领域出现非常频繁，值得为它起一个名字——第n位调和数（harmonic number）。这个名字源自何处？它源于音乐中的泛音或称和声。一根弦以一个基波长震动，同时还以1/2，1/3，1/4，…的谐波长震动：这对应一个无穷和，当n=∞时，它被称为调和级数（harmonic series）。
由于Zipf定律给出了一个事件的概率，因此也用它命名了对应的概率分布。
在表11-1中，你可以看到一个英语语料库（布朗语料库，包含981716个单词，其中有40234个不同单词）中最常见的20个单词，其经验概率是通过统计它们在语料库中出现的次数来计算的，而它们的理论概率则是根据Zipf定律/分布计算的。简言之，我们给出了排名、单词、经验分布和理论分布。
表11-1 布朗英语语料库中20个最常见的单词及其概率和Zipf定律给出的理论值
在图11-4中，我们绘制了表11-1中的数据。注意，分布只是为整数值定义的。我们增加了一条差值线来显示总体趋势。另外注意，理论概率和经验概率并不是完全重叠。这是我们将一个数学模型应用到现实世界时必须要面对的情况。
▲图11-4 布朗语料库中最常见的20个单词的Zipf分布
当我们发现一个快速下降的趋势时，如图11-4中的趋势，就有必要检查一下，如果我们将熟悉的x和y坐标轴替换为对数坐标轴会发生什么。在对数坐标轴中，我们将所有值转换为它们的对数后绘制出来，图11-5给出了与图11-4等价的对数坐标图：对每个y我们使用log y，对每个x，我们使用log x。
▲图11-5 对数坐标轴下布朗语料库中最常见的20个单词的Zipf分布
如你所见，理论分布的趋势现在变为一条直线，经验分布看起来位于理论预测值上方一点。在大多数情况下，理论分布与我们实际观测的结果会有一些不同，而且，两个图只显示了包含前20个最常见单词的子集，因此，基于它们我们不能真正判断是否吻合。
为了观察真正发生了什么，请查看显示了布朗语料库中所有40234个不同单词的完整分布的图11-6和图11-7。有两个现象凸显出来：首先，除非我们使用对数刻度，否则图是无用的，这很好地说明了分布有多么不均匀，我们必须使用对数值，否则任何趋势都不可见；第二，一旦我们使用了对数坐标轴，理论值和经验观察结果的吻合要好得多。
▲图11-6 布朗语料库的经验分布和Zipf分布
▲图11-7 对数坐标轴下布朗语料库的经验分布和Zipf分布
在对数刻度下，我们能看清所有东西，因为Zipf定律是幂率（power law）的一个特例。幂率是指一个值出现的概率正比于此值的负指数，用数学语言描述就是：
P(X=x) ∝ cx-k，其中 c ＞ 0，k ＞ 0
在此公式中，符号∝表示“正比于”。现在我们可以解释为什么对数图是一条直线了。如果有y=cx-k，我们可得y=log(cx-k)=log c-klog x。最后一部分就是一条直线y，截距等于log c，斜率等于-k。因此当我们遇到在对数图里成一条直线的数据时，就是其理论分布可能是幂率的明显信号。
经济学中幂率的一个例子是帕累托法则，它指出80%的结果源自20%的起因。在管理学和流行的大众理解中，其含义通常变为20%的人做了80%的工作。在帕累托法则中可以证明P(X=x)=c/x1-θ，其中θ=log 0.80/log 0.20。
幂率是如此普遍，以至于在过去二十年间产生了一个研究相关现象的完整领域似乎任何事情都有幂率现象隐藏在背后。
除了在介绍马太效应时已经提到的例子外，我们还发现幂率出现在如科技论文的引用、地震震级和月球陨石坑的直径等如此不同的领域中，还有生物物种随时间推移而增多、分形学、食肉动物的觅食模式以及太阳耀斑的射线峰值强度，其中也都有幂率现象存在。
这个列表还能继续增加：一天中长途电话的数量、停电影响的人群数量、姓氏出现的频率等。
这种规律有时似乎是凭空冒出来的。例如，一个相关的定律是Benford定律（Benford's law），因物理学家Frank Benford的名字而命名，也被称为第一位法则（First-Digit law）。它指出了在很多种类的数据中数字频率的分布。
具体地，它指出，一个数的第一位数字是1的概率是30%，从2到9每个数字出现在第一位的频率逐渐降低。用数学语言表达，这个定律指出，一个数的首位数字是d=1，2，…，9的概率是
如果我们计算每个数字的概率，就会得到表11-2中的结果。表中的数值告诉我们，如果数据库中有一组数，其首位数字为1的概率约为30%，大约有17%的数会以2开头，大约有12%的数会以3开头，依此类推。
表11-2 Benford定律，给出了数字出现在一个值首位的概率
图11-8中给出了Benford定律的一个图示。看起来和齐普夫分布没有太大不同，因此我们可能想知道如果用对数坐标轴绘制的话图会变成什么样子。图11-9给出了结果，几乎就是一条直线，意味着Benford定律与幂率相关。
▲图11-8 Benford定律
▲图11-9 对数坐标轴下的Benford定律
Benford定律的广度令人震惊。它适用于如物理常量、世界上最高建筑物的高度、人口数、股票价格、街道地址等如此不同的数据集，还有很多。
实际上，它看起来如此普遍，以至于一种检测伪造数据的方法就是检查包含的数值是否不服从Benford定律。欺诈者会修改真实值或用随机值替代真实值，他们不会注意得到的数值是否服从Benford定律。因此如果我们遇到一个看起来可疑的数据集，最好先检查首位数字是否服从Benford概率。
如果我们的搜索模式反映了数据分布模式，即如果记录的关键字服从Benford定律，且我们正在搜索的关键字也服从Benford定律的话，Benford定律可能影响我们的搜索。如果是这种情况，会有更多的记录具有以1开头的关键字，对这些关键字的搜索也会更多，以2开头的关键字少一些，依此类推。
关于作者：帕诺斯·卢里达斯（Panos Louridas），曼彻斯特大学软件工程博士，现为雅典经济与商业大学管理科学与技术系副教授。在加入高校之前，曾在投资银行担任高级软件工程师。
本文摘编自《真实世界的算法：初学者指南》，经出版方授权发布。
延伸阅读《真实世界的算法：初学者指南》
点击上图了解及购买
转载请联系微信：DoctorData
推荐语：学习算法的启蒙读本，算法尽量简单，避免读者有挫败感，仅需基本数学基础和计算机常识知识。通过真实世界需要解决的实际问题来介绍算法思想，为各领域高效运用算法提供重要指南。
更多精彩回顾
书讯 |华章计算机拍了拍你，并送来了8月书单（下）
书讯 | 华章计算机拍了拍你，并送来了8月书单（上）
上新 | 迁移学习：迈向真正的人工智能
书单 | “ABCD”,未来颇具潜力的四大信息技术方向
干货 | 周志华新作《机器学习理论导引》阅读攻略
收藏 | DB-Engines 8 月数据库排名：Redis悄悄拔高，猛超Elasticsearch