Tianchi-Wifi-Positioning

by drop-out

1st place solution for the Tianchi wifi positioning competition

131 Stars 65 Forks Last release: Not found MIT License 4 Commits 0 Releases

Available items

No Items, yet!

The developer of this repository has not created any items for sale yet. Need a bug fixed? Help with integration? A different license? Create a request here:

赛题回顾

这是一个室内定位问题。给定交易时的环境信息(包括GPS、wifi信息),确定交易所处的商铺。

详情可参见比赛页面

训练集划分

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

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

本地验证时,直接从训练集中拿出最后三天作为验证集。本地验证时不更新特征提取区间(即仍然使用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 |

二分类

二分类方案概述

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

训练

| rowid | 候选 | 特征 | label | | ------ | ------ | ---- | ----- | | 1 | shop1 | ... | 1 | | 1 | shop2 | ... | 0 | | 1 | shop3 | ... | 0 | | 2 | shop1 | ... | 0 | | 2 | shop2 | ... | 1 | | 2 | shop_3 | ... | 0 |

测试

| rowid | 候选 | 特征 | 输出概率 | 预测 | | ------ | ------ | ---- | ---- | ---- | | 3 | shop1 | ... | 0.6 | | | 3 | shop2 | ... | 0.8 | | | 3 | shop3 | ... | 0.9 | √ | | 4 | shop1 | ... | 0.1 | | | 4 | shop2 | ... | 0.9 | √ | | 4 | shop_3 | ... | 0.2 | |

全集候选与负样本抽样

一般的思路是先用规则构造候选,然后在候选集中利用模型输出概率值。这样需要同时兼顾候选集合的

覆盖率
和预测模型的
准确率
,实现上较为复杂。我的模型中,直接选取目标mall中所有的shop作为候选,大大降低了模型的复杂程度。

同时,为了避免训练集数据量过大,可以在训练集中进行样本抽样。具体方法是,保留全部正样本,负样本中随机抽取一定比例加入训练集。实际测试,抽样对于模型的精度影响不大。

特征

标记特征

  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
    型来标示。所以需要提前将wifiid和shopid进行编码。另外,
    PS-SMART
    需要提供类别总数,所以同时还要记录每个mall中含有的商铺个数(即每个mall中最大的label,见
    shop_code.csv
    )。
  4. 分区表存储训练数据。如果为每个mall都单独生成一张训练数据表,那么表会太多,而且不断的生成、删除表,会增加任务提交的排队时间。我们的解决方案是用分区表存储所有mall的训练数据,以mall_id作为分区列。模型训练时可以直接指定分区,这样避免了反复的生成表、删除表。
  5. 结果表分块合并。同时
    union
    太多的结果表会报错。这里将所有的mall分成5个小块,每个块先
    union
    ,最后再统一
    union

模型融合

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

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

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.