Python, Gráf, Programozás (fél éves)

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:

• referenciák rendbe rakása
• marógép sebességének állítása
• algoritmikus nyuszik
• Linux operációs rendszer

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