/Tianchi-Wifi-Positioning

1st place solution for the Tianchi wifi positioning competition

Primary LanguageJavaMIT LicenseMIT

赛题回顾

这是一个室内定位问题。给定交易时的环境信息(包括GPS坐标、wifi信息(bssid/信号强度/是否连接)、用户id)，确定交易所处的商铺。

详情可参见比赛页面。

训练集划分

在训练集划分上，我简单的将训练数据的最后七天划分为训练区间，此前的作为特征提取区间。

线上预测时使用全部数据作为特征提取区间。

本地验证时，直接从训练集中拿出最后三天作为验证集。本地验证时不更新特征提取区间(即仍然使用7.1-8.24作为特征提取区间)，降低了实现上的复杂性。

时间
训练集-特征提取区间 7.1 - 8.24
训练集 8.25 - 8.31
线上测试集-特征提取区间 7.1- 8.31
线上测试集 9.1 - 9.14
本地训练区间 8.25-8.28
本地验证区间 8.29-8.31

二分类(Point-wise)

二分类方案概述

二分类方案，即针对测试集中的每一条记录，构造候选shop集合，用模型输出每个候选的概率值，然后选取概率值最大的作为该条记录的预测shop。训练集和测试集的构造方法图示如下：

训练：

row_id 候选 特征 label
1 shop_1 ... 1
1 shop_2 ... 0
1 shop_3 ... 0
2 shop_1 ... 0
2 shop_2 ... 1
2 shop_3 ... 0

测试：

row_id 候选 特征 输出概率 预测
3 shop_1 ... 0.6
3 shop_2 ... 0.8
3 shop_3 ... 0.9 √
4 shop_1 ... 0.1
4 shop_2 ... 0.9 √
4 shop_3 ... 0.2

召回：全集召回与负样本抽样策略

一般的思路是先用规则构造候选(核心召回策略包括：附近召回、wifi召回、用户常去商户召回)，然后在候选集中利用模型输出概率值。这样需要同时兼顾候选集合的覆盖率和预测模型的准确率，实现上较为复杂。我的模型中，预测时直接选取目标mall中所有的shop作为候选，避免了召回策略覆盖不足的问题。

同时，为了避免训练集数据量过大，可以在训练集中进行样本抽样。具体方法是，保留全部正样本，负样本中随机抽取一定比例加入训练集。(To-Do: 负样本的抽取可以采取分层策略，加大核心召回样本的权重(如通过wifi召回的商户)，同时保证一定比例的随机样本。这种分层策略，可以使模型对于打分处于较高区间的商户给出更准确的排序结果。)

特征

标记特征

  1. 记录中是否有连接的wifi
  2. 记录中是含否有null
  3. 记录中wifi与候选shop出现过的wifi重合的个数

"总量-比例"特征(共现特征)

  1. 该mall的总历史记录数、候选shop在其中的占比
  2. 该user的总历史记录数、候选shop在其中的占比
  3. wifi历史上出现过的总次数、候选shop在其中的占比
  4. 在当前排序位置(如最强、第二强、第三强...)上wifi历史上出现过的总次数、候选shop在其中的占比
  5. 连接的wifi出现的总次数、候选shop在其中的占比
  6. 经纬度网格(将经纬度按不同精度划分成网格)中的总记录数、候选shop在其中的占比

对于特征3、4，每条记录中的10个wifi由强到弱排列，可生成10个特征。

差值特征

  1. wifi强度 - 候选shop的历史记录中该wifi的平均强度
  2. wifi强度 - 候选shop的历史记录中该wifi的最小强度
  3. wifi强度 - 候选shop的历史记录中该wifi的最大强度

三个wifi强度差值特征，按照信号强度由强到弱排列，可生成10个特征。

距离特征

  1. 与候选shop位置的GPS距离(L2)
  2. 与候选shop历史记录中心位置的GPS距离(L2)
  3. 与候选shop对应wifi信号强度历史均值的距离(L1、L2)

其他特征

特征中还包括多分类的输出概率。另外，还有一些利用规则定义的距离特征，这里不再详述。

多分类

我们的方案中采用的多分类是基于麦芽的香气开源的多分类。每个mall一个模型，经纬度和wifi强度作为特征(每个wifi_id的强度都是一个特征)。

线上赛的多分类是很多队伍头疼的地方，主要面临以下几个困难：

  1. SQL不支持循环，要写出将近500个mall的多分类脚本；
  2. PAI上的三个GBDT算法，GBDT、xgboost、PS-SMART中，只有PS-SMART支持多分类，而PS-SMART跑起多分类来特别慢；
  3. wifi_id太多，转化成数据表有困难。

针对这三个难点，我们用以下方案来解决：

  1. 使用python的文本替换(%)批量生成每个mall的脚本(见generating_sql.py)；
  2. 将所有mall的脚本拆开来，放到很多个窗口中，同时跑(数加最多支持同时开启16个窗口)；
  3. 只选取在训练集中出现过20次以上的wifi，并用kv格式存储数据。

此外，还有一些实现上的细节，列举如下：

  1. 分离信号强度为null的数据。对于信号强度为null的那些数据，强度不论填成多少，对于模型都是个干扰。所以直接去除这一部分数据，用剩下的数据来训练。
  2. wifi强度变换。在kv格式中，没有出现的wifi在算法中会默认识别成0。注意到，wifi信号强度的定义，0为最强。为了使特征数值和实际意义相一致，我们对wifi强度进行了f(x)=min(125-x,0)的变换，使wifi强度转化为0-125之间的数值，125为最强，0为最弱。
  3. shop编码和wifi编码。kv格式中，label和特征都必须用int型来标示。所以需要提前将wifi_id和shop_id进行编码。另外，PS-SMART需要提供类别总数，所以同时还要记录每个mall中含有的商铺个数(即每个mall中最大的label，见shop_code.csv)。
  4. 分区表存储训练数据。如果为每个mall都单独生成一张训练数据表，那么表会太多，而且不断的生成、删除表，会增加任务提交的排队时间。我们的解决方案是用分区表存储所有mall的训练数据，以mall_id作为分区列。模型训练时可以直接指定分区，这样避免了反复的生成表、删除表。
  5. 结果表分块合并。同时union太多的结果表会报错。这里将所有的mall分成5个小块，每个块先union，最后再统一union。

模型融合

我们采用简单的加权融合方案，将我的模型和队友的模型输出概率加权融合，然后按概率最大值选取预测商铺。

多分类没有直接参与模型融合，而是作为特征输入到二分类模型中。

To-Do

  1. WiFi文本挖掘
  2. DeepFM替代部分手工特征(如WiFi embedding-lookup+商户embedding-lookup)