这是一个Kaggle上的比赛,由俄罗斯公司Avito举办。Avito是一家类似Craigslist/58同城的网站,上面有很多广告。有些广告主,为了增加自己广告的曝光率,会一条广告,重复发放。Avito公司举办这个比赛的目的希望构建一个模型,检测两条广告是否重复。训练和测试的样本各包含300万和100万的广告对(两条广告),训练目标就是对这些样本进行二分类:是否重复。详细信息见Avito duplicate ads

比赛所给数据包含很多字段,有文本类型的,如广告标题、描述,有category类型的,如广告分类、地理位置,有半结构类型的,如广告属性(键值对,以json格式存储),有数值类型的,如商品价格。每个广告还附带若干张图片。由于字段丰富,且非常异构,包含诸如文本、图片等原始数据,特征工程的重要性就显得尤为突出。从比赛结束后的分享也可以看出,模型ensemble带来的提升,是有的,但远不如大量、有效的特征来得多。下面对这次比赛,排名较高的选手的模型和特征方案,做一总结。

模型

主流模型还是基于Boosting的决策树模型(XGB),辅以NN、LR、ET、RF等模型,做ensemble。ensemble主要使用的是stacking。为了保证ensemble起到效果,往往会将特征划分为多个子集,并将这多个子集放入多个模型进行训练,将模型输出结果(概率值)作为下一层模型(主要是XGB,RF)的输入。这样,会产生M(特征子集个数) * N(meta model个数)个模型。为了保证不同模型“好而不同”,特征子集可以通过逐渐从全集中剔除一部分特征形成。类似于阿里比赛的清华大学组的方案

另外值得一说的是,比赛的第二名TheQuants,对title,description,json这些文本字段中相同的、不同的单词,分别构造BOW的onehot表示,并喂给NB,SGD模型,将模型输出作为特征进一步学习。我在比赛中也考虑了这类特征,做法类似,但使用的是FM模型,有效果(.001),但是不够明显。到底哪个模型更能从BOW这类稀疏的编码中挖掘在信息、NB和FM如何和XGB进行组合,还有待实验检查。

特征工程

特征工程在这次比赛中扮演了至关重要的角色。从论坛公布的方案来看,前几名的特征总数都在500+。主要分为以下几个部分:

  • 基础特征:如locationID,metroID是否相同,price差值,categoryID onehot特征等
  • 文本特征:文本距离度量特征,ngram(char和word两种level)特征,特殊字符特征,TF-IDF等VSM特征以及相应的降为特征(SVD,PCA,LDA等),BM25特征,Word2Vec特征(使用Word Movers’ Distance)
  • BOW特征:之所以单列出BOW特征,是因为这类高维、极其稀疏的特征,难以用XGB直接进行处理,需要借助NB、LR、SGD等简单的线性模型进行处理。FM也可以。
  • 图片特征:RGB统计特征,histogram特征,图片是否相同(MD5),hash特征(phash,dhash,ahash),SIFT特征,BRISK特征,SSIM,MSE特征,VGG net,Inception-v3特征
  • attrsJSON特征:按照不同的JSON key值,构建onehot特征
  • 地理位置特征:将lon,lat通过在线地图服务(GoogleMap,OpenStreetMap)转换成城市(相当于聚类),或者使用dbscan,kmeans手动聚类
  • cross column/row特征:比如title_1和description_2的匹配特征(cross column),当前商品所属图片在所有样本中的出现次数(cross row)等
  • data leakage特征:这类特征争议比较大,但是确实有效。第二名TheQuants发现,将itemID有overlap的样本(比如(id1, id3)与(id1, id2)有overlap)聚类,类的大小能够很大提升AUC(.003-.004),解释是,越大的类越倾向于不是冗余的;另外,有的组发现,itemID是和时间相关的,所以用itemID的差值和比值作为特征,也带来不小提升

特征工程比较考验一个人对领域知识的了解程度,例如这个比赛,由于是俄罗斯公司举办,对俄语有所了解的选手,更能发现潜在的特征。根据论坛上的讨论,有的选手发现,title和desc中存在很多拼写错误,这些错误甚至可能是广告发布者为了躲避审查故意拼错的。另外,对文本、图片的一些基本特征抽取方法的了解也是必要的。特征抽取过程,其实就是一个头脑风暴的过程,我们不应该把自己局限在因果关系上,只抽能导致结果的特征,相关关系的特征也可能会有很好的效果。例如我当时在抽取attrsJSON特征是,只对key:value计算了Jaccard距离,而没有对key直接计算Jaccard距离。后者更像是一个相关关系,但是可能也会带来AUC的提高。换一个角度来说,特征抽取既要从人类的思维出发(我们人类是怎么判断两条广告是否重复的),也要从数据出发(数据中能抽出哪些特征,就都试一试)。

文本特征

可用的距离度量有:

  • 基于VSM:cosine similarity,euclidean dist
  • 直接应用于字符串:Levenshtein dist(包含I,D,S三种操作),Damerau-Levenshtein dist(包含I,D,S,T四种操作,最后一种是置换),LCS,Hamming dist,JW dist
  • 集合距离度量:Jaccard similarity
  • normalized compression distance:指定一种压缩算法,通过压缩后数据大小的差值,衡量两个原始数据的距离,通用性强

常用的库有FuzzyWuzzy

ngram特征可以把n设置为1,2,3等,在所有单词和unique单词上同时计算Jaccard等相似性。特殊字符可以单独处理,比如句子中的标点、数字、英文(由于是俄语,所以英文比较“特殊”)、大写字母等。SVD、PCA、LDA等常用的文本降维方法也可以使用,可以计算降维后的vector的相似性,也可以将降维结果直接喂给模型。

Word2Vec使用的是pre-trained的模型,从单词相似性,到句子相似性,使用的是Word Movers’ Distance,具体可见原论文。Word Movers’ Distance(WMD)是Earth Mover’s Distance(EMD)的一种特例,EMD通过计算将一个分布转换为另一个分布所需的最小消耗,衡量任意两个分布的相似性的,有点像编辑距离。不过,有的队说WordVec特征的贡献并不大。

BOW特征

使用BOW特征,是文本分类任务的常用做法。区分两条广告是否重复,也可以看做是文本分类任务。NB,LR,SGD等线性模型都可以直接用来上,另外FM模型,多捕捉这类稀疏特整建的依赖关系,也很有效。

Todo: 实验

图片特征

图片特征是我的模型中比较弱的环节。通过其他选手的分享可以看出,图片特征是很关键的。这里对图片特征做一汇总:

  • 简单特征

主要是基于色彩histogram的特征,可以对RGB三个channel上的色彩分布,计算若干统计值,如min,max,mean,std,skew,kurtosis,其中,skew和kurtosis分别衡量一个分布的偏斜程度和陡峭程度,计算的公式也不止一种,具体可以参见Measures of Skewness and Kurtosis。另外衡量histogram相似性有很多方式,具体可见3 ways compare histograms

  • 基于hash的特征

可以使用MD5,比较两张图片是否完全相同。另外,还可以使用ahash、phash、dhash、whash(小波hash,在比赛过程中由Dmitry Petrov开发)等专门针对图像处理问题设计的抗旋转变换的hash函数。在Avito的这次比赛中,简单的dhash和phash就能带来非常好的效果。关于这些hash函数的详细介绍,可见dhashphashwhash

  • SSIM,MSE特征

MSE特征和MSE error类似,只不过是应用到了两张维度相同的图片上,SSIM是对MSE的改进,具体可见How-to: python compare two images

  • descriptor特征

HOG descriptor特征(SIFT)和binary descriptor特征(BRISK),具体可见HOGbinary descriptors

方案汇总
2nd, 4th-1 4th-2, 5th, 14th