马尔科夫链算法的JAVA实现

xiaoxiao2021-02-27  525

首先 

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

算法实现原理

本文章讲述的是如何使用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,在数据量比较大的时候较为的不适用,可能等待时间会比较的长,尚存在优化的方向。

转载请注明原文地址: https://www.6miu.com/read-423.html

最新回复(0)