Need help with Tianchi-Wifi-Positioning?
Click the “chat” button below for chat support from the developer who created it, or find similar developers for support.

About the developer

drop-out
133 Stars 65 Forks MIT License 13 Commits 1 Opened issues

Description

1st place solution for the Tianchi wifi positioning competition

Services available

!
?

Need anything else?

Contributors list

No Data

赛题回顾

这是一个室内定位问题。给定交易时的环境信息(包括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。训练集和测试集的构造方法图示如下:

训练

| 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 | |

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

一般的思路是先用规则构造候选(核心召回策略包括:附近召回、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
    型来标示。所以需要提前将wifiid和shopid进行编码。另外,
    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)

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.