BFS & DFS dengan NetworkX di Python

Kemarin kita sudah membahas permasalahan sederhana Greedy algorithm di NetworkX. Sekarang kita akan membahas 2 permasalahan sederhana lain di Teori Graph masih dengan NetworkX, yaitu Breadth First Search (BFS) dan Depth First Search (DFS). O iya, post ini adanya di blog ini, bukannya di blog data science, karena permasalahan yang dibahas agak menjauh dari tema DS/IoT/BD.

Ada cerita yang (menurut saya) menarik dibalik post ini. DFS & BFS biasanya dibahas (setidaknya) di either mata kuliah Matematika Diskrit atau Analisa Algoritma. Either way saya akhir² ini agak "gemes" mahasiswa ga sadar betapa pentingnya materi² yang ia pelajari di kehidupan nyata. Sebenarnya mungkin ndak sepenuhnya salah mereka juga sih, karena ndak hanya pengajar, bahkan bukunya-pun jarang yang menerangkan hal ini. Tapi sekarang jaman internet, mereka bisa dengan mudah mendapatkan informasi ini. Singkat cerita, DFS/BFS ini cukup banyak aplikasinya di dunia nyata, misal saja penentuan rute di GPS atau permasalahan di bidang sistem transportasi. Kemungkinan besar they use modified version of the algorithm, tapi basic/logic-nya masih sama (baca disni atau disini).

Contoh Aplikasi Graph Traversal - Map Route (GPS)

Anyway, di kelas saya sering melempar pertanyaan dengan iming² nilai tambahan di ujian (UTS/UAS). Misal UTS/UAS+10, 20, atau bahkan 30 bergantung kesulitan soal yang saya berikan di kelas. Prinsip saya ujian kan hanya meng-evaluasi pemahaman mahasiswa, kalau di kelas ia sudah mampu menunjukan bahwa ia mengerti materi yang diberikan, maka sebenarnya ujian menjadi tidak terlalu efektif buat mereka. Anyway balik ke laptop, eh maksudnya BFS/DFS, ... pas ngajar ini di kelas saya agak gemes karena mereka kok kurang termotivasi dengan imimng² bonus nilai di ujian di atas. Walhasil saya waktu itu iseng dan mengatakan:

"kalau ada yang bisa aplikasikan DFS atau BFS ini ke NetworkX untuk menemukan Spanning Tree dari Graph dalam 30 menit, maka ndak hanya nilai ujian UTS & UAS-nya yang di tambah, tapi juga saya traktir makan siang di warung Padang, minumnya es jeruk, dan boleh nambah. Ga hanya itu, boleh di kerjakan berkelompok (semua member di traktir & dapat bonus nilai) dan boleh nyontek dari internet (copas)."

Jujur, saat itu agak deg²an juga, bukan hanya karena uang di dompet pas²an, tapi juga karena belum nge-check di internet: "ada ga ya?" ... 😂 ... (Notes, mereka sudah belajar networkX dan aplikasi²nya di pertemuan² sebelumnya). "Untungnya" ndak ada yang bisa .... 😄 ... (#DosennyaJahatGaIkhlas) ... Anyway, saya cukup PD karena saya sering menyayangkan kurikulum perguruan tinggi yang jarang update dari puluhan tahun yang lalu (di banyak universitas dalam & bahkan luar negeri). Hal ini di dukung dengan kenyataan bahwa mereka ndak bisa menemukan aplikasi langsung BFS/DFS ini ke aplikasi yang kekinian. (that!, atau nge-Google-nya kurang cermat ... 😅)

Ah udah ah ... ceritanya kepanjangan ... mari kita bahas DFS/BFS-nya 😊. BFS/DFS sebenarnya merupakan Graph traversal, atau dengan kata lain traversal adalah jalan² di graph melalui edge²nya. namun tentu saja dengan syarat tertentu. Teori "ngasal"-nya mudah sekali:
BFS: "Traverse level yang rendah dan sesuai urutan nodes terlebih dahulu"
DFS: "Keep Traversing sesuai urutan nodes, lalu backtrack kalau mentok"
Kalau mau penjelasan teori lebih lengkap dan formalnya bisa simak disini: BFS & DFS

Sehingga kalau diberikan graph seperti ini:

dengan pemisalan root = "a" dan urutan node sesuai abjad (a,b,c,d,e,f,g,h), maka spanning tree BFS-nya adalah:

Penjelasannya cukup sederhana: dimulai dari root "a" (level 0), maka di level selanjutnya (1) ada nodes b, c, & g. Sesuai level dan urutan maka setelah a terus b, lalu c, kemudian g. Setelah itu ke level 2, ada d & e. Kemudian f di level 3 dan terakhir h di level 4. Sehingga spanning tree-nya seperti di atas.

dan spanning tree DFS-nya adalah:

Dimulai dari user-defined root = "a", kemudian traverse sesuai urutan node: berarti b, kemudian terus maju sesuai urutan node: d, dan seterusnya sampai h. Karena di h mentok, lalu "backtrack" ke f, tapi di f tidak ada lagi edge yang bisa di tambahkan, kemudian backtrack lagi ke e, kemudian terakhir tambahkan g.

Mudah sekali kan? ... Ok, kalau sudah mengerti sekarang coba Agan coba sendiri dulu aplikasi NetworkX-nya. Kalau perlu refresh lagi pengetahuan dari post sebelumnya ini. Agan boleh search ke internet for clues (tapi ga boleh ke blog dan github saya). Coba selesaikan masing-masing (DFS & BFS) dalam waktu <30 menit (total 1 jam). Inputnya graph diatas, outputnya gambar graph spanning tree seperti di atas. If you can please let me know in the comment. Catt: nope, agan ga dapet makan siang gratis ... 😄 ... saya penasaran aja ... 

... Asumsi pembaca lagi ngerjain ....

~

... masih juga berasumsi yang sama ....

~

... Ceritanya masih nungguin ...

~

Ok... mari kita bahas contoh solusinya. Seperti biasa, saya akan berikan code yang tidak/kurang efisien. Saya mengharapkan Agan bisa latihan untuk meng-efisienkan code tersebut. Seperti yang dijelaskan disini, algoritma & program yang efisien sangat penting di Data Science/Big Data.

Code lengkap berikut ini saya letakkan di GitHub saya ini, dan nama filenya "BFS_NetworkX.py" dan "DFS_NetworkX.py" dengan file pendukung "my_NetworkX_lib.py" supaya BFS dan DFS-nya ndak keriting. Ok, berikut penjelasannya:

1. Menyiapkan graph awalnya:

    import networkx as nx

    from my_NetworkX_lib import buildGraph, drawGraph # ini berdasarkan post networkX saya sebelumnya.

    V = ['a', 'b', 'c', 'd' , 'e', 'f', 'g', 'h'] # Untuk memudahkan kita asumsikan urutan di V ini = urutan nodes di soal.

    E = [('a','b'),('a','c'),('a','g'),('a','g'),('b','d'),('b','g'),('c','d'),('c','e'),('d','f'),('e','f'),('e','f'),('f','h'),('g','e')]

    G = buildGraph(V, E=E) # Graph di soal

    root = V[0] # Asumsi root = "a"

   Untuk bagian ini tidak perlu penjelasan, karena sudah dibahas di post sebelumnya. Bedanya hanya sekarang kita tidak punya weight di edges-nya (lebih simple/sederhana).

2. Solusi BFS:

    Levels = [[root]]

    Vtemp = [root]

    # Mulai dengan mencari informasi nodes di setiap level [belum efisien]

    for v in V:

        e = G.edges(v)

        e = [v2 for v1,v2 in e if v2 not in Vtemp]

        if e:

            Levels.append(e)

            Vtemp = Vtemp + e

    # Mulai membangun Spanning Tree-nya

    BFS = buildGraph(V)

    for vertices in Levels:

        for v in vertices:

            e = G.edges(v) # Semua edges yang adjacent ke node v

            for v1, v2 in e:

                BFS.add_edge(v1,v2)

                if len(nx.cycle_basis(BFS,root))>0:

                    BFS.remove_edge(v1,v2)

     

Algoritmanya simple: pertama-tama cari tau dulu ada nodes apa saja di setiap level. Kemudian tambahkan edges ke BFS sesuai dengan level tersebut. Informasinya di simpan dalam variable "Levels", jadi Levels adalah "list of lists" (i.e. Levels = [['a'], ['b','c','g'], ... dst]). Variable "Vtemp" digunakan supaya kita tidak traverse ke level di atasnya. 

That's it!.... Bagian kedua program ini mirip dengan kasus Greedy kemarin. Menambahkan edge ke BFS selama tidak menimbulkan cycle. O iya, ada satu yang baru, yaitu perintah "G.edges(v)" yang akan menghasilkan (v,v2) untuk semua v2 yang adjacent/terhubung ke v. Atau dengan kata lain memberikan informasi nodes mana saja yang terhubung dengan node v.

3. Solusi DFS:

    VDFS = V[:] # a copy of V by values

    DFS = nx.Graph() # empty graph

    v = VDFS[0]; del VDFS[0]

    stack = [root] # untuk backtrack

    while VDFS: # VDFS not empty

        DFS.add_node(v)

        e = G.edges(v)

        nextNode = [v2 for v1,v2 in e if v2 not in DFS.nodes()]

        if nextNode: # Not Empty

            nextNode.sort() # meyakinkan urutannya sesuai urutan node (abjad)

            DFS.add_node(nextNode[0])

            DFS.add_edge(v,nextNode[0])

            v = nextNode[0]

            stack.append(v)

            del VDFS[VDFS.index(v)]

        else: #Backtrack

            v = stack[-1]; del stack[-1]

Bedanya dengan BFS, di DFS ini kita butuh suatu variabel untuk melakukan "BackTrack". Variabel yang saya gunakan di code ini adalah "stack". Saya gunakan variabel VDFS sebagai stopper, bahwa kita sudah men-traverse seluruh node di graph. Hati-hati ... kita tidak bisa menggunakan perintah berikut di python "VDFS=V" karena Python melakukan copy by reference (pointer) dan bukan by values (baca disini). Backtrack dilakukan di baris terakhir dengan menggunakan elemen terakhir dari variabel stack. Di dunia pemrograman biasa disebut sebagai "pop" operation. Sedangkan perintah "stack.append(v)" biasa disebut sebagai operasi "push". 

4. Plot Graph solusinya:

    drawGraph(G, file="GraphAwal.png", labels = True, edge_Label=False, gType = 'spring')

    drawGraph(BFS, file="BFS.png", labels = True, edge_Label=False, gType = 'spring')

    drawGraph(DFS, file="DFS.png", labels = True, edge_Label=False, gType = 'spring')

Graphnya selain di plot, langsung di save ke disk (dalam bentuk PNG)... 😊 ... biar handy. Ini hasilnya:

Graph Awal, BFS, & DFS. Silahkan di cek apakah hasil tersebut isomorfis dengan solusi di atas.

That's it ... mudah kan? ... 😁 ... Kalau di search di Google banyak solusi dari BFS dan DFS ini menggunakan fungsi rekursif. Agan bisa latihan dengan mencari solusi rekursifnya. O iya, hati-hati juga banyak algoritma BFS dan DFS di internet hanya sekedar untuk traversal saja, tapi belum ke spanning tree-nya. Anyway ... semakin banyak baca insya Allah akan semakin puyeng... eh salah, maksud saya semakin jelas ... 😄 ... 

Post selanjutnya kita coba masalah umum lain di Graph, that's it for now. Have a nice weekend Guys ... Cheers...

Depok, 07 Jan 2018

</TES>®

Sentence Segmentation (Boundary Detection): easy?

Sebelumnya kita sudah membahas tentang tokenisasi, yaitu pemisahan tokens - suatu entitas dalam string yang biasanya (tidak selalu) diartikan sebagai kata. Sekarang mari kita mundur sedikit dan membicarakan tentang tokenisasi kalimat. Atau dengan kata lain memisahkan kalimat dalam suatu paragraf atau teks secara umum.

KJN: ya ampun Gan... gampang banget ... ente masih Noob sih ... gini nih Gan caranya:

Sentence = "ini adalah kalimat pertama. berikutnya ini kalimat kedua"
Sentence.split(".")

Tuh Gan.... ente kudu belajar dulu ya yg banyak sebelum nulis blog .... #Sedakep, #PalaTengadah, #Mangap #Ngences #MintaDiGampar

TS: O iya kah? kalau kalimatnya begini bagaimana?
kalimat = "Halo apa kabar .... Ada yang bisa kami bantu Mr. Han?"

KJN: anu Gan ... itu mah masalah lu, bukan masalah gue .... #TambahMintaDiGampar ...

Segmentasi kalimat gampang-gampang susah. Ia dibutuhkan terutama ketika kita mengolah teks hasil speech recognition (misal Alexa/Siri/Cortana), OCR, atau sumber text lain yang rentan akan noise dalam ill-formed string. Tanda titik "." tidak selalu menandakan akhir kalimat. Apalagi jika string adalah hasil speech recognition, long pause juga not necessarily means a sentence. Contoh lain adalah apabila ada singkatan (misal et.al. ), URL (alamat website di internet), nama file dengan ekstensi, dsb. Saking rumitnya, bahkan manusia saja terkadang kesulitan untuk memisahkan kalimat.

Ok, sebelum kita membahas lebih jauh, mari kita gunakan beberapa modul yang sudah ada saja dulu untuk segmentasi kalimat. Dari beberapa contoh ini akan semakin menguatkan kita bahwa memisahkan kalimat adalah suatu maslaah yang cukup signifikan di NLP/Text Mining.

Saya akan menggunakan/mencontohkan 3 modul NLP di Python yang paling tenar: NLTK, TextBlob, dan Spacy. Note, saya ndak begitu suka OpenNLP for some reasons yang ndak ingin saya bahasa di sini.

KJN: udah cepetan bahas Gan... jangan kebanyakan kecap, entar kemanisan ... kayak politikus kampanye aje ngomongnye manis-manis gituh ...
TS: #ngasahGolok

NLTK:

# Contoh Tokenization menggunakan modul NLTK 
import nltk
T = "Hello, Mr. Man. He smiled!! This, i.e. that, is it."
print(nltk.sent_tokenize(T)) # Tokenisasi kalimat
# Perhatikan hasilnya, setuju?

Output:

['Hello, Mr. Man.', 'He smiled!!', 'This, i.e.', 'that, is it.']

TextBlob:

# Tokenizing di TextBlob
from textblob import TextBlob
T = "Hello, Mr. Man. He smiled!! This, i.e. that, is it."
print(TextBlob(T).sentences)

Output:

[Sentence("Hello, Mr. Man."), Sentence("He smiled!!"), Sentence("This, i.e."), Sentence("that, is it.")]

Spacy:

# Contoh tokenisasi menggunakan Spacy
import spacy
nlp_spacy_en = spacy.load('en')

T = "Hello, Mr. Man. He smiled!! This, i.e. that, is it."
kalimatS = nlp_spacy_en(T).sents
print( [str(kalimat) for kalimat in kalimatS] ) # Segmentasi kalimat

Output:

['Hello, Mr. Man.', 'He smiled!!', 'This, i.e. that, is it.']

Notice perbedaan hasil segmentasinya? .... Bahkan diantara modul NLP terkenal saja ada ketidaksamaan hasil. Hal ini semakin menguatkan bahwa sentence segmentation is not that easy.

KJN: Berarti yang bener cara gue kan?... gue bilang juga ape...
TS: ... #tebas .... #kelapa ... #haus ...

Mencari benar-salah atau cara terbaik disini akan sangat sulit sekali. Karena seperti yang sudah dibahas sebelumnya begitu banyak kasus berbeda yang harus di pertimbangkan: URL, speech recognition, ocr, abbreviation, dll .... namun karena environment/application dependent, kalau saya pribadi berarti lebih suka rule-based sentence segmentation.

KJN: Gan, ente ngomong apa kumur-kumur ... apaan tuh rule-based segmentation ... ente lagi puber?
TS: #ambilWudhu #shalatSunah2Rakaat ....

Ada modul python khusus yang memungkinkan kita untuk melakukan segmentasi kalimat berdasarkan aturan (rule) tertentu. Salah satunya ...

http://fnl.es/segtok-a-segmentation-and-tokenization-library.html

https://github.com/fnl/segtok

KJN: Ribet amat sih Gan .. gue biasanya jadi konsultan perusahaan internasional PT gombal-gambel pake segmentasi kalimat yang biasa baik-baik aja kok...

TS: nah kali ini komen-nya rada bener luh tong... Tumben ada bagusnye dikit omongan luh. Nape? Ciki rasa Mi'cin abis?... #sekaliKaliGantianNgeselin.

Komentar terakhir KJN ada benernya. Pada kasus umum dimana datanya well-formatted seperti teks dari website, document (doc/csv), dan semacamnya biasanya (>90%) segmentasinya sudah akurat dengan cara standar. Namun ada kalanya kita membutuhkan akurasi yang lebih baik dan-atau aplikasinya memaksa kita untuk menggunakan segmentasi kalimat yang tidak standar (OCR, speech recognition, AI, dll).

That's it .... hanya itu pembahasan di post kali ini. 

Cheers,

</TES>^®

Tokenization dalam Bahasa Inggris, Indonesia, & Alay

Kali ini kita akan membahas salah satu bagian penting dari Text Mining/Natural Language Processing: Tokenization. Tokenization adalah salah satu bagian penting dari proses awal pengolahan data teks. Pengolahan data teks dimulai dengan proses preprocessing yang terkadang disebut juga sebagai data munging/wrangling. Membahas definisi exact dari apa itu data Munging atau wrangling dan apa bedanya menurut saya tidak penting dan menghabiskan waktu. Salah satu istilah yang lebih umum dipakai adalah preprocessing, so mari kita pakai istilah ini saja.

[Text Analytics </TES>®]

Sebelum data diolah dalam model data science/machine learning, data dalam bentuk teks diolah dalam preprocessing terlebih dahulu. Di dalam preprocessing data teks ada beberapa sub proses utama:

Teori Graph di Python lewat NetworkX: Studi Kasus Greedy Algorithm

Di post sebelumnya kita sudah mengaplikasikan Teori Graph di data media sosial. Post ini justru mundur ke belakang dan fokus ke memperkenalkan NetworkX untuk aplikasi terkait Teori Graph secara umum. Graph banyak digunakan untuk memodelkan berbagai permasalahan di dunia nyata, mulai dari media sosial, transportasi, Data Science, sampai penyelesaian permainan Sudoku. Tapi saya lihat banyak pengajar & pelajar yang penelitian tentang graph-nya hanya berhenti sampai pembahasan secara teori, jarang sekali yang mengaplikasikannya sampai ke aplikasi (minimal program). Nah post ini semoga bisa menjadi sumber motivasi untuk mengembangkan lebih lanjut dengan menunjukkan bahwa membuat aplikasi graph itu mudah dengan NetworkX di Python.

Several Graph Applications [various sources].

Menyiapkan Modul Python untuk Suatu Pelatihan?

Semenjak Data Science (DS) & Big Data (BD) ngetrend di dunia akademis & jagad digital (kalau disebut "dunia Maya" takutnya ada yang keselek 😄), berbagai pelatihan atau workshop menjamur di berbagai tempat. (Don't get me wrong, it's a good thing. Educating people is always a good thing). Biasanya pelatihan terkait DS/BD ini akan menggunakan bahasa pemrograman Python, R, atau Java.

Masing² bahasa pemrograman memiliki kelebihan & kekurangannya sendiri. Solusi terbaik tentu saja menggabungkan berbagai bahasa pemrograman tersebut dalam suatu sistem DS/BD yang terintegrasi. Tapi kita hanya manusia ... eh kok jadi drama gini ... Maksud saya tapi tentu saja tidak ideal jika suatu pelatihan menggunakan beberapa bahasa pemrograman sekaligus. Selain peserta & instrukturnya puyeng bin pusing, pelatihan-nya juga menjadi tidak fokus. Kalau disuruh memilih satu diantara ketiganya saya pribadi prefer Python. Alasannya sudah pernah dibahas di blog ini (Link1, Link2), namun singkatnya begini: Python relatif cepat, mudah dipelajari & gunakan, bisa buat IoT & Big Data, library data science-nya cukup lengkap, scalable, most popular (jadi kalau butuh bantuan banyak yang bisa menolong 😁), dan yang terpenting: gratis!!... (gratis is the best :D )

Namun seperti yang pernah disebutkan sebelumnya, tidak ada bahasa pemrograman yang sempurna, termasuk Python. Jika modul-modul Python yang terinstall di komputer kita tidak sinkron, maka program tidak akan berjalan dengan baik, atau bahkan tidak jalan sama sekali ... 😣 ... Kalau kasusnya di sebuah pelatihan, hal ini akan cukup merepotkan panitia & buat keringet dingin instrukturnya. Nah, post ini akan membahas bagaimana membuat script python yang akan memeriksa modul & menginstalnya jika diperlukan (online/offline) secara automatis, sehingga memudahkan panitia & nyenengke  peserta ... 😃 ...

Evaluasi Eksternal Clustering “Pairwise” F-ß-Score & NMI: Teori & Aplikasi

Tidak seperti model klasifikasi (supervised learning), evaluasi pada model clustering (unsupervised learning) jauh lebih menantang. Mengapa? Hal ini berawal dari definisi awal permasalahan pengelompokan (clustering) yang sebenarnya tidak well-definedditambah dengan tidak adanya nilai pembanding yang jelas seperti klasifikasi. Namun pada kasus tertentu, terdapat suatu nilai pengelompokan pembanding yang biasa disebut Ground Truth (GT)/gold standard. GT ini adalah pengetahuan sebelumnya (prior information kalau kata orang Bekasi :) ) yang dapat digunakan untuk mendapatkan hasil evaluasi clustering yang lebih terarah (tidak musti objective, malah seringnya subjective). Namun sayangnya menggunakan GT untuk evaluasi semi-supervised clustering tidak semudah pada kasus klasifikasi. Artikel ini akan membahas secara mendalam penggunaan GT, baik secara teori, maupun aplikasinya.

Text PreProcessing & Terms Distribution

Artikel ini merupakan lanjutan dari artikel sebelumnya tentang Crawling Data Twitter dengan Python. Akan tetapi apa yang dijelaskan di artikel ini dapat diterapkan di sembarang data text/dokumen, tidak harus data sosial media. Preprocessing text seperti stopword filtering & stemming, serta menghitung term distribution (frekuensi kata) dibahas menggunakan Python. Di tulisan selanjutnya kita akan coba melakukan analisa lanjut seperti clustering, centrality, community detection, visualisasi, dsb.

Cython: semudah Python & secepat Java, bahkan lebih

Beberapa waktu yang lalu saya menulis sebuah artikel yang membandingkan performa 7 bahasa pemrograman ketika memproses 3 operasi dasar: “if”,”for”, & “while”.  Beberapa bahasa pemrograman seperti Matlab, PHP, R, & Python memiliki keleluasaan antara sebuah interpreter dan compiler, bahkan diantara keduanya (JIT). Artikel kali ini akan memperkenalkan Cython (compiled Python) dan melihat peningkatan performanya dibandingkan versi murni Python, JIT, dan Java.