-
TUGAS AKHIR MATA KULIAH TEXT MINING
KLASTERISASI DOKUMEN TEKS KANKER DENGAN MENGGUNAKAN METODE
K-MEANS
oleh:
Novan Dimas Pratama 125150200111002 M. Fatqur Rohman 125150200111008 Felia Eliantara 125150200111016 Gilang Yanuar Wirana 125150200111037
PROGRAM STUDI INFORMATIKA FAKULTAS ILMU KOMPUTER
UNIVERSITAS BRAWIJAYA MALANG
-
2015 BAB I
PENDAHULUAN
1.1 Latar Belakang
Jutaan kasus kematian pada tahun 2008, menjadikan kanker adalah salah satu
area studi yang paling penting bagi para peneliti biomedis. Telah banyak dipelajari
selama lebih dari 100 tahun. Pertumbuhan yang cepat dari teks pada penelitian
kanker menyediakan sumber daya yang berharga. Banyak publikasi penelitian kanker
dan jumlah publikasi terus meningkat setiap tahun. Penulis mencari di PubMed
dengan kata '' kanker '' dalam judul atau abstrak dan penulis mendapati lebih dari
847.000 publikasi. Hampir mustahil untuk orang untuk membaca semua publikasi ini
dan menemukan pengetahuan baru. Text mining dapat membantu peneliti untuk
menyelesaikan tugas sulit ini. Menyadari keuntungan dari Text Mining akan banyak
memfasilitasi penelitian kanker, dengan membantu untuk menemukan pengetahuan
baru untuk diagnosa kanker, pengobatan, dan pencegahan.
Jumlah teks biomedis yang besar menyediakan sumber yang kaya
pengetahuan untuk penelitian biomedis. Text mining dapat membantu kita untuk
menggaliinformasi dan pengetahuan dari teks dan sekarang banyak diterapkan dalam
penelitian biomedis.
Banyak peneliti telah mengambil keuntungan dari teknologi text mining untuk
menemukan pengetahuan baru untuk meningkatkan pengembangan penelitian
biomedis, khususnya yang berkaitan dengan penyakit ganas, seperti kanker.
K-Means adalah suatu metode penganalisaan data atau metode Text Mining
yang melakukan proses unsupervised learning dan merupakan salah satu metode yang
melakukan pengelompokan data dengan sistem partisi. Metode k-means berusaha
mengelompokkan data yang ada ke dalam beberapa kelompok, dimana data dalam
satu kelompok mempunyai karakteristik yang sama satu sama lainnya dan
mempunyai karakteristik yang berbeda dengan data yang ada di dalam kelompok
yang lain. Dengan kata lain, metode ini berusaha untuk meminimalkan variasi antar
data yang ada di dalam suatu cluster dan memaksimalkan variasi dengan data yang
ada di cluster lainnya. Dalam sistem ini metode K-Means akan diimplementasikan
untuk mengklasifikasikan teks yang berhubungan dengan jenis jenis kanker.
-
1.2 Rumusan Masalah
1. Bagaimana implementasi Algoritma K-Means dalam pemograman?
2. Bagaimana hasil pengujian Algoritma K-Means dalam
1.3 Tujuan
1. Mengetahui implementasi algoritma K-Means dalam pemograman
3. Mengetahui hasil pengujian Algoritma K-Means dalam klasterisasi dokumen
tentang jenis-jenis kanker
-
BAB II
LANDASAN TEORI
Clustering adalah proses membuat pengelompokan sehingga semua anggota
dari setiap partisi mempunyai persamaan berdasarkan matrik tertentu. Sebuah cluster
adalah sekumpulan obyek yang digabung bersama karena persamaaan atau
kedekatannya. Clustering berdasarkan persamaannya merupakan teknik yang sangat
berguna karena akan mentranslasi ukuran persamaan yang intuitif menjadi ukuran
yang kulantitatif. Ada banyak pendekatan untuk membuat cluster, diantaranya adalah
membuat aturan yang mendikte keanggotaan dalam group yang sama berdasarkan
tingka persamaan dinatara anggota-anggotanya. Pendekatan lainny adalah dengan
membuat sekumpulan fungsi yang mengukur beberapa property dari pengelompokan
tersebut sebagai fungsi dari beberapa parameter dari sebuah clustering.
- Analisa Cluster
Analisa cluster atau analisa kelompok merupakan teknik analisis data yang
bertujuan untuk mengelompokkan individu atau obyek ke dalam beberapa kelompok
yang memiliki sifat berbeda antar kelompok, sehingga individu atau obyek yang
terletak dalam satu kelompok akan mempunyai sifat relative homogeny
- Tipe Clustering
Ada dua jenis data clustering yang sering dipergunakan dalam proses
pengelompokan data yaitu:
1. hierarchical (hirarki) data clustering
metode pengelompokan hirarki digunakan apabila beluma da informasi
jumlah kelompok.
2. non-hierarchical (non hirarki) data clustering.
Metode pengelompokan Non hirarki bertujuan mengelompokkan n obyek ke dala k
kelompok (k < n). salah satu prosedur pengelompokan pada non hirarki adalah
dengan menggunakan metode K-Means. Metode ini merupakan metode
pengelompokan yang bertujuan mengelompokkan obyek sedemikian hingga jarak
tiap-tiap obyek ke pusat kelompok di dalam satu kelompok adalah minimum
2.1 algoritma K-MEANS
KMeans merupakan salah satu metode data clustering non hirarki yang
berusaha mempartisi data yang ada ke dalam bentuk satu atau lebih cluster atau
kelompok. Metode ini mempartisi data ke dalam cluster atau kelompok sehingga data
-
yang memiliki karakteristik yang sama dikelompokkan ke dalam satu cluster yang
sama dan data yang mempunyai karakteristik yang berbeda dikelompokkan ke dalam
kelompok yang lain. Adapun tujuan dari data clustering ini adalah untuk
meminimalisasikan objective function yang diset dalam proses clustering, yang pada
umumnya berusaha meminimalisasikan variasi di dalam suatu cluster dan
memaksimalisasikan variasi antar cluster. Data clustering menggunakan metode K-
Means ini secara umum dilakukan dengan algoritma dasar sebagai berikut :
1. Tentukan jumlah cluster
2. Alokasikan data ke dalam cluster secara random
3. Hitung centroid atau rata-rata dari data yang ada di masing-masing cluster
4. Alokasikan masing-masing data ke centroid atau rata-rata terdekat
5. Kembali ke Step 3, apabila masih ada data yang berpindah cluster atau
apabila perubahan nilai centroid, ada yang di atas nilai threshold yang
ditentukan atau apabila perubahan nilai pada objective function yang
digunakan di atas nilai threshold yang ditentukan.
- Penentuan Jumlah dan Pusat Klaster
Inisialisasi atau penentuan nilai awal pusat klaster dapat dilakukan dengan
berbagai macam cara, antara lain:
1. Pemberian nilai secara random
2. Pengambilan sampel awal dari data
3. Penentuan nilai awal hasil dari klaster hirarki dengan jumlah klaster yang
sesuai dengan penentuan awal.
Dalam hal ini biasanya user memiliki pertimbangan intuitif karena dia
memiliki informasi awal tentang obyek yang sedang dipelajari, termasuk jumlah
klaster yang paling tepat.
- Penempatan Obyek ke Dalam Klaster
Penempatan obyek ke dalam klaster didasarkan pada kedekatannya dengan
pusat klaster. Dalam tahap ini perlu dihitung jarak tiap data ke tiap pusat klaster
yang telah ditentukan. Jarak paling dekat antara suatu data dengan pusat klaster
tertentu merupakan hal penentu data tersebut akan masuk klaster yang mana.
- Perhitungan Kembali Pusat Klaster
Pusat klaster ditentukan kembali dengan cara dihitung nilai rata-rata
data/obyek dalam klaster tertentu. Jika dikehendaki dapat pula digunakan
perhitungan median dari anggota klaster yang dimaksud. Mean bukan satu-
satunya ukurang yang bisa dipakai.
-
Pada kasus tertentu pemakaian median memberikan hasil yang lebih baik. Karena
median tidak sensitif terhadap data outlier (data yang terletak jauh dari yang lain,
meskipun dalam satu klaster - pencilan)
Contoh:
Mean dari 1, 3, 5, 7, 9 adalah 5
Mean dari 1, 3, 5, 7, 1009 adalah 205
Median dari 1, 3, 5, 7, 1009 adalah 5
2.1.1 keterbatasan K-Means
1. K-Means sangat bergantung pada penentuan pusat cluster awal
2. Penentuan nilai awal yang berbeda dapat memberikan hasil akhir
yang berbeda.
2.1.2 Kelebihan K-Means
1. Relatively efficient: O(tkn), dimana n adalah # objects, k adalah #
clusters, dan t merupakan # iterations. Umumnya, k, t
-
BAB III
PEMBAHASAN
3.1 Data
Diambil 44 dokumen teks yang membahas tentang kanker.
NO Dokumen
D1 Cancer of the pancreas usually develops without early symptoms.
D2 Symptoms may include weight loss,mild abdominal discomfort that may radiate to the back, and occasionally the development of diabetes.
D3 Tumors that develop
D4
20 Cancer Facts & Figures 2015 near the common bile duct may cause a blockage that leads to jaundice (yellowing of the skin and eyes), which can sometimes allow the tumor to be diagnosed at an early stage.
D5
Signs of advanced stage disease may include severe abdominal pain, nausea, and vomiting.
D6
Approximately 20% of pancreatic cancers are attributable to cigarette smoking; incidence rates are about twice as high for smokers as for never smokers.
D7 Use of smokeless tobacco products also increases risk.
D8
Other risk factors include a family history of pancreatic cancer and a personal history of chronic pancreatitis, diabetes, obesity, and possibly high levels of alcohol consumption.
D9 Early ovarian cancer usually has no obvious symptoms.
D10
However, studies have indicated that some women experience persistent, nonspecific symptoms, such as bloating, pelvic or abdominal pain, difficulty eating or feeling full quickly, or urinary urgency or frequency.
D11 Women who experience such symptoms daily for more than a few weeks should seek prompt medical evaluation.
D12 The most common sign of ovarian cancer is swelling of the abdomen, which is caused by the accumulation of fluid.
D13 Abnormal vaginal bleeding is rarely a symptom of ovarian cancer, though it is a symptom of cervical and uterine cancers.
D14 The most important risk factor is a strong family history of breast or ovarian cancer.
D15 Women who have had breast cancer or who have tested positive for inherited mutations in BRCA1 or BRCA2 genes are at increased risk.
D16 Studies indicate that preventive surgery to remove the ovaries and fallopian tubes in these women decreases the risk of ovarian cancer.
D17 Other medical conditions associated with increased risk include pelvic inflammatory disease and Lynch syndrome.
-
D18 The use of estrogen alone as menopausal hormone therapy has been shown to increase risk in several large studies.
D19 Tobacco smoking increases the risk of mucinous ovarian cancer.
D20 Heavier body weight may be associated with increased risk of ovarian cancer.
D21 Pregnancy, long-term use of oral contraceptives, and tubal ligation reduce risk.
D22 Hysterectomy (removal of the uterus) and salpingectomy (removal of fallopian tubes) may reduce risk.
-
3.2 Manualisasi
Dokumen :
D1 Cancer of the pancreas usually develops without early symptoms
D2 Use of smokeless tobacco products also increases risk D3 Early ovarian cancer usually has no obvious symptoms D4 Men who experience such symptoms daily for more than a few weeks should seek prompt medical evaluation
D5 The most common sign of ovarian cancer is swelling of the abdomen, which is caused by the accumulation of fluid
Dokumen setelah dilakukan pre-processing
D1 : Cancer pancreas develops early symptoms
D2 : Smokeless tobacco products increases risk
D3 : Early ovarian cancer obvious symptoms
D4 : Men experience symptoms daily weeks seek prompt medical evaluation
D5 : Common ovarian cancer swelling abdomen accumulation fluid
Terms tf
idf tf.idf
D1 D2 D3 D4 D5 Tf D1 D2 D3 D4 D5
Cancer 1 1 1 3 0.221849 0.221849 0 0.221849 0 0.221849
Pancreas 1 1 0.69897 0.69897 0 0 0 0
Develops 1 1 0.69897 0.69897 0 0 0 0
Early 1 1 2 0.39794 0.39794 0 0.39794 0 0
Symptoms 1 1 1 3 0.221849 0.221849 0 0.221849 0.221849 0
Smokeless 1 1 0.69897 0 0.69897 0 0 0
Tobacco 1 1 0.69897 0 0.69897 0 0 0
-
Products 1 1 0.69897 0 0.69897 0 0 0
Increases 1 1 0.69897 0 0.69897 0 0 0
Risk 1 1 0.69897 0 0.69897 0 0 0
Ovarian 1 1 2 0.39794 0 0 0.39794 0 0.39794
Obvious 1 1 0.69897 0 0 0.69897 0 0
Men 1 1 0.69897 0 0 0 0.69897 0
Experience 1 1 0.69897 0 0 0 0.69897 0
Daily 1 1 0.69897 0 0 0 0.69897 0
Weeks 1 1 0.69897 0 0 0 0.69897 0
Seek 1 1 0.69897 0 0 0 0.69897 0
Prompt 1 1 0.69897 0 0 0 0.69897 0
Medical 1 1 0.69897 0 0 0 0.69897 0
Evaluation 1 1 0.69897 0 0 0 0.69897 0
Common 1 1 0.69897 0 0 0 0 0.69897
Swelling 1 1 0.69897 0 0 0 0 0.69897
Abdomen 1 1 0.69897 0 0 0 0 0.69897
Accumulation 1 1 0.69897 0 0 0 0 0.69897
Fluid 1 1 0.69897 0 0 0 0 0.69897
Tf.Idf Cancer Pancreas Develops Early Symptoms Smokeless Tobacco Products Increases Risk Ovarian
1 0.221849 0.69897 0.69897 0.39794 0.221849 0 0 0 0 0 0
2 0 0 0 0 0 0.69897 0.69897 0.69897 0.69897 0.69897 0
3 0.221849 0 0 0.39794 0.221849 0 0 0 0 0 0.39794
4 0 0 0 0 0.221849 0 0 0 0 0 0
-
5 0.221849 0 0 0 0 0 0 0 0 0 0.39794
Tf.Idf Obvious Men Experience Daily Weeks Seek Prompt Medical Evaluation Common Swelling
1 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0
3 0.69897 0 0 0 0 0 0 0 0 0 0
4 0 0.69897 0.69897 0.69897 0.69897 0.69897 0.69897 0.69897 0.69897 0 0
5 0 0 0 0 0 0 0 0 0 0.69897 0.69897
Tf.Idf Abdomen Accumulation Fluid
1 0 0 0
2 0 0 0
3 0 0 0
4 0 0 0
5 0.69897 0.69897 0.69897
Cluster
Pusat Cluster 1
Cancer Pancreas Develops Early Symptoms Smokeless Tobacco Products Increases Risk Ovarian Obvious Men
1 0.2218487 0.69897 0.69897 0.39794 0.2218487 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0.69897 0.69897 0.69897 0.69897 0.69897 0 0 0
-
Cluster
Pusat Cluster 1
Experience Daily Weeks Seek Prompt Medical Evaluation Common Swelling Abdomen Accumulation Fluid
1 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0
Menghitung jarak dari pusat cluster dengan pusat cluster D1 dan D2
Doc Jarak C1 Jarak C2 CLUSTER
1 0 1.917473 1 2 1.917473 0 2 3 1.274376 1.829344 1 4 2.256804 2.529918 1 5 1.945724 2.256804 1
Cluster
Pusat Cluster 2
Cancer Pancreas Develops Early Symptoms
Smokeless
Tobacco Products
Increases
Risk Ovarian Obvious Men
1 0.1663
87 0.1747
43 0.1747
43 0.198
97 0.1663
87 0 0 0 0 0 0.198
97 0.1747
43 0.1747
43
2 0 0 0 0 0 0.698
97 0.698
97 0.698
97 0.698
97 0.698
97 0 0 0
-
Cluster
Experience Daily Weeks Seek Prompt Medical Evaluation Common Swelling Abdomen Accumulation Fluid
1 0.17474 0.17474 0.17474 0.17474 0.17474 0.17474 0.17474 0.17474 0.17474 0.17474 0.17474 0.17474
2 0 0 0 0 0 0 0 0 0 0 0 0
Menghitung jarak dari pusat cluster
Doc Jarak C1 Jarak C2 CLUSTER
1 1.425452 2.770686 1
2 2.008822 2 2
3 1.337024 2.710443 1
4 1.539006 2.757645 1
5 1.670138 3.015487 1
-
3.3 Potongan Source Code
package KMeans;
/**
*
* @author Kelompok 1
*/
public class KMeans {
private Matrix data;
private double[][] centroid;
private int K;//jumlah cluster
private double[][] jarak;
private int clusterBaru[];
private int clusterLama[];
public KMeans(Matrix data, int jum_kluster) {
this.data = data;
K = jum_kluster;
//create centroid awal
centroid = new double[K][data.getColumns()];
for (int i = 0; i < centroid.length; i++) {
centroid[i] = data.getDataPerRow(i);
}
//end creae centroid awal
jarak = new double[data.getRows()][jum_kluster];//inisialisasi
var jarak yang merupakan jarak data terhadap masing2 kluster
clusterBaru = new int[data.getRows()];
clusterLama = new int[data.getRows()];
}
public void mulai() {
hitungJarak();
generateCluster();
// cetakK(clusterBaru);
do {
System.arraycopy(clusterBaru, 0, clusterLama, 0,
clusterBaru.length);
updateCentroid();
hitungJarak();
generateCluster();
// cetakK(clusterBaru);
}while (!isStop());
}
private void hitungJarak() {
CariJarak cari_jarak = new CariJarak();
jarak = cari_jarak.ecludian(data.getDataMatrix(), centroid);
}
-
private void generateCluster() {
for (int i = 0; i < clusterBaru.length; i++) {
clusterBaru[i] = getCluster(i);
}
}
private int getCluster(int row_data) {
int dekat = 0;
for (int j = 1; j < K; j++) {
if (jarak[row_data][j] < jarak[row_data][dekat]) {
dekat = j;
}
}
return dekat + 1;
}
private void updateCentroid() {
for (int k = 1; k
-
Tampilan program dalam melakukan klustering