research-on-frequent-pattern-mining-based-on-hotspot-trajectories

Draft Research Proposal

轨迹热点挖掘的基础概念与公式

1. 关系（Relation）

• 单向关系：$a_i\to b_j$$a_i\to b_j$a_(i)rarrb_(j)a_i \to b_j$a_i\to b_j$ 或 $a_i\leftarrow b_j$$a_i\leftarrow b_j$a_(i)larrb_(j)a_i \leftarrow b_j$a_i\leftarrow b_j$
• 双向关系：$a_i\leftrightarrow b_j$$a_i\leftrightarrow b_j$a_(i)harrb_(j)a_i \leftrightarrow b_j$a_i\leftrightarrow b_j$

2. 并置模式（Co-location）

3. 参与集（Participation Set）

4. 参与度（Participation Rate）

5. 频繁并置（Prevalent Co-location）

6. 轨迹序列（Trajectory Sequence）

• $N=\{n_1,n_2,...,n_k\}$$N=\{n_1,n_2,...,n_k\}$N={n_(1),n_(2),...,n_(k)}N=\{n_1,n_2,...,n_k\}$N=\{n_1,n_2,...,n_k\}$ （轨迹点集合）
• $E=\{e_1,e_2,...,e_{k-1}\}$$E=\{e_1,e_2,...,e_{k-1}\}$E={e_(1),e_(2),...,e_(k-1)}E=\{e_1,e_2,...,e_{k-1}\}$E=\{e_1,e_2,...,e_{k-1}\}$ （轨迹边集合）

7. 轨迹序列集合（Trajectory Sequence Set）

8. 轨迹序列并置（Trajectory Sequence Co-location）

9. 轨迹序列频繁并置（Trajectory Sequence Prevalent Co-location）

10. 轨迹热点（Trajectory Hotspots）

实验原理（Markdown 版）

课题：基于热点轨迹的频繁模式挖掘研究
目标：在保证时空效率的前提下，体系化挖掘 Geo‑Trajectories 数据中的热点路径（Hotspot Trails），并为后续的行为预测与智能推荐奠定理论基础。

1. 轨迹数据建模

• 节点：$v\in V⟺\mathrm{\exists }{p}_i\text{落入网格}{g}_v$$v\in V⟺\mathrm{\exists }{p}_i\text{ 落入网格 }{g}_v$v in VLongleftrightarrowEEp_(i)" 落入网格 "g_(v)v\in V\iff\exists p_i\text{ 落入网格 }g_v$v\in V⟺\mathrm{\exists }{p}_i\text{ 落入网格 }{g}_v$
• 边：$e=(v_i\to v_j)\in E⟺p_k\in g_{v_i},p_{k+1}\in g_{v_j}$$e=(v_i\to v_j)\in E⟺p_k\in g_{v_i},p_{k+1}\in g_{v_j}$e=(v_(i)rarrv_(j))in ELongleftrightarrowp_(k)ing_(v_(i)),p_(k+1)ing_(v_(j))e=(v_i\rightarrow v_j)\in E\iff p_{k}\in g_{v_i},\,p_{k+1}\in g_{v_j}$e=(v_i\to v_j)\in E⟺p_k\in g_{v_i},p_{k+1}\in g_{v_j}$

2. 并置模式与热点路径定义

2.1 并置模式（Co‑location Pattern）

2.2 频繁并置

2.3 热点路径（Hotspot Trail）

• 长度阈值 $k_{min}$$k_{min}$k_(min)k_{\min}$k_{min}$
• 支持阈值 $m_{min}$$m_{min}$m_(min)m_{\min}$m_{min}$

1. $k\ge k_{min}$$k\ge k_{min}$k >= k_(min)k\ge k_{\min}$k\ge k_{min}$
2. 经过该序列的轨迹集合 ${\mathrm{SG}}_H$${\mathrm{SG}}_H$SG_(H)\mathrm{SG}_H${\mathrm{SG}}_H$ 满足 $|{\mathrm{SG}}_H|\ge m_{min}$$|{\mathrm{SG}}_H|\ge m_{min}$|SG_(H)| >= m_(min)|\mathrm{SG}_H|\ge m_{\min}$|{\mathrm{SG}}_H|\ge m_{min}$

3. 三类热点挖掘算法

3.1 NDTTJ — N‑Degree Trajectory Table Join

1. 初始队列：筛出满足 $m_{min}$$m_{min}$m_(min)m_{\min}$m_{min}$ 的一阶边。
2. 连接规则：若 $p_1=(v_1\dots v_r),p_2=(v_r\dots v_{r+1})$$p_1=(v_1\dots v_r),p_2=(v_r\dots v_{r+1})$p_(1)=(v_(1)dotsv_(r)),p_(2)=(v_(r)dotsv_(r+1))p_1=(v_1\dots v_r), p_2=(v_r\dots v_{r+1})$p_1=(v_1\dots v_r),p_2=(v_r\dots v_{r+1})$，则

3. 剪枝：$|\text{new}\mathrm{\_}\text{sg}|<m_{min}$$|\text{new}\mathrm{\_}\text{sg}|<m_{min}$|"new"_"sg"| < m_(min)|\text{new}\_\text{sg}|<m_{\min}$|\text{new}\mathrm{\_}\text{sg}|<m_{min}$ 直接丢弃。
4. 迭代至无新路径或达到 $\text{max\_depth}$$\text{max\_depth}$"max\_depth"\text{max\_depth}$\text{max\_depth}$。

3.2 NDTTT — N‑Degree Trajectory Table Traversal

3.3 TTHS — Trajectory‑Traversal Hotspot Search

4. 多维特征工程

4.1 时间特征

• 平均起始时刻 $\overline{h}={\displaystyle \frac{1}{|\mathrm{SG}|}}\sum _i{h}_i$$\overline{h}={\displaystyle \frac{1}{|\mathrm{SG}|}}\sum _i h_i$bar(h)=(1)/(|SG|)sum _(i)h_(i)\bar{h}=\dfrac{1}{|\mathrm{SG}|}\sum_i h_i$\overline{h}={\displaystyle \frac{1}{|\mathrm{SG}|}}\sum _i{h}_i$
• 时间熵 $H_t=-\sum _b{p}_b{\log }_2{p}_b$$H_t=-\sum _b p_b{\log }_2{p}_b$H_(t)=-sum_(b)p_(b)log_(2)p_(b)H_t=-\sum_{b} p_b\log_2 p_b$H_t=-\sum _b{p}_b{\log }_2{p}_b$

4.2 空间特征

• 欧氏路径长：$L=\sum _{i=1}^{k-1}\Vert {\mathbf{v}}_{i+1}-{\mathbf{v}}_i{\Vert }_2$$L=\sum _{i=1}^{k-1} \Vert {\mathbf{v}}_{i+1}-{\mathbf{v}}_i{\Vert }_2$L=sum_(i=1)^(k-1)||v_(i+1)-v_(i)||_(2)L=\sum_{i=1}^{k-1}\|\mathbf{v}_{i+1}-\mathbf{v}_{i}\|_2$L=\sum _{i=1}^{k-1}\Vert {\mathbf{v}}_{i+1}-{\mathbf{v}}_i{\Vert }_2$
• 空间熵：对经纬度各做 1D 熵并求和。

4.3 语义特征

• 主导 POI：$\arg \underset{c}{max}\text{freq}(c)$$\arg \underset{c}{max} \text{freq}(c)$arg max_(c)"freq"(c)\arg\max_{c} \text{freq}(c)$\arg \underset{c}{max}\text{freq}(c)$
• POI 熵 $H_{poi}$$H_{poi}$H_(poi)H_{poi}$H_{poi}$，衡量类型多样性。

5. 数据流程汇总

flowchart TD
    %% ========== ① 数据清洗 ==========
    A["Geolife .plt<br/>Raw trajectories"] -->|"15-min<br/>Sampling"| B["Cleaned CSV"]

    %% 拆分
    B --> NODES["nodes.csv"]
    B --> EDGES["edges.csv"]
    B --> META["traj_metadata.csv"]

    %% ========== ② 热点挖掘 ==========
    %% ---- Path-table line ----
    META --> PT1["1-degree<br/>Path Table"]
    PT1 --> HT1["NDTTJ / NDTTT<br/>Hotspots"]:::algo

    %% ---- Graph line ----
    NODES & EDGES --> GDB["Neo4j / JanusGraph"]:::store
    GDB --> HT2["TTHS<br/>Hotspots"]:::algo

    %% 合并
    HT1 & HT2 --> M["Merged hotspot set"]

    %% ========== ③ 三维特征 ==========
    M -->|时间映射| TF["Temporal features"]
    M -->|空间投影| SF["Spatial features"]
    M -->|POI映射| PF["Semantic features"]
    NODES --> PF
    META  --> TF

    TF & SF & PF --> EH["Enhanced hotspot table"]

    %% ========== ④ 质量清洗 ==========
    EH -->|"IQR-trim<br/>(length)"| CQ{"滤除极端值"}
    CQ --> FP["Final cleaned paths.csv"]

    %% ---------- 样式 ----------
    classDef algo  fill:#ffe2e2,stroke:#d44,stroke-width:1.3px,color:#000;
    classDef store fill:#e1ecff,stroke:#4682ff,stroke-width:1.3px,color:#000;

高阶语义热点轨迹频繁模式挖掘方案

背景说明

• 发挥三类热点挖掘算法生成路径序列的结构优势（稳定、高覆盖）；
• 基于熵加权构建支持度体系（SU-Support），挖掘更有区分度和语义代表性的热点路径模式；
• 借助自适应算法调度与剪枝，提升效率和表达质量；
• 支持后续 Web 可视查询与 API 接口输出。

建模与支持度构建

三维熵加权支持度定义（SU-Support）

• $H_s^{\prime },H_t^{\prime },H_{poi}^{\prime }\in [0,1]$$H_s^{\prime },H_t^{\prime },H_{poi}^{\prime }\in [0,1]$H_(s)^('),H_(t)^('),H_(poi)^(')in[0,1]H_s', H_t', H_{poi}' \in [0,1]$H_s^{\prime },H_t^{\prime },H_{poi}^{\prime }\in [0,1]$：分别为空间、时间、POI 熵归一化后值；
• $\lambda ,\mu ,\nu$$\lambda ,\mu ,\nu$lambda,mu,nu\lambda, \mu, \nu$\lambda ,\mu ,\nu$：三维惩罚系数，控制熵惩罚强度；
• 当三个熵值越高，路径越不稳定，SU 值越小。

差分进化优化权重系数

• 目标函数：

• $\text{Coverage}$$\text{Coverage}$"Coverage"\text{Coverage}$\text{Coverage}$：SU 前 K 模式覆盖所有轨迹的比例；
• $\text{Redundancy}$$\text{Redundancy}$"Redundancy"\text{Redundancy}$\text{Redundancy}$：前 K 模式之间的 Jaccard 平均相似度；
• $\theta$$\theta$theta\theta$\theta$：SU 阈值，保留高质量候选集；
• $\alpha$$\alpha$alpha\alpha$\alpha$：权衡因子，推荐值为 0.7。

自适应算法调度机制

核心思想：

• NDTTJ 适合稀疏轨迹结构（连接型 Join）
• NDTTT 适合中等密度（深度优先 Path-Growth）
• TTHS 适合稠密区域（图结构下 DFS 遍历）

实现方式：

1. 对每条路径计算空间密度：

2. 设置分界阈值 ${\rho }_l,{\rho }_h$${\rho }_l,{\rho }_h$rho _(l),rho _(h)\rho_l, \rho_h${\rho }_l,{\rho }_h$：

3. 可训练决策树/聚类划分 $\rho$$\rho$rho\rho$\rho$ 区间，动态微调

模式构建与双层消歧流程

步骤一：SU-FP-Tree 构建

• 将 path 序列构建 FP-Tree，使用 SU 值作为浮点计数；
• 前缀遍历生成候选模式集 ${\mathcal{P}}_1$${\mathcal{P}}_1$P_(1)\mathcal{P}_1${\mathcal{P}}_1$

步骤二：PrefixSpan 补充

• 使用 Spark MLlib 执行 PrefixSpan，补充遗漏的序列模式 ${\mathcal{P}}_2$${\mathcal{P}}_2$P_(2)\mathcal{P}_2${\mathcal{P}}_2$
• 最终模式集 $\mathcal{P}={\mathcal{P}}_1\cup {\mathcal{P}}_2$$\mathcal{P}={\mathcal{P}}_1\cup {\mathcal{P}}_2$P=P_(1)uuP_(2)\mathcal{P} = \mathcal{P}_1 \cup \mathcal{P}_2$\mathcal{P}={\mathcal{P}}_1\cup {\mathcal{P}}_2$

步骤三：超图 k-Truss 精炼

• 将模式转为超边图结构 $\mathcal{G}$$\mathcal{G}$G\mathcal{G}$\mathcal{G}$，节点为热点格点；
• 执行 $k$$k$kk$k$-truss 分解（$k=\lceil |H|/2\rceil$$k=\lceil |H|/2\rceil$k=|~|H|//2~|k = \lceil |H|/2 \rceil$k=\lceil |H|/2\rceil$）保留强连通模式

步骤四：信息密度增益剪枝

• $|{\text{POI}}_H|$$|{\text{POI}}_H|$|"POI"_(H)||\text{POI}_H|$|{\text{POI}}_H|$：该路径涵盖的 POI 类别数目
• 使用阈值 ${\tau }_G$${\tau }_G$tau _(G)\tau_G${\tau }_G$ 保留高 Gain 模式

实验流程与模块落地