Python for Data Science¶

Joe McCarthy, Data Scientist, Indeed

1. Introduction¶

This short primer on Python is designed to provide a rapid "on-ramp" to enable computer programmers who are already familiar with concepts and constructs in other programming languages learn enough about Python to facilitate the effective use of open-source and proprietary Python-based machine learning and data science tools.

The primer is motivated, in part, by the approach taken in the Natural Language Toolkit (NLTK) book, which provides a rapid on-ramp for using Python and the open-source NLTK library to develop programs using natural language processing techniques (many of which involve machine learning).

The Python Tutorial offers a more comprehensive primer, and opens with an excellent - if biased - overview of some of the general strengths of the Python programming language:

Python is an easy to learn, powerful programming language. It has efficient high-level data structures and a simple but effective approach to object-oriented programming. Python’s elegant syntax and dynamic typing, together with its interpreted nature, make it an ideal language for scripting and rapid application development in many areas on most platforms.

Hans Petter Langtangen, author of Python Scripting for Computational Science, emphasizes the utility of Python for many of the common tasks in all areas of computational science:

Very often programming is about shuffling data in and out of different tools, converting one data format to another, extracting numerical data from a text, and administering numerical experiments involving a large number of data files and directories. Such tasks are much faster to accomplish in a language like Python than in Fortran, C, C++, C#, or Java

Foster Provost, co-author of Data Science for Business, describes why Python is such a useful programming language for practical data science in Python: A Practical Tool for Data Science, :

The practice of data science involves many interrelated but different activities, including accessing data, manipulating data, computing statistics about data, plotting/graphing/visualizing data, building predictive and explanatory models from data, evaluating those models on yet more data, integrating models into production systems, etc. One option for the data scientist is to learn several different software packages that each specialize in one or two of these things, but don’t do them all well, plus learn a programming language to tie them together. (Or do a lot of manual work.)

An alternative is to use a general-purpose, high-level programming language that provides libraries to do all these things. Python is an excellent choice for this. It has a diverse range of open source libraries for just about everything the data scientist will do. It is available everywhere; high performance python interpreters exist for running your code on almost any operating system or architecture. Python and most of its libraries are both open source and free. Contrast this with common software packages that are available in a course via an academic license, yet are extremely expensive to license and use in industry.

The goal of this primer is to provide efficient and sufficient scaffolding for software engineers with no prior knowledge of Python to be able to effectively use Python-based tools for data science research and development, such as the open-source library scikit-learn. There is another, more comprehensive tutorial for scikit-learn, Python Scientific Lecture Notes, that includes coverage of a number of other useful Python open-source libraries used by scikit-learn (numpy, scipy and matplotlib) - all highly recommended ... and, to keep things simple, all beyond the scope of this primer.

Using an IPython Notebook as a delivery vehicle for this primer was motivated by Brian Granger's inspiring tutorial, The IPython Notebook: Get Close to Your Data with Python and JavaScript, one of the highlights from my Strata 2014 conference experience. You can run this notebook locally in a browser once you install ipython notebook.

One final note on external resources: the Python Style Guide (PEP-0008) offers helpful tips on how best to format Python code. Code like a Pythonista offers a number of additional tips on Python programming style and philosophy, several of which are incorporated into this primer.

We will focus entirely on using Python within the interpreter environment (as supported within an IPython Notebook). Python scripts - files containing definitions of functions and variables, and typically including code invoking some of those functions - can also be run from a command line. Using Python scripts from the command line may be the subject of a future primer.

To help motivate the data science-oriented Python programming examples provided in this primer, we will start off with a brief overview of basic concepts and terminology in data science.

2. Data Science: Basic Concepts¶

Data Science and Data Mining¶

Foster Provost and Tom Fawcett offer succinct descriptions of data science and data mining in Data Science for Business:

Data science involves principles, processes and techniques for understanding phenomena via the (automated) analysis of data.

Data mining is the extraction of knowledge from data, via technologies that incorporate these principles.

Knowledge Discovery, Data Mining and Machine Learning¶

Provost & Fawcett also offer some history and insights into the relationship between data mining and machine learning, terms which are often used somewhat interchangeably:

The field of Data Mining (or KDD: Knowledge Discovery and Data Mining) started as an offshoot of Machine Learning, and they remain closely linked. Both fields are concerned with the analysis of data to find useful or informative patterns. Techniques and algorithms are shared between the two; indeed, the areas are so closely related that researchers commonly participate in both communities and transition between them seamlessly. Nevertheless, it is worth pointing out some of the differences to give perspective.

Speaking generally, because Machine Learning is concerned with many types of performance improvement, it includes subfields such as robotics and computer vision that are not part of KDD. It also is concerned with issues of agency and cognition — how will an intelligent agent use learned knowledge to reason and act in its environment — which are not concerns of Data Mining.

Historically, KDD spun off from Machine Learning as a research field focused on concerns raised by examining real-world applications, and a decade and a half later the KDD community remains more concerned with applications than Machine Learning is. As such, research focused on commercial applications and business issues of data analysis tends to gravitate toward the KDD community rather than to Machine Learning. KDD also tends to be more concerned with the entire process of data analytics: data preparation, model learning, evaluation, and so on.

Cross Industry Standard Process for Data Mining (CRISP-DM)¶

The Cross Industry Standard Process for Data Mining introduced a process model for data mining in 2000 that has become widely adopted.

The model emphasizes the *iterative* nature of the data mining process, distinguishing several different stages that are regularly revisited in the course of developing and deploying data-driven solutions to business problems:

• Business understanding
• Data understanding
• Data preparation
• Modeling
• Deployment

We will be focusing primarily on using Python for data preparation and modeling.

Data Science Workflow¶

Philip Guo presents a Data Science Workflow offering a slightly different process model emhasizing the importance of reflection and some of the meta-data, data management and bookkeeping challenges that typically arise in the data science process. His 2012 PhD thesis, Software Tools to Facilitate Research Programming, offers an insightful and more comprehensive description of many of these challenges.

Provost & Fawcett list a number of different tasks in which data science techniques are employed:

• Classification and class probability estimation
• Regression (aka value estimation)
• Similarity matching
• Clustering
• Co-occurrence grouping (aka frequent itemset mining, association rule discovery, market-basket analysis)
• Profiling (aka behavior description, fraud / anomaly detection)
• Link prediction
• Data reduction
• Causal modeling

We will be focusing primarily on classification and class probability estimation tasks, which are defined by Provost & Fawcett as follows:

Classification and class probability estimation attempt to predict, for each individual in a population, which of a (small) set of classes this individual belongs to. Usually the classes are mutually exclusive. An example classification question would be: “Among all the customers of MegaTelCo, which are likely to respond to a given offer?” In this example the two classes could be called will respond and will not respond.

To further simplify this primer, we will focus exclusively on supervised methods, in which the data is explicitly labeled with classes. There are also unsupervised methods that involve working with data in which there are no pre-specified class labels.

Supervised Classification¶

The Natural Language Toolkit (NLTK) book provides a diagram and succinct description (below, with italics and bold added for emphasis) of supervised classification:

Supervised Classification. (a) During training, a feature extractor is used to convert each input value to a feature set. These feature sets, which capture the basic information about each input that should be used to classify it, are discussed in the next section. Pairs of feature sets and labels are fed into the machine learning algorithm to generate a model. (b) During prediction, the same feature extractor is used to convert unseen inputs to feature sets. These feature sets are then fed into the model, which generates predicted labels.

Data Mining Terminology¶

• Structured data has simple, well-defined patterns (e.g., a table or graph)
• Unstructured data has less well-defined patterns (e.g., text, images)
• Model: a pattern that captures / generalizes regularities in data (e.g., an equation, set of rules, decision tree)
• Attribute (aka variable, feature, signal, column): an element used in a model
• Instance (aka example, feature vector, row): a representation of a single entity being modeled
• Target attribute (aka dependent variable, class label): the class / type / category of an entity being modeled

Data Mining Example: UCI Mushroom dataset¶

The Center for Machine Learning and Intelligent Systems at the University of California, Irvine (UCI), hosts a Machine Learning Repository containing over 200 publicly available data sets.

We will use the mushroom data set, which forms the basis of several examples in Chapter 3 of the Provost & Fawcett data science book.

The following description of the dataset is provided at the UCI repository:

This data set includes descriptions of hypothetical samples corresponding to 23 species of gilled mushrooms in the Agaricus and Lepiota Family (pp. 500-525 [The Audubon Society Field Guide to North American Mushrooms, 1981]). Each species is identified as definitely edible, definitely poisonous, or of unknown edibility and not recommended. This latter class was combined with the poisonous one. The Guide clearly states that there is no simple rule for determining the edibility of a mushroom; no rule like leaflets three, let it be'' for Poisonous Oak and Ivy.

Number of Instances: 8124

Number of Attributes: 22 (all nominally valued)

Attribute Information: (classes: edible=e, poisonous=p)

1. cap-shape: bell=b, conical=c, convex=x, flat=f, knobbed=k, sunken=s
2. cap-surface: fibrous=f, grooves=g, scaly=y, smooth=s
3. cap-color: brown=n ,buff=b, cinnamon=c, gray=g, green=r, pink=p, purple=u, red=e, white=w, yellow=y
4. bruises?: bruises=t, no=f
5. odor: almond=a, anise=l, creosote=c, fishy=y, foul=f, musty=m, none=n, pungent=p, spicy=s
6. gill-attachment: attached=a, descending=d, free=f, notched=n
7. gill-spacing: close=c, crowded=w, distant=d
8. gill-size: broad=b, narrow=n
9. gill-color: black=k, brown=n, buff=b, chocolate=h, gray=g, green=r, orange=o, pink=p, purple=u, red=e, white=w, yellow=y
10. stalk-shape: enlarging=e, tapering=t
11. stalk-root: bulbous=b, club=c, cup=u, equal=e, rhizomorphs=z, rooted=r, missing=?
12. stalk-surface-above-ring: fibrous=f, scaly=y, silky=k, smooth=s
13. stalk-surface-below-ring: fibrous=f, scaly=y, silky=k, smooth=s
14. stalk-color-above-ring: brown=n, buff=b, cinnamon=c, gray=g, orange=o, pink=p, red=e, white=w, yellow=y
15. stalk-color-below-ring: brown=n, buff=b, cinnamon=c, gray=g, orange=o, pink=p, red=e, white=w, yellow=y
16. veil-type: partial=p, universal=u
17. veil-color: brown=n, orange=o, white=w, yellow=y
18. ring-number: none=n, one=o, two=t
19. ring-type: cobwebby=c, evanescent=e, flaring=f, large=l, none=n, pendant=p, sheathing=s, zone=z
20. spore-print-color: black=k, brown=n, buff=b, chocolate=h, green=r, orange=o, purple=u, white=w, yellow=y
21. population: abundant=a, clustered=c, numerous=n, scattered=s, several=v, solitary=y
22. habitat: grasses=g, leaves=l, meadows=m, paths=p, urban=u, waste=w, woods=d

Missing Attribute Values: 2480 of them (denoted by "?"), all for attribute #11.

Class Distribution: -- edible: 4208 (51.8%) -- poisonous: 3916 (48.2%) -- total: 8124 instances

The data file associated with this dataset has one instance of a hypothetical mushroom per line, with abbreviations for the values of the class and each of the other 22 attributes separated by commas.

Here is a sample line from the data file:

p,k,f,n,f,n,f,c,n,w,e,?,k,y,w,n,p,w,o,e,w,v,d

This instance represents a mushroom with the following attribute values (highlighted in bold):

class: edible=e, poisonous=p

1. cap-shape: bell=b, conical=c, convex=x, flat=f, knobbed=k, sunken=s
2. cap-surface: fibrous=f, grooves=g, scaly=y, smooth=s
3. cap-color: brown=n ,buff=b, cinnamon=c, gray=g, green=r, pink=p, purple=u, red=e, white=w, yellow=y
4. bruises?: bruises=t, no=f
5. odor: almond=a, anise=l, creosote=c, fishy=y, foul=f, musty=m, none=n, pungent=p, spicy=s
6. gill-attachment: attached=a, descending=d, free=f, notched=n
7. gill-spacing: close=c, crowded=w, distant=d
8. gill-size: broad=b, narrow=n
9. gill-color: black=k, brown=n, buff=b, chocolate=h, gray=g, green=r, orange=o, pink=p, purple=u, red=e, white=w, yellow=y
10. stalk-shape: enlarging=e, tapering=t
11. stalk-root: bulbous=b, club=c, cup=u, equal=e, rhizomorphs=z, rooted=r, missing=?
12. stalk-surface-above-ring: fibrous=f, scaly=y, silky=k, smooth=s
13. stalk-surface-below-ring: fibrous=f, scaly=y, silky=k, smooth=s
14. stalk-color-above-ring: brown=n, buff=b, cinnamon=c, gray=g, orange=o, pink=p, red=e, white=w, yellow=y
15. stalk-color-below-ring: brown=n, buff=b, cinnamon=c, gray=g, orange=o, pink=p, red=e, white=w, yellow=y
16. veil-type: partial=p, universal=u
17. veil-color: brown=n, orange=o, white=w, yellow=y
18. ring-number: none=n, one=o, two=t
19. ring-type: cobwebby=c, evanescent=e, flaring=f, large=l, none=n, pendant=p, sheathing=s, zone=z
20. spore-print-color: black=k, brown=n, buff=b, chocolate=h, green=r, orange=o, purple=u, white=w, yellow=y
21. population: abundant=a, clustered=c, numerous=n, scattered=s, several=v, solitary=y
22. habitat: grasses=g, leaves=l, meadows=m, paths=p, urban=u, waste=w, woods=d

Building a model with this data set will serve as a motivating example throughout much of this primer.

3. Python: Basic Concepts¶

A note on Python 2 vs. Python 3¶

There are 2 major versions of Python in widespread use: Python 2 and Python 3. Python 3 has some features that are not backward compatible with Python 2, and some Python 2 libraries have not been updated to work with Python 3. I have been using Python 2, primarily because I use some of those Python 2[-only] libraries, but an increasing proportion of them are migrating to Python 3, and I anticipate shifting to Python 3 in the near future.

For more on the topic, I recommend a very well documented IPython Notebook, which includes numerous helpful examples and links, by Sebastian Raschka, Key differences between Python 2.7.x and Python 3.x, the Cheat Sheet: Writing Python 2-3 compatible code by Ed Schofield ... or googling Python 2 vs 3.

Nick Coghlan, a CPython core developer, sent me an email suggesting that relatively minor changes in this notebook would enable it to run with Python 2 or Python 3: importing the print_function from the __future__ module, and changing my print statements (Python 2) to print function calls (Python 3). Although a relatively minor conceptual change, it necessitated the changing of many individual cells to reflect the Python 3 print syntax.

I decided to import the division module from the future, as I find the use of / for "true division" - and the use of // for "floor division" - to be more aligned with my intuition. I also needed to replace a few functions that are no longer available in Python 3 with related functions that are available in both versions; I've added notes in nearby cells where the incompatible functions were removed explaining why they are related ... and no longer available.

The differences are briefly illustrated below, with print statements or function calls before and after the importing of the Python 3 versions of the print function and division operator.

Names (identifiers), strings & binding values to names (assignment)¶

The sample instance of a mushroom shown above can be represented as a string.

A Python *string* (str) is a sequence of 0 or more characters enclosed within a pair of single quotes (') or a pair of double quotes (").

Python identifiers (or names) are composed of letters, numbers and/or underscores ('_'), starting with a letter or underscore. Python identifiers are case sensitive. Although camelCase identifiers can be used, it is generally considered more pythonic to use underscores. Python variables and functions typically start with lowercase letters; Python classes start with uppercase letters.

The following assignment statement binds the value of the string shown above to the name single_instance_str. Typing the name on the subsequent line will cause the intepreter to print the value bound to that name.

Printing¶

The print function writes the value of its comma-delimited arguments to sys.stdout (typically the console). Each value in the output is separated by a single blank space.

The print function has an optional keyword argument, end. When this argument is used and its value does not include '\n' (newline character), the output cursor will not advance to the next line.

Comments¶

The Python *comment* character is '#': anything after '#' on the line is ignored by the Python interpreter. PEP8 style guidelines recommend using at least 2 blank spaces before an inline comment that appears on the same line as any code.

*Multi-line strings* can be used within code blocks to provide multi-line comments.

Multi-line strings are delimited by pairs of triple quotes (''' or """). Any newlines in the string will be represented as '\n' characters in the string.

Multi-line strings can be printed, in which case the embedded newline ('\n') characters will be converted to newlines in the output.

Lists¶

A list is an ordered *sequence* of 0 or more comma-delimited elements enclosed within square brackets ('[', ']'). The Python str.split(sep) method can be used to split a sep-delimited string into a corresponding list of elements.

In the following example, a comma-delimited string is split using sep=','.

Python lists are heterogeneous, i.e., they can contain elements of different types.

The Python + operator can be used for addition, and also to concatenate strings and lists.

Accessing sequence elements & subsequences¶

Individual elements of sequences (e.g., lists and strings) can be accessed by specifying their zero-based index position within square brackets ('[', ']').

The following statements print out the 3rd element - at zero-based index position 2 - of single_instance_str and single_instance_list.

Note that the 3rd elements are not the same, as commas count as elements in the string, but not in the list created by splitting a comma-delimited string.

Negative index values can be used to specify a position offset from the end of the sequence.

It is often useful to use a -1 index value to access the last element of a sequence.

The Python *slice notation* can be used to access subsequences by specifying two index positions separated by a colon (':'); seq[start:stop] returns all the elements in seq between start and stop - 1 (inclusive).

Slices index values can be negative.

The start and/or stop index can be omitted. A common use of slices with a single index value is to access all but the first element or all but the last element of a sequence.

Slice notation includes an optional third element, step, as in seq[start:stop:step], that specifies the steps or increments by which elements are retrieved from seq between start and step - 1:

The Python tutorial offers a helpful ASCII art representation to show how positive and negative indexes are interpreted:

 +---+---+---+---+---+
 | H | e | l | p | A |
 +---+---+---+---+---+
 0   1   2   3   4   5
-5  -4  -3  -2  -1

Splitting / separating statements¶

Python statements are typically separated by newlines (rather than, say, the semi-colon in Java). Statements can extend over more than one line; it is generally best to break the lines after commas, parentheses, braces or brackets. Inserting a backslash character ('\') at the end of a line will also enable continuation of the statement on the next line, but it is generally best to look for other alternatives.

Processing strings & other sequences¶

The str.strip([chars]) method returns a copy of str in which any leading or trailing chars are removed. If no chars are specified, it removes all leading and trailing whitespace. [Whitespace is any sequence of spaces, tabs ('\t') and/or newline ('\n') characters.]

Note that since a blank space is inserted in the output after every item in a comma-delimited list, the second asterisk below is printed after a leading blank space is inserted on the new line.

A common programming pattern when dealing with CSV (comma-separated value) files, such as the mushroom dataset file mentioned above, is to repeatedly:

1. read a line from a file
2. strip off any leading and trailing whitespace
3. split the values separated by commas into a list

We will get to repetition control structures (loops) and file input and output shortly, but here is an example of how str.strip() and str.split() be chained together in a single instruction for processing a line representing a single instance from the mushroom dataset file. Note that chained methods are executed in left-to-right order.

[Python providees a csv* module to facilitate the processing of CSV files, but we will not use that module here]*

The str.join(words) method is the inverse of str.split(), returning a single string in which each string in the sequence of words is separated by str.

A number of Python methods can be used on strings, lists and other sequences.

The len(s) function can be used to find the length of (number of items in) a sequence s. It will also return the number of items in a dictionary, a data structure we will cover further below.

The in operator can be used to determine whether a sequence contains a value.

Boolean values in Python are True and False (note the capitalization).

The s.count(x) ormethod can be used to count the number of occurrences of item x in sequence s.

The s.index(x) method can be used to find the first zero-based index of item x in sequence s.

Note that an ValueError exception will be raised if item x is not found in sequence s.

Mutability¶

One important distinction between strings and lists has to do with their mutability.

Python strings are immutable, i.e., they cannot be modified. Most string methods (like str.strip()) return modified copies of the strings on which they are used.

Python lists are mutable, i.e., they can be modified.

The examples below illustrate a number of list methods that modify lists.

When more than one name (e.g., a variable) is bound to the same mutable object, changes made to that object are reflected in all names bound to that object. For example, in the second statement above, list_2 is bound to the same object that is bound to list_1. All changes made to the object bound to list_1 will thus be reflected in list_2 (since they both reference the same object).

We can create a copy of a list by using slice notation and not specifying a start or end parameter, i.e., [:], and if we assign that copy to another variable, the variables will be bound to different objects, so changes to one do not affect the other.

The dir() function returns all the attributes associated with a Python name (e.g., a variable) in alphabetical order.

When invoked with a name bound to a list object, it will return the methods that can be invoked on a list. The attributes with leading and trailing underscores should be treated as protected (i.e., they should not be used); we'll discuss this further below.

There are sorting and reversing functions, sorted() and reversed(), that do not modify their arguments, and can thus be used on mutable or immutable objects.

Note that sorted() always returns a sorted list of each element in its argument, regardless of which type of sequence it is passed. Thus, invoking sorted() on a string returns a list of sorted characters from the string, rather than a sorted string.

The sorted() function sorts its argument in ascending order by default.

An optional *keyword argument*, reverse, can be used to sort in descending order. The default value of this optional parameter is False; to get non-default behavior of an optional argument, we must specify the name and value of the argument, in this case, reverse=True.

Tuples (immutable list-like sequences)¶

A tuple is an ordered, immutable sequence of 0 or more comma-delimited values enclosed in parentheses ('(', ')'). Many of the functions and methods that operate on strings and lists also operate on tuples.

Note that the methods that modify lists (e.g., append(), remove(), reverse(), sort()) are not defined for immutable sequences such as tuples (or strings). Invoking one of these sequence modification methods on an immutable sequence will raise an AttributeError exception.

However, one can approximate these modifications by creating modified copies of an immutable sequence and then re-assigning it to a name.

Note that Python has a += operator which is a shortcut for the name = name + new_value pattern. This can be used for addition (e.g., x += 1 is shorthand for x = x + 1) or concatenation (e.g., x += (7,) is shorthand for x = x + (7,)).

A tuple of one element must include a trailing comma to differentiate it from a parenthesized expression.

Conditionals¶

One common approach to handling errors is to look before you leap (LBYL), i.e., test for potential exceptions before executing instructions that might raise those exceptions.

This approach can be implemented using the if statement (which may optionally include an else and any number of elif clauses).

The following is a simple example of an if statement:

Note that

• a colon (':') is used at the end of the lines with if, else or elif
• no parentheses are required to enclose the boolean condition (it is presumed to include everything between if or elif and the colon)
• the statements below each if, elif and else line are all indented

Python does not have special characters to delimit statement blocks (like the '{' and '}' delimiters in Java); instead, sequences of statements with the same indentation level are treated as a statement block. The Python Style Guide recommends using 4 spaces for each indentation level.

An if statement can be used to follow the LBYL paradigm in preventing the ValueError that occured in an earlier example:

Seeking forgiveness vs. asking for permission (EAFP vs. LBYL)¶

Another perspective on handling errors championed by some pythonistas is that it is easier to ask forgiveness than permission (EAFP).

As in many practical applications of philosophy, religion or dogma, it is helpful to think before you choose (TBYC). There are a number of factors to consider in deciding whether to follow the EAFP or LBYL paradigm, including code readability and the anticipated likelihood and relative severity of encountering an exception. For those who are interested, Oran Looney wrote a blog post providing a nice overview of the debate over LBYL vs. EAFP.

In keeping with practices most commonly used with other languages, we will follow the LBYL paradigm throughout most of this primer.

However, as a brief illustration of the EAFP paradigm in Python, here is an alternate implementation of the functionality of the code above, using a try/except statement.

There is no local scoping inside a try, so the value of i persists after the try/except statement.

The Python null object is None (note the capitalization).

Defining and calling functions¶

Python function definitions start with the def keyword followed by a function name, a list of 0 or more comma-delimited parameters (aka 'formal parameters') enclosed within parentheses, and then a colon (':').

A function definition may include one or more return statements to indicate the value(s) returned to where the function is called. It is good practice to include a short docstring to briefly describe the behavior of the function and the value(s) it returns.

A function call starts with the function name, followed by a list of 0 or more comma-delimited arguments (aka 'actual parameters') enclosed within parentheses. A function call can be used as a statement or within an expression.

Note that Python does not distinguish between names used for variables and names used for functions. An assignment statement binds a value to a name; a function definition also binds a value to a name. At any given time, the value most recently bound to a name is the one that is used.

This can be demonstrated using the type(object) function, which returns the type of object.

Another way to determine the type of an object is to use isinstance(object, class). This is generally preferable, as it takes into account class inheritance. There is a larger issue of duck typing, and whether code should ever explicitly check for the type of an object, but we will omit further discussion of the topic in this primer.

Call by sharing¶

An important feature of Python functions is that arguments are passed using call by sharing.

If a mutable object is passed as an argument to a function parameter, assignment statements using that parameter do not affect the passed argument, however other modifications to the parameter (e.g., modifications to a list using methods such as append(), remove(), reverse() or sort()) do affect the passed argument.

Not being aware of - or forgetting - this important distinction can lead to challenging debugging sessions.

The example below demonstrates this difference and introduces another list method, list.insert(i, x), which inserts x into list at position i.

One way of preventing functions from modifying mutable objects passed as parameters is to make a copy of those objects inside the function. Here is another version of the function above that makes a shallow copy of the list_parameter using the slice operator.

[Note: the Python copy module provides both [shallow] copy() and deepcopy() methods; we will cover modules further below.]

Another way to avoid modifying parameters is to use assignment statements which do not modify the parameter objects but return a new object that is bound to the name (locally).

Multiple return values¶

Python functions can return more than one value by separating those return values with commas in the return statement. Multiple values are returned as a tuple.

If the function-invoking expression is an assignment statement, multiple variables can be assigned the multiple values returned by the function in a single statement. This combining of values and subsequent separation is known as tuple *packing* and *unpacking*.

Iteration: for, range¶

The for statement iterates over the elements of a sequence or other iterable object.

The value of the variable used to iterate in a for statement persists after the for statement

In Python 2, the range(stop) function returns a list of values from 0 up to stop - 1 (inclusive). It is often used in the context of a for loop that iterates over the list of values.

The more general form of the function, range(start, stop[, step]), returns a list of values from start to stop - 1 (inclusive) increasing by step (which defaults to 1), or from start down to stop + 1 (inclusive) decreasing by step if step is negative.

In Python 2, the xrange(stop[, stop[, step]]) function is an iterable version of the range() function. In the context of a for loop, it returns the next item of the sequence for each iteration of the loop rather than creating all the elements of the sequence before the first iteration. This can reduce memory consumption in cases where iteration over all the items is not required.

In Python 3, the range() function behaves the same way as the xrange() function does in Python 2, and so the xrange() function is not defined in Python 3.

To maximize compatibility, we will use range() throughout this notebook; however, note that it is generally more efficient to use xrange() rather than range() in Python 2.

Modules, namespaces and dotted notation¶

A Python *module* is a file containing related definitions (e.g., of functions and variables). Modules are used to help organize a Python *namespace*, the set of identifiers accessible in a particular context. All of the functions and variables we define in this IPython Notebook are in the __main__ namespace, so accessing them does not require any specification of a module.

A Python module named simple_ml (in the file simple_ml.py), contains a set of solutions to the exercises in this IPython Notebook. [The learning opportunity provided by this primer will be maximized by not looking at that file, or waiting as long as possible to do so.]

Accessing functions in an external module requires that we first import the module, and then prefix the function names with the module name followed by a dot (this is known as *dotted notation*).

For example, the following function call in Exercise 1 below:

simple_ml.print_attribute_names_and_values(single_instance_list, attribute_names)

uses dotted notation to reference the print_attribute_names_and_values() function in the simple_ml module.

After you have defined your own function for Exercise 1, you can test your function by deleting the simple_ml module specification, so that the statement becomes

print_attribute_names_and_values(single_instance_list, attribute_names)

This will reference the print_attribute_names_and_values() function in the current namespace (__main__), i.e., the top-level interpreter environment. The simple_ml.print_attribute_names_and_values() function will still be accessible in the simple_ml namespace by using the "simple_ml." prefix (so you can easily toggle back and forth between your own definition and that provided in the solutions file).

Exercise 1: define print_attribute_names_and_values()¶

Complete the following function definition, print_attribute_names_and_values(instance, attribute_names), so that it generates exactly the same output as the code above.

File I/O¶

Python file input and output is done through file objects. A file object is created with the open(name[, mode]) statement, where name is a string representing the name of the file, and mode is 'r' (read), 'w' (write) or 'a' (append); if no second argument is provided, the mode defaults to 'r'.

A common Python programming pattern for processing an input text file is to

• open the file using a with statement (which will automatically close the file after the statements inside the with block have been executed)
• iterate over each line in the file using a for statement

The following code creates a list of instances, where each instance is a list of attribute values (like instance_1_str above).

Exercise 2: define load_instances()¶

Define a function, load_instances(filename), that returns a list of instances in a text file. The function definition is started for you below. The function should exhibit the same behavior as the code above.

Output can be written to a text file via the file.write(str) method.

As we saw earlier, the str.join(words) method returns a single str-delimited string containing each of the strings in the words list.

SQL and Hive database tables sometimes use a pipe ('|') delimiter to separate column values for each row when they are stored as flat files. The following code creates a new data file using pipes rather than commas to separate the attribute values.

To help maintain internal consistency, it is generally a good practice to define a variable such as DELIMITER or SEPARATOR, bind it to the intended delimiter string, and then use it as a named constant. The Python language does not support named constants, so the use of variables as named constants depends on conventions (e.g., using ALL-CAPS).

List comprehensions¶

Python provides a powerful list comprehension construct to simplify the creation of a list by specifying a formula in a single expression.

Some programmers find list comprehensions confusing, and avoid their use. We won't rely on list comprehensions here, but we will offer several examples with and without list comprehensions to highlight the power of the construct.

One common use of list comprehensions is in the context of the str.join(words) method we saw earlier.

If we wanted to construct a pipe-delimited string containing elements of the list, we could use a for loop to iteratively add list elements and pipe delimiters to a string for all but the last element, and then manually add the last element.

This process is much simpler using a list comprehension.

Missing values & "clean" instances¶

As noted in the initial description of the UCI mushroom set above, 2480 of the 8124 instances have missing attribute values (denoted by '?').

There are several techniques for dealing with instances that include missing attribute values, but to simplify things in the context of this primer - and following the example in the Data Science for Business book - we will simply ignore any such instances and restrict our focus to only the clean instances (with no missing values).

We could use several lines of code - with an if statement inside a for loop - to create a clean_instances list from the all_instances list. Or we could use a list comprehension that includes an if statement.

We will show both approaches to creating clean_instances below.

Note that line breaks can be used before a for or if keyword in a list comprehension.

Dictionaries (dicts)¶

Although single character abbreviations of attribute values (e.g., 'x') allow for more compact data files, they are not as easy to understand by human readers as the longer attribute value descriptions (e.g., 'convex').

A Python dictionary (or dict) is an unordered, comma-delimited collection of *key: value* pairs, serving a siimilar function as a hash table or hashmap in other programming languages.

We could create a dictionary for the cap-type attribute values shown above:

bell=b, conical=c, convex=x, flat=f, knobbed=k, sunken=s

Since we will want to look up the value using the abbreviation (which is the representation of the value stored in the file), we will use the abbreviations as keys and the descriptions as values.

A Python dictionary can be created by specifying all key: value pairs (with colons separating each key and value), or by adding them iteratively. We will show the first method in the cell below, and use the second method in a subsequent cell.

Note that a value in a Python dictionary (dict) can be accessed by specifying its key using the general form dict[key] (or dict.get(key, [default]), which allows the specification of a default value to use if key is not in dict).

A Python dictionary is an iterable container, so we can iterate over the keys in a dictionary using a for loop.

Note that since a dictionary is an unordered collection, the sequence of abbreviations and associated values is not guaranteed to appear in any particular order.

Python supports dictionary comprehensions, which have a similar form as the list comprehensions described above, except that both a key and a value have to be specified for each iteration.

For example, if we provisionally omit the 'convex' cap-type (whose abbreviation is the last letter rather than first letter in the attribute name), we could construct a dictionary of abbreviations and descriptions using the following expression.

While it's useful to have a dictionary of values for the cap-type attribute, it would be even more useful to have a dictionary of values for every attribute. Earlier, we created a list of attribute_names; we will now expand this to create a list of attribute_values wherein each list element is a dictionary.

Rather than explicitly type in each dictionary entry in the Python interpreter, we'll define a function to read a file containing the list of attribute names, values and value abbreviations in the format shown above:

• class: edible=e, poisonous=p
• cap-shape: bell=b, conical=c, convex=x, flat=f, knobbed=k, sunken=s
• cap-surface: fibrous=f, grooves=g, scaly=y, smooth=s
• ...

We can make calls to shell commands from a Python cell by using the bang (exclamation point). [There are a large number of cell magics that extend the capability of IPython Notebooks (which we will not explore further in this notebook.]

For example, the following cell will show the contents of the agaricus-lepiota.attributes file on OSX or Linux (for Windows, substitute type for cat).

Exercise 3: define load_attribute_values()¶

We earlier created the attribute_names list manually. The load_attribute_values() function above creates the attribute_values list from the contents of a file, each line of which starts with the name of an attribute. Unfortunately, the function discards the name of each attribute.

It would be nice to retain the name as well as the value abbreviations and descriptions. One way to do this would be to create a list of dictionaries, in which each dictionary has 2 keys, a name, the value of which is the attribute name (a string), and values, the value of which is yet another dictionary (with abbreviation keys and description values, as in load_attribute_values()).

Complete the following function definition so that the code implements this functionality.

Counters¶

Data scientists often need to count things. For example, we might want to count the numbers of edible and poisonous mushrooms in the clean_instances list we created earlier.

More generally, we often want to count the number of occurrences (frequencies) of each possible value for an attribute. One way to do so is to create a dictionary where each dictionary key is an attribute value and each dictionary value is the count of instances with that attribute value.

Using an ordinary dictionary, we must be careful to create a new dictionary entry the first time we see a new attribute value (that is not already contained in the dictionary).

The Python collections module provides a number of high performance container datatypes. A frequently useful datatype is a Counter, a specialized dictionary in which each key is a unique element found in a list or some other container, and each value is the number of occurrences of that element in the source container. The default value for each newly created key is zero.

A Counter includes a method, most_common([n]), that returns a list of 2-element tuples representing the values and their associated counts for the most common n values in descending order of the counts; if n is omitted, the method returns all tuples.

Note that we can either use

import collections

and then use collections.Counter() in our code, or use

from collections import Counter

and then use Counter() (with no module specification) in our code.

When a Counter object is instantiated with a list of items, it returns a dictionary-like container in which the keys are the unique items in the list, and the values are the counts of each unique item in that list.

This allows us to count the number of values for cap-state in a very compact way.

We can use a Counter initialized with a list comprehension to collect all the values of the 2nd attribute, cap-state.

The following shows the first 10 instances; the second element in each sublist is the value of cap-state or that instance.

The following list comprehension gathers the 2nd attribute of each of the first 10 sublists (note the slice notation).

Now we will gather all of the values for the 2nd attribute into a list and create a Counter for that list.

Exercise 4: define attribute_value_counts()¶

Define a function, attribute_value_counts(instances, attribute, attribute_names), that returns a Counter containing the counts of occurrences of each value of attribute in the list of instances. attribute_names is the list we created above, where each element is the name of an attribute.

This exercise is designed to generalize the solution shown in the code directly above (which handles only the cap-state attribute).

More on sorting¶

Earlier, we saw that there is a list.sort() method that will sort a list in-place, i.e., by replacing the original value of list with a sorted version of the elements in list.

We also saw that the sorted(iterable[, cmp[, key[, reverse]]]) function can be used to return a copy of a list, dictionary or any other iterable container it is passed, in ascending order.

sorted() can also be used with dictionaries (it returns a sorted list of the dictionary keys).

We can use the sorted keys to access the values of a dictionary in ascending order of the keys.

Sorting a dictionary by values¶

It is often useful to sort a dictionary by its values rather than its keys.

For example, when we printed out the counts of the attribute values for cap-shape above, the counts appeared in an ascending alphabetic order of their attribute names. It is often more helpful to show the attribute value counts in descending order of the counts (which are the values in that dictionary).

There are a variety of ways to sort a dictionary by values, but the approach described in PEP-256 is generally considered the most efficient.

In order to understand the components used in this approach, we will revisit and elaborate on a few concepts involving dictionaries, iterators and modules.

The dict.items() method returns an unordered list of (key, value) tuples in dict.

In Python 2, a related method, dict.iteritems(), returns an iterator: a callable object that returns the next item in a sequence each time it is referenced (e.g., during each iteration of a for loop), which can be more efficient than generating all the items in the sequence before any are used ... and so should be used rather than items() wherever possible

This is similar to the distinction between xrange() and range() described above ... and, also similarly, dict.items() is an iterator in Python 3 and so dict.iteritems() is no longer needed (nor defined) ... and further similarly, we will use only dict.items() in this notebook, but it is generally more efficient to use dict.iteritems() in Python 2.

The Python operator module contains a number of functions that perform object comparisons, logical operations, mathematical operations, sequence operations, and abstract type tests.

To facilitate sorting a dictionary by values, we will use the operator.itemgetter(i) function that can be used to retrieve the ith value in a tuple (such as a (key, value) pair returned by [iter]items()).

We can use operator.itemgetter(1)) to reference the value - the 2nd item in each (key, value) tuple, (at zero-based index position 1) - rather than the key - the first item in each (key, value) tuple (at index position 0).

We will use the optional keyword argument key in sorted(iterable[, cmp[, key[, reverse]]]) to specify a sorting key that is not the same as the dict key (recall that the dict key is the default sorting key for sorted()).

We can now sort the counts of attribute values in descending frequency of occurrence, and print them out using tuple unpacking.

Note that this example is rather contrived, as it is generally easiest to use a Counter and its associated most_common() method when sorting a dictionary wherein the values are all counts. The need to sort other kinds of dictionaries by their values is rather common.

String formatting¶

It is often helpful to use fancier output formatting than simply printing comma-delimited lists of items.

Examples of the str.format() function used in conjunction with print statements is shown below.

More details can be found in the Python documentation on format string syntax.

The following example illustrates the use of str.format() on data associated with the mushroom dataset.

The following variation - splitting off the printing of the attribute name from the printing of the values and counts of values for that attrbiute - may be more useful in developing a solution to the following exercise.

Exercise 5: define print_all_attribute_value_counts()¶

Define a function, print_all_attribute_value_counts(instances, attribute_names), that prints each attribute name in attribute_names, and then for each attribute value, prints the value abbreviation, the count of occurrences of that value and the proportion of instances that have that attribute value.

4. Using Python to Build and Use a Simple Decision Tree Classifier¶

Decision Trees¶

Wikipedia offers the following description of a decision tree (with italics added to emphasize terms that will be elaborated below):

A decision tree is a flowchart-like structure in which each internal node represents a test of an attribute, each branch represents an outcome of that test and each leaf node represents class label (a decision taken after testing all attributes in the path from the root to the leaf). Each path from the root to a leaf can also be represented as a classification rule.

[Decision trees can also be used for regression, wherein the goal is to predict a continuous value rather than a class label, but we will focus here solely on their use for classification.]

The image below depicts a decision tree created from the UCI mushroom dataset that appears on Andy G's blog post about Decision Tree Learning, where

• a white box represents an internal node (and the label represents the attribute being tested)
• a blue box represents an attribute value (an outcome of the test of that attribute)
• a green box represents a leaf node with a class label of edible
• a red box represents a leaf node with a class label of poisonous

It is important to note that the UCI mushroom dataset consists entirely of categorical variables, i.e., every variable (or attribute) has an enumerated set of possible values. Many datasets include numeric variables that can take on int or float values. Tests for such variables typically use comparison operators, e.g., $age < 65$ or $36,250 < adjusted\_gross\_income <= 87,850$. [Aside: Python supports boolean expressions containing multiple comparison operators, such as the expression comparing adjusted_gross_income in the preceding example.]

Our simple decision tree will only accommodate categorical variables. We will closely follow a version of the decision tree learning algorithm implementation offered by Chris Roach.

Our goal in the following sections is to use Python to

• *create* a simple decision tree using a set of training instances
• *classify* (predict class labels) for a set of test instances using a simple decision tree
• *evaluate* the performance of a simple decision tree on classifying a set of test instances

First, we will explore some concepts and algorithms used in building and using decision trees.

Entropy¶

When building a supervised classification model, the frequency distribution of attribute values is a potentially important factor in determining the relative importance of each attribute at various stages in the model building process.

In data modeling, we can use frequency distributions to compute *entropy*, a measure of disorder (impurity) in a set.

We compute the entropy of multiplying the proportion of instances with each class label by the log of that proportion, and then taking the negative sum of those terms.

More precisely, for a 2-class (binary) classification task:

$entropy(S) = - p_1 log_2 (p_1) - p_2 log_2 (p_2)$

where $p_i$ is proportion (relative frequency) of class i within the set S.

From the output above, we know that the proportion of clean_instances that are labeled 'e' (class edible) in the UCI dataset is $3488 \div 5644 = 0.618$, and the proportion labeled 'p' (class poisonous) is $2156 \div 5644 = 0.382$.

After importing the Python math module, we can use the math.log(x[, base]) function in computing the entropy of the clean_instances of the UCI mushroom data set as follows.

Exercise 6: define entropy()¶

Define a function, entropy(instances), that computes the entropy of instances. You may assume the class label is in position 0; we will later see how to specify default parameter values in function definitions.

[Note: the class label in many data files is the last rather than the first item on each line.]

Information Gain¶

Informally, a decision tree is constructed from a set of instances using a recursive algorithm that

• selects the best attribute
• splits the set into subsets based on the values of that attribute (each subset is composed of instances from the original set that have the same value for that attribute)
• repeats the process on each of these subsets until a stopping condition is met (e.g., a subset has no instances or has instances which all have the same class label)

Entropy is a metric that can be used in selecting the best attribute for each split: the best attribute is the one resulting in the largest decrease in entropy for a set of instances. [Note: other metrics can be used for determining the best attribute]

Information gain measures the decrease in entropy that results from splitting a set of instances based on an attribute.

$IG(S, a) = entropy(S) - [p(s_1) × entropy(s_1) + p(s_2) × entropy(s_2) ... + p(s_n) × entropy(s_n)]$

Where

• $n$ is the number of distinct values of attribute $a$
• $s_i$ is the subset of $S$ where all instances have the $i$th value of $a$
• $p(s_i)$ is the proportion of instances in $S$ that have the $i$th value of $a$

We'll use the definition of information_gain() in simple_ml to print the information gain for each of the attributes in the mushroom dataset ... before asking you to write your own definition of the function.

We can sort the attributes based in decreasing order of information gain, which shows that odor is the best attribute for the first split in a decision tree that models the instances in this dataset.

[The following variation does not use a list comprehension]

Exercise 7: define information_gain()¶

Define a function, information_gain(instances, i), that returns the information gain achieved by selecting the ith attribute to split instances. It should exhibit the same behavior as the simple_ml version of the function.

Building a Simple Decision Tree¶

We will implement a modified version of the ID3 algorithm for building a simple decision tree.

ID3 (Examples, Target_Attribute, Candidate_Attributes)
    Create a Root node for the tree
    If all examples have the same value of the Target_Attribute, 
        Return the single-node tree Root with label = that value 
    If the list of Candidate_Attributes is empty,
        Return the single node tree Root,
            with label = most common value of Target_Attribute in the examples.
    Otherwise Begin
        A ← The Attribute that best classifies examples (most information gain)
        Decision Tree attribute for Root = A.
        For each possible value, v_i, of A,
            Add a new tree branch below Root, corresponding to the test A = v_i.
            Let Examples(v_i) be the subset of examples that have the value v_i for A
            If Examples(v_i) is empty,
                Below this new branch add a leaf node 
                    with label = most common target value in the examples
            Else 
                Below this new branch add the subtree 
                    ID3 (Examples(v_i), Target_Attribute, Attributes – {A})
    End
    Return Root

[Note:* the algorithm above is recursive, i.e., the there is a recursive call to ID3 within the definition of ID3. Covering recursion is beyond the scope of this primer, but there are a number of other resources on using recursion in Python. Familiarity with recursion will be important for understanding both the tree construction and classification functions below.]*

In building a decision tree, we will need to split the instances based on the index of the best attribute, i.e., the attribute that offers the highest information gain. We will use separate utility functions to handle these subtasks. To simplify the functions, we will rely exclusively on attribute indexes rather than attribute names.

First, we will define a function, split_instances(instances, attribute_index), to split a set of instances based on any attribute. This function will return a dictionary where each key is a distinct value of the specified attribute_index, and the value of each key is a list representing the subset of instances that have that attribute_index value.

We will use a defaultdict, a specialized dictionary class in the collections module, which automatically creates an appropriate default value for a new key. For example, a defaultdict(int) automatically initializes a new dictionary entry to 0 (zero); a defaultdict(list) automatically initializes a new dictionary entry to the empty list ([]).

To test the function, we will partition the clean_instances based on the odor attribute (index position 5) and print out the size (number of instances) in each partition rather than the lists of instances in each partition.

Now that we can split instances based on a particular attribute, we would like to be able to choose the best attribute with which to split the instances, where best is defined as the attribute that provides the greatest information gain if instances were split based on that attribute. We will want to restrict the candidate attributes so that we don't bother trying to split on an attribute that was used higher up in the decision tree (or use the target attribute as a candidate).

Exercise 8: define choose_best_attribute_index()¶

Define a function, choose_best_attribute_index(instances, candidate_attribute_indexes), that returns the index in the list of candidate_attribute_indexes that provides the highest information gain if instances are split based on that attribute index.

A leaf node in a decision tree represents the most frequently occurring - or majority - class value for that path through the tree. We will need a function that determines the majority value for the class index among a set of instances. One way to do this is to use the Counter class introduced above.

[The following variation does not use a list comprehension]

It is often useful to compute the number of unique values and/or the total number of values in a Counter.

The number of unique values is simply the number of dictionary entries.

The total number of values can be computed by taking the sum() of all the counts (the value of each key: value pair ... or key, value tuple, if we use Counter().most_common()).

Before putting all this together to define a decision tree construction function, we will cover a few additional aspects of Python used in that function.

Truth values in Python¶

Python offers a very flexible mechanism for the testing of truth values: in an if condition, any null object, zero-valued numerical expression or empty container (string, list, dictionary or tuple) is interpreted as False (i.e., not True):

Sometimes, particularly with function parameters, it is helpful to differentiate None from empty lists and other data structures with a False truth value (one common use case is illustrated in create_decision_tree() below).

Conditional expressions (ternary operators)¶

Python also offers a conditional expression (ternary operator) that allows the functionality of an if/else statement that returns a value to be implemented as an expression. For example, the if/else statement in the code above could be implemented as a conditional expression as follows:

More on optional parameters in Python functions¶

Python function definitions can specify default parameter values indicating the value those parameters will have if no argument is explicitly provided when the function is called. Arguments can also be passed using keyword parameters indicting which parameter will be assigned a specific argument value (which may or may not correspond to the order in which the parameters are defined).

The Python Tutorial page on default parameters includes the following warning:

Important warning: The default value is evaluated only once. This makes a difference when the default is a mutable object such as a list, dictionary, or instances of most classes.

Thus it is generally better to use the Python null object, None, rather than an empty list ([]), dict ({}) or other mutable data structure when specifying default parameter values for any of those data types.

Exercise 9: define majority_value()¶

Define a function, majority_value(instances, class_index), that returns the most frequently occurring value of class_index in instances. The class_index parameter should be optional, and have a default value of 0 (zero).

Your function definition should support the use of optional arguments as used in the function calls below.

Building a Simple Decision Tree¶

The recursive create_decision_tree() function below uses an optional parameter, class_index, which defaults to 0. This is to accommodate other datasets in which the class label is the last element on each line (which would be most easily specified by using a -1 value). Most data files in the UCI Machine Learning Repository have the class labels as either the first element or the last element.

To show how the decision tree is being built, an optional trace parameter, when non-zero, will generate some trace information as the tree is constructed. The indentation level is incremented with each recursive call via the use of the conditional expression (ternary operator), trace + 1 if trace else 0.