Review


Enam algoritma machine learning sedang dikembangkan untuk large-scale, distributed storaged, dan paralel processing di Google selama beberapa tahun terakhir ini. Disebutkan bahwa enam algoritma tersebut adalah Support Vector Machine (SVM), Singular Value Decomposition (SVD), Spectral Clustering, Association Mining, Probabilistic Latent Semantic Analysis (PLSA), dan Latent Dirichlet Allocation (LDA). Bahkan, PSVM sudah tersedia secara public dan dapat didownload. Btw, PSVM merupakan salah satu project hasil 20% time. Sebuah task SVM yang memerlukan tujuh hari pada sebuah komputer dapat diselesaikan dalam waktu dua jam dengan menggunakan PSVM pada 200 komputer.
Algoritma-algoritma di atas merupakan algoritma yang saat ini termasuk algoritma yang terbukti efektif dengan pondasi teori yang sangat kuat, namun komputasinya sangat tinggi. Pada SIGMOD record March 2008, Edward Chang, salah satu peneliti Google, melaporkan bahwa SVM, SVD, PLSA, dan LDA sangat berguna untuk klasifikasi dan collaborative filtering di Google. Google Knowledge search (baru tersedia di Rusia), dan Laiba (produk social-network dengan platform Orkut yang juga baru tersedia di Cina) adalah produk-produk terbaru Google yang menggunakan algoritma-algoritma ini pada infrastukturnya.
Apakah algoritma-algoritma ini akan menjadi tren machine learning masa depan??

Selain tentang algoritma machine learning yang sedang dikembangkan Google, paper “Data Management Projects at Google” juga menceritakan beberapa proyek Google yang lain termasuk Crawling Deep Web, Searching HTML Tables, BIGTable, dan MiniTables.

Referensi:
1. Data Management Projects at Google. SIGMOD Record, March 2008. (Vol. 37, No. 1)
2. PSVM – a parallel version of support vector machine

Sebenarnya itu topik tugas saya yang minggu lalu saya kumpulkan. Saat mengerjakan tugas ini, saya menemukan banyak hal menarik yang dapat saya share di sini, terutama dari website-website yang saya temukan.
Ini kutipan dari laporan yang saya kumpulkan, karena itu dalam bahasa Inggris. Hopefully, you can all understand. 🙂

Everyone knows that Google is one of the best (possibly the best) search engines right now. Most people prefer to use this search engine rather than other search engines. Most of them even set their homepage to Google (iGoogle). But, there are some other services offered that could be different from Google approach. They are either using another search algorithm which they believe that it performs better than others or providing new features that have not been offered before.

As an example, Ask.com (http://www.ask.com/) uses ExpertRank algorithm (formerly known as Teoma) which goes beyond mere link popularity to determine popularity among pages. Teoma analyzed links in context to rank a web page’s importance within its specific subjects. For instance, a web page about soccer would rank higher if other web page about soccer link to it. This is also known as subject-specific popularity. Ask.com says that performing this task in which includes identifying topics, the experts of those topics, and popularity amongst those experts at the exact moment of search query is processed requires many additional calculation that other search engine do not perform. Moreover, Ask.com also provides suggestion to expand and narrow the search term. As far as I know, Google is working on this issue as well. I am quite sure that Google Sets (http://labs.google.com/sets) is one of important parts of the system.

Search features are another aspect of providing good search engine. They could be vertical (specific) search, suggestion, or good user interface. There are many vertical search engines which are preferred bycertain users. For example: Digg (http://digg.com/) for share content, Technorati (http://technorati.com/) for blog and tagged social media, Retrevo (http://www.retrevo.com/) for consumer electronics. Better user interface offers assistance for user to evaluate and explore search result. Vivisimo (http://vivisimo.com/) gives clustered results, in a tree form, to make users easier explore and evaluate search results. This feature is also offered by some meta search engines such as Clusty (http://clusty.com/) which is owned by vivisimo, and Grokker (http://www.grokker.com/). Furthermore, Grokker also provides Map View. Here is the example (follow the link). In this aspect, Google is also working hard to provide additional useful feature to its users, making it faster, easier, and user friendlier. Prototype of the work can be found in Google Experimental Search (http://www.google.com/experimental/).

Related to web 2.0 which encourage web users to collaborate in providing good resources, some companies even have tried to organize and make use of it. Swivel (http://www.swivel.com/) is a very good example. Swivel tries to make data useful. Every user can post and share data so people can share insights, makegreat decisions, and improves lives.I think this service will be a huge data repository, and could be next YouTube for data. Another good example is Spock (http://www.spock.com/), people search engine. This service uses man and machine as the approach to search people. Spock performs some entity resolution algorithm (to distinguish and organize web content about people in the web) combine with Spock members tag to provide the result.

There are many aspects of search engine that can be explored. So, although Google is the most popular search engine right now with its complicated and sophisticated architecture, there are always other aspects that other search engine can offer. These things make all search engine companies, including the leaders such as Google, Ask.com, Yahoo still keep trying to develop some idea for an ideal search engine.

Update:
Selain itu, masih ada beberapa website yang saya temukan kemudian. Beberapa di antaranya sangat menarik.

  • FareCast (http://www.farecast.com/): Smart travel search
    Farecast merupakan travel search engine. Search engine ini dapat membantu kita mencari penerbangan. Yang menarik dari website ini adalah adanya airfare prediction. Mereka dapat memberi saran tentang harga tiket, apakah akan naik (beli sekarang) atau turun (tunggu).
  • Pluggd (http://www.pluggd.com/): Podcast search
    Pluggd adalah podcast search, jadi kita dapat mencari podcast di sini. Yang menarik dari website ini adalah adanya track bar yang menunjukkan bagian-bagian podcast yang sesuai dengan search query kita. Jadi kita tidak perlu melihat semuanya, cukup melihat yang sesuai dengan apa yang kita cari.
  • Quitura (http://www.quintura.com/): using tag cloud to navigate query
    Yang menarik dari website ini adalah kita adanya navigasi query dengan menggunakan tag cloud.

Machine Learning merupakan area yang sangat berkaitan erat dengan data mining. Sangat tepat sekali jika mengenal machine learning dari sudut pandang pakar machine learning.
Tom Mitchell adalah salah satu pakar machine learning, salah satu bukunya “Machine Learning” merupakan salah satu text book machine learning yang populer dan banyak dipakai hingga saat ini.
Papernya “The Discipline of Machine Learning” memberikan gambaran beliau secara personal tentang machine learning sebagai suatu disiplin ilmu, dan hubungannya dengan bidang ilmu pengetahuan lain dan bidang sosial. Paper ini juga memaparkan secara singkat current states dan arah perkembangan machine learning. Saya banyak belajar dari paper ini, sungguh sangat menarik mengetahui banyak hal yang dilakukan oleh machine learning. Peranan machine learning pada dunia computer science juga dipaparkan dengan sangat menarik di sini.
Satu hal yang menarik adalah research question yang menunjukkan arah yang ingin dicapai oleh machine learning. Apakah unlabeled data berguna untuk supervised learning? Bagaimana cara memindahkan pengetahuan yang sudah diperoleh pada suatu proses training agar dapat digunakan untuk meningkatkan pelatihan pada task yang lain? Apa hubungan antara algoritma-algoritma learning, algoritma apa yang seharusnya dipakai dalam suatu problem? Semua itu muncul sebagai research question yang akan terus digali oleh para peneliti machine learning. Lebih jauh lagi muncul pertanyaan seperti ini: dapatkah kita membangun sebuah never-ending learner (seperti makhluk hidup belajar dan beradaptasi)? Dapatkah teori dan algoritma machine learning digunakan untuk menjelaskan cara manusia belajar? Jika cara manusia belajar bisa dijelaskan, wah ini digunakan untuk meningkatkan strategi dan metode pengajaran di sekolah. Sungguh sangat menarik mengetahui usaha-usaha yang ingin dicapai.

Banyak pencapaian ilmu pengatahuan dan teknologi dipicu oleh adanya tantangan berhadiah (challenge).
Jika bidang robotika ada DARPA Grand Challenge tahun 2005 tentang robotic car navigation, dan RoboCup yang goalnya mengembangkan tim robot humanoid yang dapat mengalahkan tim pemenang world cup pada 2050. Apakah grand challange untuk data mining?

KDD2006 panel mengusulkan beberapa kriteria grand challenge data mining:

  1. Permasalahannya harus sulit – sangat sulit untuk diselesaikan dengan teknik-teknik yang ada saat ini
  2. Melibatkan data mining – data mining harus memiliki peranan yang sangat penting untuk menyelesaikan permasalahan tersebut
  3. Menggunakan large dataset yang tersedia secara publik
  4. Goal yang jelas – sehingga dapat diketahui kapan permasalahan tersebut terselesaikan
  5. Permasalahannya harus menarik bagi para peneliti
  6. Adanya manfaat bagi masyarakat jika permasalahan tersebut dapat diselesaikan

Saat ini, tantangan yang berkaitan dengan data mining yang berhasil menarik banyak perhatian adalah Netflix Challenge. Tantangan lain yang mungkin berhubungan dengan data mining adalah Archon X Prize for Genomics, 10 juta dollar untuk tim pertama yang berhasil melakukan sequencing human genome 100 orang dalam 10 hari.

KDD2006 panel report, “What are The Grand Challenges for Data Mining?”, mengusulkan beberapa permasalahan untuk grand challange data mining mulai dari multimedia data mining, link mining, large-scale modelling, text mining, sampai mining proteomics.
Paper report ini sangat menarik, menawarkan beberapa macam permasalahan yang dapat dipertimbangkan sebagai grand challenge. Misalnya pada multimedia mining: annotate (memberi keterangan) 1000 jam digital video dalam 1 jam, prediksi minat user pada video tertentu berdasarkan browsing lima menit pertama, pencarian interview seseorang yang mirip pada arsip video broadcast. Pada text mining, grand challenge yang diusulkan adalah sistem text mining yang mampu melewati standard reading comprehension tests seperti SAT, GRE, GMAT. Pada link mining, grand challengenya dinamai Wikipedia Test, mempertandingkan artikel oleh participatory journalism (seperti para penulis artikel di Wikipedia) dengan artikel oleh link mining tool yang dilakukan secara otomatis. Dapatkah orang membedakan artikel wikipedia asli atau yang dibuat secara otomatis oleh link mining tool? dan mana yang lebih baik? Grand challenge link mining ini mengingatkan saya pada Turing test.
Area mining proteomics mengusulkan grand challenge untuk menentukan keberadaan protein beserta jumlah dan interaksinya. Sedangkan, pada large-scale modelling diusulkan challange yang mengestimasi jutaan hingga miliaran parameter data mining model.
Saya banyak belajar dari paper report ini tentang permasalahan-permasalahan yang berkaitan dengan data mining, ternyata banyak sekali.

Grand Challenge seperti apa yang akan muncul? kita tunggu saja nanti. 🙂

Akhirnya bisa blogging lagi setelah sekian lama.
Kali ini saya ingin menyoroti beberapa tantangan-tantangan (challenge) / kompetisi yang saat ini sedang rame. Saya sendiri banyak belajar dari beberapa kompetisi dan challenge data mining yang pernah ada, terutama dari sisi aplikasinya.
Umumnya, problem-problem yang diangkat dalam kompetisi-kompetisi tersebut diambil dari real world problem yang saat itu sedang menjadi issue hangat. Jadi, kompetisi-kompetisi yang ada merefleksikan real world problem yang sedang terjadi. Saya sering melihatnya juga sebagai tren-tren yang saat ini sedang dihadapi.

Berikut ini akan saya berikan review singkat beberapa kompetisi/challenge yang saat ini sedang berlangsung:

  1. Netflix Challenge (http://www.netflixprize.com/)
    Tantangan dari netflix ini cukup menarik perhatian banyak pihak. Salah satu sebabnya adalah prize money yang disediakan sebagai hadiah utama sebesar US$1juta. Permasalahannya tentang collaborative filtering. Tantangan dibuka selama 5 tahun (sampai 2011), dan berakhir jika ada yang berhasil menyelesaikannya. Saat ini aja udah lebih dari 16ribu tim dari 135 negara terdaftar sebagai peserta.
  2. KDD Cup 2007 (http://www.cs.uic.edu/~liub/Netflix-KDD-Cup-2007.html)
    ACM SIGKDD merupakan salah satu pihak yang tertarik dengan tantangan dari netflix. Rencananya KDD Cup tahun ini, SIGKDD bekerja sama dengan Netflix menyediakan dataset dan permasalahannya. Walaupun datasetnya berasal dari Netflix, namun task-nya akan berbeda dengan Netflix Challenge.
  3. PAKDD Competition 2007 (http://levis.shu.edu.cn/pakdd2007/competition/overview)
    Problemnya adalah tentang Cross Selling. Permasalahannya dari sebuah perusahaan financial yang memiliki credit card customer dan home load customer, dimana irisan antara dua jenis customer tersebut sangat sedikit. Tugasnya adalah scoring customer, semakin besar scoring semakin besar kecenderungan customer yang membuka credit card akan membuka home load dalam 2 tahun. Datasetnya berisi 40.700 data (700 label positif, dan 40.000 label negatif). Mungkin inilah yang akan menjadi problem, jumlah data tiap kelas tidak seimbang, beda jauh malahan.
  4. Web Spam Challenge (http://webspam.lip6.fr/)
    Permasalahannya adalah memberi label sebuah large graph yang diaplikasikan pada web spam. Akan didiskusikan dua kali tahun ini salah satunya pada AIRWeb 2007.
  5. Challenge on Time Series Classification at SIGKDD 2007 (http://www.cs.ucr.edu/~eamonn/SIGKDD2007TimeSeries.html)
    Tantangan ini sebenarnya untuk sebuah workshop di SIGKDD tentang time series mining. Tantangan ini berusaha mencari algoritma klasifikasi time series yang paling baik. Yang menarik perhatian saya dari tantangan ini adalah jangka waktu publikasi dataset dengan pengumpulan hasil yang hanya 24 jam. Karena algoritma yang dicari adalah algoritma yang secara umum baik, tidak hanya pada kondisi-kondisi tertentu saja, maka penyelenggara meminimalisasi waktu bagi peserta untuk mempelajari data. Jadi waktu 24 jam tersebut hanya disiapkan untuk running algoritma secara langsung, biarkan segalanya dilakukan secara otomatis oleh program. Meminimalisasi campur tangan manusia. Publikasi di webnya saat ini dimaksudkan agar semua bisa mulai mendesain dan berlatih dengan dataset-dataset yang ada.
  6. Mining Software Repositories Challenge 2007 (http://msr.uwaterloo.ca/msr2007/challenge/)
    Tantangan yang baru berakhir bulan ini sangat menarik karena tantangan ini memberikan gambaran aplikasi data mining pada bidang software engineering. Yang dimining adalah software repository terkenal yaitu Eclipse dan Firefox. Menarik bukan. Ternyata dari sebuah software repository dapat dimining beberapa hal seperti bug analysis, change analysis, dan process analysis.

Ternyata begitu banyak kompetisi yang berhubungan dengan data mining. Umumnya mereka secara rutin mengadakan kompetisi setiap tahunnya.

Selamat tahun baru 2007…. 🙂
Semoga di tahun yang baru ini segala harapan, impian, dan cita-cita kita semua dapat tercapai.
Posting pertama tahun ini akan dimulai dengan pemikiran saya dan apa yang saya bayangkan tentang hal-hal yang menjadi akan menjadi tren di tahun 2007, terutama yang berkaitan dengan data mining tentunya.
Banyak hal yang saya lihat dalam email, news, blog, dan rss feed saya di tahun 2006. Saya bisa melihat ada dua hal yang menjadi tren dan sangat diexplore tahun lalu akan menjadi semakin rame yaitu komunitas dan personalisasi. Dua hal ini yang semakin terlihat sejak tahun 2006. Di samping itu perkembangan data mining dari area biomedical, bioinformatics, dan brain informatics serta text mining juga akan semakin ramai diexplore.

Komunitas
Flickr, del.icio.us, mySpace, dan youTube merupakan nama-nama yang semakin beken di tahun 2006. Satu hal yang menghubungkan layanan-layanan tersebut adalah bahwa layanan-layanan tersebut sukses membentuk komunitas. Mengapa Yahoo! sangat tertarik membeli Flickr? yang jelas, faktor komunitas inilah yang menjadi daya tarik utama Flickr.
Issue-iisue yang berhubungan dengan komunitas seperti Social Network Analysis sangat mungkin menjadi salah satu area yang akan berkembang. SIGKDD Exploration pertengahan tahun lalu mengangkat link mining sebagai special topic. Walaupun aplikasi link mining tidak hanya social network saja, namun salah satu aplikasi besar link mining adalah mining social network.
Task-task link mining seperti group detection, link prediction, dan classification merupakan task-task penting terutama dalam bisnis yang berkaitan dengan komunitas seperti CRM, layanan-layanan iklan, sistem rekomendasi, dan sejenisnya.
Pengetahuan yang diperoleh dari komunitas dapat dipakai untuk memberikan layanan-layanan secara personal. Ini sangat berkaitan juga dengan personalisasi.

Personalisasi
Hal ini berkaitan dengan perkembangan layanan-layanan di internet dan software-software yang saat ini berkembang.
Menjadi semakin personal. Kira-kira seperti itulah tren perkembangan software dan layanan di internet.
Browser firefox dengan aneka plug in semakin diminati, Google berusaha menyempurnakan layanan search personal yang akan meningkatkan keakuratan search berdasarkan search yang pernah dilakukan seseorang. Bahkan, isunya Microsoft juga sedang mengembangkan sistem operasi yang basisnya plug in.
Bisa jadi PC masa depan semakin personal, tinggal memasang plug in sesuai kebutuhan dan keinginan. Atau, mungkin hanya perlu browser saja. Web 2.0 yang sedang dalam pengembangan memungkinkan aplikasi berjalan secara online via browser saja. Lihat saja Google Docs dan Spreadsheets. Walaupun masih terus dikembangkan, bisa jadi ini akan menggeser microsoft office.
Berkaitan dengan personalisasi salah satu yang menjadi highlight di tahun 2006 lalu adalah Netflix challenge. Selain permasalahannya yang menantang, hadiahnya juga menjadi salah satu daya tarik utama.

Biomedical, Bioinformatics, dan Brain Informatics
Area ini merupakan area yang berkembang pesat beberapa tahun belakangan. Kebutuhan akan penemuan obat-obatan baru, dan terapi yang paling tepat untuk suatu penyakit. Algoritma-algoritma yang sangat efisien dan efektif sangat diperlukan dalam mencari pola-pola yang tersembunyi karena data medis dan biologis yang sangat besar. Apalagi datanya juga bervariasi, mulai dari data, teks, bahkan gambar dan multimedia.
Brain informatics muncul setelah adanya fMRI di mana alat ini dapat mendeteksi aktifasi otak. Dengan menggunakan alat ini, para peneliti dapat mempelajari cara makhluk hidup berpikir, terutama manusia. Bagaimana mental state manusia dalam merespon sebuah rangsangan misalnya suara, atau gambar yang dilihat dapat dipelajari. Sangat mungkin jika, web intelligence mengadaptasi model pengetahuan yang diperoleh dari sini. Internet dapat memberikan respon sesuai dengan yang diharapkan manusia.

Text Mining
Jumlah dokumen yang semakin lama semakin banyak, terutama sejak boomingnya blog, menjadikan text mining sebagai area yang sangat aktif berkembang.
Tidak hanya dokumen di internet, dokumen-dokumen di area biomedical dan bioinformatics juga sangat luar biasa besar.
Karena itu text mining akan menjadi salah satu area data mining yang akan berkembang pesat.

Satu hal lagi yang pasti, area yang dijangkau data mining semakin lama akan semakin luas.
Juga, semakin banyak jenis pengetahuan yang diperoleh dari berbagai data sangat memungkinkan untuk pengembangan Data Mining secara terintegrasi. Holistic Data Mining diprediksikan oleh Nucleus Research dalam top ten prediction for 2007 sebagai salah satu tren 2007.

(Presented at ICDM 2006 in Hong Kong by Xindong Wu and Vipin Kumar)
Selalu saja ada hal menarik dari IEEE ICDM (International Conference on Data Mining). Jika tahun lalu IEEE ICDM mengidentifikasi 10 Challenging Problem in Data Mining, maka tahun ini IEEE ICDM mengidentifikasi algoritma data mining yang paling dikenal. Hal inilah yang membedakan IEEE ICDM dengan konferensi lainnya.
Setelah melewati proses seleksi (proses seleksinya dapat dilihat melalui link yang ada pada referensi di bawah), berikut ini adalah nominasi 10 Well-Known Algorithm in Data Mining (berikut dengan perhitungan citation dengan Google Scholar sampai akhir Oktober 2006 yang digunakan sebagai verifikasi) yang terbagi dalam 10 kategori:

Classification
#1. C4.5 (Google Scholar Count in October 2006: 6907)
#2. CART (Google Scholar Count in October 2006: 6078)
#3. Naive Bayes (Google Scholar Count: 498)
#4. K Nearest Neighbours (kNN) (Google SCholar Count: 183)

Statistical Learning
#5. SVM (Google Scholar Count in October 2006: 6441)
#6. EM (Google Scholar Count in October 2006: 848)

Association Analysis
#7. Apriori (Google Scholar Count in October 2006: 3639)
#8. FP-Tree (Google Scholar Count in October 2006: 1258)

Link Mining
#9. PageRank (Google Shcolar Count in October 2006: 2558)
#10. HITS (Google Shcolar Count in October 2006: 2240)

Clustering
#11. K-Means (Google Scholar Count in October 2006: 1579)
#12. BIRCH (Google Scholar Count in October 2006: 853)

Bagging and Boosting
#13. AdaBoost (Google Scholar Count in October 2006: 1576)

Sequential Patterns
#14. GSP (Google Scholar Count in October 2006: 596)
#15. PrefixSpan (Google Scholar Count in October 2006: 248)

Integrated Mining
#16. CBA (Google Scholar Count in October 2006: 436)	 

Rough Sets
#17. Finding reduct (Google Scholar Count in October 2006: 329)

Graph Mining
#18. gSpan (Google Scholar Count in October 2006: 155)

Dari daftar nominasi, algoritma-algoritma yang masuk nominasi merupakan algoritma-algoritma pionir pada masing-masing pendekatan. Dan, banyak pengembangan lebih lanjut dari masing-masing algoritma tersebut. Hal ini dapat dilihat dari banyaknya paper yang mengutip algoritma tersebut. Sebagai informasi, algoritma yang jumlah citation berdasarkan Google Scholar tidak sampai 55 citation sudah tereliminasi.
Algoritma-algoritma ini adalah yang paling umum digunakan dalam data mining, tentunya dengan masing-masing modifikasi sesuai dengan permasalahan yang dihadapi. Sangat baik jika kita mengenal dengan baik algoritma-algoritma ini.
Menurut saya semakin simpel algoritma tersebut, jelas semakin populer. Banyak orang yang lebih tertarik untuk menggunakannya. Kita tunggu saja, algoritma-algoritma mana yang termasuk 10 Well-Known Algorithm in Data Mining. Dilihat dari nominasinya, 18 algoritma tersebut akan bersaing ketat.

Referensi:
1. 10 Well-Known Algorithm in Data Mining. http://www.cs.uvm.edu/~icdm/algorithms/index.shtml.

Laman Berikutnya »