Elección ponderada aleatoria en T-SQL

Question

¿Cómo se selecciona aleatoriamente una fila de una tabla en T-SQL en función de un peso aplicado para todas las filas candidatas?

Por ejemplo, tengo un conjunto de filas en una tabla ponderada en 50, 25 y 25 (que suma 100 pero no es necesario) y quiero seleccionar una de ellas al azar con un resultado estadístico equivalente al respectivo. peso.

Answer 1

La respuesta de Dane incluye un yo que se une de una manera que introduce una ley del cuadrado. (n*n/2) filas después de la unión donde hay n filas en la tabla.

Lo que sería más ideal es poder analizar la tabla una sola vez.

DECLARE @id int, @weight_sum int, @weight_point int
DECLARE @table TABLE (id int, weight int)

INSERT INTO @table(id, weight) VALUES(1, 50)
INSERT INTO @table(id, weight) VALUES(2, 25)
INSERT INTO @table(id, weight) VALUES(3, 25)

SELECT @weight_sum = SUM(weight)
FROM @table

SELECT @weight_point = FLOOR(((@weight_sum - 1) * RAND() + 1), 0)

SELECT
    @id = CASE WHEN @weight_point < 0 THEN @id ELSE [table].id END,
    @weight_point = @weight_point - [table].weight
FROM
    @table [table]
ORDER BY
    [table].Weight DESC

Esto recorrerá la mesa, configurando @id a cada registro id valor mientras que al mismo tiempo disminuye @weight punto.Finalmente, el @weight_point saldrá negativo.Esto significa que el SUM de todos los pesos anteriores es mayor que el valor objetivo elegido aleatoriamente.Este es el récord que queremos, así que a partir de ese momento establecimos @id a sí mismo (ignorando cualquier ID en la tabla).

Esto recorre la tabla solo una vez, pero tiene que recorrer toda la tabla incluso si el valor elegido es el primer registro.Debido a que la posición promedio está en la mitad de la tabla (y menos si se ordena por peso ascendente), escribir un bucle posiblemente podría ser más rápido...(Especialmente si las ponderaciones están en grupos comunes):

DECLARE @id int, @weight_sum int, @weight_point int, @next_weight int, @row_count int
DECLARE @table TABLE (id int, weight int)

INSERT INTO @table(id, weight) VALUES(1, 50)
INSERT INTO @table(id, weight) VALUES(2, 25)
INSERT INTO @table(id, weight) VALUES(3, 25)

SELECT @weight_sum = SUM(weight)
FROM @table

SELECT @weight_point = ROUND(((@weight_sum - 1) * RAND() + 1), 0)

SELECT @next_weight = MAX(weight) FROM @table
SELECT @row_count   = COUNT(*)    FROM @table
SET @weight_point = @weight_point - (@next_weight * @row_count)

WHILE (@weight_point > 0)
BEGIN
    SELECT @next_weight = MAX(weight) FROM @table WHERE weight < @next_weight
    SELECT @row_count   = COUNT(*)    FROM @table WHERE weight = @next_weight
    SET @weight_point = @weight_point - (@next_weight * @row_count)
END

-- # Once the @weight_point is less than 0, we know that the randomly chosen record
-- # is in the group of records WHERE [table].weight = @next_weight

SELECT @row_count = FLOOR(((@row_count - 1) * RAND() + 1), 0)

SELECT
    @id = CASE WHEN @row_count < 0 THEN @id ELSE [table].id END,
    @row_count = @row_count - 1
FROM
    @table [table]
WHERE
    [table].weight = @next_weight
ORDER BY
    [table].Weight DESC

Answer 2

Simplemente necesita sumar los pesos de todas las filas candidatas, luego elegir un punto aleatorio dentro de esa suma, luego seleccionar el registro que se coordina con ese punto elegido (cada registro lleva consigo de forma incremental una suma de peso acumulada).

DECLARE @id int, @weight_sum int, @weight_point int
DECLARE @table TABLE (id int, weight int)

INSERT INTO @table(id, weight) VALUES(1, 50)
INSERT INTO @table(id, weight) VALUES(2, 25)
INSERT INTO @table(id, weight) VALUES(3, 25)

SELECT @weight_sum = SUM(weight)
FROM @table

SELECT @weight_point = ROUND(((@weight_sum - 1) * RAND() + 1), 0)

SELECT TOP 1 @id = t1.id
FROM @table t1, @table t2
WHERE t1.id >= t2.id
GROUP BY t1.id
HAVING SUM(t2.weight) >= @weight_point
ORDER BY t1.id

SELECT @id

Answer 3

El "llevando incrementalmente una suma de peso acumulada" La parte es cara si tienes muchos registros.Si también ya tiene una amplia gama de puntuaciones/pesos (es decir:el rango es lo suficientemente amplio como para que la mayoría de los pesos de los registros sean únicos.De 1 a 5 estrellas probablemente no serían suficientes), puede hacer algo como esto para elegir un valor de peso.Estoy usando VB.Net aquí para demostrarlo, pero esto también se podría hacer fácilmente en Sql puro:

Function PickScore()
    'Assume we have a database wrapper class instance called SQL and seeded a PRNG already
    'Get count of scores in database
    Dim ScoreCount As Double = SQL.ExecuteScalar("SELECT COUNT(score) FROM [MyTable]")
    ' You could also approximate this with just the number of records in the table, which might be faster.

    'Random number between 0 and 1 with ScoreCount possible values
    Dim rand As Double = Random.GetNext(ScoreCount) / ScoreCount

    'Use the equation y = 1 - x^3 to skew results in favor of higher scores
    ' For x between 0 and 1, y is also between 0 and 1 with a strong bias towards 1
    rand = 1 - (rand * rand * rand)

    'Now we need to map the (0,1] vector to [1,Maxscore].
    'Just find MaxScore and mutliply by rand
    Dim MaxScore As UInteger = SQL.ExecuteScalar("SELECT MAX(Score) FROM Songs")
    Return MaxScore * rand
End Function

Ejecute esto y elija el registro con la puntuación más grande menor que el peso devuelto.Si más de un registro comparte esa puntuación, selecciónelo al azar.Las ventajas aquí son que no es necesario mantener ninguna suma y puedes modificar la ecuación de probabilidad utilizada para adaptarla a tus gustos.Pero nuevamente, funciona mejor con una distribución más amplia de puntuaciones.

Answer 4

La forma de hacer esto con generadores de números aleatorios es integrar la función de densidad de probabilidad.Con un conjunto de valores discretos puedes calcular la suma del prefijo (suma de todos los valores hasta este) y almacenarlo.Con esto se selecciona el valor mínimo de la suma del prefijo (agregado hasta la fecha) mayor que el número aleatorio.

En una base de datos, los valores posteriores después de una inserción deben actualizarse.Si la frecuencia relativa de las actualizaciones y el tamaño del conjunto de datos no hacen que el costo de hacer esto sea prohibitivo, significa que se puede obtener el valor apropiado a partir de una única consulta s-argable (predicado que se puede resolver mediante una búsqueda de índice). .

Answer 5

Si necesita obtener un grupo de muestras (por ejemplo, desea tomar una muestra de 50 filas de una colección de 5 millones de filas) donde cada fila tiene una columna llamada Weight que es un int y donde valores más grandes significan más peso, puedes usar esta función:

SELECT * 
FROM 
(
    SELECT TOP 50 RowData, Weight 
    FROM MyTable 
    ORDER BY POWER(RAND(CAST(NEWID() AS VARBINARY)), (1.0/Weight)) DESC
) X 
ORDER BY Weight DESC

La clave aquí es usar la función POWER( ) como se ilustra aquí

Una referencia sobre la elección de una función aleatoria es aquí y aquí

Alternativamente puedes usar:

1.0 * ABS(CAST(CHECKSUM(NEWID()) AS bigint)) / CAST(0x7FFFFFFF AS INT) 

Echas suma de comprobación como BIGINT en lugar de INT porque este asunto:

Debido a que la suma de verificación devuelve un int, y el rango de un int es -2^31 (-2,147,483,648) a 2^31-1 (2,147,483,647), la función ABS () puede devolver un error de desbordamiento si el resultado es exactamente -2,147,483,648 !Las posibilidades obviamente son muy bajas, aproximadamente 1 de cada 4 mil millones, sin embargo, lo estábamos ejecutando en una mesa de fila de ~ 1.8b todos los días, ¡así que sucedía aproximadamente una vez por semana!Fix es para lanzar la suma de verificación a Bigint antes del ABS.