Algoritmo de Toivonen en análisis de datos

En este artículo, vamos a discutir el algoritmo de Toivonen en el análisis de datos.

Algoritmo de Toivonen:
Utiliza la volubilidad de una manera diferente al algoritmo de muestreo simple. Este algoritmo, con una memoria principal adecuada, utilizará una pasada sobre una muestra pequeña y una pasada completa sobre los datos. No dará falsos negativos ni positivos, pero hay una posibilidad pequeña pero finita de que no producirá ninguna respuesta. En ese caso, debe replicarse hasta que dé una respuesta. En este algoritmo, antes de producir el número promedio de pasadas necesarias y solo los conjuntos de elementos frecuentes es una pequeña constante.

• El algoritmo de Toivonen se embarca seleccionando una pequeña muestra del conjunto de datos de entrada y encontrando a partir de ella los conjuntos de elementos frecuentes candidatos.
• El procedimiento del algoritmo en cuestión es exactamente el mismo que el algoritmo aleatorio simple, excepto que es esencial en este algoritmo establecer el umbral en algo menor que el valor proporcional.
• Es decir, si el umbral de soporte para el conjunto de datos completo es s y la magnitud de la muestra es la fracción p, cuando busque conjuntos de elementos frecuentes en la muestra, use un umbral de 0,9 ps o 0,8 ps.
• Cuanto más pequeño hacemos el umbral, más memoria principal se necesita para calcular todos los conjuntos de elementos que son frecuentes en la muestra, pero es más probable que eludamos la situación cuando el algoritmo se rompe para proporcionar la respuesta.
• Habiendo ensamblado la colección de conjuntos de elementos frecuentes para la muestra, luego configuramos el borde negativo. Esta es la colección de conjuntos de elementos que no son frecuentes en la muestra, pero todos sus subconjuntos instantáneos (subconjuntos creados al eliminar exactamente un elemento) son frecuentes en la muestra.

Para concluir el algoritmo de Toivonen, hacemos un recorrido por todo el conjunto de datos, contando todos los conjuntos de elementos que son frecuentes en la muestra o que están debajo del borde negativo.
Hay dos consecuencias viables:

1. En el conjunto de datos completo, ningún miembro del borde negativo es frecuente. En este caso, el conjunto exacto de conjuntos de elementos frecuentes es el mismo que los conjuntos de elementos de la muestra que se marcaron como frecuentes en el total.
2. Pocos miembros en el conjunto de datos completo del borde negativo son frecuentes. En este caso, no podemos estar seguros de que no existan conjuntos aún mayores, ni en el borde negativo ni en la colección de conjuntos de ítems frecuentes para la muestra, que también lo sean en el todo. Por lo tanto, no podemos dar respuestas en este momento y debemos repetir el algoritmo con una muestra aleatoria recién descubierta.

Por qué funciona el algoritmo de Toivonen:
Claramente, el algoritmo de Toivonen nunca construye un falso positivo, ya que solo describe como frecuentes aquellos conjuntos de elementos que se han contado y se ha encontrado que son frecuentes en el total. Para afirmar que nunca juntó un falso negativo, debemos demostrar que cuando ningún morgan del borde negativo es frecuente en el todo, entonces no puede haber ningún conjunto de elementos que sea como sigue.

1. Concluyó como frecuente en el itemset completo.
2. Pero ni en el borde negativo ni en la colección de conjuntos de elementos frecuentes para la muestra dada.