Hauptnavigation

ALLGEMEINES

FORSCHUNG

LEHRE

MITARBEITER

Seminar: Knowledge Discovery for Ubiquitous Computing

Veranstaltung Wochentag Termin Ort
041408 Donnerstag 14.15 - 16.00 R.113, GB IV (Campus Süd)

Inhalt

Das klassische Data Mining analysiert sehr große Datenmengen, die typischerweise zentral auf einem Server gespeichert sind. Deshalb heißt es ja auch: Knowledge Discovery in Databases. Dabei gibt es weder starke Rechenzeit- noch Platzbeschräkungen. Es gibt aber nicht weniger große Datenmengen, die bei Sensormessungen anfallen, die sich aus verteilten Quellen ergeben, die von mobilen Systemen stammen oder von ihnen genutzt werden sollen. Auch das ubiqutous computing schafft Daten und braucht Datenanalyse. Hierfür braucht man aber neue Techniken, die verteilt arbeiten und wenig Zeit und Speicherplatz verbrauchen.

Es entsteht gerade ein neues Forschungsgebiet: Knowledge Discovery for Ubiquitous Computing. Hier werden Verfahren entwickelt für

  • Verteiltes Data Mining
    • Mehrere Datenbanken des selben Schemas (z.B. die Verkaufsdaten verschiedener Länder eines Konzerns) sollen analysiert werden, ohne dass man alle Daten an einem Ort zusammenbringt.
    • In Peer-to-peer-Netzwerken sind Daten mit unterschiedlichen Schemata, aber zumindest teilweise den gleichen Tupeln, und man möchte aus all diesen Daten etwas lernen.
    • [7, 18, 2, 6, 17, 3, 19]
  • Datenströme
    • Sensornetzwerke messen Daten an verschiedenen Orten. Man möchte sich aber ein Gesamtbild verschaffen.
    • Obwohl die Daten nicht sehr dynamisch sind, sind es schlicht so viele, dass der Data Mining Algorithmus sie wie einen Strom behandeln muss.
    • [4, 8, 12, 13, 9, 14] [16, 15, 5]
  • Vertraulichkeit (privacy)
    • Gerade wegen der Datenanalyse ist die Vertraulichkeit von Daten oft in Gefahr. So kann aus verteilten Datenbeständen (z.B. Kreditkartenabrechnung, Telefonabrechnung, Krankenkassendaten und Adressdaten) manchmal eindeutig eine Person identifiziert werden, die zu einem bestimmten Zeitpunkt an einem bestimmten Ort war, eine bestimmte Krankheit hat... Deshalb gibt es nun Methoden des privacy-preserving data mining.
    • [10, 11, 1]

Lernziel

In diesem Seminar erarbeiten Sie sich selbst die neuen Methoden. Das ist genau die Situation, die Sie später im Berufsleben erfahren werden: ein neues Thema kommt auf und niemand vermittelt es Ihnen. Sie müssen sich selbst einarbeiten. Am Anfang verstehen Sie nur Bruchstücke der Artikel - am Ende war es dann doch nicht so schwer. Diese Situation wird mit dem Seminar geübt. Im Gegensatz zum Berufsleben wird Ihnen jetzt noch geholfen!

Das Seminar verhilft dazu, aktuelle Forschungsergebnisse zu verstehen.

Vorgehen

Schauen Sie sich die angegebene Literatur an: welches Referat möchten Sie gern halten? Es sind weit mehr Artikel angegeben, als in ein Seminar passen. Es kann natürlich sein, dass sich mehrere auf den selben Artikel stürzen. Sie sind sicherer, wenn Sie sich mehrere Artikel aussuchen!

Sie sehen schon an den Autoren und Titeln, dass einige Artikel zusammen 1 Thema ergeben. Allerdings gibt es noch viel mehr Artikel, als sie hier aufgeführt sind...

Ein Referat zu halten, bedeutet:

  • Den Originaltext lesen, einige der zitierten Aufsätze und ggf. Hintergrundmaterial lesen.
  • Eine Präsentation des Textes im Seminar abhalten.
  • Eine schriftliche Ausarbeitung des Originaltextes mit Bezügen zu den anderen Referaten abgeben.

Beginn und Anmeldung

Das Seminar beginnt am Donnerstag, 22.10.2009, 14 Uhr c.t.. Die Anmeldung erfolgt durch Erscheinen im R 113 des GB IV. an diesem ersten Termin. Eine zusätzliche Anmeldung ist nicht erforderlich.

Voraussetzungen

Voraussetzung für das Seminar ist ein abgeschlossenes Grundstudium und die Wahlpflichtveranstaltung 'Darstellung, Erwerb und Verarbeitung von Wissen'. Das Seminar passt gut zu den Vorlesungen 'Wissensentdeckung' und 'Maschinelles Lernen', die aber nicht vorausgesetzt werden.

Literatur

[1] Maurizio Atzori, Francesco Bonchi, Fosca Giannotti, and Dino Pedreschi. Anonymity preserving pattern discovery. In The International Journal on Very Large Data Bases, 2008.
[2] Sanghamitra Bandyopadhyay, Chris Giannella, Ujjwal Maulik, Hillol Kargupta, Kun Liu, and Souptik Datta. Clustering distributed data streams in peer-to-peer environments. In Information Science Journal, 2006.
[3] Yitzhak Birk, Liran Liss, Assaf Schuster, and Ran Wolff. A local algorithm for ad hoc majority voting via charge fusion. 2004..
[4] Joel Branch, Boleslaw Szymanski, Chris Giannella, Ran Wolff, and Hillol Kargupta. In-network outlier detection in wireless sensor networks. In ICDCS '06: Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, 2006.
[5] Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava. Finding hierarchical heavy hitters in streaming data. In ACM Transactions on Knowledge Discovery from Data, 2008.
[6] Kamalika Das, Kanishka Bhaduri, Kun Liu, and Hillol Kargupta. Distributed identification of top-l inner product elements and its application in a peer-to-peer network. In IEEE Transactions on Knowledge and Data Engineering, 2008..
[7] Souptik Datta, Kanishka Bhaduri, Chris Giannella, Ran Wolff, and Hillol Kargupta. Distributed data mining in peer-to-peer networks. In IEEE Internet Computing, 2006.
[8] Souptik Datta, C. Giannella, and Hillol Kargupta. K-means clustering over a large, dynamic network. In Proceedings of 2006 SIAM Conference on Data Mining, 2006.
[9] Mohamed Medhat Gaber, Arkady Zaslavsky, and Shonali Krishnaswamy. Resource-aware knowledge discovery in data streams. In Proceedings of the First International Workshop on Knowledge Discovery in Data Streams, 2004..
[10] Bobi Gilburd, Assaf Schuster, and Ran Wolff. k-ttp: a new privacy model for large-scale distributed environments. In KDD '04: Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, 2004.
[11] Bobi Gilburd, Assaf Schuster, and Ran Wolff. Privacy-preserving data mining on data grids in the presence of malicious participants. In Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing, 2004.
[12] Hillol Kargupta and Byung-Hoon Park. Mining decision trees from data streams in a mobile environment. In ICDM '01: Proceedings of the 2001 IEEE International Conference on Data Mining, 2001.
[13] Hillol Kargupta and Byung-Hoon Park. A fourier spectrum-based approach to represent decision trees for mining data streams in mobile environments. In IEEE Transactions on Knowledge and Data Engineering, 2004.
[14] Denis Krivitski, Assaf Schuster, and Ran Wolff. A local facility location algorithm for sensor networks. In Distributed Computing in Sensor Systems, 2005..
[15] Gurmeet Singh Manku and Rajeev Motwani. Approximate counts over data streams. In Procs. of the 28th VLDB Conference, 2002.
[16] Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. Approximate medians and other quantiles in one pass and with limited memory. In SIGMOD '98, 1998.
[17] Assaf Schuster, Ran Wolff, and Dan Trock. A high-performance distributed algorithm for mining association rules. In Knowledge and Information Systems, 2005.
[18] Ran Wolff, Kanishka Bhaduri, and Hillol Kargupta. Local l2-thresholding based data mining in peer-to-peer systems. In Proceedings of the Sixth SIAM International Conference on Data Mining (SDM 06), 2006.
[19] Michael Wurst, Katharina Morik, and Ingo Mierswa. Localized alternative cluster ensembles for collaborative structuring.. In Proceedings of the European Conference on Machine Learning, 2006.