Utilisation de minHash pour comparer plus de 2 séries

Question

J'ai une classe appelée FindSimilar qui utilise minHash pour trouver des similitudes entre 2 ensembles (et pour cet objectif, cela fonctionne très bien). Mon problème est que j'ai besoin de comparer plus de 2 ensembles, plus précisément, j'ai besoin de comparer un set1 donné avec une quantité inconnue d'autres ensembles. Voici la classe:

import java.util.HashSet; 
import java.util.Map; 
import java.util.Random; 
import java.util.Set; 

public class FindSimilar<T> 
{ 
private int hash[]; 
private int numHash; 

public FindSimilar(int numHash) 
{ 
    this.numHash = numHash; 
    hash = new int[numHash]; 
    Random r = new Random(11); 
    for (int i = 0; i < numHash; i++) 
    { 
     int a = (int) r.nextInt(); 
     int b = (int) r.nextInt(); 
     int c = (int) r.nextInt(); 
     int x = hash(a * b * c, a, b, c); 
     hash[i] = x; 
    } 
} 

public double similarity(Set<T> set1, Set<T> set2) 
{ 
    int numSets = 4; 
    Map<T, boolean[]> bitMap = buildBitMap(set1, set2); 
    int[][] minHashValues = initializeHashBuckets(numSets, numHash); 
    computeFindSimilarForSet(set1, 0, minHashValues, bitMap); 
    computeFindSimilarForSet(set2, 1, minHashValues, bitMap); 
    return computeSimilarityFromSignatures(minHashValues, numHash); 
} 

private static int[][] initializeHashBuckets(int numSets, 
     int numHashFunctions) 
{ 
    int[][] minHashValues = new int[numSets][numHashFunctions]; 
    for (int i = 0; i < numSets; i++) 
    { 
     for (int j = 0; j < numHashFunctions; j++) 
     { 
      minHashValues[i][j] = Integer.MAX_VALUE; 
     } 
    } 
    return minHashValues; 
} 

private static double computeSimilarityFromSignatures(
     int[][] minHashValues, int numHashFunctions) 
{ 
    int identicalFindSimilares = 0; 
    for (int i = 0; i < numHashFunctions; i++) 
    { 
     if (minHashValues[0][i] == minHashValues[1][i]) 
     { 
      identicalFindSimilares++; 
     } 
    } 
    return (1.0 * identicalFindSimilares)/numHashFunctions; 
} 

private static int hash(int x, int a, int b, int c) 
{ 
    int hashValue = (int) ((a * (x >> 4) + b * x + c) & 131071); 
    return Math.abs(hashValue); 
} 

private void computeFindSimilarForSet(Set<T> set, int setIndex, 
     int[][] minHashValues, Map<T, boolean[]> bitArray) 
{ 
    int index = 0; 
    for (T element : bitArray.keySet()) 
    { 
     /* 
     * for every element in the bit array 
     */ 
     for (int i = 0; i < numHash; i++) 
     { 
      /* 
      * for every hash 
      */ 
      if (set.contains(element)) 
      { 
       /* 
       * if the set contains the element 
       */ 
       int hindex = hash[index]; 
       if (hindex < minHashValues[setIndex][index]) 
       { 
        /* 
        * if current hash is smaller than the existing hash in 
        * the slot then replace with the smaller hash value 
        */ 
        minHashValues[setIndex][i] = hindex; 
       } 
      } 
     } 
     index++; 
    } 
} 

public Map<T, boolean[]> buildBitMap(Set<T> set1, Set<T> set2) 
{ 
    Map<T, boolean[]> bitArray = new HashMap<T, boolean[]>(); 
    for (T t : set1) 
    { 
     bitArray.put(t, new boolean[] { true, false }); 
    } 
    for (T t : set2) 
    { 
     if (bitArray.containsKey(t)) 
     { 
      // item is present in set1 
      bitArray.put(t, new boolean[] { true, true }); 
     } 
     else if (!bitArray.containsKey(t)) 
     { 
      // item is not present in set1 
      bitArray.put(t, new boolean[] { false, true }); 
     } 
    } 
    return bitArray; 
} 

public static void main(String[] args) 
{ 
    Set<String> set1 = new HashSet<String>(); 
    set1.add("FRANCISCO"); 
    set1.add("abc"); 
    set1.add("SAN"); 
    Set<String> set2 = new HashSet<String>(); 
    set2.add("b"); 
    set2.add("a"); 
    set2.add("SAN"); 
    set2.add("USA"); 
    FindSimilar<String> minHash = new FindSimilar<String>(set1.size() + set2.size()); 
    System.out.println("Set1 : " + set1); 
    System.out.println("Set2 : " + set2); 
    System.out.println("Similarity between two sets: " 
      + minHash.similarity(set1, set2)); 
} 
} 

J'ai besoin d'utiliser la méthode similarity sur plus de 2 ensembles. Le problème est que je ne peux pas trouver un moyen de tous les parcourir. Si je crée un for, je ne peux pas dire que je veux comparer set1 et seti. Je ne suis pas sûr si j'ai du sens, je dois admettre que je suis un peu confus.

Le but du programme est de comparer les utilisateurs. Un utilisateur a une liste de contacts (autres utilisateurs) et des utilisateurs similaires ont des contacts similaires. Chaque ensemble est un utilisateur et le contenu des ensembles sera leurs contacts.

Answer 1

J'ai trouvé un (pas sûr) solution ringard pour mon problème en plaçant tous sets à l'intérieur d'une structure ArrayList puis la convertir en une array réelle:

ArrayList<Set<String>> list = new ArrayList<Set<String>>(); 

for(int i = 0; i < numPeople; i++){ 
    Set<String> set1 = new HashSet<String>(); 
    list.add(set1); 
    //another for goes here later on 
} 

Set<String>[] bs = list.toArray(new Set[0]); 

. 
. 
. 

public static void main(String[] args) 
{ 
    . 
    . 
    . 

    for(int i = 1; i<bs.length; i++){ 
     System.out.format("Set %d: ", i+1); 
     System.out.println(bs[0]); 
     System.out.println("Similarity between two sets: " 
       + minHash.similarity(bs[0], bs[i]));  
    } 
} 

Cela dégage un avertissement The expression of type Set[] needs unchecked conversion to conform to Set<String>[], mais fonctionne bien. Cela fait exactement ce que je voulais (j'ai encore besoin d'un for pour mettre les données à l'intérieur du sets, mais cela ne devrait pas être difficile.) Si quelqu'un pouvait me dire si cette solution devrait être utilisée ou s'il existe une meilleure alternative, J'aime apprendre, puisque j'apprends encore et que toute information serait utile

Answer 2

Dans les implémentations d'algorithmes de jointure de similarité d'ensemble, les ensembles sont généralement convertis en un tableau d'entiers. Les tableaux sont triés, de sorte que le chevauchement entre deux ensembles peut être calculé de la même manière.Si vous êtes intéressé par ces algorithmes et leurs techniques d'élagage, l'article au http://ssjoin.dbresearch.uni-salzburg.at/ pourrait être un bon début.