From Simple to Complicated

This section presents three major strategies to cope with the Complicated domain: improving the asymptotic running time of an algorithm, applying randomization and sampling, and using parallel/distributed computing. All of them should be potential options in crafting your next data science product. It is very important to start with the simplest solution and gradually enhance it. For this you would need a complete performance test harness, which we are going to showcase here. I have selected the next couple of examples because they are as straightforward as possible while still conveying the main point.

Counting the Occurrences of a Digit

Suppose you need to count how many times a particular digit d appears in numbers inside an interval [1, n], where n ∈ ℕ ∧ n ≤ 10⁵⁰. You may start with the naive approach depicted in Listing 11-1. Don’t underestimate the utility of such a brute-force program. It may serve well as a test generator (source of truth) for more advanced solutions.

k, n = tuple(map(int, input().split()))

def count_occurrences_digit_naive(k, n):

    k = str(k)

    count = 0

    for i in range(n + 1):

        count += str(i).count(k)

    return count

print(count_occurrences_digit_naive(k, n))

Listing 11-1

Dumb Algorithm That Works Reasonably Well If n Is Under 10⁷

According to the nonfunctional requirements (users should not wait for decades to get the result), we definitely cannot accept this program. It is simply too slow, with roughly linear running time, so we must move beyond the Simple case, as suggested by the Cynefin framework. This is the moment to build the proper infrastructure around performance testing. A similar job is needed to test feeding data into your product, which is part of the data engineering effort. We will use visualization to track time measurements. Listing 11-2 shows the facility to test comparatively different program variants. The functions shown in bold comprise the reusable pieces of this script. The driver code is located inside the conditional block at the end. All you need to do is provide a proper configuration. The attach_model function finds the right constant that goes along with the base model.

import time

import numpy as np

import pandas as pd

def measure(f, num_repetitions=5):

    measurements = np.array([])

    for _ in range(num_repetitions):

        start = time.clock()

        f()

        measurements = np.append(measurements, time.clock() - start)

    return measurements.mean()

def execute(config):

    execution_times = {}

    for config_name in config['functions']:

        execution_times[config_name] = np.array([])

    for x in config['span']:

        for config_name in config['functions']:

            execution_times[config_name] = np.append(

                    execution_times[config_name],

                    measure(lambda: config['functions'][config_name](x)))

    return execution_times

def attach_model(execution_times, config, function_name, model_name):

    model_vals = np.vectorize(config['models'][model_name])(config['span'])

    c = np.mean(execution_times[function_name] / model_vals)

    execution_times[model_name] = c ∗ model_vals

def report(execution_times, x_vals, ∗∗plot_kwargs):

    df = pd.DataFrame(execution_times)

    df.index = x_vals

    ax = df.plot.line(

        figsize=(10, 8),

        title='Performance Test Report',

        grid=True,

        **plot_kwargs

    )

    ax.set_xlabel('Span')

    ax.set_ylabel('Time [s]')

    return df

if __name__ == '__main__':

    from count_occurrences_digit_naive import count_occurrences_digit_naive

    config = {

        'functions': {

            'naive(k=0)': lambda n: count_occurrences_digit_naive(0, n)

        },

        'models': {

            'O(n)': lambda n: n

        },

        'span': np.geomspace(10∗∗2, 10∗∗7, num=14, dtype=int)

    }

    execution_times = execute(config)

    attach_model(execution_times, config, 'naive(k=0)', 'O(n)')

    print(report(execution_times, config['span'], logx=True, style=['-ro', ':r^']))

Listing 11-2

Performance Test Harness to Track Time Measurements and Visualize Them

After executing this code you will get the following report as well as the line plot, as shown in Figure 11-3:

          naive(k=0)      O(n)

100         0.000073  0.000050

242         0.000111  0.000121

587         0.000251  0.000293

1425        0.000608  0.000712

3455        0.001539  0.001725

8376        0.003793  0.004183

20309       0.009700  0.010141

49238       0.023221  0.024587

119377      0.060661  0.059611

289426      0.145676  0.144526

701703      0.361976  0.350397

1701254     0.872631  0.849525

4124626     2.182770  2.059641

10000000    5.334004  4.993522

The O(n) model is a slight underestimation, since the body of the loop in Listing 11-1 does depend on the input size. Nevertheless, for very large input sizes (when the running time would be better modeled as O(n log n)), we cannot even wait for the test to finish.

Listing 11-3 shows a much faster O(log n) algorithm that is a result of analyzing the recurring pattern for the number of digits in ranges [1, 10ⁱ − 1], ∀ i ∈ ℕ ∧ i ≤ 50. Digits from one to nine produce the same pattern, while zero is a bit different (we need to ignore leading zeros, so the formula is somewhat more challenging). After changing the driver to code to include this faster variant, we get as the line plot shown in Figure 11-4. The difference in execution time is indeed startling. You may modify the test run to cover the full range (you should omit the naive algorithm, as it cannot perform acceptably when n > 10⁷). It is not hard to generalize the code to handle numbers in arbitrary base (like 16).

def setup():

    MAX_EXPONENT = 50

    # Holds the number of occurrences of digit k in [0, (10**i) - 1], i > 0.

    # If the range is partial (first part of the composite key is False), then

    # leading zeros are omitted (this is a special case when k == 0).

    table_of_occurrences = {(False, 0): 0, (False, 1): 1,

                             (True, 0): 0, (True, 1): 1}

    for i in range(2, MAX_EXPONENT + 1):

        table_of_occurrences[(True, i)] = i * 10**(i - 1)

        table_of_occurrences[(False, i)] =

            10**(i - 1) + 10 * table_of_occurrences[(False, i - 1)] - 10

    return table_of_occurrences

def count_occurrences_digit(k, n, table_of_occurrences=setup()):

    digits = str(n)

    num_digits = len(digits)

    count = 0

    is_first_digit = num_digits > 1

    for digit in map(int, digits):

        span = 10**(num_digits - 1)

        count += (digit - 1) * table_of_occurrences[(True, num_digits - 1)]

        count += table_of_occurrences[(k != 0 or not is_first_digit, num_digits - 1)]

        if digit > k:

            if k > 0 or not is_first_digit:

                count += span

        elif digit == k:

            count += (n % span) + 1

        num_digits -= 1

        is_first_digit = False

    return count

if __name__ == '__main__':

    k, n = tuple(map(int, input().split()))

    print(count_occurrences_digit(k, n))

Listing 11-3

Improved Logarithmic Version That Uses an Additional O(log n) Memory Space.

This case study has demonstrated a situation in which speedup is possible without jeopardizing accuracy. Moreover, the improved code doesn’t require any additional infrastructural support. Trying to find a better algorithm should be your top priority (before thinking about Hadoop, Spark, etc.).

Estimating the Edge Betweenness Centrality

In Chapter 10, as part of graph analysis, we examined some centrality metrics for a social network. Among them was the edge betweenness centrality. Calculating the exact value for this metric is CPU intensive. When the network is large and you are interested only in getting a good enough result, then sampling is a viable option. The idea is very simple: You calculate the metric based upon N samples instead over a whole network. This usually gives you nearly identical results, although in a much shorter time. NetworkX has built-in support for this approach. Listing 11-4 shows the code for visually comparing the absolutely accurate outcome with that from sampling. You may want to play around with the code and increase the number of samples. Obviously, as the sample size increases, you will get more accurate figures, but the running time will also increase. You need to experiment to attain the sweet spot.

import operator

import networkx as nx

import matplotlib.pyplot as plt

G = nx.karate_club_graph()

node_colors = ['orange' if props['club'] == 'Officer' else 'blue'

               for _, props in G.nodes(data=True)]

node_sizes = [180 * G.degree(u) for u in G]

plt.figure(figsize=(10, 10))

pos = nx.kamada_kawai_layout(G)

nx.draw_networkx(G, pos,

                 node_size=node_sizes,

                 node_color=node_colors, alpha=0.8,

                 with_labels=False,

                 edge_color='.6')

# Calculating the absolute edge betweenness centrality.

main_conns = nx.edge_betweenness_centrality(G, normalized=True)

main_conns = sorted(main_conns.items(), key=operator.itemgetter(1), reverse=True)[:5]

main_conns = tuple(map(operator.itemgetter(0), main_conns))

nx.draw_networkx_edges(G, pos, edgelist=main_conns, edge_color="green", alpha=0.5, width=6)

# Estimating the edge betweenness centrality by sampling 40% of nodes.

NUM_SAMPLES = int(0.4 * len(G))

est_main_conns = nx.edge_betweenness_centrality(G, k=NUM_SAMPLES, normalized=True, seed=10)

est_main_conns = sorted(est_main_conns.items(), key=operator.itemgetter(1), reverse=True)[:5]

est_main_conns = tuple(map(operator.itemgetter(0), est_main_conns))

nx.draw_networkx_edges(G, pos, edgelist=est_main_conns,

                       edge_color='red', alpha=0.9, width=6, style="dashed")

Listing 11-4

For the sake of terseness, only the first part of the code is repeated, which slightly differs from the original version. Notice the section for evaluating est_main_conns by using 40% of nodes. The karate club network is very small, and sampling is truly beneficial with huge networks. Nonetheless, the principle is the same.

Observe that I’ve set the seed parameter. This is crucial in order for others to reproduce the results using randomization. Figure 11-5 shows the new graph.

This case study has illustrated how you may exchange accuracy for better performance. This sort of randomization belongs to the class of Monte Carlo methods. The Las Vegas model always produces an accurate result, but in some very rare incidents it may run slower (a good example is quick sort). At any rate, the new code runs faster without reaching out for a computing cluster (see Exercise 11-2).

From Disorder to Complex

The Complicated domain is characterized by known unknowns, while the Complex domain is about unknown unknowns. Disorder should be a temporary state while you explore the problem space to understand where it belongs. In this respect, Disorder is the catalyst for exploratory data analysis.

High-dimensional datasets are the most probable reason for initial confusion. Classical visualization doesn’t properly operate here, since you don’t even know how to represent those dimensions. With high-dimensional data there are lots of duplicated and uninformative features (for example, those that have extremely low or zero variance). These should be dropped from the corpus. Furthermore, many of them will turn out to be unrelated to the target variable, and as such should also be removed as irrelevant. The primary aim is to reduce dimensionality, so that you can see the forest for the trees. The gold standard is the principal component analysis (PCA) method, which applies feature extraction to describe your data in terms of orthogonal principal components.

In this section, we will focus our attention solely on a special visualization technique called t-SNE to glimpse into high-dimensional data; see reference [2] for a nice interactive introduction to this topic as well as how to avoid common pitfalls. In a sense, this is a meta application of the Cynefin framework, since we must consider visualization as Complex/Complicated instead of treating it as Simple.

As a side note, you should also try to peek into the dataset using standard techniques, such as using the describe method on the Pandas dataframe. Columns whose variance is near zero are good candidates for removal. Moreover, you can pairwise visualize columns using the pairplot function in Seaborn. Highly correlated columns are redundant, and you should avoid them. These actions are all associated with feature selection. Part of this can also be automated. For example, you can use the sklearn.feature_selection module that implements feature selection algorithms. For pruning low-variance features, you may use the VarianceThreshold class . At any rate, all these methods are OK for low-dimensional datasets (those with less than ten columns/features).

Feature extraction is complementary to feature selection when new features are created. For example, arranging instances into bins (a process called binning) is an example of creating new categorical features. We have already encountered this in Chapter 2, where we grouped users by age range.

Exploring the KDD Cup 1999 Data

As stated on the official KDD Cup 1999 Data web site (see https://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html ):

• This is the data set used for The Third International Knowledge Discovery and Data Mining Tools Competition, which was held in conjunction with KDD-99 The Fifth International Conference on Knowledge Discovery and Data Mining. The competition task was to build a network intrusion detector, a predictive model capable of distinguishing between “bad” connections, called intrusions or attacks, and “good” normal connections. This database contains a standard set of data to be audited, which includes a wide variety of intrusions simulated in a military network environment.

Listing 11-6 shows t-SNE in action for revealing some patterns in the KDD Cup dataset (scikit-learn is packaged with full support for this data). There are 41 features in total. Among them, 34 are numerical, which are only acceptable by t-SNE. Categorical variables should be deselected or encoded. The t-SNE method is very susceptible to even tiny changes. The two auxiliary methods in Listing 11-6 download the column descriptors from the official web site (see also Figure 11-6).

from sklearn.datasets import fetch_kddcup99

from sklearn.manifold import TSNE

import pandas as pd

import matplotlib.pyplot as plt

import seaborn as sns

def retrieve_column_desc():

    import requests

    r = requests.get('https://kdd.ics.uci.edu/databases/kddcup99/kddcup.names')

    column_desc = {}

    for row in r.text.split(' ')[1:]:

        if row.find(':') > 0:

            col_name, col_type = row[:-1].split(':')

            column_desc[col_name] = col_type.strip()

    return column_desc

def get_numeric_columns(column_desc):

    return [name for name in column_desc if column_desc[name] == 'continuous']

column_desc = retrieve_column_desc()

numeric_columns = get_numeric_columns(column_desc)

print('Number of numeric columns:', len(numeric_columns))

X, _ = fetch_kddcup99(subset='SA', random_state=10, return_X_y=True)

X = pd.DataFrame(X, columns=column_desc.keys())

X[numeric_columns] = X[numeric_columns].apply(pd.to_numeric)

# We need to work on a small sample to get results in any reasonable time frame.

X = X.sample(frac=0.05, random_state=10)

m = TSNE(learning_rate=150, random_state=10)

X_tsne = m.fit_transform(X[numeric_columns])

print('First 10 rows of the TSNE reduced dataset:')

print(X_tsne[:10, :])

X['t-sne_1'] = X_tsne[:, 0]

X['t-sne_2'] = X_tsne[:, 1]

sns.set(rc={'figure.figsize': (10, 10)})

sns.scatterplot(x='t-sne_1', y='t-sne_2',

                hue='protocol_type', style="protocol_type",

                data=X[numeric_columns + ['protocol_type', 't-sne_1', 't-sne_2']])

plt.show()

Listing 11-6

Code to Showcase the Power of t-SNE, although you must be patient to try out many different parameter settings (learning rate, random state, perplexity, number of t-SNE components, etc.).

The protocol_type symbolic variable is used to mark various groups (observe the green icmp cluster on the right), and there is a good separation in behavior between them. Once again, t-SNE was able to squeeze out these patterns without looking at the protocol_type feature.

This case study has illuminated the importance of doing exploratory data analysis as part of figuring out into which Cynefin domain your data science problem belongs. Once you know that you need to perform feature extraction and related dimensionality reduction, then you can proceed further by applying PCA or a similar technique. Reducing dimensionality aids your machine learning efforts, since the reduced dataset doesn’t require huge storage or processing time, and you reduce the danger of overfitting your model.

Cynefin and Data Science

Summary

Knowing when a particular approach is proper and admissible is the cornerstone of being a successful data scientist. You must resist the hype and temptation to build your product around a novel technology for the sake of trying things out. Algorithms are at the heart of dealing with Big Data, together with mathematical statistics. This chapter has illustrated how the Cynefin framework provides context for better decision-making and choosing the right solution.

References