2014 Montpellier Internship

This year, there are two internships from Polytech of Montpellier, France: Adrien Claudin and Florian Guihard. They are working on a template project for a web system which includes a generic user administration module, a data maintenance module, a data warehouse module, and data mining modules implementing two data mining methods: naive bayes and k-means algorithm. They are staying in Bali for three months (June 2nd – August 28th, 2014).

Today (August 23rd, 2014), they presented their work in front of students and lecturers, in conjunction to a final project presentation by Forth year student group at Stikom Bali’s Dual Degree program. The project went well, despite of new technologies that they have to implement. The user administration module is a generic module to administrate users of the systems. The data warehouse module is also new to them, and they make to the end an analysis of user activity data warehouse systems. For the data mining module, they manage to implement two methods out of three methods I have asked them in the beginning. All applications are implemented using the Java EE with the Model View Controller (MVC) concept as well as Data Access Object (DAO) design pattern. They also implemented the JFreeChart library for graph display and the WEKA library for implementing the naive Bayes data mining method. The whole project is intended to become a system template for students who will be taking web application, data warehouse, and data mining subjects, so they do not have to build a system from scratch for the sake of learning Data Warehouse or Data Mining alone.

This year. the result of the internship is very good, and very useful for the next teaching as well as the next internship program.

Despite of the hard working, the two internships have also enjoyed to stay in Bali. They have played the things that they have planned such as kite surfing and diving. Hope they will have a lot of memories and experiences while staying in Bali both in terms of the Balinese culture and the technology learning.

This is a picture taken at the end of their presentation time. Form the left: Adrien Claudine, Me, Nico Bruhne (Forth Year Stikom Bali’s Dual Degree Program), Florian Guihard, Putu Sri Sasmitha Dewi (Forth Year Stikom Bali’s Dual Degree Program), and Klinton Putra B.B.M. (Forth Year Stikom Bali’s Dual Degree Program).

Document Clustering Algorithm

Untuk melakukan proses clustering pada document, bisa digunakan beberapa metode clustering yang telah umum digunakan seperti k-means clustering algorithm, atau variasinya: bisecting k-means, dan hierarchical clustering algorithm, baik Agglomerative atau Divisive.

Dalam melakukan proses clustering, perbandingan kesamaan (similarity) juga perlu diukur. Dalam kegiatan Document Clustering similarity measure yang banyak digunakan adalah cosine measure yang didefinisikan sebagai berikut:

cosine (d1, d2) = (d1 . d2) / (||d1|| ||d2||)

dimana . adalah vector dot product dan ||d|| adalah panjang dari vector d.

Untuk menghitung centroid dari cluster digunakan rumus berikut ini:

c = 1/|S| sum_(d in S) d

yang tidak lain merupakan vector yang didapatkan dengan merata-ratakan weight dari berbagai macam terms yang ada di dalam dokumen S.

Goodness of fit dalam document clustering yang menggunakan cosine sebagai similarity measure adalah sebagai berikut:

1/|S|^2 sum_(d in S, d’ in S) cosine (d’, d) = ||c||^2

Untuk mengukur kualitas cluster dapat digunakan
1. Entropy: memanfaatkan probabilitas dari cluster yang terbentuk yang dihitung dengan rumus E_j = – sum_i p_(ij) log p_(ij) dimana p_(ij) adalah probabilitas suatu anggota di cluster j untuk masuk ke cluster i.
2. F Measure: memanfaatkan ide presisi dan recall, dimana recall(i,j) = n_ij/n_i dan precision(i,j) = n_(ij)/n_j. n adalah jumlah anggota cluster. F Measure dihitung dengan rumus F(i,j) = (2 * recall(i,j) * precision(i,j)) / ((precision(i,j) + recall(i,j)).

Referensi:
Michael Steinbach, George Karypis, dan Vipin Kumar (2000). A Comparison of Document Clustering Techniques. Technical Report #00-034, Department of Computer Science and Engineering, University of Minnesota.

Image Clustering

Image Clustering merupakan suatu proses data mining yang bertujuan untuk mengelompokkan gambar menjadi kelompok-kelompok dimana gambar dalam satu kelompok akan memiliki karakteristik yang sama, sedangkan image dalam kelompok yang berbeda memiliki karakteristik yang berbeda.

Karakteristik gambar yang dijadikan dasar untuk pengelompokan ada bermacam-macam bentuknya. Ada yang berupa variabel yang diekstrak dari gambarnya seperti komposisi warna, komposisi warna pixel di sekeliling suatu pixel, dan lan-lain. Karakteristik yang digunakan ada juga yang mengharuskan campur tangan manusia untuk mendeskripsikan terlebih dahulu gambar yang ada menjadi keywords atau narasi, sehingga pengelompokan dilakukan berdasarkan keywords atau narasi tersebut. Disamping itu, karakteristik gambar juga dapat diekstrak berdasarkan arah gambar dan jumlah garis yang ada pada gambar, seperti halnya gambar huruf Chinese atau Japanese.

Sehingga secara keseluruhan kegiatan image clustering mempunyai tahapan-tahapan sebagai berikut:
1. Memasukkan semua input gambar yang akan dikelompokkan
2. Mengekstrak variabel (karakteristik) dari gambar-gambar yang telah diinputkan
3. Melakukan proses clustering (pengelompokan) menggunakan metode clustering yang ditentukan.

1. Memasukkan semua input gambar yang akan dikelompokkan

Proses ini sangat umum dilakukan dalam kegiatan entry data atau sistem informasi. Data gambar yang dimasukkan akan disimpan di dalam database untuk selanjutnya variabel gambar terkait akan diekstrak. Ukuran gambar dapat berbeda-beda.

2. Mengekstrak variabel (karakteristik) dari gambar-gambar yang telah diinputkan

Proses ini dapat dilaksanakan secara otomatis begitu suatu gambar diinputkan, tetapi dapat juga dilakukan secara bersama-sama setelah beberapa gambar diinputkan. Proses ekstraksi variabel (karakteristik) ditentukan berdasarkan jenis karakteristik (variabel) yang diekstrak. Apabila variabel (karakteristik) yang diekstrak itu berasal langsung dari informasi yang ada dalam gambar, maka suatu program ekstraksi perlu untuk dikembangkan.

File gambar umumnya mempunyai beberapa informasi yang terkandung di dalamnya seperti ukuran gambar, bit pixelnya, informasi warna setiap pixelnya dll. Untuk melihat komposisi informasi dalam gambar bisa dilihat di Format File BMP, Format File TIFF, dan Format File JPG. Untuk dapat mengekstraksi variabel yang didapat dari informasi gambar perlu untuk mengerti komposisi informasi dari gambar tersebut, sehingga variabel dapat diekstraksi dengan tepat.

Sedangkan apabila variabel (karakteristik) yang diekstraksi berasal dari keywords atau narasi yang diberikan user, maka perlu untuk menyediakan program entry untuk menginputkan keywords dan narasi yang bersangkutan.

3. Melakukan proses clustering (pengelompokan) menggunakan metode clustering yang ditentukan

Ada beberapa metode clustering yang dapat digunakan untuk melakukan proses pengelompokan. Ada yang berbasis partition-base seperti fuzzy c-means, ada yang berbasis mixture model, dan ada yang berbasis hierarchical clustering.

Pada dasarnya, tujuan dari metode-metode ini adalah sama yaitu untuk menghasilkan gambar-gambar yang dikelompokkan ke masing-masing kelompok yang sesuai. Yang berbeda dari mereka adalah basis yang digunakan untuk mengukur kesamaan masing-masing gambar. Ada yang mengukur tingkat kesamaan gambar dari jarak antar variabelnya, ada yang mengukur berdasarkan komposisi distribusi masing-masing gambar dll. Untuk lebih jelasnya mengenai clustering, silahkan baca tulisan saya tentang Clustering, K-Means, dan Mixture Model.

Demikian sedikit informasi, semoga bermanfaat.

Single Pass Clustering

Single Pass Clustering merupakan suatu tipe clustering yang berusaha melakukan pengelompokan data satu demi satu dan pembentukan kelompok dilakukan seiring dengan pengevaluasian setiap data yang dimasukkan ke dalam proses cluster. Pengevaluasian tingkat kesamaan antar data dan cluster dilakukan dengan berbagai macam cara termasuk menggunakan fungsi jarak, vectors similarity, dan lain-lain.

Algoritma yang sering digunakan dalam Single Pass Clustering adalah sebagai berikut:

1) for each data d loop
a) find a cluster c that maximises an objective function
b) if the value of the objective function > a threshold value then include d in c
c) else create a new cluster whose only data is d
2) end loop

Dalam menggunakan algoritma ini, dua hal yang perlu menjadi perhatian adalah penentuan objective function dan penentuan threshold value. Objective function yang ditentukan haruslah sebisa mungkin mencerminkan keadaan data yang dimodel dan dapat memberikan nilai tingkat kesamaan atau perbedaan yang terkandung di dalam data tersebut. Penentuan threshold value juga merupakan hal yang subjektif, makin besar nilai threshold, makin mudah suatu data untuk bergabung ke dalam suatu cluster, dan demikian juga sebaliknya.

Reference:
Klampanos I. A., Jose J. M., and van Rijsbergen C. J. K. (2006). Single Pass Clustering for Peer-to-Peer Information Retrieval: The Effect of Document Ordering. Proceedings of the First International Conference on Scalable Information Systems, Hongkong.

My Clustering Bibliography

Agusta, Y. (2004). Minimum Message Length Mixture Modelling for Uncorrelated and Correlated Continuous Data Applied to Mutual Funds Classification, Ph.D. Thesis, School of Computer Science and Software Engineering, Monash University, Clayton, 3800 Australia

Agusta, Y. and Dowe, D.L. (2002a). MML Clustering of Continuous-Valued Data using Gaussian and t Distributions, in B. McKay and J. Slaney (eds), Lecture Notes in Artificial Intelligence 2557, Proceedings of the 15th Australian Joint Conference on Artificial Intelligence (AI02), Springer-Verlag, Berlin, Germany, pp. 143-154

Agusta, Y and Dowe, D.L. (2002b). Clustering of Gaussian and t Distribution using Minimum Message Length, in M. Sasikumar, H. J. Jayprasad and M. Kavitha (eds), Artificial Intelligence: Theory and Practice, Proceedings of the International Conference Knowledge-Based Computer Systems (KBCS-2002), Vikas Publishing House Pvt. LTD., New Delhi, India, pp. 289-299.

Agusta, Y and Dowe, D.L. (2003). Unsupervised Learning of Correlated Multivariate Gaussian Mixture Models using MML, in T.D. Gideon and L.C. Fung (eds), Lecture Notes in Artificial Intelligence 2903, Proceedings of the 16th Australian Joint Conference on Artificial Intelligence (AI03), Springer-Verlag, Berlin, Germany, pp. 477-489.

Akaike, H. (1974). A New Look at the Statistical Model Identification, IEEE Transaction on Automatic Control AC-19(6): 716-723.

Bezdek, J. C. (1981). Pattern Recognition with Fuzzy Objective Function Algoritmss, Plenum Press, New York.

Cheeseman, P. and Stutz, J. (1996). Bayesian Classification (AutoClass): Theory and Results, in U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth and R. Uthurusamy (eds), Advances in Knowledge Discovery and Data Mining, AAAI Press/MIT Press, Cambridge, MA, pp. 153-180.

Figueiredo, M. A. and Jain A.K. (2002). Unsupervised Learning of Finite Mixture Models. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(3): 381-396.

Fraley, C. and Raftery, A. E. (1998). MCLUST: Software for Model-Based Cluster and Discriminant Analysis, Technical Report 342, Department of Statistics, University of Washington, Box 354322, Seattle, WA, USA.

MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations, Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1: 281-297.

McLachlan, G.J. and Peel, D. (2002a). On Computational Aspects of Clustering via Mixtures of Normal and t-Components, Proceedings of the American Statistical Association (Bayesian Statistical Science Section), Indianapolis, Alexandria, Virginia.

McLachlan, G.J. and Peel, D. (2002b). Finite Mixture Models, John Wiley and Sons, New York.

McLachlan, G. J., Peel, D., Basford, K. E. and Adams, P. (1999). The EMMIX Software for the Fitting of Mixtures of Normal and t-Components, Journal of Statistical Software 4(2): 1087-1092.

Miyamoto, S. and Agusta, Y. (1995). An Efficient Algorithm for L1 Fuzzy c-Means and its Termination, Control and Cybernetics 24(4): 422-436.

Miyamoto, S. and Agusta, Y. (1995). Algorithms for L1 and Lp Fuzzy C-Means and Their Convergence, in C. Hayashi, N. Oshumi, K. Yajima, Y. Tanaka, H. H. Bock and Y. Baba (eds), Data Science, Classification, and Related Methods, Springer-Verlag, Tokyo, Japan, pp. 295-302.

Miyamoto S. and Nakayama, Y. (2003). Algorithms of Hard C-Means Clustering Using Kernel Functions in Support Vector Machines, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 7, No. 1, pp. 19–24.

Miyamoto, S. and Suizu, D. (2003). Fuzzy C-Means Clustering Using Kernel Functions in Support Vector Machines, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol. 7, No. 1, pp. 25–30.

Neal, R. M. (1991). Bayesian Mixture Modeling by Monte Carlo Simulation, Technical Report CRG-TR-91-2, Department of Computer Science, University of Toronto, Toronto, Canada.

Pena, J. M., Lozano, J. A. and Larranaga, P. (1999). An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recognition Lett., 20:1027-1040.

Schwarz, G. (1978). Estimating the Dimension of a Model, The Annals of Statistics 6: 461 – 464.

Shannon, C. E. (1948). A Mathematical Theori of Communication, Bell System Tech. Journal 27: 379-423.

Tibshirani, R., Walter, G. and Hastie, T. (2000). Estimating the Number of Clusters in a Dataset using the Gap Statistics, Technical Report 208, Department of Statistics, Stanford University, Standford, CA 94305, USA.

Wallace, C. S. (1986). An Improved Program for Classification, Proceedings of the 9th Australian Computer Science Conference (ACSC-9), Vol. 8, Monash University, Australia, pp. 357-366.

Wallace, C. S. and Boulton, D. M. (1968). An Information Measure for Classification, Computer Journal 11(2): 185-194.

Wallace, C. S. and Dowe D. L. (1994). Intrinsic Classification by MML – the Snob Program, Proceedings of the 7th Autralian Joint Conference on Artificial Intelligence (AI94), World Scientific, Singapore, pp. 37-44.

Wallace, C. S. and Dowe, D. L. (1997). MML Mixture Modelling of Multi-State, Poisson, von Mises Circular and Gaussian Distribusions, Proceedings of the 6th International Workshop on Artificial Intelligence and Statistics, Fort Launderdale, Florida, pp. 529-536.

Wallace, C. S. and Dowe, D. L. (2000). MML Clustering of Multi-state, Poisson, von Mises Circular and Gaussian Distributions, Statistics and Computing 10: 73-83.

Wallace, C. S. and Freeman, P. R. (1987). Estimation and Inference by Compact Coding, Journal of the Royal Statistical Society B 49(3): 240-265.

Related Theory

Bernardo J.M. and Smith A.F.M. (1994). Bayesian Theory, Wiley, Chichester, UK.

Dowe D.L., Oliver J.J. and Wallace C.S. (1996). MML Estimation of the Parameters of the Spherical Fisher Distribution, in S. Arikawa and A.K. Sharma (eds), Lecture Notes in Artificial Intelligence 1160, Proceedings of the 7th International Workshop on Algorithmic Learning Theory, (ALT’96), Springer-Verlag, Heidelberg, Germany, pp. 213-227.

Fitzgibbon L.J., Dowe D.L. and Allison L. (2002a). Univariate Polynomial Inference by Monte Carlo Message Length Approximation, in C. Sammut and A. Hoffmann (eds), Proceedings of 19th International Conference on Machine Learning (ICML-2002), Morgan Kaufman, Sydney, pp. 147-154.

Fitzgibbon L.J., Dowe D.L. and Allison L. (2002b). Change-Point Estimatin Using New Minimum Message Length Approximations, in M. Ishizuka and A. Sattar (eds), Lecture Notes in Artificial Intelligence 2417, Seventh Pacific Rim International Conference on Artificial Intelligence (PRICAI-2002), Springer-Verlag, Berlin, Germany, pp. 244-254.

Girolami, M. (2002). Mercel Kernel Based Clustering in Feature Space, IEEE Transactions on Neural Networks, Vol. 13, No. 3, pp. 761-766.

Lam E. (2000). Improved Approximation in MML, Honours’ Thesis, School of Computer Science and Software Engineering, Monash University, Clayton, Victoria 3800, Australia.

Lindley, D.V. (1972). Bayesian Statistics, A Review, SIAM, Philadelpia, PA, USA.

Wallace, C. S. and Dowe, D. L. (1999a). Minimum Message Length and Kolmogorov Complexity, Computer Journal 42(4): 270-283. Special issue on Kolmogorov Complexity.

Wallace, C. S. and Dowe, D. L. (1999b). Refinements of MDL and MML Coding, Computer Journal 42(4): 345-347. Special issue on Kolmogorov Complexity.