12/27/2012Joel Castellanose-mail: [email protected]: http://cs.unm.edu/~joel/Office: Farris Engineering Center (FEC) room 319Project 1: Stock Price Prediction using Markov ChainsCS 241 Data Organization using C2Stocks=,5Days=,15Date,GOOG,MSFT,INTC,AAPL,AMZN1/31/2012,580.11,29.53,26.42,456.48,194.441/30/2012,577.69,29.61,26.74,453.01,192.151/27/2012,579.98,29.23,26.73,447.28,195.371/26/2012,568.10,29.50,26.75,444.63,193.321/25/2012,569.49,29.56,26.90,446.66,187.801/24/2012,580.93,29.34,26.90,420.41,187.001/23/2012,585.52,29.73,26.71,427.41,186.091/20/2012,585.99,29.71,26.38,420.30,190.931/19/2012,639.57,28.12,25.63,427.75,194.451/18/2012,632.91,28.23,25.39,429.11,189.441/17/2012,628.58,28.26,25.04,424.70,181.661/13/2012,624.99,28.25,25.14,419.81,178.421/12/2012,629.64,28.00,25.75,421.39,175.931/11/2012,625.96,27.72,25.80,422.55,178.901/10/2012,623.14,27.84,25.59,423.24,179.34Project 1: Milestone I Data FormatWill always be odd and 5 (thus, 1, 3, or 5)3000You may assume dates are sorted newest to oldestYou may assume data is in correct format.25-day Moving Average In statistics, a moving average is a type of finite impulse response filter used to analyze a set of data points by creating a series of averages of equal sized subsets of the full data set. A moving average is commonly used with time series data to smooth out short-term fluctuations and highlight longer-term trends or cycles. 34566736425.65.45.6A First-Order Markov Chain A First-order Markov chain, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states.  A First-order Markov chain is a random process characterized as memoryless: the next state depends only on the current state and not on the sequence of events that preceded it. 4School  bikingSchool  bikingSchool  drivingSchool  bikingSchool  bikingSchool  walkingSchool  driving■ Probabilities can be inferred from historical data:PSchool  walking 1 / 735thOrder Markov ChainIf they in thou, thy love, that old,Thought, that which yet do the heat did excessMy love concord never saw my woeful tasteAt ransoms you for that so unprovident:For thereby beauty show’st I am fled,Althoughts to the dead, that careWith should thus shall by their fair,Where too much my jade,Her loves, my heart.5Composed by 5thorder Markov Chains based on a set of Shakespeare's sonnets.Code by Jim, February 2009Space of Possible PatternsStocks CombinationsGOOG MSFT INTC AAPL AMZN Row Totalday-2 [0,3] [0,3] [0,3] [0,3] [0,3] 10241024= 45day-1 [0,3] [0,3] [0,3] [0,3] [0,3] 1024 1,048,576= 410 Today [0,3] 4 4,194,304 = 4116Note: Fits within an int if sizeof(int) = 4Does NOT fit if sizeof(int) = 24Simplified Example: 3 Corps x 14 daysThe next few slides show the full process of building the Markov Field for this small data set.Also, to keep it simple, only two states will be used:   5-day Average < 5-day AverageFile name:stockData_3x14.txt7Date MSFT INTC AAPL1/31/2012 29.53 26.42 456.481/30/2012 29.61 26.74 453.011/27/2012 29.23 26.73 447.281/26/2012 29.50 26.75 444.631/25/2012 29.56 26.90 446.661/24/2012 29.34 26.90 420.411/23/2012 29.73 26.71 427.411/20/2012 29.71 26.38 420.301/19/2012 28.12 25.63 427.751/18/2012 28.23 25.39 429.111/17/2012 28.26 25.04 424.701/13/2012 28.25 25.14 419.811/12/2012 28.00 25.75 421.391/11/2012 27.72 25.80 422.555-day Moving Averages8DateMSFT INTC AAPLClose Price5-day MAClose Price5-day MAClose Price5-day MA1/11/2012 27.72 25.80 422.551/12/2012 28.00 25.75 421.391/13/2012 28.25 25.14 419.811/17/2012 28.26 25.04 424.701/18/2012 28.23 28.09 25.39 25.42 429.11 423.511/19/2012 28.12 28.17 25.63 25.39 427.75 424.551/20/2012 29.71 28.51 26.38 25.52 420.30 424.331/23/2012 29.73 28.81 26.71 25.83 427.41 425.851/24/2012 29.34 29.03 26.90 26.20 420.41 425.001/25/2012 29.56 29.29 26.90 26.50 446.66 428.511/26/2012 29.50 29.57 26.75 26.73 444.63 431.881/27/2012 29.23 29.47 26.73 26.80 447.28 437.281/30/2012 29.61 29.45 26.74 26.80 453.01 442.401/31/2012 29.53 29.49 26.42 26.71 456.48 449.615Percent Change:Today's Close vs 5-day Moving Ave. 9DateMSFTClose Price5-day MA % 1/11/2012 27.721/12/2012 28.001/13/2012 28.251/17/2012 28.261/18/2012 28.23 28.091/19/2012 28.12 28.17 0.1%1/20/2012 29.71 28.51 5.5%1/23/2012 29.73 28.81 4.3%1/24/2012 29.34 29.03 1.8%1/25/2012 29.56 29.29 1.8%1/26/2012 29.50 29.57 0.7%1/27/2012 29.23 29.47 -1.1%1/30/2012 29.61 29.45 0.5%1/31/2012 29.53 29.49 0.3%This table only shows MSFT, but the same data must be calculated for each of the companies.The percent change (%)is:yesterdayyesterdaytodayMAMAClosePriceFile name:stockData_3x14.txtPercent Change Mapped Up or DownDateMSFT INTC AAPL%  %  %1/11/20121/12/20121/13/20121/17/20121/18/20121/19/2012 0.1% 1 0.8% 1 1.0% 11/20/2012 5.5% 1 3.9% 1 -1.0% 01/23/2012 4.3% 1 4.7% 1 0.7% 11/24/2012 1.8% 1 4.1% 1 -1.3% 01/25/2012 1.8% 1 2.7% 1 5.1% 11/26/2012 0.7% 1 0.9% 1 3.8% 11/27/2012 -1.1% 0 0.0% 1 3.6% 11/30/2012 0.5% 1 -0.2% 0 3.6% 11/31/2012 0.3% 1 -1.4% 0 3.2% 110So as to need a smaller Markov table, this example maps the percent change to only two bins:■ 0: < 0%■ 1:  0%Your project must map the percent change to 4 bins.6First 16 of the 128 Markov Fields for 3 Corporations, 2-Day Chains with 2 BinsMSFT INTC AAPLIndex into Markov Tableday-2 day-1 day-2 day-1 today day-2 day-1000 0 00 00000 0 00 11000 0 01 02000 0 01 13000 0 10 04000 0 10 1 5000 0 11 0 6000 0 11 1 7000 1 00 0 8000 1 00 19000 1 01 010000 1 01 111000 1 10 012000 1 10 1 13000 1 11 0 14000 1 11 1 1511All 128 fields must each map to a unique index into the Markov Table.This shows the first 15 fields and their mappings.Next 16 of the 128 Markov FieldsMSFT INTC AAPLIndex into Markov Tableday-2 day-1 day-2 day-1 today day-2 day-1001 0 00 016001 0 00 117001 0 01 018001 0 01 119001 0 10 020001 0 10 1 21001 0 11 0 22001 0 11 1 23001 1 00 0 24001 1 00 125001 1 01 026001 1 01 127001 1 10 028001 1 10 1 29001 1 11 0 30001 1 11 1 31127First Field of the Markov TableMSFT INTC AAPL  11111011111011111101110110113The first field from the sample data is:1111110If the mapping shown on the previous two slides is used then this Markov Field maps to Markov Table Index 126.Add this field to the Markov table with the command:markovTable[126]++;26242125232022Fields 2 & 3 from stockData_3x14.txtMSFT INTC AAPL 