Versuch eine Markovkette zu Implementieren und zu Unit Testen

[hmm]

Hi Leute,

ich versuche gerade eine Markovkette zu implementieren und zu Unit testen. Leider habe ich einen Fehler in der Auswertung der Markovkette und ich find ihn nicht :-( Außerdem habe ich das Gefühl, dass mein Code immernoch so unlesbar ist, dass sich das ganze nicht gut mit Unit Tests absichern lässt.

Hier mein Code:

import java.util.HashMap;

public class StochastischerGraph {

	private HashMap<String, Integer> vertexs;
	private HashMap<String, Integer> edges;
	
	public StochastischerGraph() {
		setVertexs(new HashMap<String, Integer>());
		setEdges(new HashMap<String, Integer>());
	}
	
	public void addVertex(Integer vertex) {
		String vertexStr = String.valueOf(vertex);		
		if(getVertexs().containsKey(vertexStr)) {
			getVertexs().put(vertexStr, getVertexs().get(vertexStr) + 1);
		}
		else {
			getVertexs().put(vertexStr, 1);
		}
	}
	
	public void addVertexNum(Integer vertex, Integer vertexNum) {
		String vertexStr = String.valueOf(vertex);
		getVertexs().put(vertexStr, vertexNum);
	}
	
	public void addEdge(Integer from, Integer to) {
		String fromTo = String.valueOf(new StochTuple<Integer, Integer>(from, to).toString());
		if(getEdges().containsKey(fromTo)) {
			getEdges().put(fromTo, getEdges().get(fromTo) + 1);
		}
		else {
			getEdges().put(fromTo, 1);
		}
	}
	
	public void addEdgeNum(Integer from, Integer to, Integer edgeNum) {
		String fromTo = String.valueOf(new StochTuple<Integer, Integer>(from, to).toString());
		getEdges().put(fromTo, edgeNum);
	}
	
	public void save(StochastischerGraph newGraph) {
		
		vertexs = new HashMap<String, Integer>();
		edges = new HashMap<String, Integer>();
		
		for(String key: newGraph.getEdges().keySet()) {
			edges.put(key, newGraph.getEdges().get(key));
		}
		
		for(String key: newGraph.getVertexs().keySet()) {
			vertexs.put(key, newGraph.getVertexs().get(key));
		}
	}
	
	public HashMap<String, Integer> getVertexs() {
		return this.vertexs;
	}
	
	private void setVertexs(HashMap<String, Integer> vertexs) {
		this.vertexs = vertexs;
	}
	
	public HashMap<String, Integer> getEdges() {
		return this.edges;
	}
	
	private void setEdges(HashMap<String, Integer> edges) {
		this.edges = edges;
	}
}

Ich befüttere das mit Daten per train() und berechne die prognose matrix mit updateToProgGraph():

public class Analyse {

	private final Logger logger = LoggerFactory.getLogger(Analyse.class);
	private HashMap<String, LinkedList<Level>> symbolsLevelsWithAnalyse;
	private HashMap<String, LinkedList<Candlestick>> symbolCandleMap;
	private StochastischerGraph graph;

	public Analyse(HashMap<String, LinkedList<Level>> symbolsLevels,
			HashMap<String, LinkedList<Candlestick>> symbolCandleMap) {
		logger.info("Create new Analyse Class.");
		setSymbolsLevelsWithAnalyse(symbolsLevels);
		setSymbolCandleMap(symbolCandleMap);
		setStochastischerGraph(new StochastischerGraph());
	}


	private void setSymbolsLevelsWithAnalyse(HashMap<String, LinkedList<Level>> symbolsLevels) {
		this.symbolsLevelsWithAnalyse = symbolsLevels;
	}

	public HashMap<String, LinkedList<Level>> getSymbolsLevelsWithAnalyse() {
		return this.symbolsLevelsWithAnalyse;
	}

	public StochastischerGraph getStochastischerGraph() {
		return this.graph;
	}
	
	public void setStochastischerGraph(StochastischerGraph stochastischerGraph) {
		this.graph = stochastischerGraph;
	}

	private HashMap<String, LinkedList<Candlestick>> getSymbolCandleMap() {
		return this.symbolCandleMap;
	}

	private void setSymbolCandleMap(HashMap<String, LinkedList<Candlestick>> symbolCandleMap) {
		this.symbolCandleMap = symbolCandleMap;
	}

	/**
	 * Liesst die Wahrscheinlichkeit aus dem Prognosegraphen ab.
	 * 
	 * @param istZustand
	 * @param zielZustand
	 * @return
	 */
	private double calcProbability(StochastischerGraph newGraph, int istZustand, int zielZustand) {
		double p = 0;
		for (String vertex : newGraph.getVertexs().keySet()) {

			Integer vertexNum = Integer.valueOf(vertex);
			StochTuple<Integer, Integer> edge = new StochTuple<Integer, Integer>(istZustand, vertexNum);
			if (newGraph.getEdges().containsKey(edge.toString())
					&& (vertexNum >= 0 && vertexNum >= zielZustand || vertexNum < 0 && vertexNum <= zielZustand)) {

				p += newGraph.getEdges().get(edge.toString()).doubleValue()
						/ newGraph.getVertexs().get(String.valueOf(istZustand)).doubleValue();
			}
		}

		return p;
	}

	/**
	 * Trainiert den Stoachastischen Graphen anhand der Historischen Werte.
	 * 
	 */
	public void train() {
		for (String symbol : getSymbolCandleMap().keySet()) {

			int activVertex = 0;
			Candlestick activCandle = getSymbolCandleMap().get(symbol).get(0);

			for (int i = 1; i < getSymbolCandleMap().get(symbol).size(); i++) {
				Candlestick nextCandle = getSymbolCandleMap().get(symbol).get(i);
				int nextVertex = calculateNumberOfBreaksInOneDay(symbol, activCandle, nextCandle);

				if (i != getSymbolCandleMap().size() - 1) {
					graph.addVertex(nextVertex);
				}
				graph.addEdge(activVertex, nextVertex);

				activCandle = nextCandle;
				activVertex = nextVertex;
			}
		}
	}

	/**
	 * Aendert den Stochastischen Graph zu einem Graph dessen Kanten 30 Tage
	 * repraesentieren.
	 * 
	 * @param tage
	 * @return
	 */
	public StochastischerGraph updateToProgGraph(int tage) {
		StochastischerGraph newGraph = new StochastischerGraph();
		newGraph.save(graph);
		
		for (int i = 0; i < tage; i++) {
			StochastischerGraph helperGraph = new StochastischerGraph();
			
			for (String rootVertex : newGraph.getVertexs().keySet()) {
				int activVertex = Integer.valueOf(rootVertex);

				for (String vertex : newGraph.getVertexs().keySet()) {
					
					StochTuple<Integer, Integer> edge = new StochTuple<Integer, Integer>(activVertex, Integer.valueOf(vertex));
					if (newGraph.getEdges().containsKey(edge.toString())) {

						for (String nextVertex : graph.getVertexs().keySet()) {
							
							StochTuple<Integer, Integer> nextEdge = new StochTuple<Integer, Integer>(Integer.valueOf(vertex), Integer.valueOf(nextVertex));
							if (graph.getEdges().containsKey(nextEdge.toString())) {
								
								String fromTo = String.valueOf(new StochTuple<Integer, Integer>(activVertex, Integer.valueOf(nextVertex)).toString());
								if(helperGraph.getEdges().containsKey(fromTo)) {
									// addieren, wenn active -> vertex -> next fuer 2 unterschiedliche vertex gilt		
									Integer newVertexNum = helperGraph.getVertexs().get(String.valueOf(activVertex)) * newGraph.getVertexs().get(String.valueOf(activVertex)) * graph.getVertexs().get(vertex);
									Integer newEdgeNum = (helperGraph.getVertexs().get(String.valueOf(activVertex)) * newGraph.getEdges().get(edge.toString()) * graph.getEdges().get(nextEdge.toString())) + (helperGraph.getEdges().get(fromTo) * newGraph.getVertexs().get(String.valueOf(activVertex)) * graph.getVertexs().get(vertex));
									helperGraph.addVertexNum(activVertex, newVertexNum);
									helperGraph.addEdgeNum(activVertex, Integer.valueOf(nextVertex), newEdgeNum);
								}
								else {
									helperGraph.addVertexNum(activVertex, newGraph.getVertexs().get(String.valueOf(activVertex)) * graph.getVertexs().get(vertex));
									helperGraph.addEdgeNum(activVertex, Integer.valueOf(nextVertex), newGraph.getEdges().get(edge.toString()) * graph.getEdges().get(nextEdge.toString()));
								}
							}
						}
					}
				}
			}
			newGraph.save(helperGraph);
		}
		
		return newGraph;
	}

	/**
	 * Generiert die Wahrscheinlichkeit fuer einen durchbrochenen Widerstand
	 * nach 30 Tagen.
	 * 
	 * @param tage
	 */
	public void generateProbability(int tage) {

		StochastischerGraph newGraph = updateToProgGraph(tage);

		for (String symbol : getSymbolsLevelsWithAnalyse().keySet()) {

			Candlestick activCandle = getSymbolCandleMap().get(symbol).get(0);

			for (Level level : getSymbolsLevelsWithAnalyse().get(symbol)) {
				int anzahlAnNotwendigenBreaks = numberOfBreaks(activCandle, level, symbol);
				double probability = calcProbability(newGraph, 0, anzahlAnNotwendigenBreaks);
				level.setBreakProbability(probability);
			}
		}
	}

}

Und hiermit Versuch ich das zu Unit Testen:

@RunWith(SpringRunner.class)
@SpringBootTest
public class AnalyseTests {

	private final Logger logger = LoggerFactory.getLogger(AnalyseTests.class);
	private Analyse analyse;
	private LinkedList<Candlestick> candles;
	private LinkedList<Level> levels;

	@Before
	public void setUp() {
		HashMap<String, LinkedList<Candlestick>> symbolCandleMap = new HashMap<String, LinkedList<Candlestick>>();

		candles = new LinkedList<Candlestick>();
		candles.addLast(new Candlestick("symbol1", 3, 1, 2, 3, Timeframe.M15, new Date(1)));
		candles.addLast(new Candlestick("symbol1", 5, 1, 2, 5, Timeframe.M15, new Date(2)));
		candles.addLast(new Candlestick("symbol1", 3, 2, 2, 3, Timeframe.M15, new Date(3)));
		candles.addLast(new Candlestick("symbol1", 4, 1, 2, 4, Timeframe.M15, new Date(4)));
		candles.addLast(new Candlestick("symbol1", 3, 1, 2, 3, Timeframe.M15, new Date(5)));
		candles.addLast(new Candlestick("symbol1", 3, 1, 2, 3, Timeframe.M15, new Date(6)));
		candles.addLast(new Candlestick("symbol1", 1, 1, 2, 1, Timeframe.M15, new Date(7)));
		candles.addLast(new Candlestick("symbol1", 2, 1, 2, 2, Timeframe.M15, new Date(8)));
		candles.addLast(new Candlestick("symbol1", 2, 1, 2, 2, Timeframe.M15, new Date(9)));

		HashMap<String, LinkedList<Level>> symbolsLevels = new HashMap<String, LinkedList<Level>>();
		levels = new LinkedList<Level>();

		levels.addLast(new Level(candles.get(1).getHigh(), candles.get(1).getLow(), LevelArt.Higher, candles.get(1).getDate()));
		levels.addLast(new Level(candles.get(2).getHigh(), candles.get(2).getLow(), LevelArt.Lower, candles.get(2).getDate()));
		levels.addLast(new Level(candles.get(3).getHigh(), candles.get(3).getLow(), LevelArt.Higher, candles.get(3).getDate()));
		levels.addLast(new Level(candles.get(6).getHigh(), candles.get(6).getLow(), LevelArt.Lower, candles.get(6).getDate()));

		symbolsLevels.put("symbol1", levels);
		symbolCandleMap.put("symbol1", candles);

		analyse = new Analyse(symbolsLevels, symbolCandleMap);
	}
	
	@Test
	public void trainTest() {
		logger.info("Start AnalyseTests: trainTest.");
		
		analyse.train();
		StochastischerGraph graph = analyse.getStochastischerGraph();
		
		Assert.assertTrue(graph.getEdges().keySet().size() == 3);
		Assert.assertTrue(graph.getVertexs().keySet().size() == 2);
		
		analyse.setStochastischerGraph(new StochastischerGraph());
		logger.info("End AnalyseTests: trainTest.");
	}
	
	@Test
	public void updateToProgGraphTest() {
		logger.info("Start AnalyseTests: updateToProgGraphTest.");
		
		analyse.train();
		
		int tage = 2;
		StochastischerGraph newGraph = analyse.updateToProgGraph(tage);
		
		// check
		
		analyse.setStochastischerGraph(new StochastischerGraph());
		logger.info("End ANalyseTests: updateToProgGraphTest.");
	}
	
	@Test
	public void generateProbabilityTest() {
		logger.info("Start AnalyseTests: generateProbabilityTest.");
				
		analyse.train();
		
		int tage = 2;
		StochastischerGraph newGraph = analyse.updateToProgGraph(tage);
		
		// check
		
		analyse.setStochastischerGraph(new StochastischerGraph());
		logger.info("End AnalyseTests: generateProbabilityTest.");
	}
}
	

Leider habe ich einen Fehler in updateToProgGraph. Der Gedanke einer Markovkette ist, dass wir einen Graphen bzw eine Matrix P mit Häufigkeiten haben mit der Aussage: Heute stehen wir auf Zustand x und haben historisch folgende häufigkeit zu zustand y zu wechseln. In updateToPrgGraph rechnen wir das für n-Tage hoch indem wir P^n rechnen (wir berechnen damit die häufigkeit das wir in exakt n-Tage aufzustand y landen).

Ich habe folgende 2 Probleme:

1. Ich finde den Fehler nicht
2. Ich krieg die scheiße nicht gut geunittestet, weil mein Code nicht gut testbar ist.

Habt ihr ein paar verbesserungsvorschläge? besonders zu code testbarkeit?

[Rolf B]

Hallo hmm,

ich glaube, ich habe seinerzeit (1988) meine große Programmieraufgabe mit einer Art Markovkette gelöst, ohne den Namen zu kennen. Wir sollten da ein möglichst hohes Türmchen aus einer gegebenen Menge von Bauklötzen zusammensetzen. Ich weiß nur, dass ich damals gekotzt habe, weil das Ding überhaupt nicht so wollte wie ich.

Im Folgenden sind jetzt sicherlich ein paar persönliche Vorlieben dabei, und vermutlich gibt es auch Leute, die mir widersprechen werden.

• Ich verwende private getter und setter nur dann, wenn sie Logik enthalten. Ansonsten greife ich direkt auf die Objekteigenschaft zu. Es gibt Leute, die das anders sehen, sie sagen: „Es könnte ja mal Logik hineinkommen“ - ja. Aber bei PRIVATEN gettern/settern ist das kein Beinbruch. Klassen sollten eh nicht zu riesig werden.

• Das Ergebnis "teurer" Operationen cache ich in lokalen Variablen. Zum Beispiel in train der Wert von getSymbolCandleMap().get(symbol).

• Du solltest einheitlich darin sein, wie Du eine Vertex repräsentierst. In der Vertex-Hashmap ist der Vertex-Key ein String. Eine Edge, die zwei Vertexe verbindet, sollte demzufolge als StochTuple<String,String> repräsentiert sein. Alles andere führt nur zu sinnlosem Hin- und Herrechnen zwischen Integer und String und bläht den Code auf.

• Eigentlich verstehe ich die train-Methode nicht. Die Kette aus Vertices und Edges, die Du da erzeugst, ist mir rätselhaft. Das mag aber auch daran liegen dass ich die Fachlichkeit nicht kenne.

• Folgenden Code der train-Methode verstehe ich aber gar nicht. (1) Warum die Size der Map und nicht die Size der Liste eines Symbols. (2) Warum wird eine Edge für eine Vertex erzeugt, die nicht in der Vertex-Liste ist?

        if (i != getSymbolCandleMap().size() - 1) {
					graph.addVertex(nextVertex);
				}
				graph.addEdge(activVertex, nextVertex);

• Dein Check-Teil von trainTest ist zu wenig. Du müsstest schon genau prüfen, welche Vertext und Edges für deine Test-Candles entstanden sind.

• Die updateToProgGraph-Methode schreit laut: „entkerne mich!“. Das sind 4 Schleifen ineinander, mutmaßlich verdient jeder Schleifenrumpf eine eigene Methode. Um nicht zu viele Parameter durchschleifen zu müssen, könnte man eine Worker-Klasse in Erwägung ziehen, die newGraph und helperGraph als Eigenschaften enthält und die einzelnen Schleifenebenen als Methoden enthält. Diese Workerklasse kannst Du dann auch schön genüsslich testen; insbesondere ob die Formeln ganz innen tun, was sie sollen.

Rolf