ตอนก่อนหน้า: บันทึก training data science EP 8: Ensemble – Avenger's ensemble

น่าจะมีสักครั้งแหละ ที่ปัญหาของเรามันมาเป็นแผนที่จราจรเลย ตัวอย่างเช่น ความสัมพันธ์ของชาว Facebook ที่มันจะมีทั้งเพื่อนเรา เพื่อนของเพื่อนเรา เพื่อนของเพื่อนไปอีกสามชั้นของเรา โยงเส้นกันให้วุ่นไปหมด จะทำยังไงดีให้ปัญหายังกะแผนที่จราจรแบบนี้สามารถแก้ไขได้นะ

อย่ากระนั้นเลย ให้ Library ของ Python ตัวนี้ช่วยงานเราดีกว่า

NetworkX

Library ตัวนี้ช่วยให้เราทำ visualize data เป็นแผนที่ง่ายๆ ได้ฮะ

เริ่มต้น สมมติเรามีไฟล์ตัวนึง อยู่ในรูปแบบข้างล่างนี้

เริ่มต้น initiate

เราสามารถสร้างแผนที่ได้สองวิธี นั่นคือ networkx.read_edgelist() เพื่ออ่านไฟล์ หรือสร้างแผนที่เปล่าๆ ด้วยคำสั่ง networkx.Graph()

เมื่อใส่ข้อมูลเข้าไปแล้ว ใช้คำสั่ง networkx.draw() เพื่อสร้างแผนที่มาดูได้เลยฮะ

เอ๊ะ ถ้ามีจุด (node) ใหม่ขึ้นมาจะทำยังไง ก็ใช้คำสั่ง .add_node() เพื่อเพิ่มจุดใหม่และโยงเข้ากับแผนที่ด้วยคำสั่ง .add_edge() เพื่อเพิ่มเส้น (edge) ฮะ

ดูข้อมูลเบื้องต้น

ใช้ networkx.info() เพื่อดูข้อมูลเบื้องต้น คือ จำนวน node, จำนวน edge และ average degree ซึ่งเป็นค่าเฉลี่ยของจำนวน edge ที่เชื่อมกับแต่ละ node

networkx.connected_components(): แสดงรายการ node ของ graph

networkx.subgraph(): แสดงรายการแผนที่ย่อย (subgraph) โดยระบุ node ที่ต้องการ

Density

networkx.density()

คำนวณค่าความหนาแน่นจากสมการดังนี้ฮะ

  • ถ้าเป็นแผนที่ไม่มีทิศทาง (Undirected graph), \(d = 2 \cdot \frac{edge}{node \cdot (node - 1)}\)
    ซึ่งตัวอย่างแผนที่ข้างบนเนี่ย คำนวณได้ \(d = 2 \cdot \frac{19}{12 \cdot (12-1)} = 2 \cdot 0.14\overline{39} = 0.2\overline{87}\).
  • ถ้าเป็นแผนที่มีทิศทาง (Directed graph), \(d = \frac{edge}{node \cdot (node - 1)}\).

Clustering

คำนวณค่า clustering หรือความหนาแน่นของแต่ละ node ฮะ สามารถหาได้ว่าแต่ละ node เนี่ยมันมี node แวดล้อมกัน แล้ว node แวดล้อมมันเชื่อมต่อกันเป็นอัตราส่วนเท่าไหร่ฮะ โดยที่ 0 คือ ไม่มีการเชื่อมโยงระหว่าง node แวดล้อมเลย ไปจนถึง 1 ก็คือ node แวดล้อมมันเชื่อมต่อถึงกันหมด โดยหาค่า (\(C_i\)) ได้จากนับจำนวน edge ระหว่าง node แวดล้อม หารด้วยผลคูณของจำนวน node แวดล้อมกับจำนวน node แวดล้อม -1
ถ้าเป็นแผนที่ไม่มีทิศทาง ก็เอา 2 ไปคูณฮะ

ตัวอย่างเช่น \(C_A = \frac{2 \cdot e_{BD}}{(node_B + node_C + node_D)(node_B + node_C + node_D - 1)} = \frac{2 \cdot 1}{3 \cdot 2} = \frac{1}{3}\)

และอีกตัวอย่าง \(C_L = \frac{2 \cdot 0}{node_L \cdot (node_L - 1)} = 0\)

Reference: https://en.wikipedia.org/wiki/Clustering_coefficient

networkx.clustering()
networkx.average_clustering()

คำนวณค่า Average clustering หรือค่าเฉลี่ยของความหนาแน่น จากสมการ \(\displaystyle \overline{C} = \frac{1}{n} \sum_{i=1}^{n}C_{i}\).

Shortest paths

networkx.shortest_path_length()

คำนวณค่าระยะทางที่สั้นที่สุดระหว่าง node ฮะ ดูตัวอย่างบรรทัดแรก node A สามารถไปยัง node I ได้สั้นที่สุดคือ ผ่าน 3 edge ฮะ

networkx.shortest_path()

หา node ที่ผ่านสำหรับการหาเส้นทางที่สั้นที่สุดฮะ

networkx.average_shortest_path_length()

คำนวณค่าเฉลี่ยเส้นทางสั้นที่สุดระหว่าง node ที่เราได้จาก networkx.shortest_path_length()ข้างบนฮะ อ้างอิงสมการ \(\displaystyle \alpha = \sum_{s,t \in V}\frac{d(s,t)}{n(n-1)}\)

Centrality

ค่า Centrality เป็นค่าแสดงความเป็นศูนย์กลางของแต่ละ node ในแผนที่ฮะ มีค่านี้ในหลายๆ เทอมเลย เช่น

Degree Centrality

networkx.degree_centrality()

ค่า Degree Centrality เป็นอัตราส่วนระหว่าง degree ของแต่ละ node กับ degree ของ node แวดล้อมและตัวเองฮะ ยิ่งมีค่าสูงแปลว่า node นี้มีเพื่อนเยอะ สามารถไปหา node อื่นได้เยอะนั่นเองฮะ

จากตัวอย่าง node A เนี่ยมันมี degree เป็น 3 และ node แวดล้อมของ node A มีค่าเท่ากับ degree ของ node B, C, และ D รวมกันบวกกับตัวเอง ซึ่งเท่ากับ \(3 + 2 + 3 + 3 = 8\) ดังนั้น ค่า Degree Centrality ของ node A จะเท่ากับ \(\frac{3}{11}= 0.\overline{27}\).

Closeness Centrality

networkx.closeness_centrality()

Closeness Centrality บอกได้ว่า node นี้อยู่ใกล้จุดศูนย์กลางของแผนที่มากแค่ไหน ยิ่งสูงแปลว่ายิ่งอยู่ใกล้ศูนย์กลางมาก ก็มีโอกาสเป็นทางผ่านให้กับเส้นทางในแผนที่มากนั่นเองฮะ คำนวณจากจำนวน node ทั้งหมดในแผนที่ที่มีตัวเองอยู่ – 1 (ไม่นับตัวเอง) หารด้วยผลรวมของ shortest path ระหว่าง node ในแผนที่ ซึ่งดูได้จาก networkx.shortest_path_length() ข้างบนน่ะแหละฮะ

ตัวอย่าง node B บ้าง node B อยู่ในแผนที่ที่มีทั้งหมด 12 node และ node B มี shortest path ไปยังแต่ละ node รวมกันเป็น \(0 + 1 + 1 + 2 + 2 + 3 + 3 + 3 + 3 + 4 + 4 + 5 = 31\) และเราก็ได้ค่า Closeness Centrality ของ node B เป็น \(\frac{12-1}{31} = 0.3548\) นั่นเองฮะ

Betweenness Centrality

networkx.betweenness_centrality()

Betweeness Centrality ใช้วัดว่า node นี้มีความสำคัญที่จะเป็นตัวกลางการเชื่อมต่อของทุกๆ node ในแผนที่นี้ ยิ่งมีค่าสูง แปลว่า มีความสำคัญมากที่จะเป็นตัวกลางของแผนที่ฮะ มันคำนวณอัตราส่วนระหว่าง shortest path ที่มี node ที่ต้องการกับ shortest path ทั้งหมดที่เป็นไปได้ของแต่ละคู่ node โดยที่คู่ node นั้นไม่ใช่ node ที่ต้องการฮะ จากนั้นก็หาผลรวมและหารอีกทีด้วยความเป็นไปได้ของคู่ node นั่นคือ \((n-1)(n-2)\) สำหรับ directed graph หรือ \(\frac{(n-1)(n-2)}{2}\) สำหรับ undirected graph

ตัวอย่าง node C นะฮะ เริ่มต้นจากหา shortest path ทั้งหมดก่อน

จากนั้นก็หาว่า ในแต่ละคู่ node มี shortest path ไหนบ้างที่มี node ที่เราต้องการ หารด้วยจำนวน shortest path ทั้งหมดของคู่ node นั้นๆ และสุดท้ายก็หาผลรวม ซึ่ง node C ก็ได้ค่ามาเป็น \(6.2\) นั่นเองฮะ

ท้ายสุดก็เอาเข้าสมการที่ว่า ก็จะได้เป็น \(\displaystyle g(v) = \sum_{s \ne v \ne t}\frac{\sigma_{st}(v)}{\sigma_{st}} = \frac{2(6.2)}{(12-1)(12-2)} = \frac{2(6.2)}{110} = 0.11\overline{27}\) เราต้องเอา 2 ไปคูณเพราะมันเป็น undirected graph.

และ networkx.betweenness_centrality() ก็จะคำนวณให้ทุก node ในแผนที่ดังรูปข้างล่างนี่แหละฮะ

Reference:

Eigenvector Centrality

networkx.eigenvector_centrality()

Eigenvector Centrality ใช้การคำนวณ Eigenvector จากการแปลง node ในแผนที่เป็น matrix ฮะ ผลลัพท์ที่ได้จะบอกว่า node นี้มีความเป็น “hub” หรือความเป็นจุดศูนย์รวมของ node แวดล้อม มากน้อยแค่ไหน ยิ่งมีค่าสูง แปลว่ามีความเป็น “hub” สูงตามไปด้วยฮะ

จากตัวอย่างข้างล่าง เราจะพบว่า node F มีค่านี้สูงที่สุดฮะ รองลงมาคือ node E

Reference:

Page rank

networkx.pagerank()

ฟังก์ชันนี้ มีพื้นฐานมาจาก algorithm การจัดลำดับ webpage ฮะ มันใช้บอก “ความสำคัญ” ของแต่ละ node ฮะ โดยคำนวณจาก Eigenvector ข้างบนนั่นล่ะฮะ

Clique

Clique คือ subgraph ที่เล็กที่สุดของแผนที่ฮะ หรือพูดอีกอย่างคือกลุ่ม node ที่เป็นเพื่อนบ้านกันที่เล็กที่สุดที่เราสามารถหาเจอในแผนที่นั้นๆ ได้ฮะ

networkx.clique.find_cliques()

ฟังก์ชันนี้จะหา clique ทั้งหมดที่พบในแผนที่

networkx.clique.cliques_containing_node()

หา clique ทั้งหมดที่มี node ที่เราต้องการ

Numpy and Pandas

networkx.to_numpy_matrix()

เราจะได้ matrix หนึ่งตัวที่เป็นความสัมพันธ์ของ node ทุก node ในแผนที่ โดยค่า 0 หรือ 1 คือ ค่าน้ำหนัก (weight) ของ edge ระหว่าง node คู่นั้นๆ ที่เป็น 1 เพราะแผนที่ของเราไม่ได้กำหนดน้ำหนักไว้ฮะ

networkx.to_pandas_adjacency()

คล้ายๆ กับฟังก์ชันข้างบนฮะ แต่ได้ผลลัพท์เป็น DataFrame แทนฮะ

networkx.to_pandas_edgelist()

อันนี้จะได้เป็น DataFrame ที่มาเป็นคู่ node แทนฮะ

ลองวิเคราะห์ด้วย Matplotlib

มา plot graph เพื่อดูการกระจายของจำนวน degree ฮะ

import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline
# create dict of degree of each node
degree = dict(sample.degree)
# transform to Series 
degree_series = pd.Series(index=degree.keys(), data=list(degree.values()))
# create Series of unique values and counts
degree_series_count = degree_series.value_counts()
degree_series_count
# plotting bar graph
plt.bar(degree_series_count.index, degree_series_count)
plt.xlabel("Degree")
plt.ylabel("Node counts")

เมื่อเล่นจนพอใจแล้วก็สามารถเขียนลงไฟล์ด้วยคำสั่ง networkx.write_edgelist() ฮะ

ก็ถือว่าเป็น library ที่จัดการข้อมูลแบบแผนที่ได้ดีทีเดียวนะฮะ

เราสามารถใช้เจ้านี่ไปวิเคราะห์ความสัมพันธ์ได้หลากหลายแบบมากๆ เลยฮะ ซึ่งเท่าที่ผมดู มักจะเป็นพวกโจทย์ที่เกี่ยวกับสังคมสิ่งมีชีวิต เช่น วิเคราะห์ความสำคัญของนักฟุตบอลแต่ละคนของแต่ละสโมสร เป็นต้น

แล้วเจอกัน เมื่อชาติต้องการฮะ

บาย

ตอนต่อไป: บันทึก training data science EP 10: Cluster – เชื่อมก้อนให้เป็นกลุ่ม