Donnerstag, 30. Juli 2015

.Net und C# Alternative zu Matlab: ILNumerics.

Hinweis: Für diesen Post wurde ich von der ILNumerics GmbH bezahlt, konnte und sollte aber den Inhalt selber frei bestimmen.

Im heutigen Post möchte ich die Klassenbibliothek ILNumerics vorstellen und meine Erfahrungen damit teilen.
ILNumerics ist eine Klassenbibliothek für .Net mit dem Ziel numerische Berechnungen, Plots etc. einfacher und schneller in .Net implementieren zu können. Natürlich könnte man dies alles prinzipiell auch mit .Net Mitteln umsetzen, was allerdings sehr umständlich sein kann (man denke allein an die Darstellung von Vektoren, Matrix Multiplikation etc.). Mit ILNumerics steht nun eine Matlab sehr ähnliche Spracherweiterung bereit, mit welcher komplexere Algorithmen effizient implementiert werden können. Im folgenden werde ich nun, wie gesagt, eine kleine Einführung in dieses Thema geben und das kostenpflichtige Produkt testen, welches mir insgesamt sehr gut gefallen hat.

Fangen wir mit der Installation an: Heruntergeladen werden kann die Bibliothek über die Homepage. Erhältlich ist kostenlos nur eine Trial Version, diese Tatsache und der Preis ist der einzige Negativpunkt meiner Meinung nach. Dieser ist relativ hoch, anfangend von 89 Euro pro Monat, also wahrscheinlich für den Freizeitnutzer nicht geeignet. Sehr wohl jedoch für Universitäten, Firmen o.ä., hier kann ich mir ILNumerics als Alternative zu Matlab vorstellen, insbesondere da ich persönlich sehr gerne in C# und .Net programmiere. Eine kostenlose Version für Studenten wäre sehr zu begrüßen.
Nach der Installation kann die Trial Version getestet werden bzw. die Version aktiviert werden.
Weitere Informationen hierzu gibt es auf der Support Seite. Auf dieser gibt es auch ein Tutorial und eine genauere Dokumentation, welche auch mir als Referenz diente.

Die Bibliothek beinhaltet im Wesentlichen zwei Komponenten: Die Computation und die Visualization Engine. Zuerst werde ich die Verwendung der Computation Engine erläutern, dann die der Visualization Engine.

Um die Computation Engine ganz einfach einzubinden, legen wir ein neues Windows Projekt an und klicken dann im Menü auf Projekt - Neues Element hinzufügen. Im sich öffnenden Fenster wählen wir "Computing Module" aus und fügen damit eine neue .cs Datei in Form eines Computing Modules dem Projekt hinzu. In dieser sind bereits einige Beispielmethoden implementiert, die die Verwendung von ILNumerics demonstrieren, welche aber natürlich gelöscht werden können. Die Main - Methode lassen wir aber, da wir das Computing Module als Einstiegspunkt in das Programm verwenden möchten. Dies müssen wir dem Programm mitteilen, da auch die angelegte Form Klasse eine Main - Methode besitzt. Dies tun wir, in dem wir unter Projekteigenschaften - Anwendung Startobjekt auf das Computation Module setzen.
Der Code der Datei Computing Module1.cs sollte so aussehen:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ILNumerics;
using System.IO;

namespace IlNumericsTest
{

    public class Computing_Module1 : ILMath
    {
        public static void Main(params string[] parameter)
        {
        }
    }

}

Fangen wir mit ein paar leichten Operationen zur Eingewöhnung an.
Matrizen werden über die ILNumerics Klasse ILArray verwaltet. Mit diesen lassen sich mit +. -, *, / die erwarteten Rechenoperationen durchführen, nämlich Matrixaddition / -subtraktion und komponentenweise Multiplikation / Division. Der folgende Code erzeugt 3 Matrizen der Größe 10 x 10, die erste wird mit Einsen gefüllt, die zweite mit Nullen und die dritte mit zufälligen Werten zwischen 0 und 1. Dann wird auf der Konsole A + C ausgegeben sowie A * (-1).

ILArray<double> A = ones(10, 10);
ILArray<double> B = zeros(10, 10);
ILArray<double> C = rand(10, 10);
Console.WriteLine(A + C);
Console.WriteLine(-A);

Nun ein paar etwas komplexere Beispiele, ich möchte ein paar Operationen auf Graphen und Netzwerken zeigen. Wer Graphen nicht kennt sei auf Wikipedia verwiesen, diese sind jedenfalls eine oft benutzte Datenstruktur in der Informatik. Das Fachgebiet Web Science befasst sich insbesondere mit der Erforschung und Analyse von Netzwerken (wie dem Internet), dabei werden Graphen zur Repräsentation der Daten verwendet, welche riesige Ausmaße annehmen können. Auf Grund der Themenrelevanz (oft wird dabei z.B. mit Matlab gearbeitet) habe ich mich entschieden, aus diesem Bereich ein paar Beispiele zu zeigen, wie zum Beispiel den PageRank Algorithmus von Google.
Zuerst aber eine Funktion zum Einlesen von Daten:

            var file = File.ReadAllText("Graph.txt");
            ILArray AdjMatrix = csvread(file);

In der ersten Zeile wird die Datei in einen String gelesen, welcher dann mit der ILNumerics Funktion csvread() in eine Matrix gelesen wird. csvread() trennt die eingelesenen Werte (zum Beispiel) nach Komma. Die Eingabedatei soll die kommagetrennte Adjazenzmatrix eines Graphen enthalten, welche eine 1 an Position i, j besitzt falls die Knoten i und j mit einer Kante verbunden sind, ansonsten 0. Für einen Graph mit 4 Knoten könnte die Datei so aussehen:

0, 1, 0, 0
1, 0, 1, 1
0, 1, 0, 1
0, 1, 1, 0

Nun möchten wir aus der Adjazenzmatrix die Laplace Matrix bestimmen, welche den Grad von Knoten i im i-ten Diagonaleintrag enthält und -1 an Position i, j falls die Knoten i, j verbunden sind.
Dafür legen wir eine neue Funktion an. Da ILNumerics sehr auf Performance / Speichermanagement achtet (achten muss wenn es große Daten handhaben will), sind hier ein paar Dinge zu beachten. Zum einen gibt es nicht nur den vorgestellten Typ ILArray, sondern auch noch ILInArray, ILOutArray und ILRetArray (und generell noch andere Typen als Array). Für genaueres sei auf die Dokumentation verwiesen, hier nur kurz, ILInArray wird zum Beispiel für Eingabeparameter verwendet, ist nicht änderbar und wird direkt nach Verlassen des entsprechenden Scopes gelöscht (eben aus Speicher / Performance Gründen). Dafür müssen wir auch jede Funktion mit einem neuen Scope umschließen, welcher die Input Parameter enthält.
Die Funktion zur Berechnung der Laplace Matrix sieht so aus:

public static ILRetArray<double> CalcLaplacian(ILInArray<double> AdjMatrix)
{
    using (ILScope.Enter(AdjMatrix))
    {
        ILArray<double> Degrees = sum(AdjMatrix);
        ILArray<double> LaplacianMatrix = Degrees * eye(AdjMatrix.Length, AdjMatrix.Length);
        LaplacianMatrix = LaplacianMatrix - AdjMatrix;
        return LaplacianMatrix;
    }
}

Der Eingabeparameter ist die Adjazenzmatrix. In der ersten Zeile im Scope wird der Grad der Knoten ausgerechnet, was mit der Funktion sum() getan wird. Diese summiert alle Spalten der Matrix auf und gibt einen Vektor mit dem Ergebnis aus, welcher genau der Gradfolge entspricht. eye() erzeugt eine Matrix mit Einsen auf der Diagonalen, Multiplizieren mit dem Gradvektor und Subtrahieren von der Adjazenzmatrix liefert genau die gewünschte Matrix.

Als nächstes Beispiel berechnen wir die Dichte eines Netzwerks. Diese ist eine wichtige Kennzahl in Netzwerken, sie berechnet sich als Anzahl der vorhandenen Kanten durch die Anzahl der möglichen Kanten und gibt somit eben an, wie dicht bzw. zentralisiert ein Netzwerk ist. Durch eine doppelte Summation über die Matrixdimension lässt sich die Dichte ganz leicht berechnen:

public static ILRetArray<double> CalcDensity(ILInArray<double> AdjMatrix)
{
    using (ILScope.Enter(AdjMatrix))
    {
        ILArray<double> NrLinks = sum(sum(AdjMatrix));
        return (double)NrLinks / (AdjMatrix.Length * (AdjMatrix.Length - 1));
    }
}

Nun zu einem Algorithmus, welcher seine Erfinder reich und weltberühmt gemacht hat, im Kern im Prinzip aber so einfach ist, dass wir ihn hier jetzt umsetzen (im Kern, natürlich gehört noch viel mehr dazu als die paar Zeilen Code). Die Rede ist von Googles Pagerank Algorithmus, für lange Zeit die Basis für das Ranking von Webseiten bei der Google Suche. Der Algorithmus weist jeder Seite einen Pagerank (eine Popularität) zu, welcher sich aus der Summe der Pageranks der zu der Seite verlinkenden Seiten zusammensetzt. Die Formel zur Berechnung ist im verlinkten Wikipedia Artikel erklärt, in der Praxis wird der Pagerank jedoch iterativ wie folgt approximiert: Starte mit einem beliebigen Pagerank Vektor P, dann berechnet sich der neue Pagerank zu P = (1 - d) * e * A'T*P. Hierbei ist d ein Dämpfungsfaktor (z.B. 0.5), e der Einheitsvektor und A' die Matrix die aus der Adjazenzmatrix A entsteht, indem alle Zeilen mit nur Nullen durch Zeilen mit Einträgen 1/n (n = Anzahl der Knoten) ersetzt wird. Dies wiederholen wir so oft, bis sich neuer und alter Pagerank genügend nah angenährt haben, das Verfahren also pro Iteration nicht mehr viel verändert. In ILNumerics sieht das wie folgt aus:

        public static ILRetArray<double> CalcPageRank(ILArray<double> AdjMatrix)
        {
            using (ILScope.Enter(AdjMatrix))
            {
                ILArray<double> Degrees = sum(AdjMatrix.T);
                double epsilon = 0.00001;
                double d = 0.5;
                for (int i = 0; i < AdjMatrix.Length; i++)
                {
                    for (int j = 0; j < AdjMatrix.Length; j++)
                    {
                        if (Degrees[i] != 0)
                            AdjMatrix[i, j] /= Degrees[i];
                    }
                    if (AdjMatrix["0", ":"].Equals(zeros(1, AdjMatrix.Length)))
                        AdjMatrix["0", ":"] = ones(AdjMatrix.Length) / AdjMatrix.Length;
                }
                ILArray<double> POld = zeros(AdjMatrix.Length);
                ILArray<double> PNew = ones(AdjMatrix.Length);

                do
                {
                    POld = PNew;
                    PNew = (1 - d) * ones(AdjMatrix.Length) + d * multiply(AdjMatrix.T, POld);
                }
                while (norm(POld - PNew, 1) > epsilon);

                return PNew;
            }
        }

Mit der vorher beschriebenen Methode muss also zuerst die Adjazenzmatrix eines beliebigen Graphen eingelesen werden, die Funktion berechnet dann für jeden Knoten im Graph den Pagerank und gibt den Vektor der Pageranks zurück. Wie man sieht, ist auch die Auswahl von Untermatrizen wie in Matlab möglich. Matrix["a:b", "c:d"] wählt die Untermatrix aus, welche aus den Zeilen a - b und den Spalten c - d von Matrix besteht.

Allerdings sollte man die Pagerank Berechnung so nicht in ILNumerics implementieren. Ich habe den Code nur erst in diesem Stil geschrieben, um einen intuitiven Einstieg zu geben, und damit aufzuzeigen, wie man die Fähigkeiten von ILNumerics besser ausnutzt.
Generell empfiehlt sich die Verwendung von ILNumerics eigenen Funktionen und die Vermeidung von selber gebauten, wie for - Schleifen über große Matrizen etc. So verwenden wir statt dem iterieren durch die Matrix und Testen der Zeilen auf 0 den ILLogical Datentyp. Dieser liefert uns einen Vektor, welcher angibt, welche Elemente aus einem gegebenen Vektor eine bestimmte Bedingung erfüllen. Wir wählen als Bedingung Degrees = 0, wählen dann die Untermatrix mit den entsprechenden Zeilen aus und ersetzen diese durch 1/n. Das gleiche tun wir, um Einträge zu Knoten mit Grad ungleich 0 durch n zu teilen. Desweiteren haben wir unnötige Rechenoperationen aus der Rechenschleife herausgezogen, wie das Generieren eines Vektors von Einsen und das Transponieren der Matrix. Der entstandene, deutlich schlankere und schnellere Code sieht so aus:

        public static ILRetArray<double> CalcPageRank(ILArray<double> AdjMatrix)
        {
            using (ILScope.Enter(AdjMatrix))
            {
                ILArray<double> Degrees = sum(AdjMatrix, 1);
                double epsilon = 0.00001;
                double d = 0.5;

                ILLogical dummy = Degrees == 0;

                AdjMatrix[dummy, full] = 1.0 / AdjMatrix.Length;
                dummy = Degrees != 0;

                AdjMatrix[dummy, full] = AdjMatrix[dummy, full] / Degrees[dummy];
                AdjMatrix = AdjMatrix.T;

                ILArray<double> POld = zeros(AdjMatrix.Length);
                ILArray<double> PNew = ones(AdjMatrix.Length);
                ILArray<double> ILOnes = (1.0 - d) * ones(AdjMatrix.Length);

                do
                {
                    POld = PNew;
                    PNew = ILOnes + d * multiply(AdjMatrix, POld);
                }
                while (norm(POld - PNew, 1) > epsilon);

                return PNew;
            }
        }

Dieses Verfahren in Matlab implementiert benötigt bei einem 20 MB großen Graphen (ca. 3000 Knoten) etwa 5s, ILNumerics ebenfalls. Bei so geringen Laufzeiten lassen sich natürlich keine verlässlichen Performancemessungen durchführen, aber ich denke diese liegt im vergleichbaren Bereich. Laut Angaben der Hersteller hat ILNumerics einen etwas größeren Overhead, soll aber bei längeren Ausführungszeiten wesentlich schneller sein.

Um die Computing Engine abzuschließen, hier noch ein Beispiel wie sich ein lineares Gleichungssystem lösen lässt:

            ILArray<double> A = ILMath.zeros(3, 3);
            A["0;:"] = new double[] { 1, 2, 1 };
            A["1;:"] = new double[] { 3, 4, 0 };
            A["2;:"] = new double[] { -1, 0, 1 };

            ILArray<double> B = new double[] { 5, 4, 7};

            ILArray<double> x = ILMath.linsolve(A, B);

Kommen wir nun zur Visualization Engine. Hierbei gibt es natürlich unglaublich viele Möglichkeiten und Einstellungen, den gewünschten Plot zu erzeugen, deswegen werde ich hier nur eine kurze Einführung geben und für den Rest auf die Online Dokumentation verweisen.
Wie bei der Computation Engine folgen wir hier dem Quick Start Guide und legen ein neues Windows-Form Projekt an. Dann fügen wir mittels Projekt - Neues Element hinzufügen eine Plotting Form hinzu. In der Datei Program.cs ändern wir die Zeile Application.Run(new Form1()); zu Application.Run(new Plotting_Form1());, um dem Programm mitzuteilen, dass es das Plotting Formular starten soll.
Dieses enthält bereits Demo Plots, wir löschen aber erst einmal den Code um von Grund auf einen neuen Plot zu erstellen. Die Plotting Form stellt ein Steuerelement names ilPanel1 bereit, in dessen Load() Funktion zeichnen wir beim Starten des Formulars einen einfachen Linienplot mit 6 Punkten:

        private void ilPanel1_Load(object sender, EventArgs e)
        {
            var scene = new ILScene();
            // create some data

            ILArray<float> A = new float[] { 1, 2, 3, 4, -1, -2 };
            // add a plot cube
            scene.Add(new ILPlotCube {
  new ILLinePlot(A)
});
            ilPanel1.Scene = scene;
        }

Grundbestandteil der Plots sind sogennante scenes. Wir legen hier eine neue an und fügen dieser dann einen neuen Linienplot mit den angegebenen Daten hinzu. Das Ergebnis sieht so aus:


Standardmäßig kann der Zeichenbereich verschoben, gezoomt etc. werden. Hierfür muss der Plot per Code neugezeichnet werden.









Dies soll schon genügen, hier noch ein paar interessante Plots von der Homepage, die sich auch sehr leicht implementieren lassen:



Als Zusammenfassung kann ich noch einmal sagen, dass ich als Manko den Preis sehe, mir aber das Produkt insgesamt sehr gut gefallen hat, es bietet ein schnelles und einfach zu bedienendes Rechen- und Visualisierungstoolkit und ich auch von der Geschwindigkeit des Codes überzeugt bin. Ich sehe darin eine echte Alternative zu Matlab und würde mich freuen, wenn diese öfter eingesetzt wird.

Keine Kommentare:

Kommentar veröffentlichen