Gergő Balogh, PhD.

Researcher and Software Engineer

Python, Gráf, Programozás (4 órás)

középiskola bármelyik osztály

Gráf alapú adattárolás és programozási alapismeretek
Az szoftverfejlesztés során fontos készség az elvont adatstruktúrák megértése, tervezése és kezelése. Az egyik ilyen alapvető adatstruktúra a gráf, melyet számtalan rendszer használ információ rövid vagy hosszútávú tárolására és az entitások közötti kapcsolatok jelölésére. A szakkör során a tanulók megismerkedhetnek a gráf alapú adatreprezentáció alapjaival. Az elméleti ismeretket gyakorlati példák során szilárdítjuk meg, melyhez az ismert és ipari környezetben is gyakran használt Neo4J gráf alapú adatbázis rendszert használjuk. A rendszer látványos és könnyen érthető grafikus felületén keresztül térképezhetjük fel az adatbázisok tartalmát és szerkezetét. A szakkör célja, hogy a fiatalok a saját világukból és életükből vett problémák megoldásán keresztül ismerjék meg a fenn említett technológiákat és eszközöket.

1. foglalkozás

Mit csinál egy informatikus (szoftverfejlesztő)?

(15 perc)
A tanulók saját tapasztalatai alpján felsoroljuk és megismerjük az informatika szakterületeit.

  • folyamat tervezés
  • adatszerkezet tervezés
  • fejlesztés (kódolás)
  • tesztelés
  • hibajavítás

Mi az a gráf?

(30 perc)
Gráfelméleti alapfogalmak bevezetése.

  • gráf definíció: pontok és élek
  • kapcsolatok leírása gráfként
  • irányítás
  • él-súlyok
  • csomópont-tulajdonságok
  • él-tulajdonságok

Szünet

(10 perc)

Bevezetés a gráf adatbázisok világába

(20 perc)
Neo4J gráf adatbázis szerkezete és a Cypher lekérdező nyelv. Üres adatbázis létrehozása és feltöltése egy példa adatbázison keresztül.

  • Neo4J gráf modell
  • Cypher szintaxis
    • Példa
      MATCH (m:Movie)<-[:RATED]-(u:User) //Search for an existing graph pattern
WHERE m.title CONTAINS "Matrix" //Filter matching paths to only those matching a predicate
WITH m.title AS movie, COUNT(*) AS reviews //Count number of paths matched for each movie
RETURN movie, reviews //Specify columns to be returned by the statement
ORDER BY reviews DESC //Order by number of reviews, in descending order
LIMIT 5; //Only return first five records
  • minta illesztés
  • változók
  • feltételek
  • rendezés
  • limitek
  • utasítások: paraméterek és visszatérési érték
  • összegző függvények

Gráfadatbázisok a gyakrolatban

(40 perc)
Egy filmajánló rendszer megvalósítása IMDB alapján, egy példa adatbázison keresztül.
Online angol nyelvű oktató anyag elérhető a Neo4J Sandboxban

Keressünk egy példa filmet

match (m:Movie) return m.title

Érdekes filmek lekérdezése felhasználónkként

Ki szeretti még a Crimson Tide-ot?

match (liked:Movie {title: "Crimson Tide"})<-[:RATED]-(user:User)
return *

Milyen más filmeket szeret aki szereti a Crimson Tide-ot?

match (liked:Movie {title: "Crimson Tide"})<-[:RATED]-(user:User)
with liked, user limit 5
match (user)-[:RATED]->(other:Movie)
return * limit 35

Melyik filmet nézzem ha szeretem a Crimson Tide-ot?

match (liked:Movie {title: "Crimson Tide"})<-[:RATED]-(user:User)-[:RATED]->(other:Movie)
return other.title as recommendation, collect(user.name) as usersWhoAlsoWatched, liked.title
limit 10

match (liked:Movie {title: "Crimson Tide"})<-[:RATED]-(user:User)-[:RATED]->(other:Movie)
return other.title as recommendation, count(user) as similarity, liked.title as liked
order by similarity desc limit 10

Hasonló műfajú filmek keresése

halmazelméleti alapok

Jaccard-féle hasonlóság fogalma és kiszámítása

Milyen műfajokba sorolták be az Inception-t?

match (liked:Movie {title: "Inception"})-[:IN_GENRE]->(genre:Genre)
return liked, genre limit 20

Közös műfajok megkeresése

match (liked:Movie {title: "Inception"})-[:IN_GENRE]->(genre:Genre)<-[:IN_GENRE]-(other:Movie)
return liked.title, other.title, collect(genre.name) as intersection limit 20

Melyek az Inception műfajai

match (liked:Movie {title: "Inception"})-[:IN_GENRE]->(genre:Genre)<-[:IN_GENRE]-(other:Movie)
with liked, other, collect(genre.name) as intersection
match (liked)-[:IN_GENRE]->(likedGenre:Genre)
return liked.title, other.title, collect(likedGenre.name) as likedGenres, intersection

A műfajok uniója

match (liked:Movie {title: "Inception"})-[:IN_GENRE]->(genre:Genre)<-[:IN_GENRE]-(other:Movie)
with liked, other, collect(genre.name) as intersection
match (liked)-[:IN_GENRE]->(likedGenre:Genre)
with liked, other, collect(likedGenre.name) as likedGenres, intersection
match (other)-[:IN_GENRE]->(otherGenre:Genre)
with liked.title as liked, other.title as other, likedGenres, intersection, collect(otherGenre.name) as otherGenres
return liked, other, likedGenres, otherGenres, intersection, likedGenres+filter(genre in otherGenres where not genre in likedGenres) as both

Jaccard kiszámítása

match (liked:Movie {title: "Inception"})-[:IN_GENRE]->(genre:Genre)<-[:IN_GENRE]-(other:Movie)
with liked, other, collect(genre.name) as intersection
match (liked)-[:IN_GENRE]->(likedGenre:Genre)
with liked, other, collect(likedGenre.name) as likedGenres, intersection
match (other)-[:IN_GENRE]->(otherGenre:Genre)
with liked.title as liked, other.title as other, likedGenres, intersection, collect(otherGenre.name) as otherGenres
with liked, other, likedGenres, otherGenres, intersection, likedGenres+filter(genre in otherGenres where not genre in likedGenres) as both
return liked, other, intersection, both, (size(intersection)*1.0)/(size(both)*1.0) as jaccard limit 10

Melyik hasonló műfajú filmet nézzem meg?

match (liked:Movie {title: "Inception"})-[:IN_GENRE]->(genre:Genre)<-[:IN_GENRE]-(other:Movie)
with liked, other, collect(genre.name) as intersection
match (liked)-[:IN_GENRE]->(likedGenre:Genre)
with liked, other, collect(likedGenre.name) as likedGenres, intersection
match (other)-[:IN_GENRE]->(otherGenre:Genre)
with liked.title as liked, other.title as other, likedGenres, intersection, collect(otherGenre.name) as otherGenres
with liked, other, likedGenres, otherGenres, intersection, likedGenres+filter(genre in otherGenres where not genre in likedGenres) as both
return liked, other, intersection, both, (size(intersection)*1.0)/(size(both)*1.0) as jaccard
order by jaccard desc limit 10

2. foglalkozás

Függőségek

easy_install colorama
easy_install neo4j-driver

Mi az a szkript nyelv?

Python alapok

Példák

Eddig elkészült program

Szépen formázott kiiratás és beolvasás

Parancssorban nézzük át hogyan működnek az egyes részek.

  1. kiíratás/beolvasás
  2. string műveletek
  3. csomag behúzása, színezés

info, warning, error, question típusú üzenetek

[i] this is an info

[w] I warn you something

[!] There is some error!

[?] Can I ask a question?
[:]  


import pdb

def annotated(text, icon=''):
  return '[%s] %s' % (icon, text)

def info(text):
  print(annotated(text, icon='i'))

def warning(text):
  print(annotated(text, icon='w'))

def error(text):
  print(annotated(text, icon='!'))

def question(text):
  print(annotated(text, icon='?'))
  print(annotated('', icon=':'), end='')
  return input()

if __name__ == '__main__':
  pdb.set_trace()

üzenetek szinezése colorama modullal


import pdb
import colorama

colorama.init()

def annotated(text, icon=''):
  return '[%s] %s' % (icon, text)

def info(text):
  print(annotated(colorama.Fore.CYAN + text + colorama.Fore.RESET, icon='i'))

def warning(text):
  print(annotated(colorama.Fore.YELLOW + text + colorama.Fore.RESET, icon='w'))

def error(text):
  print(annotated(colorama.Fore.RED + text + colorama.Fore.RESET, icon='!'))

def question(text):
  print(annotated(colorama.Fore.GREEN + text + colorama.Fore.RESET, icon='?'))
  print(annotated('', icon=':'), end='')
  return input()

if __name__ == '__main__':
  pdb.set_trace()

Filmajánló rendszer megvalósítása

Korábbi Cypher alapú kód felhasználás

match (liked:Movie {title: "Inception"})-[:IN_GENRE]->(genre:Genre)<-[:IN_GENRE]-(other:Movie)
with liked, other, collect(genre.name) as intersection
match (liked)-[:IN_GENRE]->(likedGenre:Genre)
with liked, other, collect(likedGenre.name) as likedGenres, intersection
match (other)-[:IN_GENRE]->(otherGenre:Genre)
with liked.title as liked, other.title as other, likedGenres, intersection, collect(otherGenre.name) as otherGenres
with liked, other, likedGenres, otherGenres, intersection, likedGenres+filter(genre in otherGenres where not genre in likedGenres) as both
return liked, other, intersection, both, (size(intersection)*1.0)/(size(both)*1.0) as jaccard
order by jaccard desc limit 10

Beégetett ajánlás megvalósítása

Mellyek az Inception műfajai?


def get_liked_genre():
  query = '''
  match (liked:Movie {title: "Inception"})-[:IN_GENRE]->(likedGenre:Genre)
  return likedGenre.name as name
  '''
  names = []
  for record in session.run(query):
    names.append(record['name'])
  return names

Keressük ki a filmek műfajait!


def get_movies():
  query = '''
  match (m:Movie)
  return m.title as title
  '''
  titles = []
  for record in session.run(query):
    titles.append(record['title'])
  return titles

def get_genre_of(title):
  query = '''
  match (liked:Movie {title: $title})-[:IN_GENRE]->(likedGenre:Genre)
  return likedGenre.name as name
  '''
  names = []
  for record in session.run(query, parameters={'title': title}):
    names.append(record['name'])
  return names

Refactoring - egyszerűsítsük a kódot


def getAll(query, property, parameters={}):
  values = []
  for record in session.run(query, parameters=parameters):
    values.append(record[property])
  return values

def get_liked_genre():
  return get_genre_of('Inception')

def get_movies():
  query = '''
  match (m:Movie)
  return m.title as title
  '''
  return getAll(query, 'title')

def get_genre_of(title):
  query = '''
  match (liked:Movie {title: $title})-[:IN_GENRE]->(likedGenre:Genre)
  return likedGenre.name as name
  '''
  return getAll(query, 'name', parameters={'title': title})

Hasonlóság kiszámítása


def jaccard():
  likedGenres = set(get_liked_genre())
  similarMovies = []
  for title in get_movies()[:10]:
    otherGenres = set(get_genre_of(title))
    intersection = likedGenres & otherGenres
    union = likedGenres | otherGenres
    similarity = len(intersection) / len(union)
    entry = (title, similarity)
    similarMovies.append(entry)
  return similarMovies

Optimalizálás - gyorsítsuk fel a kódot


def jaccard_slow():
  likedGenres = set(get_liked_genre())
  similarMovies = []
  for title in get_movies()[:50]:
    otherGenres = set(get_genre_of(title))
    intersection = likedGenres & otherGenres
    union = likedGenres | otherGenres
    similarity = len(intersection) / len(union)
    entry = (title, similarity)
    info("similarity of %s is %f" % entry)
    similarMovies.append(entry)
  return similarMovies

def jaccard():
  similarMovies = []
  for db_entry in list(get_sets())[:50]:
    likedGenres = set(db_entry['likedGenres'])
    otherGenres = set(db_entry['otherGenres'])
    otherTitle = db_entry['other']
    intersection = likedGenres & otherGenres
    union = likedGenres | otherGenres
    similarity = len(intersection) / len(union)
    item = (otherTitle, similarity)
    info("similarity of %s is %f" % item)
    similarMovies.append(item)
  return similarMovies

Melyik filmet nézzem legközelebb?


def jaccard():
  similarMovies = []
  for db_entry in get_sets():
    likedGenres = set(db_entry['likedGenres'])
    otherGenres = set(db_entry['otherGenres'])
    otherTitle = db_entry['other']
    intersection = likedGenres & otherGenres
    union = likedGenres | otherGenres
    similarity = len(intersection) / len(union)
    item = (otherTitle, similarity)
    #info("similarity of %s is %f" % item)
    similarMovies.append(item)
  return similarMovies

def recommend():
  similarMovies = jaccard()
  similarMovies.sort(key=lambda entry: entry[1], reverse=True)
  return similarMovies[:10]

if __name__ == '__main__':
  info("The top 10 movies you should watch:")
  for i, entry in enumerate(recommend()):
    info("   %dth %s" % (i+1, entry[0]))

Paraméteres ajánlás megvalósítása