Algoritmo de coincidencia de preferencias

12

Hay un proyecto paralelo en el que estoy trabajando en el que necesito estructurar una solución al siguiente problema.

Tengo dos grupos de personas (clientes). El grupo Atiene la intención de comprar y el grupo Btiene la intención de vender un producto determinado X. El producto tiene una serie de atributos x_i, y mi objetivo es facilitar la transacción entre Ay Bhaciendo coincidir sus preferencias. La idea principal es señalar a cada miembro de Aun correspondiente en Bcuyo producto se adapte mejor a sus necesidades, y viceversa.

Algunos aspectos complicados del problema:

  1. La lista de atributos no es finita. El comprador podría estar interesado en una característica muy particular o algún tipo de diseño, lo cual es raro entre la población y no puedo predecirlo. No se pueden enumerar previamente todos los atributos;

  2. Los atributos pueden ser continuos, binarios o no cuantificables (por ejemplo, precio, funcionalidad, diseño);

¿Alguna sugerencia sobre cómo abordar este problema y resolverlo de forma automatizada?

También agradecería algunas referencias a otros problemas similares si es posible.


Grandes sugerencias! Muchas similitudes en la forma en que estoy pensando en abordar el problema.

El problema principal al mapear los atributos es que el nivel de detalle al que se debe describir el producto depende de cada comprador. Tomemos un ejemplo de un automóvil. El producto "automóvil" tiene muchos atributos que van desde su rendimiento, estructura mecánica, precio, etc.

Supongamos que solo quiero un automóvil barato o un automóvil eléctrico. Ok, eso es fácil de mapear porque representan las características principales de este producto. Pero digamos, por ejemplo, que quiero un automóvil con transmisión de doble embrague o faros de xenón. Bueno, puede haber muchos automóviles en la base de datos con estos atributos, pero no le pediría al vendedor que complete este nivel de detalle en su producto antes de la información de que alguien los está buscando. Tal procedimiento requeriría que cada vendedor complete un formulario complejo y muy detallado, solo intente vender su automóvil en la plataforma. Simplemente no funcionaría.

Pero aún así, mi desafío es tratar de ser tan detallado como sea necesario en la búsqueda para hacer una buena combinación. Entonces, la forma en que pienso es mapear los aspectos principales del producto, aquellos que probablemente sean relevantes para todos, para reducir el grupo de vendedores potenciales.

El siguiente paso sería una "búsqueda refinada". Para evitar crear un formulario demasiado detallado, podría pedirles a los compradores y vendedores que escriban un texto libre de sus especificaciones. Y luego use un algoritmo de coincidencia de palabras para encontrar posibles coincidencias. Aunque entiendo que esta no es una solución adecuada al problema porque el vendedor no puede "adivinar" lo que necesita el comprador. Pero podría acercarme.

El criterio de ponderación sugerido es excelente. Me permite cuantificar el nivel al que el vendedor coincide con las necesidades del comprador. Sin embargo, la parte de escala podría ser un problema, porque la importancia de cada atributo varía de un cliente a otro. Estoy pensando en usar algún tipo de reconocimiento de patrones o simplemente pedirle al comprador que ingrese el nivel de importancia de cada atributo.

RD
fuente

Respuestas:

9

Mi primera sugerencia sería mapear de alguna manera los atributos no cuantificables a cantidades con la ayuda de funciones de mapeo adecuadas. De lo contrario, simplemente déjelos fuera.

En segundo lugar, no creo que deba asumir que la lista de atributos no es finita. Un enfoque estándar e intuitivo es representar cada atributo como una dimensión individual en un espacio vectorial. Cada producto es simplemente un punto en este espacio. En ese caso, si desea agregar dinámicamente más atributos, simplemente tiene que reasignar los vectores del producto en el nuevo espacio de características (con dimensiones adicionales).

Con esta representación, un vendedor es un punto en el espacio de características con atributos de producto y un comprador es un punto en el mismo espacio de características con los atributos de preferencia. La tarea es encontrar el punto de comprador más similar para un punto de vendedor determinado.

Si su conjunto de datos (es decir, el número de compradores / vendedores) no es muy grande, puede resolver esto con un enfoque vecino más cercano implementado con la ayuda de árboles kd.

Para datos de gran tamaño, puede adoptar un enfoque IR. Indice el conjunto de vendedores (es decir, los atributos del producto) tratando cada atributo como un término separado con el término ponderación establecido en el valor del atributo. Una consulta en este caso es un comprador que también está codificado en el espacio de términos como un vector de consulta con ponderaciones de término apropiadas. El paso de recuperación le devolvería una lista de las K coincidencias más similares.

Debasis
fuente
Wright El problema principal aquí es el número de dimensiones, es decir, el nivel de detalle que necesito usar. ¿Podría aclararme el "enfoque IR"?
RD
1
Por IR, me refería a la recuperación de información. Puede pensar que los documentos (vendedores) en su colección y la consulta (un comprador) son todos vectores incrustados en un espacio de término (atributo). Como dije, este enfoque necesita un número predeterminado de dimensiones para trabajar.
Debasis
7

Como se sugiere, volviéndose loco . En primer lugar, corrígeme si me equivoco:

  • Solo existen algunas características para cada producto único;
  • No existe una lista definitiva de funciones, y los clientes pueden agregar nuevas funciones a sus productos.

Si es así, construir una tabla completa de características del producto podría ser costoso computacionalmente. Y la tabla de datos final sería extremadamente escasa.

El primer paso es reducir la lista de clientes (productos) para que coincidan. Construyamos un gráfico bipartito, donde los vendedores serían nodos de tipo 1 y los compradores serían nodos de tipo 2. Cree una ventaja entre cualquier vendedor y comprador cada vez que haga referencia a una característica de producto similar, como en el siguiente boceto:

grafico

Usando el gráfico anterior, para cada producto de vendedor único, puede seleccionar solo compradores que estén interesados ​​en características que coincidan con el producto (es posible filtrar al menos una característica común, igualar el conjunto completo de características o establecer un nivel de umbral). Pero ciertamente, eso no es suficiente. El siguiente paso es comparar los valores de las características, según lo descrito por el vendedor y el comprador. Hay muchas variantes (p. Ej., K-Nearest-Neighbours). Pero, ¿por qué no tratar de resolver esta pregunta usando el gráfico existente? Agreguemos pesos a los bordes:

  • para características continuas (p. ej., precio):

    precio_peso

  • para características binarias y no cuantificables, solo lógica bicondicional:

    función_peso

La idea principal aquí es escalar cada característica al intervalo [0, 1]. Además, podemos usar coeficientes de características para determinar las características más importantes. Por ejemplo, suponiendo que el precio es dos veces más importante que la disponibilidad de alguna función rara:

adj_w_1

adj_w_2

Uno de los pasos finales es simplificar la estructura del gráfico y reducir muchos bordes a un borde con un peso igual a la suma de los pesos calculados previamente de cada entidad. Con una estructura tan reducida, cada par de clientes / productos podría tener solo un borde (sin bordes paralelos). Por lo tanto, para encontrar la mejor oferta para el vendedor exacto, solo necesita seleccionar compradores conectados con bordes ponderados máximos.

Desafío futuro: introduzca un método barato para ponderar bordes en el primer paso :)

Sobach
fuente