que clustering algoritmos agrupamiento algorithm language-agnostic graph

algorithm - que - algoritmos de agrupamiento clustering



¿Qué algoritmo usar para determinar el número mínimo de acciones requeridas para llevar el sistema al estado "Cero"? (10)

Esta es una especie de pregunta más genérica, no es específica del idioma. Más sobre la idea y el algoritmo a usar.

El sistema es el siguiente:

Registra pequeños préstamos entre grupos de amigos. Alice y Bill van a almorzar, la tarjeta de Bill no funciona, entonces Alice paga su comida, $ 10.
Al día siguiente, Bill y Charles encuentran en una estación de ferrocarril, Chales no tiene dinero para el boleto, entonces Bill le compra uno, por $ 5. Más tarde ese día Alice pide prestados $ 5 a Charles y $ 1 a Bill para comprarle un regalo a su amiga.

Ahora, suponiendo que todos registraron esas transacciones en el sistema, se ve así:

Alice -> Bill $10 Bill -> Alice $1 Bill -> Charles $5 Charles -> Alice $5

Entonces, ahora, lo único que hay que hacer es que Bill dé a Alice $ 4 (le dio $ 1 y Charlie transfirió $ 5 a Alice ) y están en el estado inicial.

Si escalamos eso a muchas personas diferentes, teniendo múltiples transacciones, ¿cuál sería el mejor algoritmo para obtener la menor cantidad de transacciones posible?

Bueno, el primer paso es ignorar por completo las transacciones. Solo agrégalos. Todo lo que necesita saber es la cantidad neta de deuda que una persona debe o posee.

Podrías encontrar transacciones fácilmente, creando un flujo de flujo loco y encontrando un flujo máximo. Entonces un corte mínimo ...

Algunas elaboraciones parciales: hay un nodo fuente, un nodo receptor y un nodo para cada persona. Habrá una ventaja entre cada par de nodos, excepto que no haya borde entre el nodo fuente y el nodo receptor. Los bordes entre las personas tienen una capacidad infinita en ambas direcciones. Los bordes que provienen del nodo fuente a la persona tienen capacidad igual a la deuda neta de la persona (0 si no tienen deuda neta). Los bordes que van del nodo persona al nodo receptor tienen una capacidad igual a la cantidad neta de dinero que se le debe a esa persona (0 si no tienen ninguna deuda neta).

Aplicar flujo máximo y / o mínimo le dará un conjunto de transferencias. El monto del flujo real será la cantidad de dinero que se transferirá.

Creé una aplicación de Android que resuelve este problema. Puede ingresar los gastos durante el viaje, incluso le recomienda "quién debe pagar a continuación". Al final calcula "quién debe enviar cuánto a quién". Mi algoritmo calcula la cantidad mínima requerida de transacciones y puede configurar la "tolerancia de transacción", lo que puede reducir las transacciones aún más (no le importan las transacciones de $ 1) Pruébelo, se llama Liquidación:

https://market.android.com/details?id=cz.destil.settleup

Descripción de mi algoritmo:

Tengo un algoritmo básico que resuelve el problema con transacciones n-1, pero no es óptimo. Funciona así: de los pagos, calculo el saldo para cada miembro. El saldo es lo que pagó menos lo que debería pagar. Ordeno miembros de acuerdo al equilibrio cada vez más. Entonces siempre tomo a los más pobres y ricos y se realiza una transacción. Al menos uno de ellos termina con saldo cero y se excluye de los cálculos posteriores. Con esto, el número de transacciones no puede ser peor que n-1. También minimiza la cantidad de dinero en las transacciones. Pero no es óptimo, porque no detecta subgrupos que puedan establecerse internamente.

Encontrar subgrupos que puedan establecerse internamente es difícil. Lo resuelvo generando todas las combinaciones de miembros y comprobando si la suma de saldos en el subgrupo es igual a cero. Comienzo con 2 pares, luego 3 pares ... (n-1) pares. Implementaciones de generadores de combinación están disponibles. Cuando encuentro un subgrupo, calculo las transacciones en el subgrupo usando el algoritmo básico descrito anteriormente. Para cada subgrupo encontrado, una transacción se salva.

La solución es óptima, pero la complejidad aumenta a O (n!). Esto se ve terrible, pero el truco es que habrá solo un pequeño número de miembros en la realidad. Lo he probado en Nexus One (procesador de 1 Ghz) y los resultados son: hasta 10 miembros: <100 ms, 15 miembros: 1 s, 18 miembros: 8 s, 20 miembros: 55 s. Entonces, hasta 18 miembros, el tiempo de ejecución es bueno. Una solución para> 15 miembros puede ser utilizar solo el algoritmo básico (es rápido y correcto, pero no óptimo).

Código fuente:

El código fuente está disponible dentro de un informe sobre el algoritmo escrito en checo. El código fuente está al final y está en inglés:

http://www.settleup.info/files/master-thesis-david-vavra.pdf

Debería poder resolver esto en O (n) determinando primero cuánto debe y debe cada persona. Transfiera las deudas de cualquier persona que deba menos de lo que le debe a sus deudores (convirtiendo a esa persona en un punto final). Repita hasta que no pueda transferir más deudas.

En realidad, este parece un trabajo en el que podría ayudar el concepto de contabilidad de doble entrada.

Sus transacciones podrían estructurarse como entradas contables así:

Alice Bill Charles Balance Alice -> Bill $10 10 10- 0 0 Bill -> Alice $1 9 9- 0 0 Bill -> Charles $5 9 4- 5- 0 Charles -> Alice $5 4 4- 0 0

Y ahí lo tienes. En cada transacción, se acredita una cuenta contable y se carga otra para que el saldo sea siempre cero. Al final, simplemente calcula las transacciones numéricas mínimas que se aplicarán a cada cuenta para devolverla a cero.

Para este caso simple, es una transferencia simple de $ 4 de Bill a Alice. Lo que debe hacer es reducir al menos una cuenta (pero preferiblemente dos) a cero por cada transacción agregada. Digamos que tienes el más complicado:

Alice Bill Charles Balance Alice -> Bill $10 10 10- 0 0 Bill -> Alice $1 9 9- 0 0 Bill -> Charles $5 9 4- 5- 0 Charles -> Alice $5 4 4- 0 0 Charles -> Bill $1 4 5- 1 0

Entonces las transacciones necesarias serían:

Bill -> Alice $4 0 1- 1 0 Bill -> Charles $1 0 0 0 0

Desafortunadamente, hay algunos estados en los que esta simple estrategia ambiciosa no genera la mejor solución (felicitaciones a j_random_hacker por señalar esto). Un ejemplo es:

Alan Bill Chas Doug Edie Fred Bal Bill->Alan $5 5- 5 0 0 0 0 0 Bill->Chas $20 5- 25 20- 0 0 0 0 Doug->Edie $2 5- 25 20- 2 2- 0 0 Doug->Fred $1 5- 25 20- 3 2- 1- 0

Claramente, esto podría revertirse en cuatro movimientos (ya que cuatro movimientos es todo lo que se necesita para llegar allí), pero si eliges tu primer movimiento imprudentemente (Edie->Bill $2) , cinco es lo mínimo que conseguirás.

Puede resolver este problema en particular con las siguientes reglas:

  • (1) si puede eliminar dos balances, hágalo.
  • (2) de lo contrario, si puede eliminar un saldo y configurarse para eliminar dos en el próximo movimiento, hágalo.
  • (3) de lo contrario, elimine cualquier saldo.

Eso daría como resultado la siguiente secuencia:

  • (a) [1] no aplicable, [2] se puede lograr con Alan->Bill $5 .
  • (b) [1] se puede hacer con Chas->Bill $20 .
  • (c) y (d), razonamiento similar con Doug, Edie y Fred, para cuatro movimientos totales.

Sin embargo, eso funciona simplemente por el pequeño número de posibilidades. A medida que aumente la cantidad de personas y las interrelaciones grupales se vuelvan más complejas, lo más probable es que necesite una búsqueda exhaustiva para encontrar la cantidad mínima de movimientos necesarios (básicamente las reglas 1, 2 y 3, pero ampliadas para manejar más profundidad) .

Creo que eso es lo que se requerirá para darle la menor cantidad de transacciones en todas las circunstancias. Sin embargo, puede ser que no sea necesario para obtener la mejor respuesta (lo mejor, en este caso, lo que significa un máximo de "explosión por dólar"). Puede ser que incluso el conjunto básico de reglas 1/2/3 le brinde una respuesta lo suficientemente buena para sus propósitos.

Encontré una solución práctica que implementé en Excel:

  • averiguar quién tiene más

  • deje que esa persona pague la cantidad completa que le debe a quien debería obtener el máximo

  • eso hace que la primera persona sea cero

  • repita este proceso teniendo en cuenta que una de las (n-1) personas tiene una cantidad modificada

Debe dar como resultado un máximo de (n-1) transferencias y lo bueno de esto es que nadie está haciendo más de un pago. Tome el ejemplo (modificado) de jrandomhacker:

a = -5 b = 25 c = -20 d = 3 e = -2 f = -1 (la suma debe ser cero!)

  1. c -> b 20. resultado: a = -5 b = 5 c = 0 d = 3 e = -2 f = -1

  2. a -> b 5 resultado: a = 0 b = 0 c = 0 d = 3 e = -2 f = -1

  3. e -> d 2 resultado a = 0 b = 0 c = 0 d = 1 e = 0 f = -1

  4. f -> d 1

Ahora, todos están satisfechos y nadie se molesta en hacer dos o más pagos. Como puede ver, es posible que una persona reciba más de un pago (persona d en este ejemplo).

Este es el código que escribí para resolver este tipo de problema en Java. No estoy 100% seguro de que esto dé el menor número de transacciones. La claridad y la estructura del código se pueden mejorar mucho.

En este ejemplo:

  • Sarah gastó $ 400 en el alquiler de autos. El auto fue usado por Sarah, Bob, Alice y John.

  • John gastó $ 100 en comestibles. Los víveres fueron consumidos por Bob y Alice.

    import java.util.*; public class MoneyMinTransactions { static class Expense{ String spender; double amount; List<String> consumers; public Expense(String spender, double amount, String... consumers){ this.spender = spender; this.amount = amount; this.consumers = Arrays.asList(consumers); } } static class Owed{ String name; double amount; public Owed(String name, double amount){ this.name = name; this.amount = amount; } } public static void main(String[] args){ List<Expense> expenseList = new ArrayList<>(); expenseList.add(new Expense("Sarah", 400, "Sarah", "John", "Bob", "Alice")); expenseList.add(new Expense("John", 100, "Bob", "Alice")); //make list of who owes how much. Map<String, Double> owes = new HashMap<>(); for(Expense e:expenseList){ double owedAmt = e.amount/e.consumers.size(); for(String c : e.consumers){ if(!e.spender.equals(c)){ if(owes.containsKey(c)){ owes.put(c, owes.get(c) + owedAmt); }else{ owes.put(c, owedAmt); } if(owes.containsKey(e.spender)){ owes.put(e.spender, owes.get(e.spender) + (-1 * owedAmt)); }else{ owes.put(e.spender, (-1 * owedAmt)); } } } } //make transactions. // We need to settle all the negatives with positives. Make list of negatives. Order highest owed (i.e. the lowest negative) to least owed amount. List<Owed> owed = new ArrayList<>(); for(String s : owes.keySet()){ if(owes.get(s) < 0){ owed.add(new Owed(s, owes.get(s))); } } Collections.sort(owed, new Comparator<Owed>() { @Override public int compare(Owed o1, Owed o2) { return Double.compare(o1.amount, o2.amount); } }); //take the highest negative, settle it with the best positive match: // 1. a positive that is equal to teh absolute negative amount is the best match. // 2. the greatest positive value is the next best match. // todo not sure if this matching strategy gives the least number of transactions. for(Owed owedPerson: owed){ while(owes.get(owedPerson.name) != 0){ double negAmt = owes.get(owedPerson.name); //get the best person to settle with String s = getBestMatch(negAmt, owes); double posAmt = owes.get(s); if(posAmt > Math.abs(negAmt)){ owes.put(owedPerson.name, 0.0); owes.put(s, posAmt - Math.abs(negAmt)); System.out.println(String.format("%s paid %s to %s", s, Double.toString((posAmt - Math.abs(negAmt))), owedPerson.name)); }else{ owes.put(owedPerson.name, -1 * (Math.abs(negAmt) - posAmt)); owes.put(s, 0.0); System.out.println(String.format("%s paid %s to %s", s, Double.toString(posAmt), owedPerson.name)); } } } } private static String getBestMatch(double negAmount, Map<String, Double> owes){ String greatestS = null; double greatestAmt = -1; for(String s: owes.keySet()){ double amt = owes.get(s); if(amt > 0){ if(amt == Math.abs(negAmount)){ return s; }else if(greatestS == null || amt > greatestAmt){ greatestAmt = amt; greatestS = s; } } } return greatestS; } }

He diseñado una solución utilizando un enfoque algo diferente a los que se han mencionado aquí. Utiliza una formulación de programación lineal del problema, extraída de la literatura de Detección Comprimida, especialmente de este trabajo de Donoho y Tanner (2005) .

He escrito una publicación de blog que describe este enfoque, junto con un pequeño paquete R que lo implementa. Me encantaría recibir algunos comentarios de esta comunidad.

Aclamaciones.

Intuitivamente, esto suena como un problema NP-completo (se reduce a un problema muy similar al del bin), sin embargo, el siguiente algoritmo (una forma modificada de empaque) debe ser bastante bueno (no hay tiempo para una prueba, lo siento).

  1. Limite las posiciones de todos, es decir, de su ejemplo anterior:

    Alice = $ 4 Bill = $ -4 Charles = $ 0

  2. Clasifique todos los acreedores netos del más alto al más bajo, y todos los deudores del más bajo al más alto, luego haga coincidir iterando sobre las listas.

  3. En algún momento es posible que deba dividir las deudas de una persona para eliminar todo: aquí probablemente sea mejor dividirse en los trozos más grandes posibles (es decir, en los contenedores con el espacio restante más primero).

Esto tomará algo como O (n log n) (nuevamente, se requiere una prueba adecuada).

Para obtener más información, consulte el Problema de partición y el Empaquetado de bandejas (el primero es un problema muy similar, y si se limita a transacciones de precisión fija, entonces es equivalente, por supuesto, se necesitan pruebas).

Si toma estados como nodos de gráfico, entonces podrá usar el algoritmo de ruta más corta para conocer la respuesta.

Solo si alguien debe más de 2 personas, que también deben el mismo conjunto, ¿puede reducir la cantidad de transacciones del conjunto simple?

Es decir, el conjunto simple es solo encontrar cada equilibrio y pagarlo. ¡Eso no es más que N! actas.

Si A debe B y C, y algún subconjunto de BC se deben, entonces B debe C, entonces en vez de: A -> B, A -> C (3 transacciones). Utilizarías: A -> B, B -> C (2 transacciones).

Entonces, en otras palabras, estás construyendo un gráfico dirigido y quieres recortar vértices para maximizar la longitud de la ruta y minimizar los bordes totales.

Lo siento, no tengo un algoritmo para ti.