# Assignment 1
Autor: Dimitri Muralt


```python
import sys
import nltk
import math
import itertools
import scipy.stats
import numpy as np
import pandas as pd
from sklearn.metrics import confusion_matrix
import matplotlib.pyplot as plt
import matplotlib as mpl 
%matplotlib inline
from scipy.integrate import quad
import sympy
```

## Daten einlesen


```python
people_en = pd.read_csv('people_wiki_EN.csv', sep=',')
people_de = pd.read_csv('10k-people-raw.csv', sep=';')

char_array = [chr(c) for c in range(ord('a'), ord('z')+1)]
char_dict = {char_array[index]:index for index in range(0,26)}
```

## Hilfsfunktionen


```python
def box_plot(dist, title = None):
    chars = [chr(c) for c in range(ord('a'), ord('z') + 1)]
    print(chars)

    fig1, ax1 = plt.subplots(figsize = (18, 8))
    ax1.set_xlabel('Character')
    ax1.set_ylabel('Frequency')
    ax1.boxplot(dist, labels = chars)
    ax1.set_ylim([0, 0.3])
    if title is not None:
        plt.title(title)
    plt.show()
```


```python
def frequency_plot(mean_en, mean_de):
    chars = [chr(c) for c in range(ord('a'), ord('z')+1)]
    ind = np.arange(len(chars))
    width = 1
    frequency = np.log((np.array(mean_en) / np.array(mean_de)))
    color = ['g' if f > 0 else 'b' for f in frequency]
    
    fig, ax = plt.subplots(figsize = (18, 8))
    rects1 = ax.bar(ind, frequency, width, color = color, edgecolor = 'black')
    ax.set_xticklabels(chars)
    ax.set_xticks(ind + (width * 0.5) - 0.5)
    ax.set_xlabel('Character')
    ax.set_ylim([-2, 2])
    ax.set_ylabel('F')
    ax.set_xlim([-0.5, len(chars) - 0.5])
    ax.text(1, 1.5, 'More frequent in English ', bbox={'facecolor':'green', 'alpha':0.5, 'pad':10})
    ax.text(1, 1.2, 'More frequent in German', bbox={'facecolor':'blue', 'alpha':0.5, 'pad':10})
    ax.text(5.5, 1.35, r'$F = \ln(\frac{mean_e}{mean_d})$', fontsize=25)
    plt.show()
```


```python
def plot_confusion_matrix(cm, classes, title = 'Confusion matrix', cmap = plt.cm.Greens):
    plt.title(title)
    tick_marks = np.arange(len(classes))
    plt.xticks(tick_marks, classes, rotation = 45)
    plt.yticks(tick_marks, classes)

    cm_norm = cm.astype('float') / cm.sum(axis=1)[:, np.newaxis]
    cm_norm[np.isnan(cm_norm)] = 0
    cm_norm = np.around(cm_norm, decimals = 3)
        
    plt.imshow(cm_norm, interpolation='nearest', cmap = cmap)
    
    thresh = cm_norm.max() / 2.
    for i, j in itertools.product(range(cm_norm.shape[0]), range(cm_norm.shape[1])):
        plt.text(j, i, cm[i, j], horizontalalignment="center", color="white" if cm_norm[i, j] > thresh else "black")

    plt.tight_layout()
    plt.ylabel('True label')
    plt.xlabel('Predicted label')
    plt.show()
```

## Häufigkeitsverteilungen


```python
def character_distribution(people):
    # Implementieren Sie eine Funktion die die Buchstabenhäufigkeiten berechnet.
    # Die Funktion soll folgendes zurückgeben:
    #  mean: Durchschnittlicher relative Häufigkeit pro Buchstabe 
    #  std: Relative Standardabweichung pro Buchstabe
    #  dist: Relative Häufigkeit pro Text und pro Buchstabe 

    chars = [chr(c) for c in range(ord('a'), ord('z') + 1)]
    dist = np.zeros(shape = (len(people), 26))

    for item_index, item in enumerate(people):
        fdist = nltk.FreqDist(char.lower() for char in item if char.isalpha())

        for char_index, char in enumerate(chars):
            dist[item_index, char_index] = fdist[char]

        dist[item_index,:] = dist[item_index,:]/sum(dist[item_index])

    mean = np.mean(dist,axis=0)
    std = np.std(dist,axis=0)

    return mean, std, dist
```


```python
mean_de, std_de, dist_de = character_distribution(people_de['text'])
box_plot(dist_de, 'German')
```


```python
mean_en, std_en, dist_en = character_distribution(people_en['text'])
box_plot(dist_en, 'English')
```


```python
frequency_plot(mean_en, mean_de)
```

## Spracherkennung

### Auswahl der Buchstaben für den Sprachdetektor


```python
# integrand() Funktion übernommen von Aufgabe Übungsserie 2, Aufgabe 13
# entspricht der Fläche unterhalb des Produktes der beiden Dichtefunktionen
# je kleiner die Fläche, desto weniger überschneiden sich die Dichtefunktionen
def integrand(x):
    return 1/std_de[i]/std_en[i]*sympy.exp(-(x-mean_de[i])**2/2/std_de[i]**2-(x-mean_en[i])**2/2/std_en[i]**2)
```


```python
# für jeden Buchstaben die Fläche der Überscheidung berechnen
charOverlapArea = {}
for i in np.arange(0,26):
     charOverlapArea[char_array[i]] = quad(integrand,0,1)[0]

charOverlapAreaSorted = sorted((value, key) for (key,value) in charOverlapArea.items())
# sechs Buchstaben mit der tiefsten Fläche eignen sich potenziell ab besten für den Sprachdetektor
print("Chars with lowest overlap area:", "\n", charOverlapAreaSorted[0:6], "\n")
```

    Chars with lowest overlap area: 
     [(0.9945622527746305, 'o'), (3.5069789980395134, 'e'), (34.0850941940391, 'a'), (38.70627766315792, 'z'), (59.61832993894152, 'y'), (85.74923006903875, 't')] 
    


Nachfolgend werden für die sechs Buchstaben mit der kleinsten Fläche der Überschneidung weitere Metriken berechnet um deren Eignung für den Sprachdetektor zu genauer zu prüfen.


```python
for i in [char_dict['o'],char_dict['e'],char_dict['a'],char_dict['z'],char_dict['y'],char_dict['t']]:
    #plot
    avgMean = np.mean([mean_de[i],mean_en[i]])
    plt.plot([mean_de[i]-std_de[i]*1.5,  mean_de[i]+std_de[i]*1.5], [char_array[i],char_array[i]], 'bo--',
             [mean_en[i]-std_en[i]*1.5,  mean_en[i]+std_en[i]*1.5], [char_array[i],char_array[i]], 'go--',
             [avgMean], [char_array[i]], 'rs',)
    
    #print statistics
    if mean_de[i] < mean_en[i]:
        cdf_german = round(scipy.stats.norm.cdf(avgMean, mean_de[i], std_de[i]),4)
        cdf_english = round(1 - scipy.stats.norm.cdf(avgMean, mean_en[i], std_en[i]),4)
        print(char_array[i], '|', 
              round(cdf_german*100,1), "% in scope", 
              "| avgOfTwoMeans: ",     round(avgMean,6), "|",
              round(cdf_english*100,1), "% in scope")
    else:
        cdf_german = round(1 - scipy.stats.norm.cdf(avgMean, mean_de[i], std_de[i]),4)
        cdf_english = round(scipy.stats.norm.cdf(avgMean, mean_en[i], std_en[i]),4)
        print(char_array[i], '|',
              round(cdf_english*100,1), "% in scope", 
              "| avgOfTwoMeans: ",     round(avgMean,6), "|",
              round(cdf_german*100,1), "% in scope")
        
print()         
print("Blue:   German  chars within 1.5 sdt")
print("Green:  English chars within 1.5 sdt")  
print("Red:    Average of the two means")
plt.show()
```

Der nachfolgende Sprachdetektor benötigt vier Buchstaben. Gemäss den Erläuterungen oben eignen sich die Buchstaben o, e, a, z, y, z (in dieser Reihenfolge) am besten für den Sprachdetektor.
Die Buchstaben x und y überschneiden sich zwar wenig, allerdigs kommen sich relativ selten vor, so dass wahrscheinlicher Abweichugen in kürzeren Texten auftreten können. Folglich wurden die Buchstaben x und y nicht für den Sprachdetektor verwendet.

Ausgewählte Buchstaben: *o, e, a, t*

### Klasse CharStats

Für die vier ausgewählte Buchstaben wird je eine Instanz der Klasse CharStats erstellt. Die Klasse CharStats enthält die relevanten Metriken eines Buchstabens. So könen die Metriken später einfach zugezogen werden. 



```python
class CharStats():
    
    def __init__(self, char, char_index,  avg_mean, lang_higher_mean, upper_boundary):
        self.char             = char
        self.char_index       = char_index
        self.avg_mean         = avg_mean
        self.lang_higher_mean = lang_higher_mean
        self.upper_boundary   = upper_boundary
    
    def __str__(self):
        return "Char: %s | Average of two means: %f | Language higher mean: %s | " \
               "Upper boundary: %f | Index: %d" % \
            (self.char, 
             self.avg_mean, 
             self.lang_higher_mean, 
             self.upper_boundary, 
             self.char_index)
```


```python
char_stats = []

for i in [char_dict['o'],char_dict['e'],char_dict['a'],char_dict['t']]:

    # calculate relavant statistics for a char
    avg_mean = np.mean([mean_de[i],mean_en[i]])
    lang_higher_mean = 'G' if mean_de[i] > mean_en[i] else 'E'
    
    sizeSdt = 3 # over 99% of data are within 3 std
    if lang_higher_mean == 'G':
        upper_boundary = mean_de[i] + sizeSdt*std_de[i]
    else: 
        upper_boundary = mean_en[i] + sizeSdt*std_en[i]

    # create instance CharStats
    current_char = CharStats(char_array[i], i, avg_mean, lang_higher_mean, upper_boundary)
    char_stats.append(current_char)

    
for c in char_stats: 
    print(c)
```

    Char: o | Average of two means: 0.053039 | Language higher mean: E | Upper boundary: 0.102237 | Index: 14
    Char: e | Average of two means: 0.137985 | Language higher mean: G | Upper boundary: 0.191752 | Index: 4
    Char: a | Average of two means: 0.078075 | Language higher mean: E | Upper boundary: 0.126781 | Index: 0
    Char: t | Average of two means: 0.069298 | Language higher mean: E | Upper boundary: 0.106445 | Index: 19


### Erstellung Entscheidungsbaum

Klasse Node: Ein Node hat zwei Äste (left, right). Zusätzlich weiss ein Node auf welchem Level im Baum er liegt und enthält einen Buchstaben für die Entscheidung, ob die Sprache eher Deutsch oder Englisch ist. Der lang_code wird im nachfolgenden Snippet erklärt.


```python
class Node(object):
    
    def __init__(self,lang_code, level, char_stats):
        self.left = None
        self.right = None
        self.lang_code = lang_code
        self.level = level
        self.char_stats = char_stats
        
        if   lang_code > 1:   self.lang = 'E'
        elif lang_code < -1:  self.lang = 'G'
        else:                 self.lang = 'X'
        
    def __str__(self):
        return str(self.lang_code)
    def insert_left(self,node):
        self.left = node
    def insert_right(self,node):
        self.right = node
    def is_leaf(self):
        if self.left is None and self.right is None:
            return True
        else: 
            return False
```
Gemäss der Aufgabenstellung dürfen nur vier True/False Entscheidungen getroffen werden.
Dadurch entsteht ein vierstufiger Baum. Für jede Stufe je ein Buchstabe aus den vier auserkorenen ausgewählt.
Bei jedem Node wird die Entscheidung gefällt, ob die Buchstabenverteilung eher Deutsch oder Englisch ist.

Eine Sprache gilt als gefunden, wenn die Entscheidung zwei mal in Folge für die gleiche Sprache fällt oder 
insgesamt drei von vier mal die gleiche Sprache ausgewählt wird. Ansonsten gilt die Sprache als nicht gefunden.(X)

Dadurch entsteht der folgende Baum mit vier Stufen und zehn Blättern.


                     0                      ------ o (Buchstabe für Vergleich)
             /                 \  
            /                   \   
           /                     \     
          /                       \              
        -1                         1        ------ e
      /    \                    /     \
     /      \                  /       \
   -2       0                 0        2    ------ a
         /    \            /    \       
       -1      1         -1      1          ------ t
       / \    / \        / \    / \
     -2   0  0   2     -2   0  0   2
   |  |   |  |   |      |   |  |   |    |
   |  |   |  |   |      |   |  |   |    |
   G  G   X  X   E      G   X  X   E    E  (ausgewählte Sprache)
 

```python
def generate_tree(node):
    
    if 2 > node.lang_code > -2 and node.level < 5:
        
        char_for_decision = char_stats[node.level] if node.level < 4 else None
        
        left  = generate_tree(Node(node.lang_code-1, node.level+1, char_for_decision))
        node.insert_left(left)
        
        right = generate_tree(Node(node.lang_code+1, node.level+1, char_for_decision))
        node.insert_right(right)
        
    return node

root = Node(0,1,char_stats[0])
lang_tree = generate_tree(root)
```


```python
def test_tree(lang_tree):
    print("Höhe des Baums: ",height(lang_tree))
    print("Anzahl Blätter:", leaf(lang_tree))
    for i in range(1,7): # zu viel drucken um Baumgrenzen zu zeigen
        print_tree_level(lang_tree, i)
        print()

def height(node):
    if node.is_leaf():
        return 0
    else:
        return max(height(node.left), height(node.right)) + 1
    
def leaf(node):
    if node.is_leaf():
        return 1
    else:
        return leaf(node.left) + leaf(node.right)

# der Baum muss zur nachfollziehbaren Darstellung pro Level gedruckt werden
# Die üblichen rekursiven Baumdurchläufe "Preorder" und "Postorder" sind nicht gut lesbar
def print_tree_level(node, level):
    if not node:
        print("_", end=" ")
        return
    if (level == 1): 
        print("[",node.lang_code,
              node.lang,   
              node.char_stats.char if node.char_stats else "_",
              "]",
              end=" ")
    elif (level > 1):
        print_tree_level(node.left, level-1); 
        print_tree_level(node.right, level-1);

test_tree(lang_tree)
```

    Höhe des Baums:  4
    Anzahl Blätter: 10
    [ 0 X o ] 
    [ -1 X e ] [ 1 X e ] 
    [ -2 G a ] [ 0 X a ] [ 0 X a ] [ 2 E a ] 
    _ _ [ -1 X t ] [ 1 X t ] [ -1 X t ] [ 1 X t ] _ _ 
    _ _ [ -2 G _ ] [ 0 X _ ] [ 0 X _ ] [ 2 E _ ] [ -2 G _ ] [ 0 X _ ] [ 0 X _ ] [ 2 E _ ] _ _ 
    _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 


### Sprache bestimmen


```python
def language_tree(mean_de, mean_en, texts):
    
    lang = []  
    _, _, dist_test = character_distribution(texts)

    for index in range(len(texts)):
        #für jeden Text mit dem generierten Baum die Sprache suchen 
        current_lang = get_lang(dist_test[index], lang_tree)
        lang.append(current_lang)
                
    return lang
```


```python
# get_lang durchläuft rekursiv den erstellten Suchbaum. 
# Sobald bei einem Blatt angekommen, wird die Sprache zurückgegeben.

def get_lang(text_dist, node):
    if node.is_leaf():
        return node.lang

    # Nebst dem avg_mean wird die upper_boundary (=dreifache Standartabweichung, siehe Generierung char_stats)
    # für die Entscheidung der Sprache zugezogen um Aussreisser auszuschliessen.
    if node.char_stats.upper_boundary > text_dist[node.char_stats.char_index] > node.char_stats.avg_mean:
        
        # den Entscheidungsbaum der Sprache entsprechend absteigen
        if node.char_stats.lang_higher_mean == 'G':
            return get_lang(text_dist, node.left)
        else:
            return get_lang(text_dist, node.right)
        
    else:
        if node.char_stats.lang_higher_mean == 'G':
            return get_lang(text_dist, node.right)
        else:
            return get_lang(text_dist, node.left)
```


```python
def accuracy(cm):
    i = np.eye(cm.shape[0])
    return (i * cm).sum() / cm.sum()
```


```python
people_test = pd.read_csv('Language_test.csv', sep=';', quotechar='|')
lang_true = np.array(people_test['language'])
```


```python
lang = language_tree(mean_de, mean_en, people_test['text'])
cm = confusion_matrix(lang_true, lang)
print('Accuracy:', accuracy(cm))
```

    Accuracy: 0.9901477832512315



```python
plot_confusion_matrix(cm, ['English', 'German', 'X'])
```

### Wertung

Mit dem erstellten Baum kann English und Deutsch sehr gut unterschieden werden. Die gut überlegte Auswahl der Buchstaben, sowie Erstellung des Baums zeigen am meisten Wirkung.
Ein Schwachpunkt scheint die Indentifizierung von anderen Sprachen zu sein. Die zwei falsch zugewiesene Sprachen sind unten noch detailliert festgehalten.

Hierzu wurde nochmals der weiter oben verwendete Plot genutzt (neu mit drei Standartabweichungen). Auf dem Plot ist neu mit dem schwarzen Dreieck der Wert des jeweiligen Texts in Relation zu den vorhandenen Verteilungen in den beiden Sprachen zu sehen.

In beiden Fällen entprichen die ersten beiden Vergleiche (o und a) des Textes recht genau der Englischen Sprache(grün).

Um diese Beiden Sprachen korrekt zuteilen zu können, könnte man beispielsweise andere Buchstaben verwenden oder mehr Abfragen durchführen, bevor eine Sprache festgelegt wird.


```python
_, _, dist_test = character_distribution(people_test['text'])

for index in range(len(people_test)):

    if lang_true[index] != lang[index]:
        desc = "True: " + lang_true[index] + " Found: "+lang[index] + " ..."+people_test['text'][index][:30]+"..."
        
        plt.figure()
        for i in [char_dict['o'],char_dict['e'],char_dict['a'],char_dict['t']]:
            plt.title(desc)
            avgMean = np.mean([mean_de[i],mean_en[i]])
            plt.plot([mean_de[i]-std_de[i]*3,  mean_de[i]+std_de[i]*3], [char_array[i],char_array[i]], 'bo--',
                     [mean_en[i]-std_en[i]*3,  mean_en[i]+std_en[i]*3], [char_array[i],char_array[i]], 'go--',
                     [avgMean], [char_array[i]], 'rs',
                      dist_test[index][i],[char_array[i]], 'k^')
        plt.show
        
```

9155e417a89fbfea2bc47dea7ce2373e9b4c4790
ipynb
Jupyter Notebook
language_detector/language_detector.ipynb
dimitrimuralt/natural_language_processing
e7a159d5e2107c9f509cc436c519618f4af9fc06
MIT
language_detector/language_detector.ipynb
dimitrimuralt/natural_language_processing
e7a159d5e2107c9f509cc436c519618f4af9fc06
MIT
language_detector/language_detector.ipynb
dimitrimuralt/natural_language_processing
e7a159d5e2107c9f509cc436c519618f4af9fc06
MIT
Qwen/Qwen-72B
1. YES
2. YES