(Java) Создание всех антецедентов правила ассоциации
Например, у меня может быть частый набор символов {A, B, C, G}. Мне нужно создать все возможные предшественники ассоциативных правил. В данном случае: ABC, ABG, ACG, AB, AC, AG, BC, BG, CG, A, B, C, G. Я не знаю, с чего начать. Часы исследования научили меня терминологии и концепции, но ничего не объяснило, как сделать этот конкретный шаг. Это то, что у меня есть для метода. Все наборы элементов хранятся в виде строк и хранятся вместе как ArrayList. Я уже сделал рабочий алгоритм Apriori для генерации частых наборов элементов.
public static ArrayList<String> associationRules(ArrayList<String> data, ArrayList<String> freqItemsets, int minConf){
ArrayList<String> generatedRules = new ArrayList<String>();
for(int i = 0; i < freqItemsets.size(); i++) {
String currentItemset = freqItemsets.get(i);
if(currentItemset.length() < 2) {
continue;
}
}
return null; // temporary return statement to avoid compile error
}
Хотя код, отзывы и советы по этому и последующим шагам, конечно, очень помогли бы, все, что мне действительно нужно, это объяснение на английском языке того, как сделать этот шаг (в отличие от псевдокода или другого рабочего метода с использованием разных типов данных). Все остальное кажется управляемым.
Ответы
Предполагая, что вы определили, что вам действительно нужно (все подмножества, отсортированные как исходный список), вы можете сделать это, думая об этом как об этом и используя эти свойства:
- отсортировано как в вашем списке
- конечный
- делимый
Все, что вам нужно сделать, это пройтись по списку персонажей несколько раз и каждый раз решать для каждого персонажа, включать его на этот раз или отбрасывать. Если вы пройдете и уловите все возможности, то все готово. Для этого вы должны найти надежный способ подсчета возможных строк результатов.
итеративное решение
Подумайте о возможных битовых состояниях. У вас есть n символов и каждому символу присваивается бит (в вашем случае 4). Затем каждое возможное битовое состояние определяет допустимую перестановку подмножества, например, для {A, B, C, G}:
1001 было бы AG
Как мы знаем, все возможные состояния набора битов являются «счетными», или, другими словами, вы можете просто пересчитывать их, считая от наименьшего состояния к наибольшему, добавляя 1.
Сделайте цикл, подсчитывающий от 1 до 2 ^ n - 1 (где n - количество символов, которые у вас есть), а затем создайте свой String, добавив (в правильной последовательности) все символы, для которых у вас есть 1 в качестве их представляющего бита, и оставьте символы с 0. Затем вы «просчитываете» все возможные допустимые перестановки.
Такая реализация сильно зависит от программиста и его стиля, но для меня это выглядело бы примерно так:
public static List<String> associationRules(List<String> elements) {
List<String> result = new ArrayList<>();
long limit = 1 << elements.size(); // thanks to saka1029 for this correction. My code was n^2 not 2^n.
// count from 1 to n^2 - 1
for (long i = 1; i < limit; ++i) {
StringBuilder seq = new StringBuilder();
// for each position (character) decide, whether to include it based on the state of the bit.
for (int pos = 0; pos < elements.size(); ++pos) {
boolean include = ((i >> pos) % 2) == 1; // this line will give you true, if the in 'i' the bit at 'pos' (from behind) is 1, and false otherwise.
if (include) {
seq.append(elements.get(pos));
}
}
// add to the final result the newly generated String.
result.add(seq.toString());
}
return result;
}
и результат выглядит так: [A, B, AB, C, AC, BC, ABC, G, AG, BG, ABG, CG, ACG, BCG, ABCG]
Это итеративное (нерекурсивное) решение, но есть также рекурсивное, которое может быть (а может и нет) проще реализовать.
рекурсивное решение
Рекурсивное решение может просто работать, создав метод, который принимает в качестве аргументов набор отсортированных символов и логическое состояние (включено или не включено) и возвращает список всех возможных отсортированных подстановок. Затем вы могли бы вызвать это с помощью общедоступного метода, который передает символы и 0как позицию и либо, trueлибо falseкак начальное состояние (другое приходит позже).
Затем метод работает с «разделяй и властвуй». Вы включаете символ в определенную позицию (в зависимости от того, установлен ли флаг включения) и снова вызываете собственный метод с клонированным (под) набором символов, который не включает первый символ.
Предположим на момент, что вы начинаете с того, что не включаете первый символ каждой последовательности (но позже включаете его). Если вы передадите такому методу набор символов, {A, B, C, G}тогда метод (начнет) работать следующим образом:
A: recurse on {B, C, G}
B: recurse on {C, G}
C: recurse on {G}
G: set is empty,
G: Add to the result all Strings with 'G' prefixed and without.
G: return {"G", ""}
C: Add to the result all Strings with 'C' prefixed and without.
C: {"CG", "C", "G", ""}
...
Таким образом, вы рекурсивно соберете все отсортированные перестановки подмножеств. В зависимости от того, разрешена ли пустая строка, вы можете удалить ее в конце или не добавлять вообще.
Я реализовал это так, но есть и другие правильные способы:
public static List<String> associationRules2(List<String> elements) {
List<String> result = new ArrayList<>();
String thisElement = elements.get(0);
// build the subset list (leaving out the first element
List<String> remaining = new ArrayList<>();
boolean first = true;
for (String s : elements) {
if (first) {
first = false;
} else {
remaining.add(s);
}
}
// if the subset is not empty, we recurse.
if (! remaining.isEmpty()) {
List<String> subPermutations = associationRules2(remaining);
// add all permutations without thisElement.
result.addAll(subPermutations);
// add all permutations *with* thisElement.
for (String s : subPermutations) {
result.add(thisElement + s);
}
}
// finally add thisElement on it's own.
result.add(thisElement);
return result;
}
Результат: [G, CG, C, BG, BCG, BC, B, AG, ACG, AC, ABG, ABCG, ABC, AB, A]