论文学习笔记:High-level pattern-based classification via tourist
walks in networks , 该论文介绍了一种基于网络的游客漫步的高级数据分类技术

1. 训练过程简述

整体思想是, 训练过程先形成一个网络, 而预测过程则是, 新数据进入网络, 最接近该网络原始的内部模式和网络结构的插入位置, 作为该数据的标签.

论文概览

what's Tourist walk?

• Given a set of cities, at each time step, the tourist (walker) goes to the nearest city that has not been visited in the past l time steps. It has been shown that tourist walk is useful for data clustering [8] and image processing [3].
• Each tourist walk can be decomposed in two terms:
  • (i) the initial transient part of length t and
  • (ii) a cycle (attractor) with period c

Tranning phase

• 训练阶段还是先构建网络, 利用\(KNN和\epsilon-radius\)的方法

Classification phase(main idea)

1. 分类方法融合

   1. 将传统的机器学习方法(称为low-level classifier)
   2. 和基于网络的high-level classifier结合成如下公式:
   3. 

2. high-level classifier的主要思想就是使用了tourist walk方法.

   • 这里引出了tourist walk的两个变量
   • transient length:is the number of vertices that the tourist visits before it gets trapped in an eternal loop
   • cycle length: denotes the number of different vertices that it visits once it enters the eternal loop
   • memory length \(\mu\): 游客漫步的内存大小(行走长度).

3. 高级分类器的分类函数:

   • 
     1. $H_i^{(j)}: 讲顶点i分类到j类的打分 $
     2. $ \mu_c^{(j)}: 顶点在j类区域进行游客漫步的临界存储长度 $
     3. \(K_H: 归一化因子, 保证分类器的模糊性.\)
     4. \(w_{inter}^{(j)}(\mu): 是一个参数, 表示基于不同的游客漫步的长度\mu, 那么游客漫步的影响有对应的参数。\)
     5. \(T_i^{(j)}(\mu): 表示transient\space length的函数\)
     6. \(C_i^{(j)}(\mu): 表示cycle\space length的函数\)
     7. \(w_{intra}^{(j)}(\mu): 表示transient\space length的参数\)
     8. $C_i^{{(j)}(\mu)和T_i}{(j)}(\mu)的参数之和=1, 一个节点在一个类区域里边的游客漫步有两个过程,暂时过程和循环过程 $

4. 更为详细的

   • \(T_i^{(j)}(\mu)=1-\Delta t_i^{(j)}(\mu)p^{(i)}\) :

   • \(T_i^{(j)}(\mu)=1-\Delta c_i^{(j)}(\mu)p^{(i)}\) :

     • \(其中\Delta t_i^{(j)}\in[0,1]: 表示transient\space length长度的变化\)
     • \(其中\Delta c_i^{(j)}\in[0,1]: 表示transient\space length长度的变化\)
     • \(p^{(i)}\in[0,1]: 表示j类中数据占总数据的比例\)

5. 其中

- 一个节点插入以后区域j的平均transient length-节点插入之前的平均长度
- 分母是各个区域的求和, 用作归一化

6. 参数的细节

• 求的是cycle length的方差/ (transient length的方差+cycle length的方差+2)

7. 参数