sql - T-SQL 中的幂律分布

Question

我基本上需要 this SO question that provides a power-law distribution 的答案，为我翻译成 T-SQL。

我想从census provided table of names中一次提取一个姓氏。 。我想要得到与人口中的分布大致相同的分布。该表有 88,799 个名字，按出现频率排列。 “Smith”排名第 1，出现频率为 1.006%，“Alderink”排名第 88,799，出现频率为 1.7 x 10^-6。 “Sanders”排名 75，出现频率为 0.100%。

曲线根本不必精确拟合。只需给我大约百分之一的“史密斯”和大约百万分之一的“奥尔德林克”

这是我到目前为止所拥有的。

SELECT [LastName]
FROM [LastNames] as LN
WHERE LN.[Rank] = ROUND(88799 * RAND(), 0)

但这当然会产生均匀分布。

我保证，当一个更聪明的人做出回应时，我仍然会尝试自己解决这个问题。

Answer 1

当您可以从实际分布中得出结论时，为什么要满足幂律分布？

我建议您更改 LastNames 表以包含一个数字列，该列将包含一个数值，表示具有更常见名称的个人的实际数量。您可能需要一个较小但成比例的数字，例如，每个百分比的代表性可能为 10,000。

列表将类似于:
(除了问题中提到的 3 个名字之外，我猜测是 White、Johnson 等人)

Smith          0   
White     10,060
Johnson   19,123
Williams  28,456
...
Sanders  200,987
..
Alderink 999,997

名称选择是

SELECT TOP 1 [LastName]
FROM [LastNames] as LN
WHERE LN.[number_described_above] < ROUND(100000 * RAND(), 0)
ORDER BY [number_described_above] DESC

即选择数字不超过[均匀分布]随机数的名字。请注意查询如何使用 小于 并以 desc 结尾的顺序进行排序；这将保证第一个条目(史密斯)被选中。另一种选择是以 10,060 而不是零开始史密斯系列赛，并丢弃小于该值的随机抽签。

除了上面提到的边界管理问题(从 0 开始而不是 10,060 开始)之外，此解决方案以及迄今为止的其他两个响应与 dmckee' 中建议的解决方案相同对此问题中引用的问题的回答。本质上，这个想法是使用 CDF(累积分布函数)。

---

编辑:
如果您坚持使用数学函数而不是实际分布，下面应该提供一个幂律函数，它可以以某种方式传达真实分布的“长尾”形状。您可能想要调整 @PwrCoef 值(顺便说一句，该值不必是整数)，本质上系数越大，函数就越偏向列表的开头。

DECLARE @PwrCoef INT
SET @PwrCoef = 2
SELECT 88799 - ROUND(POWER(POWER(88799.0, @PwrCoef) * RAND(), 1.0/@PwrCoef), 0)

注释:
- 上面函数中额外的“.0”对于强制 SQL 执行浮点运算而不是整数运算非常重要。
- 我们从 88799 中减去幂计算的原因是，计算的分布是这样的:越接近我们的刻度末端的数字，就越有可能被抽取。姓氏列表按相反顺序排序(最有可能的名字在前)，我们需要这个减法。

假设 3 的幂，查询将类似于

SELECT [LastName]
FROM [LastNames] as LN
WHERE LN.[Rank]
     = 88799 - ROUND(POWER(POWER(88799.0, 3) * RAND(), 1.0/3), 0)

这是问题中除最后一行之外的查询。

重新编辑:
在查看实际分布时，如人口普查数据所示，曲线极其陡峭，需要非常大的幂系数，这反过来会导致溢出和/或极端舍入误差公式如上所示。
更明智的方法可能是在多个层级中进行操作，即在累积分布的三分之三(或四分之四或......)的每一层中执行相同数量的抽奖；在每个零件列表中，我们将使用幂律函数进行绘制，可能具有相同的系数，但范围不同。
例如
假设为三分之一，列表划分如下:

• 前三分之一 = 425 个名字，从 Smith 到 Alvarado
• 第二个第三 = 6,277 个名字，从 到 Gainer
• 最后三分之一= 82,097 个名字，从费里斯比到最后

如果我们需要 1,000 个名字，我们会从列表的前三分之一中抽取 334 个，从第二个三分之一中抽取 333 个，从最后三分之一中抽取 333 个。
对于每一个三分之一，我们都会使用类似的公式，也许前三分之一具有更大的幂系数(我们确实有兴趣支持列表中较早的名称，并且还有相对的频率更具统计相关性)。这三个选择查询可能如下所示:

-- Random Drawing of a single Name in top third
--   Power Coef = 12
SELECT [LastName]
FROM [LastNames] as LN
WHERE LN.[Rank]
     =  425 - ROUND(POWER(POWER(425.0, 12) * RAND(), 1.0/12), 0)

-- Second third; Power Coef = 7
...
WHERE LN.[Rank]
     =  (425 + 6277) - ROUND(POWER(POWER(6277.0, 7) * RAND(), 1.0/7), 0)

-- Bottom third; Power Coef = 4
...
WHERE LN.[Rank]
     =  (425 + 6277 + 82097) - ROUND(POWER(POWER(82097.0, 4) * RAND(), 1.0/4), 0)