Dieser Artikel wurde maschinell übersetzt.
Testlauf
Häufige vorkommende Itemsets für die Assoziationsanalyse
Eine wichtige Aufgabe im Bereich des maschinellen Lernens und natürliche Benutzerschnittstellen (Unwesen) ist häufiges Element-Sets aus einer Liste von Transaktionen extrahieren. Das Problem ist am besten durch Beispiel erklären. Angenommen Sie, Sie haben eine Liste von Elementen, die durch verschiedene Kunden in einem Supermarkt gekauft. Zum Beispiel einer Debitorenbuchung möglicherweise (Brot, Äpfel, Sellerie) und anderen möglicherweise (Brot, Donuts, Eier, Salat). Es kann viele Tausende dieser Transaktionen. Ein Element-Set ist eine Teilmenge aller möglichen Elemente, wie z. B. (Äpfel, Brot). Das Problem ist nur die Element-Sets aus der Liste aller Transaktionen zu extrahieren, die einige minimale Anzahl zu erfüllen. Angenommen Sie, die minimale Anzahl ist 20 und Element-Set (Äpfel, Brot) tritt in die Liste der Transaktionen 25mal; aus diesem Grund (Äpfel, Brot) wäre ein häufiges Element-Set.
Identifizierung von häufigen Element-Sets kann in vielerlei Hinsicht nützlich sein. Bei einem Supermarkt konnte wissen davon Elemente sind häufig zusammen gekauft für Product-Placement, zielgerichtetes Marketing und So weiter verwendet werden. Zusätzlich, sobald alle häufige Elemente Sets identifiziert wurden, konnte diese Element-Sets weiter nach Auszug Regeln wie analysiert werden "Wenn Kunden Äpfel und Brot kaufen, dann es hohe Wahrscheinlichkeit, dass gibt sie auch Salat und Milch kaufen werden." Dieser Gesamtprozess zunächst extrahieren häufig Element-Sets und dann ernten wenn-dann-Regeln nennt man Verband Regel lernen.
Dieser Artikel beschreibt im Detail den häufigen Element-Set Extraktionsprozess. Das Problem ist überraschend schwer und ist Gegenstand der einiges an Forschung. Der beste Weg um zu sehen, wohin dieses Artikels ist es, einen Blick auf das Demoprogramm in Abbildung 1.
.png)
Abbildung 1 extrahieren häufig Item-Sets aus Transaktionen
Das Demoprogramm richtet eine dummy-Liste der 10 Transaktionen. Hinter den Kulissen gibt es insgesamt 12 Elemente in einem hypothetischen Supermarkt: Äpfel, Brot, Sellerie, Donuts, Eier, Mehl, Trauben, Honig, Vereisung, Gelee, Grünkohl und Salat. Die erste Transaktion ist (Äpfel, Brot, Sellerie, Mehl). Die Demo dann zeigt wie rohe Transaktionen in Ganzzahlen 0-basiert, für die effiziente Bearbeitung codiert werden können. Weil Äpfel Farbe entspricht 0, Brot, 1 Sellerie, 2 und So weiter, ist die erste Transaktion als (0, 1, 2, 5) codiert.
Der Algorithmus zum Extrahieren von häufigen Element-Sets erfordert drei Eingabeparameter. Der erste Parameter ist ein Mindestbetrag, ab-Wert für ein Element-Set als häufige einzustufen. Dies wird in der Regel den Unterstützungswert bezeichnet. In der Demo wird der Unterstützungswert bis 0.30, festgelegt, was bedeutet, dass 0,30 * 10 = 3 ist die minimale Anzahl von Zeiten, die ein Element-Set auftreten muss, in der Liste aller Transaktionen für das Element-Set der Ergebnis-Liste der häufigen Element-Sets hinzugefügt werden. Anderes Problemdomänen werden verschiedene sinnvolle Unterstützungswerte haben.
Der zweite Eingabeparameter ist die Mindestgröße für ein Element-Set. In der Demo, die Wert auf 2 festgelegt, ist also ein Element-Set von (Äpfel, Donuts) wird untersucht, aber ein Element-Set nur (Äpfel) ist nicht. Der dritte input-Parameter wird die maximale Größe eines Item-Sets. Hier wird dieser Wert 4 festgelegt, so dass nur Element-Sets mit bis zu vier Elemente, z. B. (Äpfel, Sellerie, Eier, Trauben), während größere geprüft werden-z. B. (Äpfel, Brot, Donuts, Mehl, Honig) Item-Sets sind nicht.
Das Demoprogramm Ruft die Methode um häufige Element-Sets aus der Liste der Transaktionen zu extrahieren und findet insgesamt 12 häufige Element-Sets. Ist das erste häufige Element-Set (0, 1), fünf Mal in der Transaktionsliste auftritt. Das letzte häufige Element-Set ist (0, 1, 2, 5), der dreimal vorkommt. Die Demo endet durch die häufigen Element-Sets in Form einer Zeichenfolge anzeigen.
Dieser Artikel setzt voraus, Sie haben mindestens Mittelstufe Programmierkenntnisse, aber übernimmt keine weißt du nichts über Zuordnung Regel lernen. Der komplette Demo-Programm-Code wird präsentiert in diesem Artikel, und es ist auch erhältlich als Download unter msdn.microsoft.com/magazine/msdnmag0114. Die Demo ist in C#- aber Sie sollte nicht zu viel Mühe-Umgestaltung in eine andere Sprache, wie z. B. Python. Alle normalen Fehlerüberprüfung wurde entfernt, um die Größe des Codes kleiner zu halten.
Warum häufige Element-Set-Extraktion ein schwieriges Problem ist?
Bei ersten Gedanken scheint extrahieren häufig Element-Sets aus einer Liste von Transaktionen so schwierig nicht. Ein einfacher Brute-Force-Ansatz wäre, einfach alle möglichen Produkt-Sets zu generieren und durchlaufen die Transaktionen für jeden Kandidaten, zählen die Häufigkeit des Auftretens, die der Kandidat scheint zu sehen, ob das Element-Set Anzahl der minimalen Unterstützung erfüllt. Leider ist die Anzahl der möglichen Element-Sets in allen aber künstlich kleine Probleme, unvorstellbar große. Angenommen, haben ein typischer Supermarkt weit mehr als 10.000 verschiedene Artikel auf Lager. Die Anzahl der Element-Sets der Größe 2 ist auswählen (10.000, 2) = 49,995,000, wo auswählen (n, k) ist die Anzahl der Möglichkeiten n Elementen k Elemente auswählen. Die Anzahl der möglichen Element-Sets Größe 9 ist auswählen (10.000, 9) = 2,745,826,321,280,434,929,668,521,390,000, was ist... nun, viel.
Es gibt verschiedene clevere Algorithmen effizient häufige Element-Sets aus einer Liste von Transaktionen, einschließlich der Apriori, Eclat und FP-Wachstum-Algorithms extrahiert. Jeder Algorithmus hat viele Variationen. Die Demo-Anwendung verwendet eine Variante des Apriori-Algorithmus, die in dargestellt ist Abbildung 2.
.png)
Abbildung 2 der Apriori-Algorithmus in Aktion
Kurz gesagt, der Apriori-Algorithmus beginnt mit allen häufigen Element-Sets der Größe k = 1 — einzelne Elemente, die die Unterstützung-Schwelle in der Liste der Transaktionen zu erfüllen. Anschließend der Bauprozess iterativ häufige Element-Sets der Größe k = 2, 3 und So weiter, bis keine neuen häufige Element-Sets gefunden werden.
Das Bild im Abbildung 2 zeigt wie Element-Sets der Größe k = 4 bestehen. Eine Liste häufiger Element-Sets aller Größen wird beibehalten. In der Abbildung gibt es derzeit drei häufige Element-Sets mit grosse k = 3: (0, 2, 3), (0, 2, 8) und (0, 3, 6). Der Algorithmus führt auch eine Liste der Elemente, die in der Zeit zu einem bestimmten Zeitpunkt gültig sind. Hier gibt es fünf gültigen Elemente: {0, 2, 3, 6, 8}. Gültigen Elemente, Element-Sets der Größe k häufig zu konstruieren = 4 sind die unterschiedlichen Elemente in alle häufigen Element-Sets Größe k-1 = 3.
Der Algorithmus scannt jede häufige Element-Set der Größe k = 3. Für jedes vorhandene Element-Set, ein neuer Kandidaten häufig Element-Set der Größe k = 4 wird generiert. So ist der erste Kandidat (0, 2, 3,?). Die? ein gültiges Element eingetragen werden können. Der Algorithmus setzt voraus, dass die Elemente in ein Element-Set immer in Reihenfolge gespeichert werden also die? nur 6 oder 8 kann in diesem Fall sein. Jedes neue Kandidaten wird untersucht, um zählen, wie oft sie in der Liste der Transaktionen auftritt. Erfüllt die Transaktionsanzahl Anzahl der minimale Unterstützung, wird der Kandidat auf der Liste der häufigen Element-Sets hinzugefügt.
Der Algorithmus reduziert die Höhe der Berechnung benötigt, verglichen mit der Brute-Force-Generation-Ansatz. Beachten Sie, dass z. B. das zweite vorhandene häufige Element-Set mit grosse k = 3 ist (0, 2, 8). Die potenziellen Kandidaten haben Form (0, 2, 8,?). Aber, da kein gültiges Element größer als 8 ist, gibt es keine möglichen Kandidaten generiert.
Allgemeine Programmstruktur
Die allgemeine Struktur des Demo-Programm mit einigen WriteLine-Anweisungen entfernt und ein paar kleinere Änderungen präsentiert sich in Abbildung 3. Um die Demo zu erstellen, ich Visual Studio 2012 gestartet und erstellt ein neue Konsole-Anwendung-Programm mit dem Namen FreqItemSets. Die Demo hat keine bedeutenden .NET-Abhängigkeiten, und eine relativ neue Version von Visual Studio wird gut funktionieren. Nachdem der Template-Code in den Editor geladen, im Fenster Projektmappen-Explorer ich benannte Datei Program.cs zu FreqItemSetProgram.cs und Visual Studio automatisch umbenannt Klasse Programm für mich.
Abbildung 3-Demo-Programm-Struktur
using System;
using System.Collections.Generic;
namespace FreqItemSets
{
class FreqItemSetProgram
{
static void Main(string[] args)
{
try
{
Console.WriteLine("\nBegin frequent item-set extraction demo\n");
string[] rawItems = new string[] { "apples", "bread ", "celery", "donuts",
"eggs ", "flour ", "grapes", "honey ", "icing ", "jelly ",
"kale ", "lettuce" };
int N = rawItems.Length; // total number of items to deal with ( [0..11] )
string[][] rawTransactions = new string[10][];
rawTransactions[0] = new string[] { "apples", "bread ", "celery",
"flour " };
rawTransactions[1] = new string[] { "bread ", "eggs ", "flour " };
rawTransactions[2] = new string[] { "apples", "bread ", "donuts",
"eggs " };
rawTransactions[3] = new string[] { "celery", "donuts", "flour ",
"grapes" };
rawTransactions[4] = new string[] { "donuts", "eggs " };
rawTransactions[5] = new string[] { "donuts", "eggs ", "jelly " };
rawTransactions[6] = new string[] { "apples", "bread ", "donuts",
"icing " };
rawTransactions[7] = new string[] { "bread ", "grapes", "honey " };
rawTransactions[8] = new string[] { "apples", "bread ", "celery",
"flour ", "kale " };
rawTransactions[9] = new string[] { "apples", "bread ", "celery",
"flour " };
for (int i = 0; i < rawTransactions.Length; ++i) {
Console.Write("[" + i + "] : ");
for (int j = 0; j < rawTransactions[i].Length; ++j)
Console.Write(rawTransactions[i][j] + " ");
Console.WriteLine("");
}
List<int[]> transactions = new List<int[]>();
transactions.Add(new int[] { 0, 1, 2, 5 });
transactions.Add(new int[] { 1, 4, 5 });
transactions.Add(new int[] { 0, 1, 3, 4 });
transactions.Add(new int[] { 2, 3, 5, 6 });
transactions.Add(new int[] { 3, 4 });
transactions.Add(new int[] { 3, 4, 9 });
transactions.Add(new int[] { 0, 1, 3, 8 });
transactions.Add(new int[] { 1, 6, 7 });
transactions.Add(new int[] { 0, 1, 2, 5, 10 });
transactions.Add(new int[] { 0, 1, 2, 5 });
for (int i = 0; i < transactions.Count; ++i) {
Console.Write("[" + i + "] : ");
for (int j = 0; j < transactions[i].Length; ++j)
Console.Write(transactions[i][j].ToString() + " ") ;
Console.WriteLine("");
}
Console.WriteLine("");
double minSupportPct = 0.30;
int minItemSetLength = 2;
int maxItemSetLength = 4;
List<ItemSet> frequentItemSets =
GetFrequentItemSets(N, transactions, minSupportPct,
minItemSetLength, maxItemSetLength);
Console.WriteLine("\nFrequent item-sets in numeric form are:");
for (int i = 0; i < frequentItemSets.Count; ++i)
Console.WriteLine(frequentItemSets[i].ToString());
Console.WriteLine("\nFrequent item-sets in string form are:");
for (int i = 0; i < frequentItemSets.Count; ++i) {
for (int j = 0; j < frequentItemSets[i].data.Length; ++j) {
int v = frequentItemSets[i].data[j];
Console.Write(rawItems[v] + " ");
}
Console.WriteLine("");
}
Console.WriteLine("\nEnd frequent item-set extraction demo\n");
Console.ReadLine();
}
catch (Exception ex)
{
Console.WriteLine(ex.Message); Console.ReadLine();
}
}
static List<ItemSet> GetFrequentItemSets(int N, List<int[]> transactions,
double minSupportPct, int minItemSetLength, int maxItemSetLength) { .
.
}
static int CountTimesInTransactions(ItemSet itemSet,
List<int[]> transactions) { .
.
}
}
public class ItemSet { .
.
}
} // ns
An der Spitze des Quellcodes löschte ich alle unnötigen Verweise auf .NET Namespaces, wobei nur System und Collections.Generic. Die Demo beginnt mit dem Einrichten einer Auflistung aller Elemente in einem hypothetischen Supermarkt:
string[] rawItems = new string[] { "apples", "bread ", "celery",
"donuts", "eggs ", "flour ", "grapes", "honey ", "icing ",
"jelly ", "kale ", "lettuce" };
int N = rawItems.Length; // total items in inventory
Als nächstes setzt das Programm 10 fest programmierte Transaktionen. In den meisten Szenarien werden Ihre Transaktionen in einer Textdatei oder SQL-Datenbank gespeichert. Beachten Sie doppelte Transaktionen sind zulässig und nicht alle Elemente im Inventar befinden sich unbedingt in einer Transaktion:
string[][] rawTransactions = new string[10][];
rawTransactions[0] = new string[] { "apples", "bread ", "celery", "flour "};
rawTransactions[1] = new string[] { "bread ", "eggs ", "flour " };
...
rawTransactions[9] = new string[] { "apples", "bread ", "celery", "flour "};
Die Demo richtet nach der Anzeige der rohen Transaktionen, eine Liste der codierten Transaktionen 0-basiert. Statt Hartcodierung, würde in den meisten Fällen Sie programmgesteuert die numerischen Transaktionen aus den rohen Transaktionen erstellen. Beachten Sie, dass die Elemente in jeder Transaktion unterscheidbar und sortiert sind:
List<int[]> transactions = new List<int[]>();
transactions.Add(new int[] { 0, 1, 2, 5 });
transactions.Add(new int[] { 1, 4, 5 });
...
transactions.Add(new int[] { 0, 1, 2, 5 });
Nach der Anzeige der Liste der Transaktionen, der drei input-Parameter-Wert werden eingerichtet. Hier ist die maximale Größe des ein häufiges Element-Set 4 festgelegt. Sie möchten möglicherweise Durchsuchen Sie die Liste der Transaktionen und legen Sie den Wert auf die Länge der längsten Transaktion:
double minSupportPct = 0.30;
int minItemSetLength = 2;
int maxItemSetLength = 4;
Die Arbeit wird durch einen Aufruf von der Methode GetFrequentItemSets ausgeführt:
List<ItemSet> frequentItemSets =
GetFrequentItemSets(N, transactions, minSupportPct,
minItemSetLength, maxItemSetLength);
Beachten Sie, dass als Ergebnis eine Programm definierten ItemSet-Klasse verwendet. Die Demo kommt zu dem Schluss, die häufigen Element-Sets in numerische und String-Form angezeigt.
Klasse ItemSet
Im Wesentlichen ist ein Element-Set nur ein Array von Ganzzahlen, sodass kein Programm definierten Klasse erforderlich ist. Aber meiner Meinung nach eine Klasse in diesem Fall vereinfacht den Code. Die ItemSet-Klasse ist definiert Abbildung 4.
Abbildung 4 die ItemSet-Klasse
public class ItemSet
{
public int N; // data items are [0..N-1]
public int k; // number of items
public int[] data; // ex: [0 2 5]
public int hashValue; // "0 2 5" -> 520 (for hashing)
public int ct; // num times this occurs in transactions
public ItemSet(int N, int[] items, int ct) { .
.
}
private static int ComputeHashValue(int[] data) { .
.
}
public override string ToString() { .
.
}
public bool IsSubsetOf(int[] larger) { .
.
}
private static int IndexOf(int[] array, int item, int startIdx) { .
.
}
}
Memberfeld N ist die Gesamtzahl der Elemente im Inventar. Feld-k ist die Größe der Element-Set. Arraydaten hält die Elementwerte. Feld HashValue ist eine eindeutige Ganzzahl um das Element-Set zu identifizieren, also doppelte Element-Sets vermieden werden können. Feld-ct ist die Häufigkeit des Auftretens, die das Element-Set in die Transaktionen-Liste angezeigt wird. Der ItemSet-Konstruktor wird definiert:
public ItemSet(int N, int[] items, int ct)
{
this.N = N;
this.k = items.Length;
this.data = new int[this.k];
Array.Copy(items, this.data, items.Length);
this.hashValue = ComputeHashValue(items);
this.ct = ct;
}
Die Hilfsmethode, den HashValue zu berechnen ist:
private static int ComputeHashValue(int[] data)
{
int value = 0;
int multiplier = 1;
for (int i = 0; i < data.Length; ++i) {
value = value + (data[i] * multiplier);
multiplier = multiplier * 10;
}
return value;
}
Die Helfer konvertiert die Elementwerte in eine einzelne ganze Zahl in umgekehrter Reihenfolge. Wenn die Elemente sind (0, 2, 5), ist der Hash-Wert beispielsweise 520. Die Methode funktioniert in umgekehrter Reihenfolge mit führender 0-Elemente, weil sonst (0, 2, 5) und (2, 5) würde beide hash-bis 25.
IsSubsetOf-Methode gibt true, wenn das Element-Set-Objekt eine Teilmenge einer Transaktion ist:
public bool IsSubsetOf(int[] trans)
{
int foundIdx = -1;
for (int j = 0; j < this.data.Length; ++j) {
foundIdx = IndexOf(trans, this.data[j], foundIdx + 1);
if (foundIdx == -1) return false;
}
return true;
}
Die Methode ist kurz, aber etwas subtiler. Da Transaktionen und Item-Sets bestellt, nachdem ein Elementwert ein Element-Set innerhalb einer Transaktion gefunden wurde, die Suche nach der nächsten Elementwert muss nicht am Index 0 beginnen — es kann beginnen am nächsten Index nach Standort, wo der vorherige Elementwert gefunden wurde. Helfer IndexOf wird definiert:
private static int IndexOf(int[] array, int item, int startIdx)
{
for (int i = startIdx; i < array.Length; ++i) {
if (i > item) return -1; // i is past target loc
if (array[i] == target) return i;
}
return -1;
}
IndexOf-Methode nutzt auch der Bestellung. Wenn der aktuelle Suche-Index größer als den Wert des Target-Element gesucht wird ist, wird die Suche ist zu weit gegangen und nie das Element finden. Genommen Sie eine Transaktion ist (0, 2, 4, 5, 6, 8) und das Ziel-Element gesucht wird 3 an. Der neueste Wert 3 kann auftreten, weil Transaktionen bestellt sind, wäre in einer Transaktion, die Form hat (0, 1, 2, 3, x, X). Die ToString-Methode verwendet Zeichenfolgenverkettung für Einfachheit:
public override string ToString()
{
string s = "{ ";
for (int i = 0; i < data.Length; ++i)
s += data[i] + " ";
return s + "}" + " ct = " + ct; ;
}
Die GetFrequentItemSets-Methode
Die Definition der Methode GetFrequentItemSets beginnt:
static List<ItemSet> GetFrequentItemSets(int N, List<int[]> transactions,
double minSupportPct, int minItemSetLength, int maxItemSetLength)
{
int minSupportCount = (int)(transactions.Count * minSupportPct);
...
Statt einen Eingabeparameter für die Unterstützung-Schwelle als Prozentsatz der Transaktionen, sollten Sie eine absolute Zählung verwenden. Als nächstes werden drei wichtige Sammlungen instanziiert:
Dictionary<int, bool> frequentDict = new Dictionary<int, bool>();
List<ItemSet> frequentList = new List<ItemSet>();
List<int> validItems = new List<int>();
...
Sammlung FrequentList hält alle häufigen Element-Sets gefunden. Anstelle von häufigen Element-Sets aller Größen in einer Liste gespeichert werden, ist eine wichtige Alternative, ein Array von Listen zu verwenden wo gibt es separate Listen für jede Element-Set-Größe. Sammlung FrequentDict hält die IDs der Element-Sets, die die FrequentList hinzugefügt wurden, so dass Duplikate vermieden werden können. Sammlung ValidItems hält Elementwerte, die zu einem bestimmten Zeitpunkt im Algorithmus, einen vorhandenen häufige Element-Satz Größe k-1 ein Kandidat häufige Element-Set der Größe k generieren hinzugefügt werden können. Als nächstes werden die Einzelposten-Werte in die Transaktionsliste gezählt:
int[] counts = new int[N];
for (int i = 0; i < transactions.Count; ++i)
{
for (int j = 0; j < transactions[i].Length; ++j) {
int v = transactions[i][j];
++counts[v];
}
}
...
Dann diese Elementwerte, die die Anzahl der minimalen Unterstützung erfüllen zum Erstellen von häufigen ItemSet Objekte der Größe k = 1, die dann zu der Liste der häufigen Elemente hinzugefügt werden:
for (int i = 0; i < counts.Length; ++i)
{
if (counts[i] >= minSupportCount) {
validItems.Add(i); // i is the item-value
int[] d = new int[1]; // ItemSet ctor wants an array
d[0] = i;
ItemSet ci = new ItemSet(N, d, 1); // size 1, ct 1
frequentList.Add(ci); // it's frequent
frequentDict.Add(ci.hashValue, true); // record
} // else skip this item
}
...
Die wichtigsten Verarbeitungsschleife im Pseudo-Code ist:
loop for size k = 2, 3, until done
foreach existing freq item-set of size k-1
foreach valid item
create a candidate item-set
count times candidate in transactions
if candidate meets support threshold
if candidate not already in frequent list
add candidate to frequent, rec list
end each valid item
update valid items
end each freq item-set
end main loop
Die wichtigsten Verarbeitungsschleife liegt bis etwa so:
bool done = false;
for (int k = 2; k <= maxItemSetLength && done == false; ++k)
{
done = true;
int numFreq = frequentList.Count;
...
Die Hauptschleife wird geschlossen, wenn alle angegebene Größen Prüfung gewesenIned, oder wenn kein neues Element-Sets von der aktuellen Größe gefunden werden. Da alle häufigen Element-Sets werden in einer Liste gespeichert (und dieser Liste hinzugefügt wird), wird die ursprüngliche Größe der Liste für den Einsatz von der inneren Schleifen, die festgelegt werden gespeichert bis etwa so:
for (int i = 0; i < numFreq; ++i)
{
if (frequentList[i].k != k - 1) continue;
for (int j = 0; j < validItems.Count; ++j)
{
int[] newData = new int[k]; // data for a candidate item-set
...
Zwei wichtige Features des Algorithmus sind, dass der Algorithmus nur häufiges Element-Sets aus der vorherigen Iteration konstruieren neuer Kandidat Element-Sets und nur gültiges Elementwerte untersucht um die Kandidaten zu beenden. Die Kandidaten häufig Element-Sets werden erstellt:
for (int p = 0; p < k - 1; ++p)
newData[p] = frequentList[i].data[p];
if (validItems[j] <= newData[k - 2]) continue;
newData[k - 1] = validItems[j];
ItemSet ci = new ItemSet(N, newData, -1);
...
Dieser Code ist etwas schwierig. Zuerst werden die Daten aus der aktuellen häufigen Element-Gruppe in der Kandidat kopiert. Der Kandidat mit dem aktuellen Wert der gültiges Element abgeschlossen ist und, wie oben beschrieben, können Sie Kandidaten basierend auf der Reihenfolge Eigenschaft von Element-Sets eliminiert. Der ItemSet-Konstruktor akzeptiert einen Dummy-Wert-1 für das Feld "ct", da die Häufigkeit des Auftretens, die der Kandidat in die Transaktionen angezeigt wird, ist noch nicht bekannt.
Die zwei inneren Schleifen sind gefesselt durch den Code in Abbildung 5.
Abbildung 5 die zwei inneren Schleifen binden
...
if (frequentDict.ContainsKey(ci.hashValue) == true)
continue;
int ct = CountTimesInTransactions(ci, transactions);
if (ct >= minSupportCount)
{
ci.ct = ct;
frequentList.Add(ci);
frequentDict.Add(ci.hashValue, true);
done = false;
}
} // j
} // i
...
Wenn der Kandidat bereits in der häufigen Element-Set-Liste angezeigt wird, gibt es keine Notwendigkeit, es weiter zu analysieren. Wenn nicht, und wenn der Bewerber die Anzahl der minimalen Unterstützung erfüllt, der Kandidat ist ein Sieger und es ist die Liste der häufigen Element-Sets hinzugefügt. Boolean Spuren getan, ob jedes neue Element-Sets gefunden wurden. Für jeden gegebenen Wert von k wenn keine neuen häufige Element-Sets gefunden werden, gibt es keine Möglichkeit, die ein häufiges Element-Set je gefunden werden.
Nachdem alle Kandidaten für die aktuelle Größe k konstruiert und geprüft haben, wird die Liste der gültigen Elemente für die nächste Iteration aktualisiert, wie in Abbildung 6.
Abbildung 6 Aktualisierung der Liste der gültigen Elemente
...
validItems.Clear();
Dictionary<int, bool> validDict = new Dictionary<int, bool>();
for (int idx = 0; idx < frequentList.Count; ++idx) {
if (frequentList[idx].k != k) continue;
for (int j = 0; j < frequentList[idx].data.Length; ++j) {
int v = frequentList[idx].data[j]; // item
if (validDict.ContainsKey(v) == false) {
validItems.Add(v);
validDict.Add(v, true);
}
}
}
validItems.Sort();
} // next k
...
Obwohl nicht ganz offensichtlich zuerst, es stellt sich heraus, dass beim Erstellen von neuen Kandidaten häufig Element-Sets der Größe k mit vorhandenen häufige Element-Sets Größe k-1 die einzige gültige Elemente um die Kandidaten zu vervollständigen Elementwerte sind, die in die häufigen Element-Sets Größe k-1 auftreten. Dieses Update ist zeitaufwändig, in einigen Szenarien erhalten Sie bessere Leistung durch Überspringen sie und verwenden stattdessen die ursprüngliche Liste der gültigen Elemente für grosse k erstellt = 1.
Die Methode schließt mit dem Filtern der Ergebnisse von Element-Set Mindestlänge:
...
List<ItemSet> result = new List<ItemSet>();
for (int i = 0; i < frequentList.Count; ++i)
{
if (frequentList[i].k >= minItemSetLength)
result.Add(new ItemSet(frequentList[i].N,
frequentList[i].data, frequentList[i].ct));
}
return result;
}
Hilfsmethode CountTimesInTransactions, früher wird definiert:
static int CountTimesInTransactions(ItemSet itemSet,
List<int[]> transactions)
{
int ct = 0;
for (int i = 0; i < transactions.Count; ++i) {
if (itemSet.IsSubsetOf(transactions[i]) == true)
++ct;
}
return ct;
}
Zusammenfassung
Sowie die Erklärung, die in diesem Artikel vorgestellten sollten erhalten, einsatzbereit, wenn Sie jemals brauchen häufig Element-Sets aus einer Liste von Transaktionen mit dem Apriori-Algorithmus bestimmen. Es ist, zwar unwahrscheinlich, dass Sie immer direkt mit Supermarkt Transaktionen arbeiten werde gibt es viele Szenarien, in denen extrahieren häufig Element-Sets nützlich sein kann. Bei NUI, Sie können sich vorstellen von Transaktionen als eine Liste von Benutzerkommandos — z. B. der Text in ein Textfeld für die Suche eingegeben — sowie die Elemente, die Worte, die den Befehl bilden. Identifizieren diese Worte, die häufig gemeinsam auftreten, kann helfen, bessere Suchergebnisse zu generieren.
Dr.James McCaffrey arbeitet für Microsoft Research in Redmond, Washington Er arbeitete an verschiedenen Microsoft-Produkten, einschließlich Internet Explorer und Bing. Er kann erreicht werden unter jammc@microsoft.com.
Unser Dank gilt dem folgenden technischen Experten für die Durchsicht dieses Artikels: Richard Hughes (Microsoft Research)