马尔科夫链算法的JAVA实现

首先 

马尔可夫链，是指数学中具有马尔可夫性质的离散事件随机过程。该过程中，在给定当前知识或信息的情况下，对于预测将来会发生什么，发生的概率是多少。

算法实现原理

本文章讲述的是如何使用JAVA来简单的实现马尔科夫链算法，相比于现有的C、C++算法，使用JAVA实现马尔科夫链算法比较的简单，其原因在于JAVA里可以使用List数组代替C、C++里的链表、指针，操作起来相对的简单。

马尔科夫链算法的实现原理，是通过统计原有的数据以及它们发生的概率，从而通过概率的大小来判断未来会发生什么，有多大的概率，其过程可以用下面的图片简单描述：

矩阵1矩阵2

上图中矩阵2由矩阵1变化而得，及其过程可以简答的理解为由1→1,2→3,3→2,1→1···依次类推，马尔科夫算法即通过统计这个过程，即1→1的次数和概率，预测矩阵3中（将由矩阵2推出矩阵3）1转换为哪个数字的概率最大，从而达到预测的功能。

程序实现

首先是新建两个数组，这里使用的Object类型的List数组，可根据自身需求选择需要的类型，第一个数组用于存放统计数据，第二个数组用于存放概率：

public static List<Object> markovChain(List<List<Integer>> rawData){ //存放统计数据 List<Object> theStatisticsArray = new ArrayList<Object>(); //存放概率P List<Object> theProbabilityArray = new ArrayList<Object>();

接下来定义一些可能用到的常量：

int len=rawData.size()-1; int times = 1; double sum=0; double p=0; 接下来先做一下异常处理，防止没有或仅有一组数据，本算法仅限于两组以上算法：

if(len==0||len==-1){ theStatisticsArray.add("数据量不够，请导入足够数据！"); return theStatisticsArray; } 接下来是核心逻辑，主要实现数据的统计：

else{ for(int i=0;i<len;i++){ for(int j=0;j<rawData.get(i).size();j++){ boolean status = true; if(theStatisticsArray.size()==0){ theStatisticsArray.add(rawData.get(i).get(j)); theStatisticsArray.add(rawData.get(i+1).get(j)); theStatisticsArray.add(times); }else{ for(int k=0;k<theStatisticsArray.size();k+=3){ if(rawData.get(i).get(j).equals(theStatisticsArray.get(k))){ if(rawData.get(i+1).get(j).equals(theStatisticsArray.get(k+1))){ theStatisticsArray.set(k+2, (Integer)theStatisticsArray.get(k+2)+1); status = false; } } } if(status){ theStatisticsArray.add(rawData.get(i).get(j)); theStatisticsArray.add(rawData.get(i+1).get(j)); theStatisticsArray.add(times); } } } } }

得到统计完的数据后就可以计算每种事假发生的概率了，这段代码比较的简单：

for(int i=0;i<theStatisticsArray.size();i+=3){ sum = sum+(Integer)theStatisticsArray.get(i+2); } for(int i=0;i<theStatisticsArray.size();i+=3){ p = (Integer)theStatisticsArray.get(i+2)/sum; for(int j=i;j<i+3;j++){ if(j==i+2) continue; theProbabilityArray.add(theStatisticsArray.get(j)); } theProbabilityArray.add(p); } return theProbabilityArray; } }

得到的最终结果是由3个为一组的数据组成的数组，例如：1，1,0.1,1,2,0.02表示是是1→1概率为0.1,1→2概率为0.02。

下图为简单的测试结果：

结果：

注意

本算法使用的是JAVA语言实现马尔科夫链算法，其复杂度为n^3，在数据量比较大的时候较为的不适用，可能等待时间会比较的长，尚存在优化的方向。