Distribuição de lei de potência em T-SQL

Question

Eu basicamente preciso da resposta para esta questão SO que fornece uma distribuição de lei de potência, traduzido para T-SQL para mim.

Quero extrair um sobrenome, um de cada vez, de um censo forneceu tabela de nomes.Quero obter aproximadamente a mesma distribuição que ocorre na população.A tabela possui 88.799 nomes classificados por frequência."Smith" está na posição 1 com frequência de 1,006%, "Alderink" está na posição 88.799 com frequência de 1,7 x 10 ^ -6."Sanders" está na posição 75 com uma frequência de 0,100%.

A curva não precisa se ajustar com precisão.Dê-me apenas cerca de 1% de "Smith" e cerca de 1 em um milhão de "Alderink"

Aqui está o que tenho até agora.

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

Mas é claro que isso produz uma distribuição uniforme.

Eu prometo que ainda estarei tentando descobrir isso quando uma pessoa mais inteligente responder.

Answer 1

Porquê contentar-se com a distribuição da lei de potência quando se pode basear-se na distribuição real?

Sugiro que você altere a tabela Sobrenomes para incluir uma coluna numérica que contenha um valor numérico representando o número real de indivíduos com um nome mais comum.Você provavelmente desejará um número em uma escala menor, mas proporcional, digamos, talvez 10.000 para cada porcentagem de representação.

A lista ficaria então mais ou menos assim:
(além dos três nomes mencionados na pergunta, acho que é White, Johnson et al)

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

E a seleção do nome seria

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

Isso é escolher o primeiro nome cujo número não exceda o número aleatório [distribuição uniforme].Observe como a consulta usa menor que e fazer o pedido desc-ordem final;isso garantirá que a primeira entrada (Smith) seja escolhida.A alternativa seria iniciar a série com Smith em 10.060 em vez de zero e descartar os sorteios aleatórios menores que esse valor.

Além da questão do gerenciamento de limites (começando em zero em vez de 10.060) mencionado acima, esta solução, juntamente com as outras duas respostas até agora, são as mesmas sugeridas em dmckeeresposta à pergunta mencionada nesta pergunta.Essencialmente, a ideia é usar o CDF (Função de distribuição cumulativa).

---

Editar:
Se você insiste em usar uma função matemática em vez da distribuição real, o seguinte deve fornecer uma função de lei de potência que de alguma forma transmitiria a forma de "cauda longa" da distribuição real.Você pode querer ajustar o valor @PwrCoef (que, aliás, não precisa ser um número inteiro), essencialmente, quanto maior o coeficiente, mais inclinada para o início da lista a função é.

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

Notas:
- os ".0" extras na função acima são importantes para forçar o SQL a realizar operações flutuantes em vez de operações inteiras.
- a razão pela qual subtraímos o cálculo da potência de 88799 é que a distribuição do cálculo é tal que quanto mais próximo um número estiver do final da nossa escala, maior será a probabilidade de ele ser sorteado.A lista de nomes de família sendo classificada na ordem inversa (nomes mais prováveis ​​primeiro), precisamos desta subtração.

Supondo uma potência de, digamos, 3, a consulta seria algo como

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

Qual é a consulta da pergunta, exceto a última linha.

Reeditar:
Ao olhar para a distribuição real, como é evidente nos dados do Censo, a curva é extremamente íngreme e exigiria um coeficiente de potência muito grande, que por sua vez causaria overflows e/ou erros extremos de arredondamento na fórmula ingênua mostrada acima.
Uma abordagem mais sensata pode ser operar em vários níveis, ou seja,realizar igual número de sorteios em cada um dos, digamos, três terços (ou quatro quartos ou...) da distribuição cumulativa;dentro de cada uma dessas listas de peças, desenharíamos usando uma função de lei de potência, possivelmente com o mesmo coeficiente, mas com intervalos diferentes.
Por exemplo
Assumindo terços, a lista se divide da seguinte forma:

• Primeiro terço = 425 nomes, de Smith a Alvarado
• Segundo terço = 6.277 nomes, de até Gainer
• Último terço = 82.097 nomes, de Frisby até o final

Se precisássemos de, digamos, 1.000 nomes, sortearíamos 334 do terço superior da lista, 333 do segundo terço e 333 do último terço.
Para cada um dos terços usaríamos uma fórmula semelhante, talvez com um coeficiente de potência maior para o primeiro terço (onde estamos realmente interessados ​​em favorecer os nomes anteriores da lista, e também onde as frequências relativas são mais relevantes estatisticamente).As três consultas de seleção poderiam ter a seguinte aparência:

-- 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)

Answer 2

Em vez de armazenar o PDF como classificação, armazene o CDF (a soma de todas as frequências até esse nome, começando em aldekirk).

Em seguida, modifique sua seleção para recuperar o primeiro LN com classificação maior que o resultado da fórmula.

Answer 3

Eu li a pergunta como "eu preciso obter um fluxo de nomes que espelharão a frequência dos sobrenomes do censo dos EUA de 1990"

Eu poderia ter lido a pergunta de maneira um pouco diferente das outras sugestões e, embora uma resposta tenha sido aceita, e uma resposta muito através da resposta, contribuirei com minha experiência com os sobrenomes do censo.

Eu havia baixado os mesmos dados do censo de 1990. Meu objetivo era produzir um grande número de nomes a serem enviados para testes de pesquisa durante o teste de desempenho de um aplicativo de registro médico. Inseri os sobrenomes e a porcentagem de frequência em uma tabela. Adicionei uma coluna e a preenchi com um número inteiro que era o produto do "Nomes totais exigidos * Frequência". Os dados de frequência do censo não somaram exatamente 100%, então meu número total de nomes também estava um pouco aquém do requisito. Consegui corrigir o número selecionando nomes aleatórios da lista e aumentando sua contagem até que eu tivesse exatamente o número necessário, a contagem adicionada aleatoriamente nunca ampliada para mais de 0,05% do total de 10 milhões.

Gerei 10 milhões de números aleatórios na faixa de 1 a 88799. Com cada número aleatório, escolheria esse nome na lista e diminuiria o contador para esse nome. Minha abordagem era simular negociar um baralho de cartas, exceto que meu baralho tinha muitas cartas mais distintas e um número variável de cada carta.

Answer 4

Você armazena as frequências reais com as fileiras?

Converter a álgebra daquela resposta aceita para MySQL não se preocupa, se você souber para quais valores usar n. y Seria o que você tem atualmente ROUND(88799 * RAND(), 0) e x0,x1 = 1,88799 Eu acho que, embora eu possa entender mal. O único operador de matemática não padrão envolvido de uma perspectiva T-SQL é ^ o que é justo POWER(x,y) == x^y.