Count Featurizer

Trong “sự nghiệp” ngắn ngủi đi làm Data Scientist dạo, mình từng thấy rất nhiều kĩ thuật feature engineering khá lạ lùng. Một trong những kĩ thuật lạ lùng nhất là hashing. Chẳng hạn có 1 feature là địa chỉ nhà (của khách hàng), thông thường là một string, và thật khó để extract bất kì thông tin nào. Hashing đơn giản chỉ là biến đổi feature đó như sau:

f = hash(s) % M

và sau đó f được dùng trong one-hot encoding. M càng lớn thì chi phí càng cao, nhưng chất lượng có thể “tốt” hơn. Kĩ thuật này đơn giản nhưng hiệu quả, vì nó sẽ hoạt động tốt ngay cả trên test  data. Về mặt kĩ thuật,  thực chất đây rất gần giống với việc gán các địa chỉ 1 cách “ngẫu nhiên” vào M ngăn, tuy nhiên nhờ tính deterministic của hàm hash nên ta có thể đảm bảo một chuỗi sẽ chỉ được gán vào đúng 1 ngăn.

Một kĩ thuật feature engineering khác cũng “lạ lùng” không kém là Count-based featurizer. Mặc dù đơn giản nhưng kĩ thuật này tỏ ra rất  hiệu quả trong nhiều bài toán lớn như Online advertisement, fraud detection. Count featurizer phù hợp để encode các feature dạng categorical mà số lượng category quá lớn, đến nỗi khó có thể dùng One-hot encoding. Các feature dạng này có thể là địa chỉ, là ID của khách hàng v.v… cụ thể như sau.

Ý tưởng chính của Count Featurizer là xây dựng một dạng conditional distribution về input features, cho trước các giá trị của target feature. Do vậy nó yêu cầu target feature phải là categorical, nói cách khác Count Featurizer chỉ sử dụng được cho các bài toán classification.

Gọi x là input feature cần encode, và y là target output. Vì là bài toán classification nên y có thể nhận các giá trị c_1, c_2, ..., c_N với N là số lượng class. Count Featurizer sẽ xây dựng bảng đếm số lần mà x thuộc lớp c_i, với mọi i từ 1 đến N, dựa trên training set. Nói cách khác, input feature x sẽ được thay thế bằng vector \mathbf{z} \in R^{N}, trong đó phần tử z_i là số lần xuất hiện của x và c_i trên cùng 1 dòng của training set.

Giả sử training set như sau:

Input feature Target
A 0
A 1
A 1
B 0
B 0

Khi đó kết quả của count featurizer sẽ là:

Input feature New feature (0) New feature (1)
A 1 2
B 2 0

Nghĩa là input A sẽ được map thành vector (1, 2), input B sẽ được map thành vector (2, 0).

Tới đây ta thấy khá gần gũi với Naive Bayes classifier.

Tuy nhiên trên thực tế, Count Featurizer sẽ không lưu số lượng samples như trên, mà sẽ lưu tỉ số log-odds:

logodds(x, c_i) = \log\left(\frac{count(x, c_i)}{count(x) - count(x, c_i)}\right)

Trong đó count(x)count(x, c_i) lần lượt là số lượng sample trong training set mà x xuất hiện, và x, c_i cùng xuất hiện đồng thời.

Sử dụng log-odds thì kết quả sẽ là:

Input feature New feature (0) New feature (1)
A log(1/2) log(2/1)
B log(2/0) log(0/2)

Rõ ràng ta thấy feature của B có vấn đề, vì lỗi chia cho 0, và log(0) = -\infty. Để tránh trường hợp này, người ta sẽ tính một vector mặc định cho tất cả các input:

default\_logodds_i = log\left(\frac{count(c_i)}{N - count(c_i)}\right)

Với N là số lượng samples trong training set. Khi đó ta có:

logodds(x, c_i) = \begin{cases} \log\left(\frac{count(x, c_i)}{count(x) - count(x, c_i)}\right) &\mbox{if } MIN\_CAT < count(x, c_i) < count(x) \\ default\_logodds(c_i) &\mbox{otherwise } \end{cases}

Trong đó MIN_CAT là hằng số xác định giá trị tối thiểu của count(x, c_i) để được tính vào vector logodds. Thông thường MIN_CAT = 1 hoặc 2, tuỳ mức độ lặp lại của input feature X.

Ngoài ra, người ta cũng thường thêm vào cuối vector logodds một giá trị thể hiện tần số xuất hiện của x:

freq(x) = \log\left(\frac{count(x)}{N - count(x)}\right)

Đó là bước training. Trong lúc testing, mô hình được cập nhật lại với mỗi x. Tuy nhiên vì trong lúc testing ta không có target value, nên chỉ có freq(x) được tính lại. Với mỗi x, nếu x đã có trong tập huấn luyện thì nó sẽ được chuyển thành logodds(x, c_i), i=1..N, nếu không thì được chuyển thành default\_logodds_i, i=1..N.

Cuối bài là cài đặt đơn giản của Count Featurizer trong Python. Như thường lệ, mã nguồn có trên github.

&lt;pre&gt;import sys
from copy import deepcopy

import numpy as np
import pandas as pd

class CountFeaturizer(object):

    def __init__(self, input_col, label_col, output_col='count_features', min_count_per_cat=2):
        self.input_col = input_col
        self.label_col = label_col
        self.output_col = output_col
        self.min_count_per_cat = min_count_per_cat

    def fit(self, data):
        self.train_set = data
        self.inputs = sorted(data[self.input_col].unique())
        self.labels = sorted(data[self.label_col].unique(), key=lambda x: '{}'.format(x))
        label_counts_tmp = data.groupby([self.label_col]).size()
        label_counts = pd.Series([label_counts_tmp.loc[i] for i in self.labels])
        pair_counts = data.groupby([self.input_col, self.label_col]).size()
        self.input_counts = data.groupby([self.input_col]).size()
        self.logodds = {}
        self.logodds_class = {}
        self.default_logodds = np.log(label_counts / (float(len(data)) - label_counts))
        for inp in self.inputs:
            self.logodds_class[inp] = np.log(self.input_counts[inp] / (float(len(data)) - self.input_counts[inp]))
            self.logodds[inp] = deepcopy(self.default_logodds)
            for cat in pair_counts[inp].keys():
                if self.min_count_per_cat &lt; pair_counts[inp].loc[cat] &lt; self.input_counts[inp]:
                    prob_inp = pair_counts[inp].loc[cat] / float(self.input_counts[inp])
                    self.logodds[inp][self.labels.index(cat)] = np.log(prob_inp) - np.log(1.0 - prob_inp)
            self.logodds[inp] = pd.Series(self.logodds[inp])
            self.logodds[inp].index = range(len(self.labels))

    def transform(self, data):
        new_inputs = sorted(data[self.input_col].unique())
        new_input_counts = data.groupby(self.input_col).size()
        only_new = set(new_inputs + self.inputs) - set(self.inputs)
        in_both = set(new_inputs).intersection(self.inputs)
        new_cnt = 0.0 if data is self.train_set else float(len(data))

        for inp in only_new:
            self.logodds_class[inp] = np.log(new_input_counts[inp] /
                                             (float(len(self.train_set) + new_cnt) - new_input_counts[inp]))
            self.logodds[inp] = deepcopy(self.default_logodds)
            self.logodds[inp].index = range(len(self.labels))
        if data is not self.train_set:
            for inp in in_both:
                prob_inp = (self.input_counts[inp] + new_input_counts[inp]) / float(len(self.train_set) + new_cnt)
                self.logodds_class[inp] = np.log(prob_inp) - np.log(1. - prob_inp)

        for i in range(0, len(self.labels)):
            data['{}_{}'.format(self.output_col, i)] = data[self.input_col].apply(lambda _: self.logodds[_].loc[i])
        data['{}_class'.format(self.output_col)] = data[self.input_col].apply(lambda _: self.logodds_class[_])
        return data&lt;/pre&gt;
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s