<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 E-Divisive Analysis
This notebook aims to test out the different E-Divisive implementations we could be using in the Dashboard, starting with the one we already have and potentially using a combination of third-party libraries. The intent of the notebook is both to compare and contrast the different approaches, pros/cons of using each of these options.
NOTE
Step1:  From this point on we can use ccd to refer to our clustering change detector implementation in the Dashboard. Here we can use all sorts of utilities that we can also analyse. The first one we'll use is the estimator implementation
Step2:  Let's now visualize the data, showing the probabilities along the range of values we've encountered.
Step3:  As we can see in the charts above, we can now see how the estimator works for finding where change points could be based on how the particular point partitions the space. While that's interesting, we still need to check which/whether these high-probability change points partition the space nicely (or in a statistically significant way).
This is where the Mann-Whitney U-Test and Kolmogorov-Smirnov tests can help us with determining the likelihood that these are actually points that clearly partition the measurements. We'll use the ChangePointEstimator function to give us a most-likely index for the dataset we've provided.
Step4:  Alternative A
Step5:  Alternative B
<ASSISTANT_TASK:>
Python Code:
import sys
_CATAPULT_PATH=os.path.join(os.path.abspath(''), '..', '..', '..')
_DASHBOARD_PATH=os.path.join(_CATAPULT_PATH, 'dashboard')
# Set up the environment so that we can import the modules in the
# Dashboard codebase.
sys.path.insert(0, _CATAPULT_PATH)
sys.path.insert(0, _DASHBOARD_PATH)
import dashboard
# Include all the paths needed for testing
for path in dashboard.PathsForTesting():
    sys.path.insert(0, path)
from dashboard.common import clustering_change_detector as ccd
import pandas as pd
import numpy as np
import statsmodels as sm
import numba as nb
import matplotlib.pyplot as plt
Explanation: E-Divisive Analysis
This notebook aims to test out the different E-Divisive implementations we could be using in the Dashboard, starting with the one we already have and potentially using a combination of third-party libraries. The intent of the notebook is both to compare and contrast the different approaches, pros/cons of using each of these options.
NOTE: This requires that pandas, numpy, scipy, statsmodels, numba, and matplotlib are installed to execute. We are also using Python 3.7 to gain access to the latest versions of these libraries. To install these in your system, this should be sufficient:
pip3 install --user numpy scipy pandas statsmodels \
    numba matplotlib
End of explanation
# Create a random dataset from some normal distributions.
measurements = np.concatenate(
        (np.random.normal(100, 5, 50),
        np.random.normal(20, 5, 50),
        np.random.normal(100, 5, 50)),
        axis=None)
commits = np.arange(1000,1150,dtype=np.int64)
frame = pd.DataFrame(measurements, columns=['measurement'], index=commits)
frame
# We then create a column of estimates. First, we'll do it with
# the pure Python implementation, and time it.
def create_estimates(measurements):
    results = np.array(
        [ccd.Estimator(measurements, i) for i in
         range(len(measurements))])
    return results
estimates=create_estimates(measurements)
frame['estimates'] = estimates
frame['probability'] = estimates / np.nanmax(estimates)
%timeit create_estimates(measurements)
Explanation: From this point on we can use ccd to refer to our clustering change detector implementation in the Dashboard. Here we can use all sorts of utilities that we can also analyse. The first one we'll use is the estimator implementation:
End of explanation
fig, axes = plt.subplots(2, 1, sharex=True)
frame['measurement'].plot.line(ax=axes[0], title='Measurements')
frame['probability'].plot.line(ax=axes[1], title='Probabilities',color='r')
Explanation: Let's now visualize the data, showing the probabilities along the range of values we've encountered.
End of explanation
# We need to convert the measurements into a Python list
# because the pure Python implementation can only work with
# those native objects.
inputs = list(measurements)
result = ccd.ClusterAndFindSplit(inputs)
# WARNING: Running this might take a while depending on how
# capable your machine is.
%timeit ccd.ClusterAndFindSplit(inputs)
print(result)
Explanation: As we can see in the charts above, we can now see how the estimator works for finding where change points could be based on how the particular point partitions the space. While that's interesting, we still need to check which/whether these high-probability change points partition the space nicely (or in a statistically significant way).
This is where the Mann-Whitney U-Test and Kolmogorov-Smirnov tests can help us with determining the likelihood that these are actually points that clearly partition the measurements. We'll use the ChangePointEstimator function to give us a most-likely index for the dataset we've provided.
End of explanation
# TODO(dberris): Implement the purely vectorized versions here.
Explanation: Alternative A: Vectorized Implementation
The shortcoming for the above implementation, is that it's using a non-vectorized core performing permutation testing on sub-sets. In this section we're going to explore an alternative implementation which uses more facilities in pandas to help us generate the permutation space in a vectorized manner, as well as vectorize our computation of the estimator.
End of explanation
# TODO(dberris): Implement a GPU-accelerated versions here.
Explanation: Alternative B: Using GPUs
While it's fine to be using just the SIMD instructions with numba, if we're dealing with a lot of data (in the order of tens of thousands of points) we might actually benefit from using GPUs.
End of explanation
<END_TASK>