{ "cells": [ { "cell_type": "markdown", "metadata": { "_cell_guid": "386bdb46-0d39-4ba7-6d64-91007c203161" }, "source": [ "Dies ist die L\u00f6sung der Blattes 2 aus dem Kurs \"K\u00fcnstliche Intelligenz\" an der WH Gelsenkirchen. \n", "Wir beginnen mit Aufgabe 3, hier vergleichen wir die rekursive mit einer iterativen L\u00f6sung des Binomial-Koeffizienten.\n", "\u00dcbrigens: Man k\u00f6nnte die rekursive L\u00f6sung mit Memoization auch noch ein wenig besser machen.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "7a859e08-38c0-1c9a-a495-54c482d28965" }, "outputs": [], "source": [ "from time import time\n", "\n", "# Some magic to time the calls to functions. timing is a decorator, usage see below:\n", "def timing(f):\n", " def wrap(*args):\n", " time1 = time()\n", " ret = f(*args)\n", " time2 = time()\n", " print('%s function took %0.3f ms' % (f.__name__, (time2-time1)*1000.0))\n", " return ret\n", " return wrap\n", "\n", "def seq(n,k):\n", " if n==0:\n", " return 0\n", " if k==1:\n", " return n\n", " return seq(n-1,k) + seq(n-1,k-1)\n", "\n", "@timing\n", "def seq_top_call(n,k):\n", " return seq(n,k)\n", "\n", "@timing\n", "def iter(n,k):\n", " result = 1 # nicht komplett \u00e4quivalent zu seq, wir behandeln die Grenzf\u00e4lle hier nicht\n", " for i in range(1,k+1): # i aus [1,k]\n", " result *= ((n-k+i) / i) # // does not work here!\n", " return result\n", "\n", "test = [(4,2),(5,3),(10,2),(30,8),(100,2)]\n", "for n,k in test:\n", " print(\"Calling iter(\",n,\",\",k,\"): \",iter(n,k))\n", " print(\"Calling seq(\",n,\",\",k,\"): \",seq_top_call(n,k))\n", " \n", "# seq is MUCH slower than iter, costs exploding exponentially...\n", "\n", "print(\"Calling iter(\",500,\",\",10,\"): \",iter(500,10)) \n", "# print(\"Calling iter(\",10000,\",\",500,\"): \",iter(10000,500)) # Too large if computed with floats..infinity\n", "# Watch it: seq(500,10) and seq(10000,500) will not work, don't try it at kaggle - only at home ;)" ] }, { "cell_type": "markdown", "metadata": { "_cell_guid": "d79cc35c-f833-67f5-dba5-9f5038e9e169" }, "source": [ "Nun folgt Aufgabe 4:" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "55ecaa4b-88e1-b3e1-7aa0-dfe6538f1173" }, "outputs": [], "source": [ "# from matplotlib import pyplot\n", "from pylab import *\n", "import numpy as np\n", "\n", "# Our data\n", "data = [(21,3), (22,8), (23,7), (24,3), (25,4), (26,1), (27,1), (28,0), (29,1)]\n", "raw_data = [ 21,21,21,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,\n", " 24,24,24,25,25,25,25,26,27,29 ]\n", "\n", "n = len(raw_data)\n", "\n", "# A4.1: Stab-, Balken- und Kreisdiagramm zu den realativen H\u00e4ufigkeiten\n", "\n", "labels,sizes = zip(*data)\n", "print(labels,sizes)\n", "\n", "# Bar chart\n", "fig1, ax1 = plt.subplots()\n", "ax1.bar(labels, sizes)\n", "ax1.set_title('S\u00e4ulen- bzw. Stabdiagramms')\n", "\n", "# Pie chart\n", "fig2, ax2 = plt.subplots()\n", "ax2.pie(sizes, labels=labels, autopct='%1.1f%%', startangle=0)\n", "ax2.axis('equal') # Equal aspect ratio ensures that pie is drawn as a circle.\n", "ax2.set_title('Kreisdiagramms')\n", "\n", "\n", "# Show the pie!\n", "plt.show()\n", "\n", "# Balkendiagramm (horizontal)\n", "fig3,ax3 = plt.subplots()\n", "ax3.hlines(labels, [0], sizes , lw=7)\n", "ax3.set_title('Balkendiagramm')\n", "\n", "plt.show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "cb9897fc-91c5-2128-76e9-1c804db258e2" }, "outputs": [], "source": [ "# Es folgt Aufgabe 4.2, ein Histogramm zu den angegbenen Intervallen:\n", "\n", "hist(raw_data,bins=[19.999,21.999,23.999,25.999,27.999,29.999],normed=True,\n", " cumulative=False) \n", "title(\"Histogramm\")\n", "show()\n", "\n", "# ... und die empirische Verteilungsfunktion (A4.3)\n", "hist(raw_data,bins=[20,21,22,23,24,25,26,27,28,29,30],normed=True,\n", " cumulative=True) #,histtype=\"step\") \n", "\n", "title(\"Empirische Verteilungsfunktion F\")\n", "show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "7ea89862-ee58-9bf4-6027-4c75b62fa47d" }, "outputs": [], "source": [ "# A4.4: Bestimmen Sie das arithmetische Mittel, den Median und den Modus der Daten\n", "# (wir k\u00f6nnten auch Funktionen z.B. aus den numpy nutzen, wir machen es hier ab \"zu Fuss\")\n", "## Mittelwert\n", "\n", "def mittelwert(data,dim=1):\n", " '''\n", " This looks a little more complex as it can give you average value\n", " in multiple dimensions in one go.\n", " Example: data = [ (1,2,3),(2,3,4) ] will give you [1.5,2.5,3.5]\n", " Example: data = [1,2,3] will give you 2\n", " '''\n", " res = []\n", " n = len(data)\n", " for i in range(dim):\n", " res.append(0.0)\n", " for d in data:\n", " for i in range(dim):\n", " if dim == 1:\n", " res[i] += d\n", " else:\n", " res[i] += d[i]\n", " for i in range(dim):\n", " res[i] /= n\n", " return res[0] if dim==1 else res\n", " \n", "## Median\n", "def median(data):\n", " '''\n", " For an odd amount of data, take the value in the middle position.\n", " Otherwise, average over the two elements next to the middle position.\n", " Example: len(data) = 11, 0..10, mid position: (11-1) / 2 = 10 / 2 = 5 =>\n", " [0..4,5,6..10]\n", " Example: len(data) = 10, 0..9, mid positions: (n-2)/2 = 4,(n-2)/2+1 = 5\n", " '''\n", " n = len(data)\n", " if n % 2: # odd\n", " return data[(n-1)//2] # not like on the slides, as we count from 0!\n", " else:\n", " return (data[(n-2)//2] + data[(n-2)//2+1]) / 2\n", " \n", "## Modus\n", "def modus(data):\n", " maxpos,maxval = data[0]\n", " for d in data:\n", " if d[1] > maxval:\n", " maxpos,maxval = d\n", " return maxpos\n", "\n", "## Teilaufgabe 4\n", "mu = mittelwert(raw_data)\n", "print(\"Mittelwert: \",mu)\n", "med = median(raw_data)\n", "print(\"Median: \",med)\n", "mod = modus(data)\n", "print(\"Modus: \",mod)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "0a9d9484-7d49-db8f-267e-e14560f88efd" }, "outputs": [], "source": [ "# A4.5: Verwenden Sie die Beziehung zwischen arithmetischem Mittel, Median und Modus, um eine Aussage zu\n", "# Steilheit bzw. Symmetrie der Verteilung treffen zu k\u00f6nnen.\n", "\n", "## Schiefe, Folie 18\n", "def schiefe(mu,med,modus):\n", " if mu > med and med > mod:\n", " print(\"Schiefe der Verteilung: linkssteil bzw. rechtsschief\")\n", " return -1\n", " if mu < med and med < mod:\n", " print(\"Schiefe der Verteilung: rechtssteil bzw. linkssschief\")\n", " return 1\n", " print(\"Symmetrisch oder ann\u00e4hernd symmetrisch\")\n", " return 0\n", "\n", "schiefe_result = schiefe(mu,med,mod)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "e59a5b35-22bc-7f4f-5bec-8e1733fd3d3e" }, "outputs": [], "source": [ "# A4.6: Bestimmen Sie die Empirische Varianz, die Standardabweichung und die Stichprobenvarianz.\n", "\n", "## (Empirische) Varianz (eindimensional)\n", "def varianz(data,mu=None,stichprobe=False):\n", " if mu == None:\n", " mu = mittelwert(data)\n", " n = len(data)\n", " sum = 0\n", " for d in data:\n", " sum += (d - mu)**2\n", " return sum / (n-1) if stichprobe else sum / n\n", " \n", "## Standardabweichung\n", "def standardabweichung(data,mu=None,stichprobe=False):\n", " return sqrt(varianz(data,mu,stichprobe))\n", "\n", "var = varianz(raw_data)\n", "print(\"Varianz: \",var)\n", "sigma = sqrt(var)\n", "print(\"Standardabweichung: \",sigma)\n", "svar = varianz(raw_data,stichprobe=True)\n", "print(\"Stichprobenvarianz: \",svar)\n", "ssigma = standardabweichung(raw_data,stichprobe=True)\n", "print(\"Standardabweichung zur Stichprobenvarianz: \",ssigma)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "d7b19e42-f8df-3f89-7982-5e6c479ff695" }, "outputs": [], "source": [ "# A4.7_ Transformieren Sie die Daten von Menschenjahren in Hundejahre (1 Menschenjahr = 7 Hundejahre). \n", "# Bestimmen Sie auf einfache Art (empirische) Varianz und Standardabweichung der entstehenden Daten.\n", "\n", "# Teilaufgabe 8\n", "print(\"Hundejahre-Varianz =\",var * (7**2))\n", "print(\"Hundjahres-Standardabweichung =\", abs(7)*sigma)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "77cf7216-5991-2136-ebc7-522301fc22a2" }, "outputs": [], "source": [ "# A4.8: Zerlegen Sie die Daten in die 5 Intervalle, die sie bereits beim Histogramm verwendet haben. \n", "# Diese Intervalle sind nun unsere Schichten. Bestimmen Sie nun die Streuung in den Schichten und\n", "# die Streuung zwischen den Schichten und, abschlie\u00dfend, die Gesamtstreuung (s. Folien 23 und 24).\n", "\n", "def split(data,splitpoints):\n", " cdata = data[:]\n", " res = []\n", " for i in range(len(splitpoints)):\n", " res.append([])\n", " for pos,split in enumerate(splitpoints):\n", " check = cdata[:]\n", " cdata = []\n", " for d in check:\n", " if d < split:\n", " res[pos].append(d)\n", " else:\n", " cdata.append(d)\n", " return res\n", "\n", "def streuungs_mittelwert(klasses):\n", " n = 0\n", " sum = 0\n", " for klass in klasses:\n", " nj = len(klass)\n", " xj = mittelwert(klass)\n", " sum += nj * xj\n", " n += nj\n", " if n == 0: return 0\n", " return sum / n\n", "\n", "def inner_class_streuung(klasses):\n", " sum = 0\n", " n = 0\n", " for klass in klasses:\n", " nj = len(klass)\n", " sum += nj * varianz(klass)\n", " n += nj\n", " if n == 0: return 0\n", " return sum / n \n", "\n", "def intra_class_streuung(klasses):\n", " mu = streuungs_mittelwert(klasses)\n", " sum = 0\n", " n = 0\n", " for klass in klasses:\n", " nj = len(klass)\n", " xj = mittelwert(klass)\n", " sum += nj * (xj - mu)**2\n", " n += nj\n", " if n == 0: return 0\n", " return sum / n \n", " \n", "# Teilaufgabe 9\n", "splitted_data = split(raw_data,[22,24,26,28,30])\n", "print(splitted_data)\n", "print(\"Streuungsmittelwert: \",streuungs_mittelwert(splitted_data))\n", "in_class_var = inner_class_streuung(splitted_data)\n", "print(\"Inner-Class-Streuung: \", in_class_var)\n", "int_class_var = intra_class_streuung(splitted_data)\n", "print(\"Intra-Class-Streuung: \", int_class_var)\n", "print(\"Varianz aus der Streuungszerlegung: \", in_class_var + int_class_var)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "c4b9a7f1-e34b-9592-7b91-65da9e4dc941" }, "outputs": [], "source": [ "# A4.9: Bestimmen sie den Momentkoeffizienten der Schiefe f\u00fcr unsere Daten und treffen Sie eine Aussage zur\n", "# Schiefe bzw. Symmetrie der Daten. Vergleichen Sie ihr Resultat mit dem oben erzielten\n", "\n", "## Momentkoeffizient der Schiefe\n", "def moment_schiefe(data,mu=None):\n", " if mu == None:\n", " mu = mittelwert(data)\n", " n = len(data)\n", " sum = 0\n", " for d in data:\n", " sum += (d - mu)**3\n", " m3 = sum / n\n", " gm = m3 / (standardabweichung(data,mu)**3)\n", " if gm > 0:\n", " print(\"Verteilung ist linkssteil\")\n", " elif gm < 0:\n", " print(\"Verteilung ist rechtssteil\")\n", " else:\n", " print(\"Verteilung ist symmetrisch\")\n", " return gm \n", "\n", "print(\"Momentkoeffizient der Schiefe: \",moment_schiefe(raw_data))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "dac90632-f15e-5b27-286a-adf490e44fdb" }, "outputs": [], "source": [ "# A4.10: Bestimmen sie das W\u00f6lbungma\u00df nach Fisher. \n", "# Ist die Verteilung spitzer oder flacher als die Normalverteilung?\n", "\n", "def moment_fisher(data,mu=None):\n", " if mu == None:\n", " mu = mittelwert(data)\n", " n = len(data)\n", " sum = 0\n", " for d in data:\n", " sum += (d - mu)**4\n", " m4 = sum / n\n", " gamma = m4 / (standardabweichung(data,mu)**4) - 3\n", " if gamma > 0:\n", " print(\"Verteilung ist spitzer, als die Normalverteilung\")\n", " elif gamma < 0:\n", " print(\"Verteilung ist flacher, als die Normalverteilung\")\n", " else:\n", " print(\"Verteilung woelbt sich wie die Normalverteilung\")\n", " return gamma \n", "\n", "print(\"Woelbung nach Fisher: \",moment_fisher(raw_data))\n", "\n", "# A4.11: Ist die Verteilung uni-, bi- oder multimodal?\n", "print(\"Die Verteilung ist multimodal (3 lokale Maxima).\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "0b0c872b-1648-e1e5-3210-1834c26a13b9" }, "outputs": [], "source": [ "# Versuchen Sie, Parameter \u00b5 und \u03c3 f\u00fcr eine Normalverteilung so zu w\u00e4hlen, dass sie sich dem Verlauf\n", "# des Histogramms m\u00f6glichst gut ann\u00e4hert. Hier ist mit \u201cm\u00f6glichst gut\u201d gemeint, dass sie dies nicht\n", "# schlechter tun soll, als eine beliebige andere Normalverteilung mit anders belegten Parametern.\n", "\n", "# Teilaufgabe 2 und 13\n", "a,b,c = hist(raw_data,bins=[19.999,21.999,23.999,25.999,27.999,29.999],normed=True)\n", "title(\"Histogramm der Altersdaten mit Normalverteilungsschaetzer\")\n", "xs = np.arange(20.0,30.0,0.01) # Viele St\u00fctzpunkte zwischen [20 und 30) im Abstand von 0.01\n", "\n", "plot(xs,normpdf(xs,mu,ssigma)) # using deviation from stichprobenvarianz\n", "plot(xs,normpdf(xs,mu,sigma)) # Using standard deviation\n", "plot(xs,normpdf(xs,mu,1.4)) # steeper\n", "show()\n", "\n", "# Eine typische Wahl sind die Standardabweichungen von empirischer bzw. Stichprobenvarianzen\n", "# \"Besser\" geht es ohne weiteres Wissen nicht. Hier mag das - gegen die in Intervalle zusammengefassten\n", "# Daten aufgetragen - nicht so richtig perfekt aussehen." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "2684f800-4483-580e-e612-e91b0dfc0580" }, "outputs": [], "source": [ "# A4.13: Zeichnen Sie einen NQ-Plot zu unseren Daten.\n", "\n", "def gaussfunc(y,ybar,sigma):\n", " \"\"\"\n", " cumulative normal distribution function of the variable y\n", " with mean ybar,standard deviation sigma\n", " uses expression 7.1.26 from Abramowitz & Stegun\n", " accuracy better than 1.5e-7 absolute\n", " \"\"\"\n", " x=(y-ybar)/(math.sqrt(2.)*sigma)\n", " t=1.0/(1.0 + .3275911*abs(x))\n", " erf=1.0 - math.exp(-x*x)*t*(.254829592 -t*(.284496736-t*(1.421413741-t*(1.453152027 -t*1.061405429))))\n", " erf=abs(erf)\n", " sign=x/abs(x)\n", " return 0.5*(1.0+sign*erf)\n", "\n", "def gauss_quantil(p):\n", " xx = arange(-3.0,3.0,0.01)\n", " for x in xx:\n", " v = gaussfunc(x,0,1)\n", " if v > p:\n", " return x-0.005\n", "\n", "def nq_data(raw_data):\n", " res = []\n", " n = len(raw_data)\n", " for i in range(1,n+1):\n", " p = (i-0.5)/float(n)\n", " res.append((gauss_quantil(p),raw_data[i-1]))\n", " return res\n", "\n", "# Show some stuff\n", "def show_result(data,titel=\"\"):\n", " x = [i[0] for i in data]\n", " y = [i[1] for i in data]\n", " scatter(x,y,s=2, marker='^', c='b')\n", " title(titel)\n", " show()\n", " \n", "## Teilaufgabe 14\n", "show_result(nq_data(raw_data),\"NQ-Plot\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "cb023ac4-c54d-83c7-4ce2-a55020433bf1" }, "outputs": [], "source": [ "def transform(data,scale = 1.0):\n", " '''\n", " Erzeugen der Daten, wie in Aufgabe 6.15 gew\u00fcnscht.\n", " '''\n", " res = []\n", " for d in data:\n", " j = d[0]\n", " anzahl = d[1]\n", " if anzahl:\n", " intervall = float(scale / anzahl)\n", " for i in range(anzahl):\n", " position = j + intervall/2 + intervall*i\n", " res.append(position)\n", " return res\n", "\n", " \n", "## Kerne\n", "def rechteck_dichte(u):\n", " if u >= -1 and u <= 1:\n", " return 0.5\n", " return 0\n", "\n", "def epanechnikov_dichte(u):\n", " if u >= -1 and u <= 1: \n", " return 0.75*(1-u*u)\n", " return 0\n", "\n", "def schaetzer(x,h,dichte):\n", " sum = 0\n", " n = len(realdata)\n", " for xi in realdata:\n", " sum += dichte((x-xi) / h)\n", " return sum / n*h\n", "\n", "def verlauf(h,dichte,links=20.0,rechts=30.0,step=0.05):\n", " res = []\n", " position = links\n", " while position < rechts:\n", " wert = schaetzer(position,h,dichte)\n", " res.append((position,wert)) \n", " position += step \n", " return res\n", "print(transform(data))\n", "\n", "def plot_data(h,dichte,dichte_name):\n", " titel = dichte_name + \" mit Fenster %1.1f\" % h\n", " if __debug__: print(\"Gefundene Schaetzungen f\u00fcr\",titel)\n", " plotdata = verlauf(h,dichte)\n", " if __debug__: print(\" \",plotdata)\n", " show_result(plotdata,titel)\n", " \n", "\n", "\n", "## Teilaufgabe 15\n", "realdata = transform(data) \n", "print(\"Erzeugte Auspr\u00e4gungen:\")\n", "print(\" \",realdata)\n", "bs = np.arange(20.0,29.5,0.5)\n", "hist(realdata,bins=bs,normed=True)\n", "title(\"Histogramm der erzeugten Auspraegungen\")\n", "show()\n", "\n", "show_result(nq_data(realdata),\"NQ-Plot fuer die gestreckten Daten\")\n", "\n", "plot_data(0.2,rechteck_dichte,\"Rechteck\")\n", "plot_data(0.4,rechteck_dichte,\"Rechteck\")\n", "plot_data(0.8,rechteck_dichte,\"Rechteck\")\n", "plot_data(1.2,rechteck_dichte,\"Rechteck\")\n", "\n", "plot_data(0.2,epanechnikov_dichte,\"Epanechnikov\")\n", "plot_data(0.4,epanechnikov_dichte,\"Epanechnikov\")\n", "plot_data(0.8,epanechnikov_dichte,\"Epanechnikov\")\n", "plot_data(1.2,epanechnikov_dichte,\"Epanechnikov\")" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "_cell_guid": "3c3c3d9d-a37c-6266-2dd4-a66b5794ca7e" }, "outputs": [], "source": [ "" ] } ], "metadata": { "_change_revision": 0, "_is_fork": false, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.0" } }, "nbformat": 4, "nbformat_minor": 0 }