# Repost of my KDD Cup 2018 summary

I finished 30th place at this year's KDD CUP. I still remember back to 2015, when I was very rusty with coding and tried to attempt that years' KDD cup with my potato laptop Lenovo U310. I did not know what I was doing, all I did is trying to throw data into XGBoost and my performance then is a joke. I see myself became more and more capable of comming up with ideas and implement them out during these two years. And below is a repost of my summary to KDD 2018.

Hooray~! fellow KDD competitors. I entered this competition on day 1 and very quickly established a reasonable baseline. Due to some personal side of things, I practically stopped improving my solutions since the beginning of May. Even though my methods did not work really well compared to many top players in phase 2, but I think my solution may worth sharing due to it is relative simplicity. I did not touch the meo data at all, and one of my models is just calculating medians.

### Alternative data source

For new hourly air quality data, as shared in the forum, I am using this for London and this for Beijing instead of the API from the organizer.

### Handling missing data

I filled missing values in air quality data with 3 steps:

1. Fill missing values for a station-measure combo based on the values from other stations.
To be specific: I trained 131 lightgbm regressors for this. If PM2.5 reading on 2:00 May 20th is missing for Beijing aotizhongxin station, the regressor aotizhongxin_aq-PM2.5 will predict this value based on known PM2.5 readings on 2:00 May 20th from 34 other stations in Beijing.
I used thresholds to decide whether to do this imputation or not. If more than the threshold number of stations also don't have a reading, then skip this step.
2. Fill the remaining missing values by looking forward and backward to find known values.
3. Finally, replace all remaining missing values by overall mean value.

### Approaches

#### 1. median of medians

This is a simple model that worked reasonably well in this Kaggle competition.

To predict PM2.5 reading on 2:00 May 20th for aotizhongxin, look back for a window of days history, calculating the median 2:00 PM2.5 readings from aotizhongxin in that window. You do this median calculation exercise for a bunch of different window sizes to obtain a bunch medians. The median value of those medians is used as the prediction.

Intuitively this is just an aggregated yesterday once more. With more larger windows in the collection, the model memorizes the long-term trend better. The more you add in smaller windows, the quicker the model would respond to recent events.

This is practically even simpler than the median of medians. I treated the number of days history I throw at it and the model parameters changepoint_prior_scalen_changepoints as main hyperparameters and tweaked them. I did a bit work to parallelizing the fitting process for all the station-measure combos to speed up the fitting process, other than that, it is pretty much out of the box.

I tried to use holiday indicator or tweaking other parameters of the model and they all degrade the performance of the model.

#### 3. neural network

My neural network is a simple feed-forward network with a single shortcut, shamelessly copied the structure from a senior colleague's Kaggle solution with tweaked hidden layer sizes.
The model looks like this:

The input to the neural network are concatenated (1) raw history readings, (2) median summary values from different window_sizes, and (3) indicator variables for the city, type of measure.

The output layer in the network is a dense layer with 48 units, each corresponding to an hourly reading in the next 48 hours.

The model is trained directly using smape as loss function with Adam optimizer. I tried standardizing inputs into zero mean and unit variance, but it will cause a problem when used together with smape loss, thus I tried switching to a clipped version MAE loss, which produced similar results compared to raw input with smape loss.

The model can be trained on CPU only machine in very short time.

I tried out some CNN, RNN models but couldn't get them working better than this simple model, and had to abandon them.

### Training and validation setup

This is pretty tricky, and I am still not quite sure if I have done it correctly or not.

#### For approach 1 and 2

I tried to generate predictions for a few historical months, calculating daily smape scores locally. Then sample 25 days out to calculate a mean smape score. Do this sample-scoring a large number of times and take mean as local validation score. I used this score to select parameters.

#### For neural network

I split the history data into (X, y) pairs based on a splitting day, and then move the splitting day backward by 1 day to generate another (X, y) pair. Do this 60 times and vertically concatenate them to form my training data.

I used groupedCV split on the concatenated dataset to do cross-validation so that measures from one station don't end up in both training and validation set. During training, the batch size is specified so that data in the batch all based on the same splitting day. I did this trying to preventing information leaking.

I got average smape scores 0.40~44 for Beijing and 0.30-0.34 for London in my local validation setting. Which I think is pretty aligned with how it averages out through May.

### Closing

Without utilizing any other weather information or integrating any sort of forecasts, all my models failed miserably for events like the sudden peak on May 27th in Beijing.

# A quick post on Decision Trees

Today is my one year anniversary studying at Bentley University in MA, US. And this short post on this special day is devoted to Decision Trees, a simple but often misused method. During my short time here, and limited times talking to marketing analysts, I saw some cases when they just take the rules directly from decision trees and throw them in decks and say that they will show that to executives as "insights". I think they should be a bit more careful since the decision tree can be rather unstable, i.e. small changes in the dataset can result in completely different trees.

Below are some python scripts, which i used to build classification trees on the iris data. But each time, I do some sort of random sampling and feed the sample to the algorithm to build trees. You can look at the difference  yourself.

I will just upload pictures of a few of these trees.

The two trees above are built on different random samples of the iris dataset. From the first one you can get the rule: if petal length is less than or equal to 2.45 cm then the flower is a setosa. Wheras from the second decision tree you get the rule: if petal width is less than or equal to 0.8 cm then the flower is a setosa. Take a quick look at the scatter plot you will see that they are both pretty good rules, and if you only build one decision tree, you will miss one of the very good rules.

Below are two trees built on different samples of the iris dataset again. And I personly would not try to interpret the splitting rules from the third level in the tree and on (take root node as the first level).

Anyway, the takeaway is that: try different algorithms, try different samples as input, build many trees and take what's common from them, rather than simply build one tree.

# K-Means 聚类

1. 初始化k个中心点
2. 每一次迭代时：
将每个数据点分配给与其“最近”的中心点
对每一个中心点，更新其新的位置为所有属于其的节点的“平均位置"
3. 重复1-2 直至收敛（一次迭代后，没有数据点被重新分配过）

• 尝试不同的k，看各个数据点到所属中心点的距离。
如果k较少，则会有许多较大的距离
如果k较大，则距离通常非常小

1. 抽样
抽样一部分数据点，使用层次聚类，找出k的值
从层次聚类的k个类中各取一个点作为中心点
2. 先随机选一个点作为中心点
再剩下点中，找到一个与已选点距离最远的点作为中心点
反复上述过程直至获得k个点

# Hierarchical Clustering 层次聚类

1. 初始时，每一个数据点单独构成一个聚集
2. 不断地将最近的两个聚集合并

1. 聚集之间的距离度量
2. 定义聚集合并后如何表示
3. 何时停止聚类

• 用中心点表示聚集，中心点与聚集内各个节点“最近”(平均距离最小、最大距离最小，距离的平方和最小等等)
• 用聚集于聚集的中心点之间的距离表示聚集之间的距离

6个数据点：(1,2),(2,1),(0,0),(5,3),(5,0),(4,1)

scipy中有层次聚类，对例子数据的聚类结果与上面一直。

1. 预先设定聚集数量k，一旦形成k个聚集就停止
2. 当新生成的聚集的“凝聚力”（cohesion）小于阈值

1. 聚集的直径 = 全局中节点之间的最大距离
2. 聚集内节点与中心点之间的距离超过预先设定的最大值
3. 聚集内的节点密度大于预先设定值

# CUR Dimension Reduction CUR分解 降维

SVD分解的缺点在于:

1. 计算比较耗时
2. 存储$UV$矩阵比较占空间

CUR分解是另外一个选择，其目标是：找到输入矩阵的一个“尽可能好”的分解为三个矩阵的乘积A = CUR，SVD分解是完美的分解（通过允许误差来加速计算）。其中：

1. $C$矩阵由$A$矩阵中的列构成
2. $R$矩阵由$A$矩阵中的行构成
3. $U$矩阵由$C,R$的交集进行伪逆求得

C矩阵获得：

• 输入：矩阵$Ain mathbb{R}^{mtimes n}$，抽样数量$c$
• 输出：$C_d in mathbb{R}^{mtimes c}$
1. for x = 1:n （计算列的分布）
2.     $P(x) = sum_i A(i,x)^2 / sum_{i,j} A(i,j)^2$
3. for i = 1:c
4.     Pick $j in 1: n$
5.     Comupte $C_d(:,i) = A(:,j)/sqrt{cP(j)}$

R矩阵的获得的方式与上面类似。

U矩阵的计算方式为：

1. 取C矩阵和R矩阵的“交集”W
2. U为W的伪逆