Go语言视频零基础入门到精通

admin

首先  
马尔可夫链，是指数学中具有马尔可夫性质的离散事件随机过程。该过程中，在给定当前知识或信息的情况下，对于预测将来会发生什么，发生的概率是多少。
算法实现原理
本文章讲述的是如何使用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数组，可根据自身需求选择需要的类型，第一个数组用于存放统计数据，第二个数组用于存放概率：
  

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

复制代码

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

1. int len=rawData.size()-1;
2. int times = 1;
3. double sum=0;
4. double p=0;

复制代码

接下来先做一下异常处理，防止没有或仅有一组数据，本算法仅限于两组以上算法：
  
  

1. if(len==0||len==-1){
2. theStatisticsArray.add("数据量不够，请导入足够数据！");
3. return theStatisticsArray;
4.         }

复制代码

接下来是核心逻辑，主要实现数据的统计：
  
  

1. else{
2.         for(int i=0;i<len;i++){
3.                 for(int j=0;j<rawData.get(i).size();j++){
4.                         boolean status = true;
5.                                 if(theStatisticsArray.size()==0){
6.                                         theStatisticsArray.add(rawData.get(i).get(j));
7.                                         theStatisticsArray.add(rawData.get(i+1).get(j));
8.                                         theStatisticsArray.add(times);
9.                                 }else{
10.                                         for(int k=0;k<theStatisticsArray.size();k+=3){
11.                                                 if(rawData.get(i).get(j).equals(theStatisticsArray.get(k))){
12.                                                         if(rawData.get(i+1).get(j).equals(theStatisticsArray.get(k+1))){
13.                                                                 theStatisticsArray.set(k+2, (Integer)theStatisticsArray.get(k+2)+1);
14.                                                                 status = false;
15.                                                                 }
16.                                                         }
17.                                                 }
18.                                         if(status){
19.                                                 theStatisticsArray.add(rawData.get(i).get(j));
20.                                                 theStatisticsArray.add(rawData.get(i+1).get(j));
21.                                                 theStatisticsArray.add(times);
22.                                 }
24.                         }
25.                 }
26.         }
27. }

复制代码

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

1. for(int i=0;i<theStatisticsArray.size();i+=3){
2.                         sum = sum+(Integer)theStatisticsArray.get(i+2);
3.                 }
4.                 for(int i=0;i<theStatisticsArray.size();i+=3){
5.                         p = (Integer)theStatisticsArray.get(i+2)/sum;
6.                         for(int j=i;j<i+3;j++){
7.                                 if(j==i+2) continue;
8.                                 theProbabilityArray.add(theStatisticsArray.get(j));
9.                         }
10.                         theProbabilityArray.add(p);
11.                 }
12.                 return theProbabilityArray;
13.         }
14. }

复制代码

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

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