数据预测类算法

一次指数平滑法

一次指数平滑法是根据以前的数据的趋势，预测即将出现的数据值

一次指数平滑法只适合于具有水平发展趋势（即没有持续的上升或下降趋势）的时间序列分析，只能对近期进行预测

公式1

本期平滑值=上期实际值*平滑系数+（1-平滑系数）*上期平滑值

公式2

本期平滑值=本期实际值*平滑系数+（1-平滑系数）*上期平滑值

两个公式都可以使用，只有少许区别
使用公式1可以子一次循环中就计算出目标预测值
公式2，则是先把已有数据的平滑值算出来，最后一步预测还有使用公式一才能算出预测期数的平滑值，因为要预测的期数实际值是没有的

二次指数平滑法

二次指数平滑法是在一次平滑的基础上，使用一次平滑的结果，做二次平滑运算
主要适用于：时间序列具有上升或下降趋势的预测

公式

本期平滑值=本期一次平滑值*平滑系数+（1-平滑系数）*上期二次平滑值

初始平滑值的确定

一次和二次指数法，第一条数据，都是没有上期平滑值的
一般分为两种情况，当样本为大样本时（n>42），上期平滑值一般以第一期的实际值代替；当样本为小样本时（n<42），上期平滑值一般取前几期（3-5）的平均值代替

平滑系数的选择

1、当原始数据呈现比较稳定的水平趋势，平滑系数一般在0.1-0.3之间，减少修正幅度
2、原数列波动较大，选择适中的值，一般在0.3-0.6之间
3、原数列波动较大，且确实明显时，一般在0.6-0.9之间

可以把预测值和实际值做趋势对比，适当调整系数，使趋势接近，提高预测的准确性

大数据筛选类算法

遗传算法

遗传算法主要用于从大量可能值中找出最优解。该算法没有具体的公式，是模拟达尔文生物进化论而总结的一种程序设计思想

概念名词

为什么要使用异常算法来筛选最优解呢？
当数据较少时，我们完全可以使用穷举法来筛选最优解。但当数据超过了当代计算机的存储和计算能力值时，遗传算法就可以用一小组样本，通过不断迭代实现结果。

以经典商旅问题为例，已知100个城市的坐标x，y，求走遍所有城市最短路线，城市编号从1到100。那么其中一个解就是包含1-100的随机顺序的数字集合。
如果我们使用穷举法，就要把所有可能的路线先列出来，100个城市的排列，套用排列公式：

n==m，分母为1，所以100个城市的排列可能就是100的阶乘，是一个长达160位的天文数字，没有服务器可以一次性处理如此巨量数据，需要分布式集群来解决。这个时候使用遗传算法，可以以较少的数量，通过多次迭代来找出最优解

最短路径算法

弗洛伊德算法

弗洛伊德算法主要用于计算一个路径图中，两两节点最短距离

局限

若两个节点没有直接联通，可通过一个中间节点联通。若需要的中间节点超过1个，则无法算出两个节点之间的距离。

弗洛伊德算法既适用于无向加权图，也适用于有向加权图
我们使用一个有向加权图为例，如下
有向，说明节点之间只能按箭头计算距离。比如0->3 ,0到3的距离是5,3到0是无穷
无向，则是0-5。0和5之间使用一条路径
加权，说明指定了两点之间的长度
无权，说明默认两点之间的长度默认为1

基本原理

以一个节点为作为中间节点，当查找一个节点到其他节点路径时，则查看能否通过中间节点进行关联。若中间节点可以关联，且关联后路径距离比原节路径的距离短，则把该路径作为最短路径

先把上图的节点关系整理为一个表格

例如：以3作为中间节点，找1到各节点的距离。
1到0，无中间节点，过
1到1，无中间节点，过
1到2，有中间节点3，新路径1-3-2距离为6，小于原1到2的路径 无穷，记录
1到3，无中间节点，过

主要经过使用三重循环
第一重：把4个点依次作为中间节点
第二重：依次查寻4个起始顶点和中间节点的关系
第三重：遍历一个起始顶点到目标顶点的值

使用go语言实现，代码如下

package main

import (
	"fmt"
	"math"
	"strconv"
)

type dist []float64
type path map[int64]string

func main(){
	//定义一个无穷数
	inf := math.Inf(1)
	//根据加权图，列出各个顶点之间的距离
	dist_data := []dist{
		{0,3,inf,5},
		{2,0,inf,4},
		{inf,1,0,inf},
		{inf,inf,2,0},
		{1,inf,inf,inf},
	}
	//声明并初始化一个map用来保存路径关系
	path_data := map[int64]path{0:{},1:{},2:{},3:{},4:{}}
	var m int64
	var s int64
	var v int64
	//第一层循环，用来更换选定中间节点，middle
	for m=0;m<4;m++{
		//第二层循环，用来更换与中间节点连接的起始节点，start
		for s=0;s<4;s++{
			//第三层循环用来遍历其起始节点start，到各点和中间点的值，value，
			for v=0;v<4;v++{
				//记录路径
				if _,ok := path_data[s][v];!ok{
					path_data[s][v] = strconv.FormatInt(s, 10)+"-"+strconv.FormatInt(v, 10)
				}
				//当选中的中间节点middle和当前起始节点start为同一个，跳出该层循环
				if m == s{
					break
				}
				//若当前start节点的v等于m ，表示不存在中间节点
				//若当前start节点的v等于s，表示自己到自己
				//若当前middle节点到v节点值为无穷数，表示是无效中间节点
				//以上三种情况都跳过该次循环
				if v == m || v == s || math.IsInf(dist_data[m][v],1){
					continue
				}
				//若当前节点到v的值，小于，当前节点到中间节点+中间节点到v的值，则更新当前节点的v值和路径
				if dist_data[s][v] > dist_data[s][m]+dist_data[m][v]{
					dist_data[s][v] = dist_data[s][m]+dist_data[m][v]
					path_data[s][v] = strconv.FormatInt(s, 10)+"-"+strconv.FormatInt(m, 10)+"-"+strconv.FormatInt(v, 10)
				}
			}
		}
	}
	fmt.Println(dist_data)
	fmt.Println(path_data)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

迪杰斯塔拉算法

杰斯塔拉算法用于计算一个顶点到其他所有点的最短路径，不会被路径中中间节点个数限制

下面是一个无向加权图，和根据图提取的表格

我们还需要根据图，提取一个节点和路径之间的映射数组，如下

$arr = [
	"0-1"	=> 2,
	"0-2"	=> 6,
	"1-3"	=> 5,
	....
]
1
2
3
4
5
6

基本原理

循环查找“总权值”行中，最小的值，此时为2。把该列对应的节点1，标记为已确定的最短路径。然后从$arr中查找，键值是以1开头的，以1之后的节点结尾的路径。如果有，且路径值+1节点的权值<原节点权值，就修改原节点的权值和路径。开启下次循环，找最小权值，但不包括已被标记为最短路径节点对应列。直到节点都被标为最短路径后结束

使用php复现流程，如下

$start = '0';//起始节点点名称
$node_arr = [1,2,3,4,5,6];//子节点名称数组
//两个节点的路径和距离对应数组
$map = [
	'0-1'	=> 2,
	'0-2'	=> 6,
	'1-3'	=> 5,
	'2-3'	=> 8,
	'3-5'	=> 15,
	'3-4'	=> 10,
	'4-5'	=> 6,
	'4-6'	=> 2,
	'5-6'	=> 6
];
//初始化各子节点到起始节点的距离和路径数组
$path = $dist = [];
foreach($node_arr as $val){
	$p = $start.'-'.$val;
	$path[$val] = $p;
	//status为1时，表示该节点到起始点已找到最近距离，不在参与之后循环
	$dist[$val] = isset($map[$p])?['val'=>$map[$p],'status'=>0]:['val'=>log(0),'status'=>0];
}
//过滤dist中已被标记为最短距离的节点和无效权值（无穷）的节点
function getDistMin($dist){
	$arr = [];
	foreach($dist as $key=>$val){
		if($val['status'] != 1 and !is_infinite($val['val'])){
			$arr[$key] = $val['val'];
		}
	}
	return $arr;
}
//循环查找和更新，循环次数大于节点数即可
for($i=1;$i<=7;$i++){
	//查找dist中的最小值，排除status为1的值和无穷值
	$min_dist = getDistMin($dist);
	//返回空，说明节点都被标记为了最短路径，可以结束循环
	if(!$min_dist){
		print_r($path);
		print_r($dist);
		exit;
	}
	//最小权值
	$min_dist_val = min($min_dist);
	//最小权值对应的节点
	$min_code = array_keys($min_dist,$min_dist_val)[0];
	//更新dist中，该节点的status为1，即标记为最短路径
	$dist[$min_code]['status'] = 1;
	//查找该节点之后的节点到该节点路径，并把值更新到path和dist中
	foreach($node_arr as $val2){
		$key2 = $min_code.'-'.$val2;
		//如果 当前节点值>最小节点值+当前节点到最小节点值,或当前节点值是无穷值，更新
		if(
			$val2 > $min_code
			&& isset($map[$key2])
			&& (is_infinite($dist[$val2]['val']) || $dist[$val2]['val'] > $min_dist_val+$map[$key2])
		){
			$dist[$val2]['val'] = $min_dist_val+$map[$key2];
			$path_str = $path[$min_code].'-'.$key2;
			$path_arr = array_unique(explode('-',$path_str));
			$path_str = implode('-',$path_arr);
			$path[$val2] = $path_str;
		}
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66