A Szinguláris felbontás adatbányászati alkalmazásai Kurucz Miklós ˝ Benczúr A. András Ph.D. Témavezeto:
Eötvös Loránd Tudomány Egyetem Informatikai Kar Informatikai Tanszék Informatikai Doktori Iskola Benczúr András D.Sc. Az Informatika Alapjai és Módszertana Doktori Program Demetrovics János D.Sc. Budapest, 2011
1
Bevezetés
Az elmúlt id˝oszakban a szinguláris felbontás (SVD) az egyik leggyakrabban használt eszköz volt statisztikai, jelfeldolgozási és modellezési problémák megoldására. A zajsz˝urés, Látens Szemantikus Allokáció és a statisztikus faktormodellezés csak néhány a számos különböz˝o megközelítés közül, amely SVD-t használ gyakorlati feladatok megoldására. A szinguláris felbontás alkalmazási területei között egy régóta népszer˝u kutatási terület, a szociális hálózatok elemzését is megtaláljuk. A különböz˝o csoportok azonosítása, a hasonló emberek keresése, és a szociális dinamikák megfigyelése mind széles körben kutatott témák. Az ezek által kinyert információk nagyon hasznosak marketing célokra, például egy új szolgáltatás célcsoportjának meghatározására, vagy olyan ügyfelek azonosítására, akik fel akarják mondani az el˝ofizetésüket. Az elmúlt években a rendelkezésre álló adatmennyiség megn˝ott, amelynek következtében teret hódítottak az információ kinyerésre használt újabb módszerek. Az egyik ilyen módszer a spektrál klaszterezés, amelyet pár évtizednyi érdektelenség után kezdtek újra felfedezni. A spektrál klaszterezés SVD-t használ arra, hogy minimális vágásokat találjon egy hálózatban. Az emberek érdekl˝odésének el˝orejelzése egy másik olyan kutatási terület, ahol az SVD-t elterjedten használják. Egyre fontosabb az olyan terméket megtalálása, amelyek érdekesek a vev˝ok számára. Amennyiben a termékekhez szöveges leírás áll rendelkezésre, ajánlást tudunk adni úgy, hogy olyan termékleírásokat keresünk, amelyek a vev˝o számára általában fontos szavakat tartalmaznak. Azonban az új tartalom szolgáltatók a televízió az internet és a mobil eszközök egybeolvadása miatt a nem szöveges tartalmakra összpontosítanak. Az ajánló technikák új értékeket adnak az új generációs szolgáltatásokhoz. A tézisünkben az SVD-vel folytatott kísérleteinket és eredményeinket mutatjuk be. Els˝oként összehasonlítjuk a létez˝o spektrál klaszterez˝o algoritmusokat nagyméret˝u adathalmazokon. A spektál klaszterez˝o algoritmusok közül vizsgáljuk a csupán a második (Fridler) szinguláris vektort, és az ennél több vektort alkalmazó módszereket is. Kísérletezünk továbbá mind a Laplace, mind a súlyozott Laplace mátrixokkal. Ezután mutatunk két el˝ofeldolgozó és egy utófeldolgozó heurisztikát, amelyek javítanak a spektrál klaszterezés eredményein. El˝ofeldolgozásként egyrészt összehúzzuk az úgynevezett csápokat, a hálózat hosszú, ritka részeit, amelyek zavarják a módszereket; illetve azonosítjuk a s˝ur˝u területeket, amelyek túl sok sajátvektort érintenek. Az utófeldolgozás során a s˝ur˝u részeket újraosztjuk a létrejött klaszterek közt, a nem összefügg˝o részeket megszüntetjük, és kiegyensúlyozzuk a klaszterméreteket. Adunk továbbá egy olyan hálózat modellt, amely megmagyarázza a spektrál klaszterezés nehézségeit. Mostanában hívták fel arra a figyelmet, hogy a spektrál klaszterezés nem talál kiegyensúlyozott vágást szociális hálózatokban, mert csak a csápokat vágja le a gráfról. A jelenlegi Barabási és 1
Kleinberg-féle modellek nem magyarázzák meg ezt a jelenséget: még ha a modell által generált gráf tartalmaz is csápokat, az algoritmus értelmes vágásokat ad. A modellek viselkedése tehát eltér a valódi hálózatokban megfigyelt eredményekt˝ol. Az általunk adott modell tulajdonságai gráf klaszterezési szempontból megegyeznek a valódi hálózatokéval. Végül pedig bemutatjuk az SVD alkalmazását hiányosan kitöltött mátrixokon. Kiszámoljuk az SVD-t egy Expectation-Maximization algoritmus és a Lánczos algoritmus segítségével is. A kezdeti szinguláris vektorokat úgy számítjuk, hogy a mátrix hiányzó elemeit valamely el˝ore meghatározott értékekkel töltjük ki. A kezd˝oértékek lehetnek a globális átlagok, vagy más, kifinomultabb módszerek eredményei. A kés˝obbi lépésekben a korábbi lépések eredményeként kapott alacsony rangú mátrixokat használjuk bemenetnek. A számolás gyorsításának érdekében két konvergencia gyorsító eljárást alkalmazunk. A módszereket a Netflix adathalmazon teszteljük.
2
Új eredmények
Az eredmények öt tézis köré vannak rendezve. Az els˝o három a szociális hálózatok elemzésével foglalkozik, az utolsó kett˝o pedig a Lánczos algoritmus ajánló rendszerekben való alkalmazását tárgyalja. Spektrál Klaszterezés Nagy szociális hálózatok klaszterezése során a spektrál módszer a s˝ur˝u részékhez gyengén csatolt csápokat vágja le, amely nem összefügg˝o részeket és egy nagy s˝ur˝u komponenst eredményez. Elméletileg lehet ilyen az optimális vágás szerkezete, azonban a nem összefügg˝o klaszter kicsi részgráfokból áll, amelyek az értelmezés szempontjából a s˝ur˝u komponens egyértelm˝uen meghatározható területeihez tartoznak. Ezen kívül a nem összefügg˝o gráfokat a további particionálás céljából komponensekre kell bontanunk, például azért, mert többszörös legnagyobb sajátértékük van, azaz az összefügg˝o részgráfokra külön kell sajátvektort számolni. Azonban ha külön klaszterként kezeljük a részgráfokat, a klaszterméretek eloszlása nagyon kiegyensúlyozatlan lesz. Adunk egy hierarchikus spektrál klaszterez˝o algoritmust klaszter méret kiegyensúlyozó heurisztikákkal, amelyet összehasonlítunk a Divide-and-Merge algoritmussal [R 1] is. Telefonhívás-hálózatok klaszterezésekor a mi algoritmusunk jobban teljesít, mint a Divide-and-Merge. Megmérjük a különböz˝o SVD bemenetek hatását: a súlyozott Laplace mátrix sokkal jobban teljesít, mint a súlyozatlan. Továbbá bevezetünk egy nagyon jó eredményre vezet˝o Jaccard-féle súlyozási módszert is. 1. Tézis El˝ofeldolgozó heurisztikák [Spec 1, Spec 2, Spec 3] Demonstráljuk, hogy a spektrál gráf particionálás végrehajtható nagyméret˝u skála-mentes há2
lózatokon a megfelel˝o el˝ofeldolgozás után. A mi el˝ofeldolgozásunk lényege az olyan er˝osen összekapcsolt közösségek eltávolítása, amelyek a teljes hálózat csupán kis részét képviselik; valamint a hosszú csápok, azaz lazán kapcsolódó tagok láncainak összehúzása. A gráfok spektrál klaszterezését leginkább áramkörök particionálásán kutatták, Lang viszonylag új eredményének [R 2] kivételével. Lang egy szemidefinit programozási módszert (SDP) javasol, hogy elkerüljük a kiegyensúlyozatlan vágásokat, azonban csupán egyetlen vágás számolási ideje ideje több óra egy 10 millió él˝u gráfnál. A szemidefinit módszerek skálázhatóságának megoldása nyitott probléma. 2. Tézis Összehasonlítás a Szemidefinit módszerrel [Spec 3, Spec 4] A f˝obb megállapításaink a gráf particionálási problémának az SVD, illetve a SDP általi relaxációinak összehasonlításához kapcsolódik. Megmutatjuk, hogy az SVD alapú módszer legalább olyan jó eredményt adhat, mint az SDP, azonban annál jóval gyorsabb, különösen mivel a Lánczos algoritmus mátrixszorzás m˝uveletét lehet párhuzamosítani. Az SVD-nek továbbá jó közelít˝o megoldásai vannak [R3, R4]. Jöv˝obeli tervünk között szerepel elosztott közelít˝o SVD algoritmusok alkalmazása olyan nagy gráfokon, mint például a UK2007WEBSPAM, amely 3 milliárd élt tartalmaz. Független téma a LiveJournal baráti hálózat elemzése, amely hárommillió felhasználót tartalmaz, 80%-ban az USA-ból, 6%-ban Nyugat-Európából és 5%ban Oroszországból illetve Kelet-Európából. Az elemzésünk felfedi a földrajzi elhelyezkedés, életkor, illetve vallási meggy˝oz˝odés hatásait. További célom a hatások b˝ovebb vizsgálata, és az általunk mutatott módszereket alkalmazása más nagy szociális hálózatokra. Szociális Hálózat modellek A spektrál klaszterezés nagy közösségi hálózatokon történ˝o alkalmazásáról az elmúlt id˝oben negatív eredményeket publikáltak. Míg Lang [R 2] részben azt állítja, hogy ez a kiterjedtség és a fokszámok hatvány eloszlása miatt van, azonban az ismert hálózat modellek, mint például a preferált illesztés modell [R 5] vagy Kumar fejl˝od˝o másoló modellje [R 6] illetve Kleinberg kis-világ modellje [R 7] könnyen és kiegyensúlyozottan particionálható a spektrál módszerrel. Következ˝o eredményünk egy hálózatmodell, amely a spektrál módszerrel nehezen particionálható gráfokat generál, és a megfigyelt s˝ur˝u részhalmaz és csáp méreteloszlást mutatja. Kleinberg kis-világ modelljéb˝ol indulunk ki, egy két dimenziós rácsból, amelyen azonban bizonyos pontokat kicsi teljes részgráfokkal helyettesítünk. Ezután a megfelel˝o hatvány-eloszlás szerint éleket generálunk, úgy hogy az élek valószín˝usége a végpontok távolságának négyzetével fordítottan arányos. A generált s˝ur˝u 3
részek számának és csápok méretének eloszlása nagyon hasonló a nehezen particionálható hálózatokéhoz. 3. Tézis Nehezen Particionálható Gráfok Generatív Modelljei [Spec 4] Megmutattuk, hogy a létez˝o modellek által generált gráfokat nem olyan nehéz klaszterezni, mint a valódi hálózatokat. Ezért olyan összetett modellt készítettünk, amelyben a szomszédsági mátrix szinguláris értékei nagyon lassan csökkennek és a gráf nehezen particionálható. Ebben az új modellben a spektrál klaszterezés csak azután ad kiegyensúlyozott vágást, miután eltávolítjuk a s˝ur˝u részgráfokat és a csápokat is. SVD nagy méretu˝ hiányos mátrixokra Az alacsony rangú közelít˝o mátrixok számolásának központi nehézségét az értékelési mátrixból hiányzó rengeteg érték okozza: a Netflix mátrix értékeinek 99%-a nem ismert. Bár több szerz˝o Expectation Maximization alapú SVD algoritmusokat adott már a ’70-es években [R 8], mások pedig ajánló rendszerekben alkalmazható módszereket is mutattak, a vizsgált feladatok mérete messze elmaradt a Netflix problémáétól. Ezek az eredmények kicsi, néhány ezerszer néhány ezres mátrixokon készültek az EachMovie vagy a Jester adathalmazokon, amelyek több nagyságrenddel kisebbek, mint amelyeket a mi algoritmusaink kezelnek. 4. Tézis A Lánczos algoritmus alkalmazása egy EM rendszerben [Rec 1] Több módosítást implementáltunk az svdpack csomagban, ami lehet˝ové teszi a hiányzó adatok kezelését nagyon nagy bemenetekre. Összehasonlítjuk a Lánczos, blokk-Lánczos és hatvány iterációs algoritmusokat. Az eredményeink szerint a legjobb módszer a Lánczos algoritmus 10 dimenzióban. Sajnos a számolás lassú, és a konvergencia gyorsítás csak kicsit javít ezen. A hatvány iterációs módszerek túltanulnak. Úgy gondoljuk, hogy az algoritmusaink részletes elemzése még javíthat az eredményeken, azonban a f˝o célunk a hiányzó értékekb˝ol adódó problémák megértése volt, a különböz˝o kapcsolódó algoritmusok vizsgálata által. 5. Tézis KDD Cup 2007 nyertes megoldás [Rec 2] Bemutatjuk a “Who Rated What in 2006” feladaton els˝o helyezést elért módszerünket. A feladat az volt, hogy megjósoljuk a valószín˝uségét annak, hogy egy felhasználó értékelt egy filmet 2006ban. Ehhez adott volt 100,000 felhasználó-film pár a Netflix adathalmazból. A megoldásunk a naiv függetlenség, az SVD, a korreláció és a szabály alapú megközelítések kombinációja volt. 4
A mi eredményünk 0.256-os hibája 0.007-tel jobb volt, mint a második helyezetté, illetve 0.023mal a csupa nulla jóslaténál.
5
Publikációk [Spec 1]
Miklós Kurucz, András A. Benczúr, Károly Csalogány, László Lukács. “Spectral Clustering in Telephone Call Graphs”. In Proceedings of the WebKDD/SNAKDD Workshop 2007 in conjunction with KDD 2007. Lecture Notes in Computer Science, 2009, Volume 5439/2009, 1-20, [Spec 2] Miklós Kurucz, László Lukács, Dávid Siklósi, András A. Benczúr, Károly Csalogány, András Lukács. “Telephone Call Network Data Mining: A Survey with Experiments”. Chapter 12, Handbook of Large-Scale Random Networks, Bolyai Society Mathematical Studies, Vol. 18, 489-530 Springer, 2008. [Spec 3] Miklós Kurucz, András A. Benczúr, Attila Pereszlényi. “Large-Scale Principal Component Analysis on LiveJournal Friends Network”. In Proceedings of the Workshop on Social Network Mining and Analysis Held in conjunction with KDD 2008. [Spec 4] Miklós Kurucz and András A. Benczúr. “Geographically Organized Small Communities and the Hardness of Clustering Social Networks”. Annals of Information Systems, 2010, Volume 12, 177-199 [Rec 1] Miklós Kurucz, András A. Benczúr, Károly Csalogány. “Methods for large scale SVD with missing values”. In Proceedings of the KDD Cup and Workshop 2007 in conjunction with KDD 2007. [Rec 2] Miklós Kurucz, András A. Benczúr, Tamás Kiss, István Nagy, Adrienn Szabó and Balázs Torma. “Who Rated What: a combination of SVD, correlation and frequent sequence mining”. In Proceedings of the KDD Cup and Workshop 2007 in conjunction with KDD 2007. SIGKDD Explorations Volume 9, Issue 2, 53-56
6
Egyéb kapcsolódó publikációk [MT]
Miklós Kurucz, László Lukács, Dávid Siklósi, András A. Benczúr, Károly Csalogány, András Lukács. “Kapcsolatok és Távolságok a Hazai Vezetékes Hívás-szokások Elemzése”. Magyar tudomány, Issue 6, 2009. [FP] Miklós Kurucz, Dávid Siklósi, István Bíró, Péter Csizsek, Zsolt Fekete, Róbert Iwatt, Tamás Kiss, Adrienn Szabó. “KDD Cup 2009 @ Budapest: feature partitioning and boosting”. In Proceedings of the KDD Cup Workshop 2009 in conjunction with KDD 2007. Journal of Machine Learning Research: Workshop and Conference Proceedings 7, 65-75, 2009 [Spam 1] Dávid Siklósi, András A. Benczúr, Zsolt Fekete, Miklós Kurucz, István Bíró, Attila Pereszlényi, Simon Rácz, Adrienn Szabó, Jácint Szabó. “Web Spam Hunting @ Budapest”. In Proceedings of Airweb 2008 in conjunction with WWW 2008 [Spam 2] András A. Benczúr, Dávid Siklósi, István Bíró, Zsolt Fekete, Miklós Kurucz, Attila Pereszlényi, Simon Rácz, Adrienn Szabó, Jácint Szabó. “Web Spam: a Survey with Vision for the Archivist”. In Proceedings of IWAW 2008.
7
Hivatkozások [R 1]
[R 2] [R 3] [R 4]
[R 5] [R 6]
[R 7] [R 8]
David Cheng and Santosh Vempala and Ravi Kannan and Grant Wang. “A divide-and-merge methodology for clustering”. PODS ’05: Proceedings of the twenty-fourth ACM SIGMODSIGACT-SIGART symposium on Principles of database systems Kevin Lang. “Fixing two weaknesses of the Spectral Method”. NIPS ’05: Advances in Neural Information Processing Systems, Vol 18, 2005 Tamás Sarlós. “Improved Approximation Algorithms for Large Matrices via Random Projections”. IEEE Symposium on Foundations of Computer Science, 2006 Petros Drineas and Ravi Kannan and Michael W. Mahoney. “Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication”. SIAM Journal on Computing, Vol 36, 132-157, 2006 Albert-László Barabási and Réka Albert and Hawoong Jeong. “Scale-free characteristics of random networks: the topology of the word-wide web”. Physica A, Vol 281, 69-77, 2000 Ravi Kumar and Prabhakar Raghavan and Sridhar Rajagopalan and D. Sivakumar and Andrew Tomkins and Eli Upfal. “Stochastic Models for the Web Graph”. IEEE Symposium on Foundations of Computer Science, 2000 Jon Kleinberg. “The Small-World Phenomenon: An Algorithmic Perspective”. Proceedings of the 32nd ACM Symposium on Theory of Computing, 2000 K. R. Gabriel and S. Zamir. “Lower Rank Approximation of Matrices by Least Squares with Any Choice of Weights”. Technometrics, Vol 21, 489-498, 1979.
8
