本文主要集中在其算法实现,大家只用记住一点就可以了:弗雷歇距离可以服务于线相似度匹配。相关的文献也有很多,在此不再一一列举。
用python实现它的原因
节点数相同的曲线/形状弗雷歇距离计算
引用库
该库结合了Frechet距离和Procrustes分析来检查两个形状/曲线之间的相似性。在实现过程中,首先使用Procrustes分析对曲线进行归一化,然后计算曲线之间的Fréchet距离。注意事项:该库的输入必须是节点数相等的!!!
代码示例
应用该库的代码示例如下,输入的形状/曲线可以用下述两种方法生成,详细使用方式请参照详细注释:
from shapesimilarity import shape_similarity
import matplotlib.pyplot as plt
import numpy as np
x = np.linspace(1, -1, num=200)
# 方法一 通过函数构建曲线
y1 = 2*x**2 + 1
y2 = 2*x**3 + 2
shape1 = np.column_stack((x, y1))
shape2 = np.column_stack((x, y2))
# 方法二 直接输入节点坐标(x, y)
shape3 = [(1.4, 2.6),(1.5, 5.6),(5.8, 10),(10.6, 9)]
shape4 = [(1.5, 2.7),(1.9, 5.4),(5.7, 12),(14.6, 5)]
shape3 = np.column_stack(shape3)
shape4 = np.column_stack(shape4)
# 调用库计算相似度
similarity1 = shape_similarity(shape1, shape2)
similarity2 = shape_similarity(shape3, shape4)
# 方法一和方法二的相似度输出
print("similarity1:{}".format(similarity1))
print("similarity2:{}".format(similarity2))
# 图形展示部分
# 方法一:
plt.plot(shape1[:, 0], shape1[:, 1], linewidth=2.0)
plt.plot(shape2[:, 0], shape2[:, 1], linewidth=2.0)
plt.title(f"Shape similarity is: {similarity1}", fontsize=14, fontweight="bold")
plt.show()
# 方法二
plt.plot(shape3[:, 0], shape3[:, 1], linewidth=2.0)
plt.plot(shape4[:, 0], shape4[:, 1], linewidth=2.0)
plt.title(f"Shape similarity is: {similarity2}", fontsize=14, fontweight="bold")
plt.show()
结果展示
输出结果:
输出像:
节点数不同的曲线/形状基于弗雷歇的相似度计算
虽然我找到上面那个库的结果很哇塞,但是很快就发现了一个致命问题:实际使用过程中大多数线要素和形状都是不等节点的!突然感觉世界灰暗了,随即硬着头皮想出了解决方案并实现。实现的总体思路如下:
读取输入数据;——对应test.py根据线的节点坐标,根据阈值重新构建节点,保证重新构建后节点数一致;——对应frechet.py调用shapesimilarity库进行计算并成果展示。——对应frechet.py中的similarity函数
与前文相同,该部分代码依旧引用了该库:
import frechet_distance_curve
if __name__ == "__main__":
c1 = [(0.45, 1.6), (4.9, 1.5), (3.9, 1.5)]
c2 = [(0.45, 1.6), (2.7, 1.6), (2.7, 1.1), (3.7, 1.6)]
if len(c1) != 0 and len(c2) != 0:
frechet_distance_curve.test_2d_curve(c1, c2)
else:
print("error: can not input empty!")
import line
import frechet
def test_2d_curve(c1, c2):
# 建立CurveByLines类,a,b具有一定的属性、方法了
# 具体包含:线集,差集,at方法
a = line.CurveByLines(c1)
b = line.CurveByLines(c2)
# 标准化格式后的线,进行弗雷歇距离计算,a,b是一个可迭代的对象
frechet.frechet_distance(a, b)
from typing import Any, Callable, List
from shapesimilarity import shape_similarity
import numpy as np
import matplotlib.pyplot as plt
import line
# 弗雷歇距离求和
def transform(l):
return [list(el) for el in l]
def similarity(l1, l2):
r1 = transform(l1)
print("r1:{}".format(r1))
r2 = transform(l2)
shape1 = np.row_stack(r1)
shape2 = np.row_stack(r2)
print("shape1:{}".format(shape1))
similarity = shape_similarity(shape1, shape2)
print("similartiy:{}".format(similarity))
# print(similarity)
plt.plot(shape1[:, 0], shape1[:, 1], linewidth=2.0)
plt.plot(shape2[:, 0], shape2[:, 1], linewidth=2.0)
plt.title(f"Shape similarity is: {similarity}", fontsize=14, fontweight="bold")
plt.show()
def frechet_distance(
# ->常常出现在python函数定义的函数名后面,为函数添加元数据,描述函数的返回类型,也可以理解为给函数添加注解
# 形参后面加冒号其实是添加注释,告诉使用者每个形参、返回值的类型,这里只是建议,传入其他类型也并不会报错
# 此处若传入的为曲线,则接受的为CurveByLines类
l1: line.Line,
l2: line.Line,
# 节点数,离散化阈值
n_disc_l1: int = 100,
n_disc_l2: int = 100,
# 星号将多个实参合并为一个元组
*,
# 预设的阈值
prec: float = 0.001,
) -> float:
print(l1)
# 输入中,l1、l2为曲线,n_xx为分段数
distance_matrix(l1, l2, n_disc_l1, n_disc_l2)
# 离散化,求距离矩阵(二维数组) 距离矩阵
def distance_matrix(l1:line.Line, l2:line.Line, nd1:int, nd2:int) -> List[List[float]]:
# 此时的l1于l2依旧是curve类
# 保留曲线的起点,在后面将其细分为参数份
ld1 = list(line.discretize(l1, nd1))
print(ld1)
ld2 = list(line.discretize(l2, nd2))
similarity(ld1, ld2)
文章为作者独立观点,不代表股票交易接口观点