【529】MT | 相关算法

Apriori 算法

Geohash 算法

参考：Geohash算法原理及实现
参考：Geohash精度和原理
参考：GeoHash核心原理解析
geohash9: 大约 4m * 4m 的网格
Geohash8: 大约 17m * 17m 的网格

DBSCAN 算法

通过计算空间密度聚类，去除掉噪声
空间邻域就是指距离中心点一定范围内的点的集合
$epsilon$：邻域半径，内部为考虑范围
$MinPts$：最少的点的个数，阈值
参考：密度聚类之DBSCAN及Python实现
参考：DBSCAN密度聚类算法-刘建平
参考：用 scikit-learn 学习 DBSCAN 聚类

　　利用大圆距离计算，需要构建大圆距离矩阵：

　　参考：DBSCAN for clustering of geographic location data

　　参考：官方示例 - Demo of DBSCAN clustering algorithm

结果中为 -1 的点就被认为是噪声点，其他点则为聚类的点
如果只有 -1，说明所有的点都比较离散
如果只有 0，说明这些点很聚集

from math import radians, cos, sin, asin, sqrt
 
def geodistance(lon1, lat1, lon2, lat2): # 经度1，纬度1，经度2，纬度2 （十进制度数）
    """
    Calculate the great circle distance between two points 
    on the earth (specified in decimal degrees)
    """
    # 将十进制度数转化为弧度
    lon1, lat1, lon2, lat2 = map(radians, [lon1, lat1, lon2, lat2])
 
    # haversine公式
    dlon = lon2 - lon1 
    dlat = lat2 - lat1 
    a = sin(dlat/2)**2 + cos(lat1) * cos(lat2) * sin(dlon/2)**2
    c = 2 * asin(sqrt(a)) 
    r = 6371 # 地球平均半径，单位为公里
    return c * r * 1000

# 构建距离矩阵
# 每个点之间的 great_circle 距离

def get_distance_matrix_from_array(points_array):
    num = len(points_array)
    distance_matrix = np.zeros((num, num))
    for i in range(num):
        for j in range(num):
            if i == j:
                continue
            lng1, lat1 = points_array[i]
            lng2, lat2 = points_array[j]
            dis = geodistance(lng1, lat1, lng2, lat2)
            distance_matrix[i][j] = dis
    return distance_matrix

from sklearn.cluster import DBSCAN

distance_matrix = get_distance_matrix_from_array(coords)

clusters = DBSCAN(eps=2, 
                  min_samples=2, 
                  metric='precomputed'
                 ).fit_predict(distance_matrix)

Isolation Forest - 孤立森林

将数据按照超平面进行切割，越容易切割出来的点，就越可能是异常点，从而来查找异常值
参考：浅谈孤立森林算法
参考：【异常检测】孤立森林（Isolation Forest）

R Tree 算法

参考：什么是R树？ - 七月在线七仔的文章 - 知乎 https://zhuanlan.zhihu.com/p/62639268
参考：一文详解:什么是B树?
参考：知道什么是B树,那你知道什么是R树吗?

OPTICS 聚类算法

参考：OPTICS 聚类算法原理

层次聚类（Hierarchical Clustering）算法

参考：层次聚类算法的原理及实现Hierarchical Clustering

HDBSCAN 算法

参考：【Python】hdbscan安装失败的解决
- 安装 anaconda，建议通过清华镜像安装
- 安装后可以安装很多 Python 的工具
- 重新打开终端，直接可以使用 conda 命令
- 然后按照参考里面的命令输入即可，conda install hdbscan 成功

convexHull，计算凸包

参考：Scipy空间--计算凸包(convexHull)

# -*- coding: utf-8 -*-

import matplotlib.pyplot as plt
import numpy as np
from scipy.spatial import ConvexHull
##########scipy 凸包################
points = np.random.rand(30, 2)
hull = ConvexHull(points)
plt.plot(points[:,0], points[:,1], 'o')
# hull.vertices 得到凸轮廓坐标的索引值，逆时针画
hull1=hull.vertices.tolist()#要闭合必须再回到起点[0]
hull1.append(hull1[0])
plt.plot(points[hull1,0], points[hull1,1], 'r--^',lw=2)
for i in range(len(hull1)-1):
    plt.text(points[hull1[i],0], points[hull1[i],1],str(i),fontsize=20)


# 得到外边缘线的索引值
hull.vertices.tolist()
# 索引值需要回到第一个值，然后将其收尾相连
# 如果是绘制polygon的话，则不需要