Gergő Balogh, PhD.

Researcher and Software Engineer

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 gyakorlat során bepillantást nyerünk a grafikus felületen túlmutató az ipari felhasználáshoz közeli hozzáférést biztosító programozási felületekhez is. Példaként a közismert szkriptnyelvet fogjuk használni, a Python 3-at. Ez az elegánsan és tisztán strukturált nyelv megkönnyíti a programozással való ismerkedést, miközben valós életben is használható szaktudást ad. 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.

Függőségek

easy_install colorama
easy_install neo4j-driver

Mit csinál egy informatikus (szoftverfejlesztő)?

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

Egy szoftverfejlesztő mindig elég lusta ahoz, hogy napokat töltsön egy szoftver elkészítésével ami megold egy 10 perces feladatot helyette.

A szoftverfejlesztés nem csak egy munka:

A szofverfejlesztés részei:

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

Mi az a szkript nyelv?

Python alapok: parancssoron keresztül néhány példa a szintaxisról

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()

Mi az a gráf?

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

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

Neo4J gráf adatbázis szerkezete és a Cypher lekérdező nyelv.

  • Neo4J gráf modell
  • Cypher szintaxis
    Keresés és minta illesztés
    MATCH (m:Movie)<-[:RATED]-(u:User)
    Keresés és minta illesztés
    MATCH (m:Movie)<-[:RATED]-(u:User)
    Szűrés feltétel alapján
    WHERE m.title CONTAINS "Matrix"
    Adatok átadása
    WITH m.title AS movie, COUNT(*) AS reviews
    Eredmények visszadása
    RETURN movie, reviews
    Rendezés
    ORDER BY reviews DESC
    Limitálás
    LIMIT 5
    • Komplex 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
    • Gyakorló feladat
      1. Listázzuk ki hogy melyik felhasználó melyik filmet hányasra osztályozta.
      2. Listázzuk ki hogy ki hányasra rangsorolta az Matrix filmeket.
      3. Számoljuk össze hogy hány szavazat érkezett filmenként.
      4. Rendezzük sorba a filmeket szavazatok száma szerint.
      5. Csak a legtöbb szavazatot kapott filmet íratsuk is.
      6. Nevezzük el a visszadott mezőket.
      </li> </ul> </li>
    • 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
      • </ul> ## Gráfadatbázisok a gyakrolatban

      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
      ## Műfaj alapú filmajánló program készítése Python-ban

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

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

      Python megvalósítás:

      
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

      
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
      ## Halmazelméleti alapok

      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 csak az Inception és a másik film 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)
with liked, other, collect(likedGenre.name) as likedGenres, intersection
match (other)-[:IN_GENRE]->(otherGenre:Genre)
return liked.title as liked, other.title as other, likedGenres, intersection, collect(otherGenre.name) as otherGenres
      ## 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

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

      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

      Python megvalósítás:

      
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 get_sets():
	query = '''
	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)
	return liked.title as liked, other.title as other, likedGenres, intersection, collect(otherGenre.name) as otherGenres

	'''
	return session.run(query)

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 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

      
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]))