精读Crowd-Flow Graph Construction and Identification with Spatio-Temporal Signal Feature Fusion_crowdflow

摘要

本文的目的是为了识别城市里人流，作者团队提出了一种更加细粒度的方案，即从智能手机中收集到WIFI和地磁干扰等信号，
通过对比人群中手机WIFI信号和电磁干扰的时空序列图来判断人与人之间是否经过了相似的路径，从而判断是否属于一个人流。
作者设计的方案可以快速来检测识别人流。
1
2
3

介绍

作者通过对全面的时空信号的提取与应用，提取了若干信号特征并结合相似度。简单的来说作者做了什么东西呢，我们都知道数据融合，利用手机可以收集到各种各样的信号特征，但以前我们只是对单一数据特征进行分析，比如利用手机收集WIFI信号的强弱，以此来构建时空特征图来对WIFI信号特征进行分析，但由于现如今对数据的认识以及分析概念的不断延伸，要研究一个东西我们不光可以只利用其最显著的特征。还可以利用更多的辅助特征来加深我们物质的理解。

用本文的例子来说明，我们要怎么识别两个人的行走路径大体相同，从而判断他们属于一个人流呢注意这里的人流是指具有相同移动路径的人群。如果两个人从A到B移动的路径大体相同，那么他们就属于一个人流我们可以通过WIFI信号随时间的强弱来判断一个人经过的周围信号源，如果两个人的信号强弱大小起伏一致，那么他们很有可能经过相同的路径，信号源对其WIFI信号的影响是相似的。

但是我们仔细想，只分析WIFI信号的话维度太低了，我们并不能把WIFI信号完全投影到一个具体的环境中去。在城市这种嘈杂的环境，可影响因素太多了，如果单单分析一个WIFI信号，那我们得想办法去噪，这样思考下去没完没了。有可能你会想出一个很好的解决方法，但这样的数据还是不能够信服的。按照以往的思考，要有多维度的参考特征，一个事物的形象才会变得越来越具体化。多维度的形象总是令人容易理解的。如果只划一个正方形，那我们可能只会了解其在二维世界中的形象。但如果这个正方形变成正方体，我们是不是就能够清晰直观的了解其在三维世界的形象。这时候我们在引入地磁信号的概念，手机会受到各种无线信号以及其他波的干扰，收集这些干扰一样做成随时间变化的时空序列图表。由此，我们从一维变成了二维，多维度使得人流的检测更为准确。

概念，定义以及数据集

定义一：人流 （Crowd-Flow）：在城市/室内环境，两个或大于两个人具有相同或相似移动路径和方向被称为人流。

为了量化和建模人流，作者又定义了人流相似度。

定义二：人流相似度( Person-to-Person Co-Flow Similarity).用人流相似度$$\Phi \left(i,j\right)$$来丈量两个人路径是否具有相似性，这里应该注意Φ(i, j) ∈ [0, 1]。当Φ(i, j) = 1 说明两个人i和j具有一模一样的移动方向和路径。

如果两个人的移动路径相似，那么两个人之间便可以形成人流图。

定义三： 人流图（Crowd-Flow Graph) .我们把i这个人看做一个顶点,用u_i 表示，如果i和j两个人都有相同的移动状态（这里指共流）我们把i与j的状态看做边e_ij。
CFID会形成这样的图G= (V, E) ，其中V ={ u_i }.。 E ={ e_ij } 用来寻找人流 F 。
这里特别规定了 $${\delta }_i是用户u_i的深度$$
假设这里的图也是没有闭环的。一个人不能与自己形成人流。
而且人流F更倾向于往更深图的方向延伸而不是连接不同的人流。

定义四： 图流（Graph Streaming) .图流被定义为一组已识别的边或者点。
$$\text{S}=\left\{e^1,...,e^n\right\}(1)$$
这里的e^t ∈（1 ≤ t ≤ n）代表第t个到达人流的边。

又让A_ij（A_ij ≥0）（A_ij为n个人对应形成的边矩阵的邻接增广矩阵的元素）代表 i 和 j 两个人边的个数。

e^ij ∈ E 能在流S 中被找到 A_ij 次。

为了量化人流，还需要图的模块度化。
什么是模块度化呢？

在社区发现算法中，几乎不可能先确定社区的数目，于是，必须有一种度量的方法，可以在计算的过程中衡量每一个结果是不是相对最佳的结果。

定义五： 模块度（Modularity） .用来衡量一个社区的划分是不是比较好的结果。一个相对好的结果在社区内部的节点相似度较高，而在社区外部节点的相似度较低
转载链接: 详细了解图的模块化.
以此来度量随机社区划分结果。
文中对模块化的定义。δ_i与δ_j为顶点的深度。I_ij表示i和j是否在同一个人流。如果I_ij = 1则两个人在一个社区。I_ij = 0则不在一个社区。

基于以上概念概念，作者定义了身份识别

*定义六： 人流识别（Crowd-Flow Identification简称CFI） .
假设用b_i^l来表示用户i是否属于人流l
如果b_i^l = 1则i在社区l。b_i^l = 0则不在。
通过用户信号收集，作者把WIFI信号和地磁信号分别表示为
$$\left[W_i,M_i\right]$$
用
$$f\left(i,j,W_i,W_j,M_i,M_j\right)$$
表示两个人的共流函数。

$$\Phi \left(i,j\right)$$表示从收集到的信号判别相似度。
$$\Gamma \left(\Phi \left(i,j\right)，j\right)$$
函数来判断两个人是否在一个社区。

我们的目标是要识别出人流，最终最大化Q来检测我们人流分布是否让人满意。
最终目标函数为

以上就是这篇文章的目的，接下来都是仔细的讲述如何处理手机WIFI信号与地磁特征信号。

手机信号预处理

通过手机的API（安卓），接入口可以获得以下的信息。
$$\left[MAC,RSSI,SSID，Timestamp\right]$$
SSID是服务设置标识符.
对于每个用户，我们把
是在时间t时由k索引AP的RSSI。由第三方绑定的移动ap根据其MAC地址中与供应商相关的组织唯一标识符(OUIs)过滤。RSSI值由dBm转换为mW来区分强弱信号。

WIFI共流特征提取与比较

该图为提取的路人A和B的WIFI信号特征共流图，对于检测到的AP集(滑动窗口T内AP的并集)

作者设计了以下空间度量来评估两个用户的相似性
简单来说就是利用三个方面参考权重来规定一个总的相似度。
Tanimoto 相似度：（科普链接.）
随着滑动窗口T的移动，在每个时间段都能检测到AP元素（所有可用的MACs）如果检测到信息比特，I_i[k]为1，否则为0.根据Tanimoto相似度公式

相似度越高，则说明采用该种计算方法的相似度越好。
** Adamic-Adar 相似度:**（ 科普链接.）

其中P^k为AP k的受欢迎程度，表示为P^k在其中占有的比例。
高效特征比较
除了比较AP集合以外，作者还考虑从AP信号序列来比较用户的动态模式，从而能继续从更深度的方向对WIFI序列进行考量。
这里作者为了促进WiFi序列比较，我们利用LB Keogh边界（LB_K）链接: 科普链接.，可有效返回动态时间规整在线性时间的两个时间序列之间（DTW）距离的下限。
算法1给出了描述

对此，我们令$${\text{W}}_i^k=\left[W_i^k(t-1),...，W_i^k(t)\right]$$为一个人的WIFI AP k在T时间滑动窗口WIFI序列。
LB_K边界全局约束

其中 id_i和id_j是两个指数级翘曲路径。P是预定义的路径约束。

紧接着LB_K沿着路径寻找上下界值u和l。（6-7行）
紧接着返回一个下限测量值 LB_Sum.（8-12行）
最后如果LB_K没有低于正向阈值。我们找了LB_K（15行）

注意，计算LB_K的复杂度与输入的WiFi序列长度成线性关系。但这里我们只计算需要的部分，多余的直接删去就好。

如果平均LB K足够小，我们进一步形成一个度量，得到用户i和j的WiFi序列之间的相似性

作者选择了两个用户共享的三个最强的APs(在RSSI方面)进行上述比较，因为它们更容易被检测到，并导致更长的测量序列，以便更好地区分。

最后将上述三个相似度混合起来（（4）（5）（8））可以得到。

地理共流特征提取与比较

除了WLAN之外，由于钢筋建筑的存在，城市/室内场地通常会混杂着各种地磁异常。如图所示，当用户A和B使用手机上的磁强计沿同一路径移动时，会捕捉到类似的磁性序列，这意味着人群的时空共存。

CFid不是专注于单个的磁读数，而是基于时空测量的序列获得更少的模糊模式。此外，将地磁的深度移动相关特征与WiFi的区域指示相融合，增强了CFid的精细精度，以及对抗外部和环境干扰的健壮性（实验可以看出）

上图显示了用户A和用户B在同一流中行走时相似的磁读数谱图。由于它们的步速、人体运动和转弯都在相同的行走路径上，地磁可能表现出相似的移动特征。

为了量化这种光谱特征,我们在磁序列进行快速傅里叶变换(我们经验设置窗口ω= 5 s),并提取共有11个光谱特性。

我们用

代表11个光谱特征。将两个人的光谱特征进行比较可以得到。

上面是从光谱特性入手的，我们再从时间特性看。
与在粗粒度的WiFi信号上应用LB_K约束不同，高采样率(通常是100Hz对1Hz的WiFi)和更多特征的磁性读数需要快速但细粒度的相似性度量。
具体地说，作者在CFid中设计了一个快速动态时间翘曲(DTW)

这里M(T)定义未给出，但据我理解为特征关于时间的序列。
每个读数M（t）减去μ，然后通过σ进行归一化。

接下来将地磁和时间相似度混合。

然后,把方程式(9)和(11),混合相似性Φ(i, j)统一计算得到。

β是一个可调整权重参数。

图4（a）展示了数据集A的一个案例，该案例研究的平均共流检测(CFD)精度与所选地磁特征的数量(带标准差)在这种情况下，我们进行了5种不同的检验试验来求其均值和方差。当特征个数较小时，由于可识别信息较少，精度不高。当选择更多的特征时，准确性会提高，但同时也会受到一些噪声信号的影响。为了反映这种权衡，我们选择了JMI默认排名前7的特性。

图4(b)为所选择的光谱特征JMI，为每个特征被选择的概率数据集a中的3个典型案例，作者进行10次排列和特征选择，评估所选特征的概率。从高阶统计(如指数9的峰度)可以看出，由于用户活动自由度和空间磁场多样性可能不同，磁场特征可能会有所不同。

接下来算是一段小重点了。
由于实际中的人群流动态问题，作者将识别问题转化为一个图流聚类问题，包括快速检测和边缘构造。
如果相似Φ(i, j)的两个用户找到足够高。我们设计了自动学习自适应参数化该决策规则，并据此进行快速的共流边缘检测。

当CFID初始化以后，可以利用affinity propagation clustering（APC）
科普链接.
利用之前的参数

在初步划分的基础上，作者发现了流内相似性的潜在统计量，从而在没有明确标记的情况下获得了一个大的人群流图。具体来说，我们找到了平均值Φ和标准偏差σ所有共同的相似之处。

基于上述APC过程中发现，又可以进行快速边缘检测。

图5（a）显示了一个典型的人群分析场景3,000平方米的办公楼。

我们的CFI的基本思想如下。 从传入边缘到达并以顺序和随机的方式进化机会相遇的动态带来的秩序用户，我们考虑动态图形流的设置这样每个边缘仅被检查一次。 回想一下期望将流内边缘与流间比较的（Def.5）。 因此，流内边缘更有可能增加在可能发生的人际互动之前确定的人群流的程度
由于程度过高而将流量分开。 合并较小人数较多的人群加强了这种增加。然后依次检查边缘以检查程度更新并降低整体复杂性。

算法2展示了流式传输时的聚类过程
我们首先初始化人群如果尚未为其分配用户，则为每个用户分配（5-8行）。
然后，CFid分别更新了两个关键的数值，用户深度δ和人流大小C。（10-11行）
如果两个人流还不够大，CFid会将用户从小人流流入大人流。（12-20行）
如果两者的人流具有相同数量的用户（顶点），我们将一个用户分配给另一个用户流并更新边缘。 所有的边缘处理后，最后的CF集返回结果。

如作者所描述，该算法的好处为
灵活：将动态流识别转换为一个图流问题，允许检测到的边以随机顺序一个接一个到达。
通过这种方法，可以由多个处理器/机器进行紧密度检测，然后产生的边缘可以动态馈入，使CFid在动态流分析中具有灵活性。

高效如算法2，每个流化边缘只被处理和检查一次，因此计算复杂度与边缘数呈线性关系。
可识别能力

实验部分

从总共50名志愿者（年龄：23〜30;高度：155〜180cm; 47位男性和3位女性）步行的痕迹。每个跟踪收集范围为15s（公寓）至30分钟（大型购物中心），具体取决于测试网站。对于数据集B和C，我们模拟了人群流在一段时间内有16个用户随机行走的场景，形成跟随随机航点的不同人群
有休息的流动模型[14]。对于所有数据集，我们不假设步行速度恒定，参与者以自己惯常的速度（设备握持姿势可能会有所不同）网站。志愿者要么贴上人群流的真相（ID）自己明确或通过相互隐式
蓝牙低功耗检测。为了进行全面的敏感性/部署评估，我们进一步利用来自50名志愿者的另外332条步行痕迹。特别是其中200人形成了多个人群（最多10;至少进行4次以进行敏感性分析），而
其余的用于设备依赖性评估。对于算法2，我们根据经验将Cmax设置为10。响应度（数据集A），采样频率设置为1HzWiFi的窗口大小T = 5s，磁性的ω= 5s读。虽然一些初步的信号特征处理和
可以在其智能手机上进行过滤，CFid核心算法在装有Intel的PC服务器上运行i7-8700K 3.7GHz，16GB RAM和Windows 10。

表1展现了数据集A,B,C上的性能。

通过对3个数据集的不同测量场景进行分类，我们还在图7中展示了性能。我们还观察到公寓建筑和办公室的识别程度更高，因为那里的用户流动性比其他地点受到更大的限制，导致较弱的衍生模式。尽管存在这些差异，一般来说，CFid在不同的测量环境下都能达到很高的精度(通常超过92.5%)。

图8提供了数据集A上CFid混淆矩阵的进一步细节，验证了其准确性。

模块化的时间动态。 我们还说明了使用数据集A的图9中的模块化动态。24位用户选择以评估其人群的模块化，流程图。 可以看到，所有涉及的模块用户逐渐增加然后减少，显示出他们的人群形成的时间动态（大约3s）然后消失（大约13秒）。

作者还研究了CFid的敏感性到各种设置的CFD决策边界：

图10显示了CFD性能与决策参数α的关系（式（17））。 随着α的增加
TNR增加而TPR减少，表明CFid的敏感性和适应性。 较小的α表示a更严格的标准，导致较低的TNR和较高的TPR，而较大的α表示以较高的TNR为代价的公差。 为了平衡这两者，我们选择α= 2.4。

图11显示测量姿势和外部干扰的影响在智能手机磁力计读数上。我们测试传统设备握持姿势，变化的步行速度（快25％或比正常情况慢），用手摇动移动设备，内裤口袋里有没有钥匙。对于测试用例
磁铁，我们将设备主体与智能手表相连里面有一块强磁铁的充电座（幅度增大放大6.94倍）来模拟用户不小心遇到的情况带上一块磁铁（或被磁化的物体）。我们还进行了在移动的电梯附近进行类似的验证（样本大小相同）评估外部磁干扰的影响。显然，可能会引入不同的姿势/手势更多样化的阅读。传统的设备固定可实现CFI准确度为98.53±1.05％。带钥匙/磁铁或移动附近的电梯，磁力计的灵敏度可能会改变并导致精度差异。尽管有一些抵消，我们找到整个磁强度序列的整体形状被保留。 CFid检索归一化且鲁棒的时空模式以进行识别，这些模式没有价值差异。更快的收集速度可能会导致某些功能某些测量中的损耗。不过，CFid专注于融合那些差异最大的特征，因此仍能准确识别输入序列（通常> 90％）。

图12显示了CFI精度（带有标准偏差）与公式中的权重β的关系。 （12）。随着β的增加，精度会提高，然后下降，显示ΦW（i，j）与ΦG（i，j）之间的权衡。 稍微小β表示地磁的重要性略高由于其更细的粒度，但是β太小过分强调磁力计会导致过度敏感和波动的身份。 考虑到上述权衡取舍，我们在一般设置中选择β= 0.45。

图13显示了AP的影响发现有关CFI准确性的AP（具有标准偏差）。我们随机删除一些AP，以评估CFid的性能下降。 显然，检测到的AP越少，CFid可能具有较低的精度。 但是，因为CFid是
根据WiFi和地磁的共同决定，仍然可以达到稳定的性能。

我们已经招募了志愿者研究9种不同设备对CFI准确性的依赖性。具体来说，我们根据9个相同人群中共有108条WiFi /地磁迹线编队（在相同的步行路径上），每个设备该模型为每个流评估贡献12条迹线。如图所示在图14中，我们选择了几种智能手机型号。不同识别精度主要来自芯片组硬件中的灵敏度差异，因此准确性会有所不同手机型号。但是，CFid显示总体良好设备（包括向后）兼容性。
•计算开销：图15显示了计算CFid的开销。由于减少了计算量，快速的CFI（第五节），我们的效率提高了30％以上比没有便利的CFid改善（不减少）和传统的频谱聚类（Trad。Cluster。）[18]。在通常，CFid会导致总体上较低的计算开销，因此适应大型CFI方案。
•能源效率：图16显示CFid取平均值耗电量仅为27.75mW（三星Note 5为一个示例），以及移动设备的总消耗平均仅增加4.21％。我们的真实测试痕迹显示最长的激活持续时间（在50参与者）要30分钟。其相应的能耗约为13.8mWh，小于0.12％注5的总电池容量（11.1Wh）。因此，CFid是高效节能，占地面积小在手机上。其他移动平台定性展示类似的结果（因此省略）。总之，平均而言，CFid仅消耗25.1347±4.1758mW，总体而言电池上的额外能量为4.37±1.8924％（高于正常使用量）我们使用的Android平台。