Tietojenkäsittelytieteen laitos

58309101 Seminaari: Tiedon louhinta verkoista (3 op), kevät 09

Tämä sivu: http://www.cs.helsinki.fi/hannu.toivonen/teaching/seminaariK09/

Seminaari kokoontuu kevätlukukaudella 2009 tiistaisin (ja maanantaisin) klo 10-12 salissa C220.

Huom: seminaarin 1. kokoontuminen on ti 13.1. Kaikille osallistujille läsnäolo pakollinen.

Seminaarin aihepiiri

Tiedon louhinnassa (data mining, knowledge discovery) tutkitaan ja kehitetään algoritmeja suurten tietoaineistojen analysointiin. Tässä seminaarissa käsitellään erityisesti verkkomuotoisen datan louhintaan kehitettyjä menetelmiä tutkimuskirjallisuuteen perustuen. Verkko (graph, network) on yleismuotoinen ja joustava tiedon esitystapa ja louhintamenetelmien kannalta hyvin erilainen kuin esimerkiksi taulukkomuoto. Analysoinnin kohteita voivat olla esim. ihmisten muodostamat sosiaaliset verkostot, hypertekstidokumenttien verkko kuten www tai biologiset verkot (esim. proteiinien interaktiot).

Ohjelma

Aiheet ovat alustavia.

13.1.	Hannu Toivonen: Seminaarin järjestäytyminen
(20.1.	ei seminaaria)
(27.1.	ei seminaaria)
(3.2.	ei seminaaria)
(10.2.	ei seminaaria)
17.2.	Teemu N.: Samanlaisuuden ja sosiaalisen vaikuttamisen mallintaminen ja ennustaminen verkkoyhteisöissä (raportti 3.2.; Tuomas ja Samuli)
24.2.	Pekka M.: Keskusaliverkkojen etsiminen kyselysolmujen välillä laajoista verkoista (raportti 3.2.; Laura ja Teemu H.)
(3.3.	väliviikko, ei seminaaria) Huom: kurssi "Graph Mining" (3 cr), 2.-6.3. ma-pe 9-15 B222
(10.3.	ei seminaaria)
17.3.	Tuomas T.: Verkon solmujen tehokas luokittelu (raportti 24.2.; Ari, Jurkka)
24.3.	Janne K.: Reitinhaku pienissä maailmoissa (raportti 3.3.; Laura, Hannu)
(MA 30.3. 10-12 C220	Olli B.: Ohjelmistovirheet PERUTTU) (raportti 10.3.: Ari ja Janne)
31.3.	Ari R.: (k, 2)-jakoisiin verkkoihin perustuva klusterointimenetelmä ohjelmistojen takaisinmallinnuksessa (raportti 10.3.; Pekka, Teemu H., Olli)
MA 6.4. 10-12 C220	Jurkka N.: Tiedon etsintä verkkotietokannoista alirakenteiden avulla (raportti 17.3.; Janne, Hannu)
7.4.	Laura L.: K-medoids in a heterogeneous biological network (raportti 17.3.; Teemu N., Ari, Olli)
(14.4.	pääsiäisloma, ei seminaaria)
21.4.	Teemu H.: Verkkodatan koostaminen SNAP- ja k-SNAP-menetelmillä (raportti 31.3.; Tuomas, Samuli, Janne)
28.4.	Hannu M.: Klusterointi ja pienimmän leikkauksen virittävät puut (raportti 7.4.; Teemu N., Pekka)
KE 29.4. 10-12 C220	Samuli S.: Tiedon louhintaa viraalimarkkinoinnin tarpeisiin (raportti 3.3.; Teemu H., Jurkka)

Esitiedot

Osallistujilta edellytetään tieteellisen kirjoittamisen kurssin suorittamista. Tiedon louhinnan menetelmät -kurssin suorittaminen on merkittävästi eduksi. Muita hyödyllisiä kursseja ovat mm. tiedon louhinnan erikoiskurssi, koneoppiminen, data-analyysi, kolme käsitettä -kurssit sekä algoritmien suunnittelu ja analyysi.

Seminaariin valitaan maks. 12 osallistujaa opintojen edistymisen ja suoritettujen kurssien sopivuuden perusteella.

Seminaarin suorittaminen

Seminaari suoritetaan osallistumalla aktiivisesti seminaarin työskentelyyn: työskentelymuotoja ovat tieteelliseen lähdemateriaaliin perehtyminen, raportin kirjoittaminen ja esitelmän pitäminen, toisten osallistujien raporttien lukeminen ja arviointi sekä esitelmien aktiivinen seuraaminen.

Arvostelu perustuu omaan kirjalliseen työskentelyyn (1/3), omaan suulliseen esitykseen (1/3), sekä toisten raporttien kommentointiin ja muuhun aktiivisuuteen (1/3).

Tarkemmista toimintamuodoista sovitaan ensimmäisessä tapaamisessa. Alla alustava ehdotus.

• Seminaarisuunnitelma: alustavasti oma aihe, lähteet, jäsentely. Pituus 1-2 sivua, palautus sähköpostissa Hannulle mahdollisimman pian, viimeistään ennen seminaarikokoontumista 27.1.2008.
• Kirjallinen raportti, 12-15 sivua. Palautus 3 viikkoa ennen omaa esitelmää arvioijille ja Hannulle.
• Kahden muun kirjallisen raportin arviointi (arviolomake.txt). Arvio palautetaan viikon kuluessa raportin saamisesta (ts. kaksi viikkoa ennen esitelmää) sähköpostitse kirjoittajalle ja Hannulle.
• Kirjallisen raportin viimeistely palautteen perusteella (aikaa viikko). Viimeistellyn raportin palautus viikko ennen omaa esitelmää sähköpostitse koko seminaarille.
• Muiden raportteihin perehtyminen (aikaa viikko ennen seminaaria).
• Esitelmä.
• Esitelmien seuraaminen ja keskustelu.
• Lyhyen kirjallisen palautteen antaminen esitelmästä.
• Kolmen harjoitustehtävän laatiminen omasta esitelmästä.
• Harjoitustehtävien tekeminen ex tempore muiden esitelmistä.
• Lyhyt itsearviointi omasta esitelmästä ja raportista esitelmää seuraavaan perjantaihin mennessä (mitä tein hyvin, mikä meni hyvin; mitä tekisin toisin, mitä neuvoja antaisin nyt muille osallistujille)
• Lyhyt itsearviointi koko seminaarista seminaarin päätteeksi.

Seminaarin kahteen ensimmäiseen esitelmään (Olli, Teemu N.) aikataulua sovelletaan joustavasti.

Seminaarikokoontumisen kulku:

• Esitelmöijä toimittaa ehdotukset harjoitustehtäviksi Hannulle ennen esitelmää.
• Esitelmä n. 45 min.
• Keskustelua esitelmän sisällöstä.
• Kirjallisten palautteiden antaminen esityksestä: vahvuudet ja kehityskohteet.
• Esitelmään liittyvine harjoitustehtävien tekoa.
• Harjoitustehtävien läpikäynti yhdessä.

Ohjeita

Kannattaa muistaa, että kirjallisella raportilla ja suullisella esitelmällä on osin erilaiset tarkoitukset.

Esitelmässä kuulijoille välitetään sisällön keskeiset ajatukset, tarvittaessa sopivasti asioita yksinkertaistaen. Hyvä esitelmä sisältää -- tietysti aiheesta riippuen -- runsaasti esimerkkejä, jotka havainnollistavat aihetta, ja vain sellaisia valikoituja teknisiä yksityiskohtia, jotka ovat tärkeitä ja joita ehditään käsitellä riittävästi esitelmän aikana. Suullisen esitelmän pituus on n. 45 minuuttia.

Raportissa korostuu esitelmää enemmän täsmällisyys ja tieteellinen ilmaisu. Raporttikin on usein tiivistelmä käytetystä lähdemateriaalista, joten valintaa ja karsintaa täytyy tehdä. Valitut asiat tulee sitten kuvata raportissa riittävällä tarkkuudella; karsittujen asioiden kohdalla voi tarvittaessa viitata lyhyemmin lähdemateriaaliin. Raportin sopiva pituus on 10-15 sivua (valmisteluohjeita esim. tieteellisen kirjoittamisen kurssin sivuilla). Lisää ohjeita myös laitoksen seminaariohjeissa.

Lähdekirjallisuutta

Alla seminaariin sopivaa lähdekirjallisuutta. Taustatietovaatimukset vaihtelevat runsaasti. Osa artikkeleista on luettavissa sähköisessä muodossa vain yliopiston verkossa olevilta koneilta (sekä sopivilla selaimen proxy-asetuksilla tai VPN-yhdyskäytävän yli). Muutakin kirjallisuutta saa käyttää. Käytettävästä kirjallisuudesta on joka tapauksessa sovittava hyvissä ajoin seminaarin pitäjän kanssa.

• Yuanyuan Tian, Richard A. Hankins ja Jignesh M. Patel: Efficient aggregation for graph summarization. Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada. PDF
• J. Kleinberg: Complex Networks and Decentralized Search Algorithms. Proceedings of the International Congress of Mathematicians (ICM), 2006. PDF
• D. Crandall, D. Cosley, D. Huttenlocher, J. Kleinberg, S. Suri: Feedback Effects between Similarity and Social Influence in Online Communities. Proc. 14th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2008. PDF
• Matthew Richardson, Pedro Domingos: Mining knowledge-sharing sites for viral marketing. Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, Edmonton, Alberta, Canada, 61 - 70, 2002. PDF
• James Moody, Douglas R. White: Structural Cohesion and Embeddedness: A Hierarchical Concept of Social Groups. American Sociological Review 68 (1): 103-127, 2003. PDF
• Hanghang Tong, Christos Faloutsos: Center-Piece Subgraphs: Problem Definition and Fast Solutions. KDD'06, August 2006, Philadelphia, Pennsylvania, USA, 404-413. PDF
• L Franke, H Bakel, L Fokkens, ED de Jong, M Egmont-Petersen, C Wijmenga: Reconstruction of a functional human gene network, with an application for prioritizing positional candidate genes. Am J Hum Genet, Vol. 78, No. 6. (June 2006), pp. 1011-1025. PDF
• X. Yan, M. Mehan, Y. Huang, M. S. Waterman, P. S. Yu, and X. Zhou: A Graph-Based Approach to Systematically Reconstruct Human Transcriptional Regulatory Modules. ISMB'07, the 15th Annual Int. Conf. on Intelligent Systems for Molecular Biology, Jul. 2007. PDF
• by C. Liu, X. Yan, H. Yu, J. Han, and P. S. Yu: Mining Behavior Graphs for `Backtrace' of Noncrashing Bugs. SDM'05,Proc. of 2005 SIAM Int. Conf. on Data Mining, 2005. PDF
• X. Yan, P. S. Yu, and J. Han: Substructure Similarity Search in Graph Databases. SIGMOD'05, Proc. of 2005 Int. Conf. on Management of Data, 2005. PDF
• Gary William Flake, Robert E. Tarjan, and Kostas Tsioutsiouliklis: Graph Clustering and Minimum Cut Trees. Internet Mathematics Vol. 1, No. 4: 385-408. PDF
• Christoph Helma, Tobias Cramer, Stefan Kramer, Luc De Raedt: Data Mining and Machine Learning Techniques for the Identification of Mutagenicity Inducing Substructures and Structure Activity Relationships of Noncongeneric Compounds. Journal of Chemical Information and Modeling 44 (4): 1402-1411 (2004). PDF
• Mustafa Bilgic, Lise Getoor: Effective label acquisition for collective classification. Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, Las Vegas, Nevada, USA, p. 43-51, 2008 PDF

Opiskelijapalaute

Seminaarin viimeisellä kerralla kerättiin anonyymisti palautetta seminaarista ja sen toiminnasta. Palaute kokonaisuudessaan on täällä.

Yhteenveto
Yleisesti palaute oli hyvin positiivista. Eniten opiskelijat kokivat oppineensa seminaarin aihealueen sisältöä sekä kirjoittamista, vähemmän esiintymistä. Seminaarin sisälsi useita minimistä poikkeavia työtäpoja: lyhyen seminaarisuunnitelman palauttaminen seminaarin alussa, raporttien ristiinarviointi, harjoitustehtävät, keskustelu, kirjallinen vertaispalaute esitelmästä sekä itsearviointi. Näitä työtapoja pidettiin johdonmukaisesti hyödyllisinä, erityisesti ristiinarviointia ja keskustelua. Toisaalta harjoitustehtävistä annettiin ristiriitaista palautetta. Toimivaksi seminaarissa koettiin myös mm. joustava aikataulu.

Palautteen saaminen raportista ja esitelmästä oli selvästi yksi toimintatapojen vahvuus. Toisaalta palautekäytäntöihin esitettiin myös parannusehdotuksia: raporttipalautteesta voisi keskustella ja palautekierroksia voisi olla useampia, ja yhteinen palautekeskustelu esitelmästä voisi olla opettavampaa. Harjoitustehtäviin toivottiin enemmän teknistä sisältöä ja parempaa ohjeistusta niiden laatimiseen. Ehdotettiin tiiviimpää aikataulua. Seminaarin sivu voisi olla selvempi.

Yhteenveto edellisen seminaarin palautteesta

Kevään 2008 tiedon louhinnan seminaarin viimeisen kokoontumiskerran lopulla kerättiin (anonyymisti) kirjallista palautetta siitä, miten seminaarin ensimmäisessä kokoontumisessa asetetut tavoitteet saavutettiin, ja mistä työskentelymuodoista oli hyötyä. Lisäksi palautetta toimitettiin sähköpostitse. Tässä yhteenveto palautteesta.

• Kirjoittajana kehittyminen: tässä useimmat olivat kokeneet kehittyneensä (yllättävänkin paljon). Hyödylliseksi mainittiin kirjoittamisen lisäksi usein myös palautteen saaminen.
• Esiintyjänä kehittyminen: tästä palaute oli keskimäärin lievästi positiivista. Johdonmukaisesti hyödyllisenä pidettiin esitysten lomassa käytyä keskustelua, usein myös sitä että aikaa esityksiin oli reilusti.
• Aihepiirin sisällön oppiminen: palaute on vaihtelevaa. Esitysten tasoa pidettiin vaihtelevana, parhaat olivat innostavia ja houkuttelivat oppimaan lisää. Muutamat pitivät seminaarin monipuolisuudesta ja sen antamasta yleiskuvasta. Huonoksi koettiin se, että tehtäviin jäi vähän aikaa.

Muita palautteissa olleita kommentteja ja ideoita:

• keskusteluun kannustava, avoin ilmapiiri sai kiitosta
• suuri keskeyttämisprosentti laski motivaatiota ja sisällön määrää
• opiskelijoiden arviot toistensa töistä olisivat voineet olla tiukempiakin
• jos kukin tekisi vain yhden arvion, siihen voisi paneutua paremmin
• tapaamisten lopussa tuli usein valitettava kiire
• tehtävät voisi jakaa etukäteen tutustuttaviksi

Seminaarin vetäjä

Prof. Hannu Toivonen, Helsingin yliopisto

• Email: etunimi.sukunimi@cs.helsinki.fi
• WWW: http://www.cs.helsinki.fi/hannu.toivonen/
• Tavattavissa seminaarissa sekä sähköpostitse sovittaessa.