กราฟวิทยาศาสตร์ข้อมูลด้วย Python/NetworkX

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

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

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

แล้วนักพัฒนาจะใช้ประโยชน์จากวิทยาศาสตร์ข้อมูลกราฟได้อย่างไร? มาดูภาษาการเขียนโปรแกรมวิทยาศาสตร์ข้อมูลที่ใช้มากที่สุด: Python

เริ่มต้นกับกราฟ "ทฤษฎีกราฟ" ใน Python

นักพัฒนา Python มีไลบรารีข้อมูลกราฟหลายตัวที่พร้อมใช้งาน เช่น NetworkX, igraph, SNAP และเครื่องมือกราฟ ข้อดีและข้อเสีย พวกเขามีอินเทอร์เฟซที่คล้ายกันมากสำหรับการจัดการและประมวลผลโครงสร้างข้อมูลกราฟ Python

เราจะใช้ไลบรารี NetworkX ยอดนิยม ติดตั้งและใช้งานง่าย และสนับสนุนอัลกอริทึมการตรวจหาชุมชนที่เราจะใช้

การสร้างกราฟใหม่ด้วย NetworkX นั้นตรงไปตรงมา:

 import networkx as nx G = nx.Graph()

แต่ G ยังไม่ใช่กราฟมากนัก เนื่องจากไม่มีโหนดและขอบ

วิธีเพิ่มโหนดในกราฟ

เราสามารถเพิ่มโหนดให้กับเครือข่ายโดยผูกกับค่าส่งคืนของ Graph() ด้วย .add_node() (หรือ .add_nodes_from() สำหรับหลายโหนดในรายการ) เรายังสามารถเพิ่มคุณลักษณะหรือคุณลักษณะตามอำเภอใจให้กับโหนดโดยส่งพจนานุกรมเป็นพารามิเตอร์ ตามที่เราแสดงด้วย node 4 และ node 5 :

 G.add_node("node 1") G.add_nodes_from(["node 2", "node 3"]) G.add_nodes_from([("node 4", {"abc": 123}), ("node 5", {"abc": 0})]) print(G.nodes) print(G.nodes["node 4"]["abc"]) # accessed like a dictionary

สิ่งนี้จะส่งออก:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5'] 123

แต่ไม่มีขอบระหว่างโหนด พวกมันถูกแยกออก และชุดข้อมูลก็ไม่ได้ดีไปกว่าตารางธรรมดา

วิธีเพิ่มขอบให้กับกราฟ

คล้ายกับเทคนิคสำหรับโหนด เราสามารถใช้ .add_edge() กับชื่อสองโหนดเป็นพารามิเตอร์ (หรือ .add_edges_from() สำหรับหลายขอบในรายการ) และสามารถเลือกรวมพจนานุกรมของแอตทริบิวต์ได้:

 G.add_edge("node 1", "node 2") G.add_edge("node 1", "node 6") G.add_edges_from([("node 1", "node 3"), ("node 3", "node 4")]) G.add_edges_from([("node 1", "node 5", {"weight" : 3}), ("node 2", "node 4", {"weight" : 5})])

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

NetworkX แสดงรายการขอบทั้งหมดเมื่อใช้ G.edges แต่ไม่รวมแอตทริบิวต์ หากเราต้องการแอตทริบิวต์ edge เราสามารถใช้ G[node_name] เพื่อรับทุกสิ่งที่เชื่อมต่อกับโหนดหรือ G[node_name][connected_node_name] เพื่อรับแอตทริบิวต์ของ edge เฉพาะ:

 print(G.nodes) print(G.edges) print(G["node 1"]) print(G["node 1"]["node 5"])

สิ่งนี้จะส่งออก:

 ['node 1', 'node 2', 'node 3', 'node 4', 'node 5', 'node 6'] [('node 1', 'node 2'), ('node 1', 'node 6'), ('node 1', 'node 3'), ('node 1', 'node 5'), ('node 2', 'node 4'), ('node 3', 'node 4')] {'node 2': {}, 'node 6': {}, 'node 3': {}, 'node 5': {'weight': 3}} {'weight': 3}

แต่การอ่านกราฟแรกของเราด้วยวิธีนี้ไม่สามารถทำได้ โชคดีที่มีตัวแทนที่ดีกว่ามาก

วิธีสร้างรูปภาพจากกราฟ (และกราฟถ่วงน้ำหนัก)

การแสดงกราฟเป็นสิ่งสำคัญ: ช่วยให้เราเห็นความสัมพันธ์ระหว่างโหนดและโครงสร้างของเครือข่ายได้อย่างรวดเร็วและชัดเจน

เพียงโทรไปที่ nx.draw(G) อย่างรวดเร็ว:

มาทำให้ขอบที่มีน้ำหนักมากขึ้นให้หนาขึ้นตามลำดับผ่าน nx.draw() ของเรา:

 weights = [1 if G[u][v] == {} else G[u][v]['weight'] for u,v in G.edges()] nx.draw(G, width=weights)

เราได้กำหนดความหนาเริ่มต้นสำหรับขอบที่ไม่มีน้ำหนัก ดังที่เห็นในผลลัพธ์:

วิธีการและอัลกอริธึมกราฟของเรากำลังจะซับซ้อนมากขึ้น ดังนั้นขั้นตอนต่อไปคือการใช้ชุดข้อมูลที่รู้จักกันดี

กราฟวิทยาศาสตร์ข้อมูลโดยใช้ข้อมูลจากภาพยนตร์ Star Wars: Episode IV

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

หมายเหตุ: ชุดข้อมูลมาจาก Gabasova, E. (2016) สตาร์วอร์ส โซเชียลเน็ตเวิร์ก ดอย: https://doi.org/10.5281/zenodo.1411479.

อันดับแรก เราจะเห็นภาพข้อมูลด้วย nx.draw(G_starWars, with_labels = True) :

อักขระที่มักจะปรากฏพร้อมกัน เช่น R2-D2 และ C-3PO จะปรากฏติดกันอย่างใกล้ชิด ในทางตรงกันข้าม เราจะเห็นว่าดาร์ธ เวเดอร์ไม่แชร์ฉากกับโอเว่น

เค้าโครงการแสดงภาพ Python NetworkX

เหตุใดแต่ละโหนดจึงอยู่ที่ตำแหน่งที่อยู่ในกราฟก่อนหน้า

เป็นผลลัพธ์ของอัลกอริทึม spring_layout เริ่มต้น มันจำลองแรงของสปริง ดึงดูดโหนดที่เชื่อมต่อและขับไล่โหนดที่ไม่ได้เชื่อมต่อ วิธีนี้ช่วยเน้นโหนดที่เชื่อมต่ออย่างดีซึ่งอยู่ตรงกลาง

NetworkX มีเลย์เอาต์อื่นที่ใช้เกณฑ์ต่างกันเพื่อวางตำแหน่งโหนด เช่น circular_layout :

 pos = nx.circular_layout(G_starWars) nx.draw(G_starWars, pos=pos, with_labels = True)

ผลลัพธ์:

เลย์เอาต์นี้เป็นกลางในแง่ที่ว่าตำแหน่งของโหนดไม่ได้ขึ้นอยู่กับความสำคัญของมัน—โหนดทั้งหมดจะถูกแสดงอย่างเท่าเทียมกัน (เลย์เอาต์แบบวงกลมยังสามารถช่วยให้เห็นภาพ ส่วนประกอบที่เชื่อมต่อ แยกกัน — กราฟย่อยที่มีเส้นทางระหว่างสองโหนด—แต่ที่นี่ กราฟทั้งหมดเป็นองค์ประกอบที่เชื่อมต่อขนาดใหญ่เพียงองค์ประกอบเดียว)

เลย์เอาต์ทั้งสองที่เราเคยเห็นมีระดับของความยุ่งเหยิงของภาพ เนื่องจากขอบสามารถตัดขอบอื่นๆ ได้อย่างอิสระ แต่ Kamada-Kawai ซึ่งเป็นอัลกอริธึมที่บังคับทิศทางอื่น เช่น spring_layout วางตำแหน่งโหนดเพื่อลดพลังงานของระบบ

ซึ่งช่วยลดการข้ามขอบแต่ต้องแลกมาด้วยราคา: ช้ากว่าเลย์เอาต์อื่นๆ ดังนั้นจึงไม่แนะนำอย่างมากสำหรับกราฟที่มีโหนดจำนวนมาก

อันนี้มีฟังก์ชั่นการวาดเฉพาะ:

 nx.draw_kamada_kawai(G_starWars, with_labels = True)

ที่ให้ผลเป็นรูปร่างนี้แทน:

หากไม่มีการแทรกแซงเป็นพิเศษ อัลกอริธึมจะใส่อักขระหลัก (เช่น ลุค เลอา และ C-3PO) ไว้ตรงกลาง และอักขระที่เด่นน้อยกว่า (เช่น คามีและนายพลโดดอนน่า) อยู่ที่ชายแดน

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

การวิเคราะห์โหนด: องศาและเพจแรงก์

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

ตัวชี้วัดพื้นฐานอย่างหนึ่งสำหรับโหนดคือ ระดับ: จำนวนขอบของโหนด ระดับของโหนดของตัวละคร Star Wars จะวัดจำนวนตัวละครอื่นๆ ที่พวกเขาแบ่งปันฉากด้วย

ฟังก์ชัน degree() สามารถคำนวณระดับของอักขระหรือของเครือข่ายทั้งหมดได้:

 print(G_starWars.degree["LUKE"]) print(G_starWars.degree)

ผลลัพธ์ของทั้งสองคำสั่ง:

 15 [('R2-D2', 9), ('CHEWBACCA', 6), ('C-3PO', 10), ('LUKE', 15), ('DARTH VADER', 4), ('CAMIE', 2), ('BIGGS', 8), ('LEIA', 12), ('BERU', 5), ('OWEN', 4), ('OBI-WAN', 7), ('MOTTI', 3), ('TARKIN', 3), ('HAN', 6), ('DODONNA', 3), ('GOLD LEADER', 5), ('WEDGE', 5), ('RED LEADER', 7), ('RED TEN', 2)]

การเรียงลำดับโหนดจากสูงสุดไปต่ำสุดตามระดับสามารถทำได้ด้วยรหัสบรรทัดเดียว:

 print(sorted(G_starWars.degree, key=lambda x: x[1], reverse=True))

ผลลัพธ์:

 [('LUKE', 15), ('LEIA', 12), ('C-3PO', 10), ('R2-D2', 9), ('BIGGS', 8), ('OBI-WAN', 7), ('RED LEADER', 7), ('CHEWBACCA', 6), ('HAN', 6), ('BERU', 5), ('GOLD LEADER', 5), ('WEDGE', 5), ('DARTH VADER', 4), ('OWEN', 4), ('MOTTI', 3), ('TARKIN', 3), ('DODONNA', 3), ('CAMIE', 2), ('RED TEN', 2)]

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

ตัวชี้วัด PageRank สามารถตีความได้ว่าเป็นเอเจนต์ที่สุ่มย้ายจากโหนดหนึ่งไปยังอีกโหนดหนึ่ง โหนดที่เชื่อมต่อได้ดีกว่าจะมีเส้นทางผ่านเข้ามามากกว่า ดังนั้นตัวแทนจึงมีแนวโน้มที่จะเข้าชมบ่อยขึ้น

โหนดดังกล่าวจะมี PageRank ที่สูงกว่า ซึ่งเราสามารถคำนวณได้ด้วยไลบรารี NetworkX:

 pageranks = nx.pagerank(G_starWars) # A dictionary print(pageranks["LUKE"]) print(sorted(pageranks, key=lambda x: x[1], reverse=True))

พิมพ์อันดับของลุคและตัวละครของเราที่จัดเรียงตามอันดับ:

 0.12100659993223405 ['OWEN', 'LUKE', 'MOTTI', 'DODONNA', 'GOLD LEADER', 'BIGGS', 'CHEWBACCA', 'LEIA', 'BERU', 'WEDGE', 'RED LEADER', 'RED TEN', 'OBI-WAN', 'DARTH VADER', 'CAMIE', 'TARKIN', 'HAN', 'R2-D2', 'C-3PO']

โอเว่นเป็นตัวละครที่มีเพจแรงก์สูงสุด แซงหน้าลุคซึ่งมีระดับสูงสุด บทวิเคราะห์: แม้ว่าโอเว่นจะไม่ใช่ตัวละครที่แชร์ฉากกับตัวละครอื่นๆ มากที่สุด แต่เขาเป็นตัวละครที่แชร์ฉากกับตัวละครสำคัญๆ มากมาย เช่น ลุคเอง, R2-D2 และ C-3PO

ในทางตรงกันข้าม C-3PO ซึ่งเป็นอักขระที่มีระดับสูงสุดเป็นอันดับสามคืออักขระที่มี PageRank ต่ำที่สุด แม้ว่า C-3PO จะมีสายสัมพันธ์มากมาย แต่ก็มีหลายอย่างที่มีอักขระที่ไม่สำคัญ

ประเด็นสำคัญ: การใช้เมตริกหลายรายการสามารถให้ข้อมูลเชิงลึกที่ลึกซึ้งยิ่งขึ้นเกี่ยวกับลักษณะต่างๆ ของโหนดของกราฟ

อัลกอริทึมการตรวจจับชุมชน

เมื่อวิเคราะห์เครือข่าย อาจเป็นสิ่งสำคัญที่จะแยก ชุมชน : กลุ่มของโหนดที่เชื่อมต่อกันอย่างสูง แต่เชื่อมต่อกับโหนดภายนอกชุมชนเพียงเล็กน้อย

มีหลายอัลกอริทึมสำหรับสิ่งนี้ ส่วนใหญ่พบได้ในอัลกอริธึมการเรียนรู้ของเครื่องที่ไม่ได้รับการดูแลเนื่องจากกำหนดป้ายกำกับให้กับโหนดโดยไม่จำเป็นต้องติดป้ายกำกับไว้ก่อนหน้านี้

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

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

ด้วยไลบรารี NetworkX การรันอัลกอริธึมนี้ใช้ Python เพียงสามบรรทัด:

 from networkx.algorithms.community.label_propagation import label_propagation_communities communities = label_propagation_communities(G_starWars) print([community for community in communities])

ผลลัพธ์:

 [{'R2-D2', 'CAMIE', 'RED TEN', 'RED LEADER', 'OBI-WAN', 'DODONNA', 'LEIA', 'WEDGE', 'HAN', 'OWEN', 'CHEWBACCA', 'GOLD LEADER', 'LUKE', 'BIGGS', 'C-3PO', 'BERU'}, {'DARTH VADER', 'TARKIN', 'MOTTI'}]

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

ข้อมูลเชิงลึกที่ชาญฉลาดโดยใช้วิทยาศาสตร์ข้อมูลกราฟใน Python

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

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

การอ่านที่แนะนำในวิทยาศาสตร์ข้อมูลกราฟ

อัลกอริทึมการตรวจจับชุมชน
Zhao Yang, Rene Algesheimer และ Claudio Tessone “การวิเคราะห์เปรียบเทียบอัลกอริธึมการตรวจจับชุมชนบนเครือข่ายประดิษฐ์” รายงานทางวิทยาศาสตร์ ฉบับที่ 6 30750 (2016).

กราฟการเรียนรู้เชิงลึก
โธมัส คิฟ “กราฟ Convolutional Network” 30 กันยายน 2559

การประยุกต์ใช้วิทยาศาสตร์ข้อมูลกราฟ
อัลบานีส, เฟเดริโก, เลอันโดร ลอมบาร์ดี, เอสเตบัน ฟอยเออร์สไตน์ และปาโบล บาเลนซูเอลา “การทำนายการเปลี่ยนแปลงของแต่ละคนโดยใช้ Text Mining และ Graph Machine Learning บน Twitter” (24 สิงหาคม 2020): arXiv:2008.10749 [cs.SI].

โคเฮน, เอลิเออร์. “มีตติ้ง PyData Tel Aviv: Node2vec” ยูทูบ. 22 พฤศจิกายน 2018 วิดีโอ 21:09 น. https://www.youtube.com/watch?v=828rZgV9t1g.