{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": true }, "source": [ "

Table of Contents

\n", "
" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# code for loading the format for the notebook\n", "import os\n", "\n", "# path : store the current path to convert back to it later\n", "path = os.getcwd()\n", "os.chdir(os.path.join('..', 'notebook_format'))\n", "\n", "from formats import load_style\n", "load_style(plot_style = False)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Ethen 2017-06-22 13:40:53 \n", "\n", "CPython 3.5.2\n", "IPython 5.4.1\n", "\n", "numpy 1.12.1\n", "pandas 0.20.2\n", "sklearn 0.18.1\n" ] } ], "source": [ "os.chdir(path)\n", "import numpy as np\n", "import pandas as pd\n", "\n", "# 1. magic to print version\n", "# 2. magic so that the notebook will reload external python modules\n", "%load_ext watermark\n", "%load_ext autoreload \n", "%autoreload 2\n", "\n", "from sklearn.preprocessing import LabelBinarizer\n", "from sklearn.feature_selection import chi2, SelectKBest\n", "from sklearn.feature_extraction.text import CountVectorizer\n", "\n", "%watermark -a 'Ethen' -d -t -v -p numpy,pandas,sklearn" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Chi-Square Feature Selection" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Feature selection is a process where you automatically select those features in your data that contribute most to the prediction variable or output in which you are interested. The benefits of performing feature selection before modeling your data are:\n", "\n", "- Avoid Overfitting: Less redundant data gives performance boost to the model and results in less opportunity to make decisions based on noise\n", "- Reduces Training Time: Less data means that algorithms train faster" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
cabcallhemepleasetonightwillyou
001000101
111010000
201012000
301110010
\n", "
" ], "text/plain": [ " cab call he me please tonight will you\n", "0 0 1 0 0 0 1 0 1\n", "1 1 1 0 1 0 0 0 0\n", "2 0 1 0 1 2 0 0 0\n", "3 0 1 1 1 0 0 1 0" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# suppose we have the following toy text data\n", "X = np.array(['call you tonight', 'Call me a cab', 'please call me... PLEASE!', 'he will call me'])\n", "y = [1, 1, 2, 0]\n", "\n", "# we'll convert it to a dense document-term matrix,\n", "# so we can print a more readable output\n", "vect = CountVectorizer()\n", "X_dtm = vect.fit_transform(X)\n", "X_dtm = X_dtm.toarray()\n", "pd.DataFrame(X_dtm, columns = vect.get_feature_names())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "One common feature selection method that is used with text data is the Chi-Square feature selection. The $\\chi^2$ test is used in statistics to test the independence of two events. More specifically in feature selection we use it to test whether the occurrence of a specific term and the occurrence of a specific class are independent. More formally, given a document $D$, we estimate the following quantity for each term and rank them by their score:\n", "\n", "$$\n", "\\chi^2(D, t, c) = \\sum_{e_t \\in \\{0, 1\\}} \\sum_{e_c \\in \\{0, 1\\}} \n", "\\frac{ ( N_{e_te_c} - E_{e_te_c} )^2 }{ E_{e_te_c} }$$\n", "\n", "Where\n", "\n", "- $N$ is the observed frequency in and $E$ the expected frequency\n", "- $e_t$ takes the value 1 if the document contains term $t$ and 0 otherwise\n", "- $e_c$ takes the value 1 if the document is in class $c$ and 0 otherwise\n", "\n", "For each feature (term), a corresponding high $\\chi^2$ score indicates that the null hypothesis $H_0$ of independence (meaning the document class has no influence over the term's frequency) should be rejected and the occurrence of the term and class are dependent. In this case, we should select the feature for the text classification." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Implementation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We first compute the observed count for each class. This is done by building a contingency table from an input $X$ (feature values) and $y$ (class labels). Each entry $i$, $j$ corresponds to some feature $i$ and some class $j$, and holds the sum of the $i_{th}$ feature's values across all samples belonging to the class $j$.\n", "\n", "Note that although the feature values here are represented as frequencies, this method also works quite well in practice when the values are tf-idf values, since those are just weighted/scaled frequencies." ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[0 1 0]\n", " [0 1 0]\n", " [0 0 1]\n", " [1 0 0]]\n", "\n", "[[0 1 1 1 0 0 1 0]\n", " [1 2 0 1 0 1 0 1]\n", " [0 1 0 1 2 0 0 0]]\n" ] } ], "source": [ "# binarize the output column,\n", "# this makes computing the observed value a \n", "# simple dot product\n", "y_binarized = LabelBinarizer().fit_transform(y)\n", "print(y_binarized)\n", "print()\n", "\n", "# our observed count for each class (the row)\n", "# and each feature (the column)\n", "observed = np.dot(y_binarized.T, X_dtm)\n", "print(observed)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "e.g. the second row of the observed array refers to the total count of the terms that belongs to class 1. Then we compute the expected frequencies of each term for each class." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[[ 0.25 1. 0.25 0.75 0.5 0.25 0.25 0.25]\n", " [ 0.5 2. 0.5 1.5 1. 0.5 0.5 0.5 ]\n", " [ 0.25 1. 0.25 0.75 0.5 0.25 0.25 0.25]]\n" ] } ], "source": [ "# compute the probability of each class and the feature count; \n", "# keep both as a 2 dimension array using reshape\n", "class_prob = y_binarized.mean(axis = 0).reshape(1, -1)\n", "feature_count = X_dtm.sum(axis = 0).reshape(1, -1)\n", "expected = np.dot(class_prob.T, feature_count)\n", "print(expected)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[ 1. 0. 3. 0.33333333 6. 1. 3.\n", " 1. ]\n" ] } ], "source": [ "chisq = (observed - expected) ** 2 / expected\n", "chisq_score = chisq.sum(axis = 0)\n", "print(chisq_score)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We can confirm our result with the scikit-learn library using the `chi2` function. The following code chunk computes chi-square value for each feature. For the returned tuple, the first element is the chi-square scores, the scores are better if greater. The second element is the p-values, they are better if smaller." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(array([ 1. , 0. , 3. , 0.33333333, 6. ,\n", " 1. , 3. , 1. ]),\n", " array([ 0.60653066, 1. , 0.22313016, 0.84648172, 0.04978707,\n", " 0.60653066, 0.22313016, 0.60653066]))" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "chi2score = chi2(X_dtm, y)\n", "chi2score" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Scikit-learn provides a `SelectKBest` class that can be used with a suite of different statistical tests. It will rank the features with the statistical test that we've specified and select the top k performing ones (meaning that these terms is considered to be more relevant to the task at hand than the others), where k is also a number that we can tweak." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "array([[0, 0, 0, 1],\n", " [0, 0, 0, 0],\n", " [0, 2, 0, 0],\n", " [1, 0, 1, 0]], dtype=int64)" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "kbest = SelectKBest(score_func = chi2, k = 4)\n", "X_dtm_kbest = kbest.fit_transform(X_dtm, y)\n", "X_dtm_kbest" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For the Chi-Square feature selection we should expect that out of the total selected features, a small part of them are still independent from the class. In text classification, however, it rarely matters when a few additional terms are included the in the final feature set. All is good as long as the feature selection is ranking features with respect to their usefulness and is not used to make statements about statistical dependence or independence of variables." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Reference" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- [Blog: Feature Selection For Machine Learning in Python](http://machinelearningmastery.com/feature-selection-machine-learning-python/)\n", "- [Blog: Using Feature Selection Methods in Text Classification](http://blog.datumbox.com/using-feature-selection-methods-in-text-classification/)\n", "- [Stackoverflow: Perform Chi-2 feature selection on TF and TF*IDF vectors](http://stackoverflow.com/questions/14573030/perform-chi-2-feature-selection-on-tf-and-tfidf-vectors)" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.4" }, "toc": { "nav_menu": { "height": "126px", "width": "252px" }, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": true, "toc_position": {}, "toc_section_display": "block", "toc_window_display": true }, "varInspector": { "cols": { "lenName": 16, "lenType": 16, "lenVar": 40 }, "kernels_config": { "python": { "delete_cmd_postfix": "", "delete_cmd_prefix": "del ", "library": "var_list.py", "varRefreshCmd": "print(var_dic_list())" }, "r": { "delete_cmd_postfix": ") ", "delete_cmd_prefix": "rm(", "library": "var_list.r", "varRefreshCmd": "cat(var_dic_list()) " } }, "types_to_exclude": [ "module", "function", "builtin_function_or_method", "instance", "_Feature" ], "window_display": false } }, "nbformat": 4, "nbformat_minor": 1 }