Zastosowanie wirtualnego super komputera do znajdowania reguł związku

Abstract

Przedstawiamy opracowaną przez nas architekturę wirtualnego superkomputera, która umożliwia równoległe przetwarzanie danych przez wybraną klasę algorytmów eksploracji danych (ang. data mining), tzn. algorytmy odkrywania reguł związku (ang. association rules). System pozwala na wydajną analizę dużych porcji danych przez zespół niezależnych od siebie komputerów – klientów. Zakłada się, że urządzenia te są typowymi komputerami osobistymi i nie posiadają dużej mocy obliczeniowej właściwej superkomputerom. Prezentowana architektura oparta jest na technologii Java, przy szczególnym wykorzystaniu platformy J2EE i serwera aplikacyjnego JBoss. W referacie przedstawione są algorytmy zarządzania procesem pobierania danych, dzielenia na części i przydziału ich konkretnym klientom. Omówione są także, bardzo ważne dla całego procesu, algorytmy łączenia wyników przetwarzania danych przez poszczególne klienty.
Autorzy: Michał Kubisz, Piotr Martyniak, Bartosz Podsiadły

1. WSTĘP

1.1. ALGORYTM APRIORI

Jako algorytm odkrywania reguł związku wybraliśmy zaproponowany w [1] algorytm Apriori. Wysoka efektywność tego algorytmu sprawia, że jest on powszechnie wykorzystywany w tej klasie algorytmów eksploracji danych. Pomimo znacznego polepszenia efektywności znajdowania reguł związku przez algorytm Apriori w porównaniu z innymi proponowanymi algorytmami, jest on wciąż niezwykle złożony obliczeniowo. W praktyce do generowania reguł w oparciu o duże ilości danych wykorzystywane są komputery o olbrzymiej mocy obliczeniowej. W swojej pracy pokazujemy możliwość rozproszenia tego procesu, co w praktyce mogłoby doprowadzić do uzyskiwania zbliżonych rezultatów przy znacznym ograniczeniu kosztów.

Algorytm Apriori nadaje się do rozpraszania. Wprawdzie ilość danych wejściowych, które trzeba przesłać do każdego komputera – klienta, jest duża, fakt olbrzymiej złożoności obliczeniowej algorytmu oraz niewielkiej – przy rzeczywistych zastosowaniach – ilości generowanych reguł, usprawiedliwia koszt związany z rozproszeniem.

1.2. PRZETWARZANE DANE

W związku z faktem, że najczęstszym praktycznym zastosowaniem algorytmów odkrywania reguł związku są badania preferencji klientów dużych sklepów (przykładowa reguła: pieluszki i soczek dla niemowląt -> piwo), zdecydowaliśmy się wykorzystać dane z tego obszaru w naszych badaniach.

Aby móc poprawnie badać uzyskane wyniki stworzyliśmy generator danych, który przyjmuje na wejściu reguły związku i wypełnia bazę danych w taki sposób, aby odpowiadały podanym zależnościom.