Estoy tratando de implementar el algoritmo Apriori en Java y tengo problemas para generar conjuntos de elementos candidatos. Para crear candidatos para k-itemset, utilizo todas las combinaciones de k-1 y 1-itemsets. Por ejemplo, para Frequent 1-itemset: pan: 9, leche: 9, café: 9, azúcar: 10.

Los conjuntos de 2 elementos candidatos generados deben ser: leche de pan, café de pan, azúcar de pan, café con leche, azúcar con leche, azúcar de café.

Pero mi código regresa: pan café, pan con leche, pan azúcar, café pan, café con leche, café con azúcar, pan con leche, café con leche, leche con azúcar, pan con azúcar, café con azúcar, leche con azúcar (todas las permutaciones; devuelve tanto la leche como la leche). pan, sin embargo, estos dos son lo mismo).

Mi código:

public static ArrayList<ArrayList<String>> getCandidates(Map<String, Long> one_itemset_1, Map<String, Long> n_itemset_1){
    ArrayList<ArrayList<String>> tuples = new ArrayList<ArrayList<String>>();


    Map<String, Long> one_itemset = sortbykey(one_itemset_1);
    Map<String, Long> n_itemset = sortbykey(n_itemset_1);

    for(String item : one_itemset.keySet()) {

        for(String item2 : n_itemset.keySet()) {
            if(!item.equals(item2) && !item2.contains(item)) {
                ArrayList<String> singleList = new ArrayList<String>();
                singleList.add(item);
                String item2_sep[] = item2.split(" ");
                for(int i = 0; i < item2_sep.length; i++)
                    singleList.add(item2_sep[i]);
                //singleList.add(item2);
                tuples.add(singleList);
            }
            //index2++;
        }
        //index2 = 0;
        //index1++;
    }

    return tuples;
}

¿Hay alguna forma de modificar este método para deshacerse de conjuntos de elementos repetitivos? Por favor avise. Gracias.

0
Helen Grey 12 oct. 2019 a las 07:34

1 respuesta

La mejor respuesta

El algoritmo Apriori no requiere que hagas una combinación entre Lk y todos los conjuntos de elementos 1 para obtener Ck + 1. Este enfoque tendrá un tiempo de ejecución mucho mayor. Más bien, unimos Lk consigo mismo con la condición de que los primeros elementos (k-1) sean iguales en ambos conjuntos de elementos k: ver aquí

En cuanto a tener elementos duplicados en su código, puede definir un orden en los elementos 1 (I1 <I2 <I3 ... In) y luego solo considere los elementos en orden ascendente (o descendente). Esto mantendrá los conjuntos de elementos ordenados -> (I1, I3, I5) es un conjunto de elementos válido pero (I1, I5, I3 ) no es.

Esto se puede hacer fácilmente con dos bucles for para su ejemplo:

for (int i=0; i<k-itemsets.size()-1; i++){
    for(int j=i+1; j<k-itemsets.size(); j++){
        // compare k-itemsets here and join in ascending order to produce k+1-itemset
    }
}

También le aconsejaría que consulte otras fuentes si no comprende el algoritmo al principio. Por ejemplo, la biblioteca SPMF tiene la implementación de los algoritmos más populares relacionados para modelar la minería.

1
fzk 3 ene. 2020 a las 12:08