pax_global_header 0000666 0000000 0000000 00000000064 14142342150 0014506 g ustar 00root root 0000000 0000000 52 comment=808b62c093b1cd8d6dbef0fd7b88bb4a63c771fd
sanity-quickdt-808b62c/ 0000775 0000000 0000000 00000000000 14142342150 0015015 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/.gitignore 0000664 0000000 0000000 00000000140 14142342150 0017000 0 ustar 00root root 0000000 0000000 target/
test-output/
*.iml
.project
.classpath
testdata/
/.idea/
.settings/
local-*
logback.xsd
sanity-quickdt-808b62c/.travis.yml 0000664 0000000 0000000 00000000017 14142342150 0017124 0 ustar 00root root 0000000 0000000 language: java
sanity-quickdt-808b62c/LICENSE 0000664 0000000 0000000 00000016744 14142342150 0016036 0 ustar 00root root 0000000 0000000 GNU LESSER GENERAL PUBLIC LICENSE
Version 3, 29 June 2007
Copyright (C) 2007 Free Software Foundation, Inc.
Everyone is permitted to copy and distribute verbatim copies
of this license document, but changing it is not allowed.
This version of the GNU Lesser General Public License incorporates
the terms and conditions of version 3 of the GNU General Public
License, supplemented by the additional permissions listed below.
0. Additional Definitions.
As used herein, "this License" refers to version 3 of the GNU Lesser
General Public License, and the "GNU GPL" refers to version 3 of the GNU
General Public License.
"The Library" refers to a covered work governed by this License,
other than an Application or a Combined Work as defined below.
An "Application" is any work that makes use of an interface provided
by the Library, but which is not otherwise based on the Library.
Defining a subclass of a class defined by the Library is deemed a mode
of using an interface provided by the Library.
A "Combined Work" is a work produced by combining or linking an
Application with the Library. The particular version of the Library
with which the Combined Work was made is also called the "Linked
Version".
The "Minimal Corresponding Source" for a Combined Work means the
Corresponding Source for the Combined Work, excluding any source code
for portions of the Combined Work that, considered in isolation, are
based on the Application, and not on the Linked Version.
The "Corresponding Application Code" for a Combined Work means the
object code and/or source code for the Application, including any data
and utility programs needed for reproducing the Combined Work from the
Application, but excluding the System Libraries of the Combined Work.
1. Exception to Section 3 of the GNU GPL.
You may convey a covered work under sections 3 and 4 of this License
without being bound by section 3 of the GNU GPL.
2. Conveying Modified Versions.
If you modify a copy of the Library, and, in your modifications, a
facility refers to a function or data to be supplied by an Application
that uses the facility (other than as an argument passed when the
facility is invoked), then you may convey a copy of the modified
version:
a) under this License, provided that you make a good faith effort to
ensure that, in the event an Application does not supply the
function or data, the facility still operates, and performs
whatever part of its purpose remains meaningful, or
b) under the GNU GPL, with none of the additional permissions of
this License applicable to that copy.
3. Object Code Incorporating Material from Library Header Files.
The object code form of an Application may incorporate material from
a header file that is part of the Library. You may convey such object
code under terms of your choice, provided that, if the incorporated
material is not limited to numerical parameters, data structure
layouts and accessors, or small macros, inline functions and templates
(ten or fewer lines in length), you do both of the following:
a) Give prominent notice with each copy of the object code that the
Library is used in it and that the Library and its use are
covered by this License.
b) Accompany the object code with a copy of the GNU GPL and this license
document.
4. Combined Works.
You may convey a Combined Work under terms of your choice that,
taken together, effectively do not restrict modification of the
portions of the Library contained in the Combined Work and reverse
engineering for debugging such modifications, if you also do each of
the following:
a) Give prominent notice with each copy of the Combined Work that
the Library is used in it and that the Library and its use are
covered by this License.
b) Accompany the Combined Work with a copy of the GNU GPL and this license
document.
c) For a Combined Work that displays copyright notices during
execution, include the copyright notice for the Library among
these notices, as well as a reference directing the user to the
copies of the GNU GPL and this license document.
d) Do one of the following:
0) Convey the Minimal Corresponding Source under the terms of this
License, and the Corresponding Application Code in a form
suitable for, and under terms that permit, the user to
recombine or relink the Application with a modified version of
the Linked Version to produce a modified Combined Work, in the
manner specified by section 6 of the GNU GPL for conveying
Corresponding Source.
1) Use a suitable shared library mechanism for linking with the
Library. A suitable mechanism is one that (a) uses at run time
a copy of the Library already present on the user's computer
system, and (b) will operate properly with a modified version
of the Library that is interface-compatible with the Linked
Version.
e) Provide Installation Information, but only if you would otherwise
be required to provide such information under section 6 of the
GNU GPL, and only to the extent that such information is
necessary to install and execute a modified version of the
Combined Work produced by recombining or relinking the
Application with a modified version of the Linked Version. (If
you use option 4d0, the Installation Information must accompany
the Minimal Corresponding Source and Corresponding Application
Code. If you use option 4d1, you must provide the Installation
Information in the manner specified by section 6 of the GNU GPL
for conveying Corresponding Source.)
5. Combined Libraries.
You may place library facilities that are a work based on the
Library side by side in a single library together with other library
facilities that are not Applications and are not covered by this
License, and convey such a combined library under terms of your
choice, if you do both of the following:
a) Accompany the combined library with a copy of the same work based
on the Library, uncombined with any other library facilities,
conveyed under the terms of this License.
b) Give prominent notice with the combined library that part of it
is a work based on the Library, and explaining where to find the
accompanying uncombined form of the same work.
6. Revised Versions of the GNU Lesser General Public License.
The Free Software Foundation may publish revised and/or new versions
of the GNU Lesser General Public License from time to time. Such new
versions will be similar in spirit to the present version, but may
differ in detail to address new problems or concerns.
Each version is given a distinguishing version number. If the
Library as you received it specifies that a certain numbered version
of the GNU Lesser General Public License "or any later version"
applies to it, you have the option of following the terms and
conditions either of that published version or of any later version
published by the Free Software Foundation. If the Library as you
received it does not specify a version number of the GNU Lesser
General Public License, you may choose any version of the GNU Lesser
General Public License ever published by the Free Software Foundation.
If the Library as you received it specifies that a proxy can decide
whether future versions of the GNU Lesser General Public License shall
apply, that proxy's public statement of acceptance of any version is
permanent authorization for you to choose that version for the
Library.
sanity-quickdt-808b62c/README.md 0000664 0000000 0000000 00000034721 14142342150 0016303 0 ustar 00root root 0000000 0000000 Quick Decision Tree Learner
===========================
License
-------
QuickDT is released under the [GNU Lesser General Public License version 3](https://www.gnu.org/licenses/lgpl-3.0.en.html).
What is it?
-----------
If you are unfamiliar with Decision Tree Learning, it's the process of building a decision tree to categorize things, based
on training data that you feed it. [Learn more on Wikipedia](http://en.wikipedia.org/wiki/Decision_tree_learning).
QuickDT is a Java Decision Tree Learning library designed to be flexible, easy to use, fast, and effective. QuickDT was originally
written by [Ian Clarke](http://blog.locut.us/), with significant contributions by Alex Hawk and Chris Reeves of [OneSpot](http://onespot.com/). The initial public release was on 2011-09-21. Sergey Antopolskiy and Martin Ruskov of [myInvenio](https://www.my-invenio.com/) needed a machine learning algorithm whose results are easier to interpret by end users, so added some optional features to that end.
QuickDT also supports Random Decision Forests, which deliver a significant improvement in predictive performance by combining
multiple decision trees. QuickDT also includes functionality to easily do cross-validation in a flexible but easy-to-use manner.
What are the alternatives?
--------------------------
Prior to starting work on QuickDT, I found two Java decision tree learning libraries.
[jaDTi](http://www.run.montefiore.ulg.ac.be/~francois/software/jaDTi/) is the first,
it works, its fast, but its API is horrible, it doesn't take advantage of Generics, and forces you to use Vectors (which have been out
of fashion for some years now). Its last release was in 2004, and it shows.
[Weka](http://www.cs.waikato.ac.nz/ml/weka/) is actually a suite of learning algorithms, which include Decision Tree algorithms. Its
API is marginally better than jaDTi, but still quite ugly by today's standards. Worse, it seems to be a memory hog, and had various
other minor annoyances that made it unsuitable for use on Google App Engine, which is what I needed.
Both of these libraries are unfortunately released under the GNU General Public License, which means that you can't use them in your
project without being forced to release your entire codebase as open source. QuickDT is under the GNU Lesser General Public License
which doesn't have this requirement.
How do I install QuickDT?
------------------------
QuickDT is distributed using Maven. To use it in your project just add this repository to your pom.xml file:
```xml
sanity-maven-repoSanity's Maven repository on GitHubhttp://sanity.github.com/maven-repo/repository/
```
And this dependency:
```xml
quickdtquickdt0.2.0.8
```
How do I use QuickDT?
---------------------
Now that it's installed, we'll create some data. Let's say we know someone's height, weight, and gender, and we want to create a
decision tree that tells us whether they are underweight, healthy, or overweight. Each "instance" is a training example. `"height", 55` is
an "attribute" of the instance, and "overweight", "healthy", and "underweight" are all "classifications".
Instance.create() is some syntactic sugar that makes it easier to create Instances (although it's easy even without it).
```java
import quickdt.*;
final Set instances = Sets.newHashSet();
// A male weighing 168lb that is 55 inches tall, they are overweight
instances.add(HashMapAttributes.create("height", 55, "weight", 168, "gender", "male").classification("overweight"));
instances.add(HashMapAttributes.create("height", 75, "weight", 168, "gender", "female").classification("healthy"));
instances.add(HashMapAttributes.create("height", 74, "weight", 143, "gender", "male").classification("underweight"));
instances.add(HashMapAttributes.create("height", 49, "weight", 144, "gender", "female").classification("underweight"));
instances.add(HashMapAttributes.create("height", 83, "weight", 223, "gender", "male").classification("healthy"));
```
In reality 5 examples wouldn't be enough to learn a useful tree, but you get the idea. Note that QuickDT can handle two types
of data:
* Categorical
These values are categories, for example the attribute "gender" in the example above has possible values "male" and "female".
It is ok for an attribute to have hundreds of possible values, but thousands or tens of thousands may slow down the tree
building process significantly. Values don't have to be strings, they can be almost any object type that isn't a number.
* Numeric
Numbers like 1.3, -25, or 3.1415. These can be integers, or floating point numbers, positive or negative, any object that
implements the java.lang.Number class. Values like Double.NaN, Double.POSITIVE_INFINITY and other non-real numbers aren't
supported and will probably result in an exception or unexpected behavior.
Next we create a TreeBuilder, and use it to build a tree using this data:
```java
TreeBuilder treeBuilder = new TreeBuilder();
Tree tree = treeBuilder.buildPredictiveModel(instances);
```
That's it! So, let's say that we have a new person and we'd like to use our decision tree to tell us if they are healthy:
```java
Leaf leaf = tree.getLeaf(HashMapAttributes.create("height", 62, "weight", 201, "gender", "female"));
if (leaf.getBestClassification().equals("healthy")) {
System.out.println("They are healthy!");
} else if (leaf.getBestClassification().equals("underweight")) {
System.out.println("They are underweight!");
} else {
System.out.println("They are overweight!");
}
```
Its as simple as that! But what if you wanted to see what the tree looks like? That's easy too:
```java
tree.dump(System.out);
```
This is what the output might look like for a larger dataset:
height > 66.0
weight > 174.0
height > 72.0
weight > 193.0
[classification=healthy, depth=4, exampleCount=9880, probability=0.5719635627530364]
weight <= 193.0
[classification=healthy, depth=4, exampleCount=5231, probability=0.7056012234754349]
height <= 72.0
weight > 193.0
[classification=overweight, depth=4, exampleCount=5514, probability=1.0]
weight <= 193.0
[classification=overweight, depth=4, exampleCount=2864, probability=0.8837290502793296]
weight <= 174.0
height > 72.0
weight > 157.0
[classification=underweight, depth=4, exampleCount=4810, probability=0.6498960498960499]
weight <= 157.0
weight > 139.0
[classification=underweight, depth=5, exampleCount=5032, probability=0.9600556438791733]
weight <= 139.0
[classification=underweight, depth=5, exampleCount=5664, probability=1.0]
height <= 72.0
weight > 139.0
weight > 157.0
[classification=healthy, depth=5, exampleCount=2582, probability=0.7153369481022464]
weight <= 157.0
[classification=healthy, depth=5, exampleCount=2672, probability=0.8944610778443114]
weight <= 139.0
[classification=underweight, depth=4, exampleCount=3041, probability=0.8122328181519237]
height <= 66.0
weight > 174.0
[classification=overweight, depth=2, exampleCount=26366, probability=1.0]
weight <= 174.0
height > 60.0
weight > 139.0
weight > 157.0
[classification=overweight, depth=5, exampleCount=2568, probability=1.0]
weight <= 157.0
[classification=overweight, depth=5, exampleCount=2802, probability=0.6912919343326196]
weight <= 139.0
[classification=healthy, depth=4, exampleCount=3113, probability=0.8801798907805974]
height <= 60.0
height > 54.0
weight > 139.0
[classification=overweight, depth=5, exampleCount=5178, probability=1.0]
weight <= 139.0
[classification=overweight, depth=5, exampleCount=3026, probability=0.8978849966953073]
height <= 54.0
[classification=overweight, depth=4, exampleCount=9657, probability=1.0]
Note that there are two types of decisions, depending on whether its a categorical or numeric field. If its numeric, then
QuickDT will normally do a less-than or greater-than decision, if its categorical (or sometimes when its numeric) it will
be a test to see if the value is or isn't a member of a set.
How do I build QuickDT?
-----------------------
QuickDT is built using [Apache Maven](http://maven.apache.org/) so if you don't have that, you should grab it. You'll also
need [git](http://git-scm.com/).
First, grab the code from github:
$ git clone git@github.com:sanity/quickdt.git
Next, build a jar file:
$ cd quickdt
$ mvn assembly:assembly
If all goes well, you'll find a file called something like quickdt-0.0.1-SNAPSHOT-jar-with-dependencies.jar in the target/ directory.
Benchmarking
------------
I've done limited benchmarking, but by way of example QuickDT is able to build a tree with 100% recall on a test set with
8,500 instances, where each instance contains 46 attributes, a mixture of categorical and numeric. On my several-years-old
MacBook Pro laptop it required only 8 seconds to produce a well-balanced tree with over 500 nodes.
Random Decision Forests
-----------------------
QuickDT allows to create forests from multiple decision trees to avoid the problem of overfitting and to improve classification accuracy. For creating such a forest, a method called "random subspace" (Tin K. Ho; The random subspace method for constructing decision forests; 1998) is employed, where only a subset of all available attributes are considered at each branch. A further mechanism which can be used, is the so called bootstrap sampling also known as "bagging". The idea behind bagging is to create different random bootstrap sample of the training data for each tree, which is a subset drawn of all available instances with duplicates. For more information see [Bagging Predictors](http://www.stat.berkeley.edu/tech-reports/421.pdf) (Leo Breiman, 1994). For classification, an instance is classified by each tree in the forest separately and a majority vote decides about the final class label.
Usage of the bagging is quite straight forward. Set up a `TreeBuilder` and if you want to use "random subspace" as described above, make sure to configure the `ignoreAttributeAtNodeProbability` to a value below 1 (0.7 is a good choice). This parameter denotes the probability, that a attribute will be skipped at a branch. Create a new `RandomForestBuilder` wrapping the TreeBuilder and specify the number of trees to grow using the `numTrees` method. Bagging can be activated by `useBagging`.
```java
import quickdt.*;
import quickdt.data.*;
import quickdt.predictiveModels.randomForest.*;
TreeBuilder treeBuilder = new TreeBuilder()
.ignoreAttributeAtNodeProbability(0.7);
RandomForestBuilder randomForestBuilder = new RandomForestBuilder(treeBuilder)
.numTrees(50)
.useBagging(true);
RandomForest randomForest = randomForestBuilder.buildPredictiveModel(instances);
Attributes attributes = HashMapAttributes.create("height", 62, "weight", 201, "gender", "female");
Serializable classification = randomForest.getClassificationByMaxProb(attributes);
System.out.println("Assigned class: " + classification);
```
Cross-validation Framework
--------------------------
QuickDT provides a simple but flexible cross-validation framework. At the simplest level
you give [CrossValidator](https://github.com/sanity/quickdt/blob/master/src/main/java/quickdt/crossValidation/CrossValidator.java) a [PredictiveModelBuilder](https://github.com/sanity/quickdt/blob/master/src/main/java/quickdt/predictiveModels/PredictiveModelBuilder.java),
a dataset (an Iterable), and it will give you a root-mean-squared-error based on
cross validation where 10% of the dataset has been reserved for testing.
See [Benchmarks.java](https://github.com/sanity/quickdt/blob/master/src/test/java/quickdt/Benchmarks.java) for
a usage example.
Hyperparameter Optimization
---------------------------
QuickDT also includes a hyperparameter optimizer, to find the optimal parameters for a PredictiveModelBuilder. See
[PredictiveModelOptimizerTest.java](https://github.com/sanity/quickdt/blob/master/src/test/java/quickdt/predictiveModelOptimizer/PredictiveModelOptimizerTest.java)
for a simple usage example.
Under the hood
--------------
**Split scoring formula**
Like all decision tree learners, QuickDT uses a formula to determine the quality of a "split" at each branch. I've tested a wide
variety of formulae, and eventually settled on [MSEScorer](https://github.com/sanity/quickdt/blob/master/src/main/java/quickdt/predictiveModels/decisionTree/scorers/MSEScorer.java).
So far as I know it's a novel approach.
This Scorer is designed to estimate the improvement in "mean-squared error" resulting from the creation of a new branch. In tests
this performed better than Gini impurity, and various other approaches I tried. Its easy to try your own, just implement [Scorer](https://github.com/sanity/quickdt/blob/master/src/main/java/quickdt/predictiveModels/decisionTree/Scorer.java)
and pass it to the TreeBuilder constructor.
**Finding the best categorical branch**
Given a categorical attribute (ie. one where the values are strings), we start by scoring the splits produced by a set of size one,
testing each value in turn.
We take the best of these, and then try adding another value to this set, again, trying each of the remaining values in turn and
scoring them.
We keep adding to the set until adding a new value results in a lower score than the set has without it. Once that happens we
terminate, and that's our set.
**Unique ID attribute**
idAttribute can be specified with `TreeBuilder.setIdAttribute(idAttribute)`. idAttribute is the name of the column which has a special function in the model. idAttribute is not used for classification, i.e. it is exempt from the splits. However, it is used to create special unique ID counts: how many data points with unique IDs are present in the leafs. Count are class-specific, kept separately for each class in each leaf.
To query the counts, use `TreeBuilder.getIdAttributesHandler()` with the following methods:
- `getCountsMap()` to get the map containing counts for each leaf, can be queried with Leaf.hashCode().
- `getCountForLeaf(Leaf.hashCode())` to get the id counts for specific leaf.
- `getCountForLeafClass(Leaf.hashCode(), class)` to get the id counts for specific class within specific leaf.
- `getCountForMajorityClass(Leaf)` to get the id counts for the majority class of the specific leaf.
- `getTotalCounts()` to get the total id counts for each class. sanity-quickdt-808b62c/logback.xsd 0000664 0000000 0000000 00000015544 14142342150 0017150 0 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/pom.xml 0000664 0000000 0000000 00000013463 14142342150 0016341 0 ustar 00root root 0000000 0000000
4.0.0quickdtquickdt0.2.2.17jargh-pagesfile:../../Documents/maven-repo/repositorysanity-maven-repoSanity's Maven repository on GitHubhttp://sanity.github.com/maven-repo/repository/twittertwitterhttp://maven.twttr.comnet.sf.supercsvsuper-csv2.2.0com.amazonawsaws-java-sdk1.11.592org.apache.commonscommons-math33.6.1com.twitter.commonstats-util0.0.60org.jooqjooq3.3.2com.google.guavaguava23.0org.javatuplesjavatuples1.2compilejoda-timejoda-time1.5.2org.apache.mahoutmahout-core0.9org.slf4jslf4j-api1.7.25ch.qos.logbacklogback-core1.2.2ch.qos.logbacklogback-classic1.2.2org.testngtestng6.8.7testorg.mockitomockito-all1.9.5testcom.googlecode.json-simplejson-simple1.1.1testorg.apache.maven.pluginsmaven-compiler-plugin3.11.81.8maven-assembly-plugin2.4jar-with-dependenciesorg.apache.maven.pluginsmaven-surefire-plugin2.16-Xmx256Morg.apache.maven.pluginsmaven-source-pluginattach-sourcesjar
sanity-quickdt-808b62c/src/ 0000775 0000000 0000000 00000000000 14142342150 0015604 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/ 0000775 0000000 0000000 00000000000 14142342150 0016530 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/ 0000775 0000000 0000000 00000000000 14142342150 0017451 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/logback.xsd 0000664 0000000 0000000 00000015544 14142342150 0021604 0 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/ 0000775 0000000 0000000 00000000000 14142342150 0021115 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/Misc.java 0000664 0000000 0000000 00000002267 14142342150 0022662 0 ustar 00root root 0000000 0000000 package quickdt;
import com.google.common.base.Optional;
import java.util.Map;
import java.util.Random;
public class Misc {
public static final Random random = new Random();
public static final > Optional> getEntryWithLowestValue(Map map) {
Optional> entryWithLowestValue = Optional.absent();
for (Map.Entry kvEntry : map.entrySet()) {
if (!entryWithLowestValue.isPresent() || entryWithLowestValue.get().getValue().compareTo(kvEntry.getValue()) >= 0){
entryWithLowestValue = Optional.of(kvEntry);
}
}
return entryWithLowestValue;
}
public static final > Optional> getEntryWithHighestValue(Map map) {
Optional> entryWithHighestValue = Optional.absent();
for (Map.Entry kvEntry : map.entrySet()) {
if (!entryWithHighestValue.isPresent() || entryWithHighestValue.get().getValue().compareTo(kvEntry.getValue()) <= 0){
entryWithHighestValue = Optional.of(kvEntry);
}
}
return entryWithHighestValue;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/TreePruner.java 0000664 0000000 0000000 00000000136 14142342150 0024053 0 ustar 00root root 0000000 0000000 package quickdt;
/**
* Created by alexanderhawk on 2/27/14.
*/
public class TreePruner {
}
sanity-quickdt-808b62c/src/main/java/quickdt/collections/ 0000775 0000000 0000000 00000000000 14142342150 0023433 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/collections/ValueSummingMap.java 0000664 0000000 0000000 00000004514 14142342150 0027354 0 ustar 00root root 0000000 0000000 package quickdt.collections;
import java.io.Serializable;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import org.apache.commons.lang3.builder.HashCodeBuilder;
/**
* Created by ian on 3/2/14.
*/
public class ValueSummingMap implements Map, Serializable {
private static final long serialVersionUID = 582080010331916162L;
private volatile double sumOfValues = 0;
private HashMap delegateMap = new HashMap<>();
@Override
public int size() {
return delegateMap.size();
}
public double getSumOfValues() {
return sumOfValues;
}
@Override
public boolean isEmpty() {
return delegateMap.isEmpty();
}
@Override
public boolean containsKey(final Object key) {
return delegateMap.containsKey(key);
}
@Override
public boolean containsValue(final Object value) {
return delegateMap.containsValue(value);
}
@Override
public Number get(final Object key) {
return delegateMap.get(key);
}
@Override
public Number put(final K key, final Number value) {
Number oldValue = delegateMap.put(key, value);
if (oldValue != null) {
sumOfValues = (sumOfValues - oldValue.doubleValue()) + value.doubleValue();
} else {
sumOfValues += value.doubleValue();
}
return oldValue;
}
public void addToValue(final K key, final double toAdd) {
Number oldValue = get(key);
if (oldValue == null) {
oldValue = new Double(0.0);
}
delegateMap.put(key, oldValue.doubleValue() + toAdd);
sumOfValues += toAdd;
}
@Override
public Number remove(final Object key) {
Number removedValue = delegateMap.remove(key);
if (removedValue != null) {
sumOfValues -= removedValue.doubleValue();
}
return removedValue;
}
@Override
public void putAll(final Map m) {
for (Entry entry : m.entrySet()) {
this.put(entry.getKey(), entry.getValue());
}
}
@Override
public void clear() {
sumOfValues = 0;
delegateMap.clear();
}
@Override
public Set keySet() {
return delegateMap.keySet();
}
@Override
public Collection values() {
return delegateMap.values();
}
@Override
public Set> entrySet() {
return delegateMap.entrySet();
}
@Override
public int hashCode() {
return new HashCodeBuilder(17, 37).append(delegateMap).toHashCode();
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/ 0000775 0000000 0000000 00000000000 14142342150 0024261 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/AttributesHashSplitter.java 0000664 0000000 0000000 00000001303 14142342150 0031602 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import com.google.common.base.Predicate;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import quickdt.data.AbstractInstance;
/**
* Created by ian on 2/28/14.
*/
public class AttributesHashSplitter implements Predicate {
private static final HashFunction hashFunction = Hashing.murmur3_32();
private final int every;
public AttributesHashSplitter(int every) {
this.every = every;
}
@Override
public boolean apply(final AbstractInstance instance) {
int hc = hashFunction.hashInt(instance.getAttributes().hashCode()).asInt();
return Math.abs(hc) % every == 0;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/CrossValLossFunction.java 0000664 0000000 0000000 00000000537 14142342150 0031234 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModel;
import java.util.List;
/**
* Created by alexanderhawk on 4/24/14.
*/
public interface CrossValLossFunction {
public abstract double getLoss(List crossValSet, PredictiveModel predictiveModel);
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/CrossValidator.java 0000664 0000000 0000000 00000000673 14142342150 0030071 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModel;
import quickdt.predictiveModels.PredictiveModelBuilder;
/**
* Created by alexanderhawk on 5/5/14.
*/
public abstract class CrossValidator {
public abstract double getCrossValidatedLoss(PredictiveModelBuilder predictiveModelBuilder, Iterable allTrainingData);
} sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/DateTimeExtractor.java 0000664 0000000 0000000 00000000371 14142342150 0030515 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import org.joda.time.DateTime;
import quickdt.data.AbstractInstance;
/**
* Created by alexanderhawk on 5/6/14.
*/
public interface DateTimeExtractor {
DateTime extractDateTime(AbstractInstance instance);
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/LogCrossValLossFunction.java 0000664 0000000 0000000 00000002571 14142342150 0031676 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import com.google.common.base.Preconditions;
/**
* Created by alexanderhawk on 4/10/14.
*/
public class LogCrossValLossFunction extends OnlineCrossValLossFunction {
private static final double DEFAULT_MIN_PROBABILITY = 10E-16;
public double minProbability;
public double maxError;
public LogCrossValLossFunction() {
this(DEFAULT_MIN_PROBABILITY);
}
public LogCrossValLossFunction(double minProbability) {
this.minProbability = minProbability;
maxError = -Math.log(minProbability);
}
@Override
public double getLossFromInstance(double probabilityOfCorrectInstance, double weight) {
Preconditions.checkArgument(!Double.isNaN(probabilityOfCorrectInstance), "Probability must be a natural number, not NaN");
Preconditions.checkArgument(!Double.isInfinite(probabilityOfCorrectInstance), "Probability must be a natural number, not infinite");
final double error = (probabilityOfCorrectInstance > minProbability) ? -weight*Math.log(probabilityOfCorrectInstance) : maxError;
return error;
}
@Override
public int compareTo(final LogCrossValLossFunction o) {
return 1 - Double.compare( super.totalLoss, o.totalLoss);
}
@Override
public String toString() {
return "total LogLoss: "+ super.totalLoss;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/MSECrossValLossFunction.java 0000664 0000000 0000000 00000001744 14142342150 0031602 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import com.google.common.base.Preconditions;
/**
* Created by ian on 2/28/14.
*/
public class MSECrossValLossFunction extends OnlineCrossValLossFunction {
@Override
public double getLossFromInstance(double probabilityOfCorrectInstance, double weight) {
Preconditions.checkArgument(!Double.isNaN(probabilityOfCorrectInstance), "Probability must be a natural number, not NaN");
Preconditions.checkArgument(!Double.isInfinite(probabilityOfCorrectInstance), "Probability must be a natural number, not infinite");
final double error = (1.0 - probabilityOfCorrectInstance);
final double errorSquared = error*error*weight;
return errorSquared;
}
@Override
public int compareTo(final MSECrossValLossFunction o) {
return 1 - Double.compare(super.totalLoss, o.totalLoss);
}
@Override
public String toString() {
return "MSE: "+ super.totalLoss;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/NonWeightedAUCCrossValLossFunction.java0000664 0000000 0000000 00000001316 14142342150 0033715 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import org.apache.mahout.classifier.evaluation.Auc;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModel;
import java.util.List;
/**
* Created by alexanderhawk on 5/17/14.
*/
public class NonWeightedAUCCrossValLossFunction implements CrossValLossFunction {
@Override
public double getLoss(List crossValSet, PredictiveModel predictiveModel) {
Auc auc = new Auc();
for (AbstractInstance instance : crossValSet) {
auc.add((Double) instance.getClassification() == 1.0 ? 1 : 0, predictiveModel.getProbability(instance.getAttributes(), 1.0));
}
return 1 - auc.auc();
}
} sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/OnlineCrossValLossFunction.java 0000664 0000000 0000000 00000001726 14142342150 0032402 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModel;
import java.util.List;
/**
* Created by ian on 2/28/14.
*/
public abstract class OnlineCrossValLossFunction implements Comparable, CrossValLossFunction {
double totalLoss = 0;
double weightOfAllInstances = 0;
protected abstract double getLossFromInstance(double probabilityOfCorrectInstance, double weight);
public double getLoss(List crossValSet, PredictiveModel predictiveModel) {
totalLoss = 0;
weightOfAllInstances = 0;
for (AbstractInstance instance : crossValSet) {
totalLoss += getLossFromInstance(predictiveModel.getProbability(instance.getAttributes(), instance.getClassification()), instance.getWeight());
weightOfAllInstances += instance.getWeight();
}
return totalLoss / weightOfAllInstances;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/OutOfTimeCrossValidator.java 0000664 0000000 0000000 00000016251 14142342150 0031664 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import com.google.common.collect.Lists;
import org.joda.time.DateTime;
import org.joda.time.Period;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModel;
import quickdt.predictiveModels.PredictiveModelBuilder;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* Created by alexanderhawk on 5/5/14.
*/
public class OutOfTimeCrossValidator extends CrossValidator {
private static final Logger logger = LoggerFactory.getLogger(OutOfTimeCrossValidator.class);
List allTrainingData;
List trainingDataToAddToPredictiveModel;
List validationSet;
final private CrossValLossFunction crossValLossFunction;
private double fractionOfDataForCrossValidation = 0.25;
private final DateTimeExtractor dateTimeExtractor;
final Period durationOfValidationSet;
private DateTime maxTime;
private double weightOfValidationSet;
private int currentTrainingSetSize = 0;
public OutOfTimeCrossValidator(CrossValLossFunction crossValLossFunction, double fractionOfDataForCrossValidation, int validationTimeSliceHours, DateTimeExtractor dateTimeExtractor) {
this.crossValLossFunction = crossValLossFunction;
this.fractionOfDataForCrossValidation = fractionOfDataForCrossValidation;
this.dateTimeExtractor = dateTimeExtractor;
this.durationOfValidationSet = new Period(validationTimeSliceHours, 0, 0, 0);
}
@Override
public double getCrossValidatedLoss(PredictiveModelBuilder predictiveModelBuilder, Iterable rawTrainingData) {
initializeTrainingAndValidationSets(rawTrainingData);
double runningLoss = 0;
double runningWeightOfValidationSet = 0;
while (!validationSet.isEmpty()) {
PredictiveModel predictiveModel = predictiveModelBuilder.buildPredictiveModel(trainingDataToAddToPredictiveModel);
runningLoss += crossValLossFunction.getLoss(validationSet, predictiveModel) * weightOfValidationSet;
runningWeightOfValidationSet += weightOfValidationSet;
logger.debug("Running average Loss: " + runningLoss / runningWeightOfValidationSet + ", running weight: " + runningWeightOfValidationSet);
updateTrainingSet();
updateCrossValidationSet();
}
final double averageLoss = runningLoss / runningWeightOfValidationSet;
logger.info("Average loss: " + averageLoss + ", runningWeight: " + runningWeightOfValidationSet);
return averageLoss;
}
private void initializeTrainingAndValidationSets(Iterable rawTrainingData) {
setAndSortAllTrainingData(rawTrainingData);
setMaxValidationTime();
int initialTrainingSetSize = getInitialSizeForTrainData();
trainingDataToAddToPredictiveModel = Lists.newArrayListWithExpectedSize(initialTrainingSetSize);
validationSet = Lists.newArrayList();
DateTime timeOfInstance;
DateTime timeOfFirstInstanceInValidationSet = dateTimeExtractor.extractDateTime(allTrainingData.get(initialTrainingSetSize));
DateTime leastUpperBoundOfValidationSet = timeOfFirstInstanceInValidationSet.plus(durationOfValidationSet);
weightOfValidationSet = 0;
for (AbstractInstance instance : allTrainingData) {
timeOfInstance = dateTimeExtractor.extractDateTime(instance);
if (timeOfInstance.isBefore(timeOfFirstInstanceInValidationSet)) {
trainingDataToAddToPredictiveModel.add(instance);
} else if (timeOfInstance.isBefore(leastUpperBoundOfValidationSet)) {
validationSet.add(instance);
weightOfValidationSet += instance.getWeight();
} else {
break;
}
}
currentTrainingSetSize = trainingDataToAddToPredictiveModel.size();
}
private void updateTrainingSet() {
trainingDataToAddToPredictiveModel = validationSet;
currentTrainingSetSize += trainingDataToAddToPredictiveModel.size();
}
private void updateCrossValidationSet() {
clearValidationSet();
if (!newValidationSetExists()) {
return;
}
DateTime timeOfFirstInstanceInValidationSet = dateTimeExtractor.extractDateTime(allTrainingData.get(currentTrainingSetSize));
DateTime leastOuterBoundOfValidationSet = timeOfFirstInstanceInValidationSet.plus(durationOfValidationSet);
while(validationSet.isEmpty()) {
for (int i = currentTrainingSetSize; i < allTrainingData.size(); i++) {
AbstractInstance instance = allTrainingData.get(i);
DateTime timeOfInstance = dateTimeExtractor.extractDateTime(instance);
if (timeOfInstance.isBefore(leastOuterBoundOfValidationSet)) {
validationSet.add(instance);
weightOfValidationSet += instance.getWeight();
} else
break;
}
leastOuterBoundOfValidationSet = leastOuterBoundOfValidationSet.plus(durationOfValidationSet);
}
}
private void clearValidationSet() {
weightOfValidationSet = 0;
validationSet = Lists.newArrayList();
}
private void setMaxValidationTime() {
AbstractInstance latestInstance = allTrainingData.get(allTrainingData.size() - 1);
maxTime = dateTimeExtractor.extractDateTime(latestInstance);
}
private int getInitialSizeForTrainData() {
int initialTrainingSetSize = (int) (allTrainingData.size() * (1 - fractionOfDataForCrossValidation));
verifyInitialValidationSetExists(initialTrainingSetSize);
return initialTrainingSetSize;
}
private void verifyInitialValidationSetExists(int initialTrainingSetSize) {
if (initialTrainingSetSize == allTrainingData.size()) {
throw new RuntimeException("fractionOfDataForCrossValidation must be non zero");
}
}
private boolean newValidationSetExists() {
return currentTrainingSetSize < allTrainingData.size();
}
private void setAndSortAllTrainingData(Iterable rawTrainingData) {
this.allTrainingData = Lists.newArrayList();
for (AbstractInstance instance : rawTrainingData) {
this.allTrainingData.add(instance);
}
Comparator comparator = new Comparator() {
@Override
public int compare(AbstractInstance o1, AbstractInstance o2) {
DateTime firstInstance = dateTimeExtractor.extractDateTime(o1);
DateTime secondInstance = dateTimeExtractor.extractDateTime(o2);
if (firstInstance.isAfter(secondInstance)) {
return 1;
} else if (firstInstance.isEqual(secondInstance)) {
return 0;
} else {
return -1;
}
}
};
Collections.sort(this.allTrainingData, comparator);
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/RMSECrossValLossFunction.java 0000664 0000000 0000000 00000001771 14142342150 0031724 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModel;
import java.util.List;
/**
* Created by ian on 2/28/14.
*/
public class RMSECrossValLossFunction extends OnlineCrossValLossFunction {
private MSECrossValLossFunction mseCrossValLoss = new MSECrossValLossFunction();
@Override
public double getLossFromInstance(final double probabilityOfCorrectInstance, double weight) {
return mseCrossValLoss.getLossFromInstance(probabilityOfCorrectInstance, weight);
}
@Override
public int compareTo(final RMSECrossValLossFunction o) {
return mseCrossValLoss.compareTo(o.mseCrossValLoss);
}
@Override
public double getLoss(List crossValSet, PredictiveModel predictiveModel) {
return Math.sqrt(super.getLoss(crossValSet, predictiveModel));
}
@Override
public String toString() {
return "RMSE: "+ super.totalLoss;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/SampleDateTimeExtractor.java 0000664 0000000 0000000 00000001427 14142342150 0031662 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import org.joda.time.DateTime;
import org.joda.time.DateTimeZone;
import quickdt.data.AbstractInstance;
import quickdt.data.Attributes;
/**
* Created by alexanderhawk on 5/6/14.
*/
public class SampleDateTimeExtractor implements DateTimeExtractor {
@Override
public DateTime extractDateTime(AbstractInstance instance){
Attributes attributes = instance.getAttributes();
int year = (Integer)attributes.get("timeOfArrival-year");
int month = (Integer)attributes.get("timeOfArrival-monthOfYear");
int day = (Integer)attributes.get("timeOfArrival-dayOfMonth");
int hour = (Integer)attributes.get("timeOfArrival-hourOfDay");
return new DateTime(year,month, day, hour, 0, 0, 0, DateTimeZone.UTC);
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/SimpleDateFormatExtractor.java 0000664 0000000 0000000 00000002530 14142342150 0032220 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import org.joda.time.DateTime;
import org.joda.time.DateTimeZone;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import quickdt.data.AbstractInstance;
import quickdt.data.Attributes;
import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
/**
* Created by alexanderhawk on 6/22/14.
*/
public class SimpleDateFormatExtractor implements DateTimeExtractor {
private static final Logger logger = LoggerFactory.getLogger(SimpleDateFormatExtractor.class);
DateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String dateAttribute = "created_at";
public void setDateFormat(String dateFormatString) {
dateFormat = new SimpleDateFormat(dateFormatString);
}
public void setDateAttribute(String dateAttribute) {
this.dateAttribute = dateAttribute;
}
@Override
public DateTime extractDateTime(AbstractInstance instance) {
Attributes attributes = instance.getAttributes();
try {
Date currentTimeMillis = dateFormat.parse((String) attributes.get(dateAttribute));
return new DateTime(currentTimeMillis, DateTimeZone.UTC);
} catch (ParseException e) {
logger.error("Error parsing date", e);
}
return new DateTime();
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/StationaryCrossValidator.java 0000664 0000000 0000000 00000006571 14142342150 0032152 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import java.util.List;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import com.google.common.base.Preconditions;
import com.google.common.collect.Lists;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModel;
import quickdt.predictiveModels.PredictiveModelBuilder;
//import com.javafx.tools.doclets.formats.html.SourceToHTMLConverter;
/**
* Created by ian on 2/28/14.
*/
public class StationaryCrossValidator extends CrossValidator {
private static final Logger logger = LoggerFactory.getLogger(StationaryCrossValidator.class);
private static final int DEFAULT_NUMBER_OF_FOLDS = 4;
private int folds;
private int foldsUsed;
private CrossValLossFunction lossFunction;
/**
* Create a new CrossValidator using an RMSECrossValLoss, generating a
* getCrossValidatedLoss dataset from 1 in 10 instances selected randomly based
* on the has of the Attributes in each Instance.
*/
public StationaryCrossValidator() {
this(StationaryCrossValidator.DEFAULT_NUMBER_OF_FOLDS, new RMSECrossValLossFunction());
}
public StationaryCrossValidator(int folds) {
this(folds, new RMSECrossValLossFunction());
}
public StationaryCrossValidator(int folds, int foldsUsed) {
this(folds, foldsUsed, new RMSECrossValLossFunction());
}
/**
* Create a new CrossValidator
*
* @param folds The number folds to be used in the cross validation procedure
*/
public StationaryCrossValidator(final int folds, CrossValLossFunction lossFunction) {
Preconditions.checkArgument(folds > 1, "Minimum number of folds is 2");
this.folds = folds;
this.foldsUsed = folds;
this.lossFunction = lossFunction;
}
public StationaryCrossValidator(final int folds, final int foldsUsed,
CrossValLossFunction lossFunction) {
Preconditions.checkArgument(folds > 1, "Minimum number of folds is 2");
this.folds = folds;
this.foldsUsed = foldsUsed;
this.lossFunction = lossFunction;
}
public double getCrossValidatedLoss(
PredictiveModelBuilder predictiveModelBuilder,
Iterable allTrainingData) {
double runningLoss = 0;
DataSplit dataSplit;
for (int currentFold = 0; currentFold < foldsUsed; currentFold++) {
dataSplit = setTrainingAndValidationSets(currentFold, allTrainingData);
PredictiveModel predictiveModel = predictiveModelBuilder
.buildPredictiveModel(dataSplit.training);
runningLoss += lossFunction.getLoss(dataSplit.validation, predictiveModel);
logger.info("running loss: " + runningLoss);
}
final double averageLoss = runningLoss / foldsUsed;
logger.info("Average loss: " + averageLoss);
return averageLoss;
}
private DataSplit setTrainingAndValidationSets(int foldNumber,
Iterable data) {
DataSplit dataSplit = new DataSplit();
int count = 0;
for (AbstractInstance instance : data) {
if (count % folds == foldNumber) // (count > testSetLowerBound && count <
// testSetUpperBound)//
dataSplit.validation.add(instance);
else
dataSplit.training.add(instance);
count++;
}
return dataSplit;
}
class DataSplit {
public List training;
public List validation;
public DataSplit() {
training = Lists.newArrayList();
validation = Lists.newArrayList();
}
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/TestDateTimeExtractor.java 0000664 0000000 0000000 00000001007 14142342150 0031352 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import org.joda.time.DateTime;
import quickdt.data.AbstractInstance;
import quickdt.data.Attributes;
/**
* Created by alexanderhawk on 5/6/14.
*/
public class TestDateTimeExtractor implements DateTimeExtractor {
@Override
public DateTime extractDateTime(AbstractInstance instance){
Attributes attributes = instance.getAttributes();
int currentTimeMillis = (Integer)attributes.get("currentTimeMillis");
return new DateTime(currentTimeMillis);
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/WeightedAUCCrossValLossFunction.java 0000664 0000000 0000000 00000015433 14142342150 0033247 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModel;
import java.io.Serializable;
import java.util.*;
/**
* AUCCrossValLoss calculates the ROC area over the curve to determine loss.
*
* Created by Chris on 5/5/2014.
*/
public class WeightedAUCCrossValLossFunction implements CrossValLossFunction {
private final Serializable positiveClassification;
public WeightedAUCCrossValLossFunction(Serializable positiveClassification) {
this.positiveClassification = positiveClassification;
}
@Override
public double getLoss(List instances, PredictiveModel predictiveModel) {
if (instances.isEmpty()) {
throw new IllegalStateException("Tried to get loss from empty data set");
}
List aucDataList = getAucDataList(instances, predictiveModel);
sortDataByProbability(aucDataList);
ArrayList aucPoints = getAUCPointsFromData(aucDataList);
return getAUCLoss(aucPoints);
}
private List getAucDataList(List instances, PredictiveModel predictiveModel) {
List aucDataList = new ArrayList();
Set classifications = new HashSet();
for (AbstractInstance instance : instances) {
classifications.add(instance.getClassification());
if (classifications.size() > 2) {
throw new RuntimeException("AUCCrossValLoss only supports binary classifications");
}
aucDataList.add(new AUCData(instance.getClassification(), instance.getWeight(), predictiveModel.getProbability(instance.getAttributes(), positiveClassification)));
}
return aucDataList;
}
protected ArrayList getAUCPointsFromData(List aucDataList) {
double truePositives = 0;
double trueNegatives = 0;
double falsePositives = 0;
double falseNegatives = 0;
ArrayList aucPoints = new ArrayList();
double threshold = 0.0;
for(AUCData aucData : aucDataList) {
if(aucData.getClassification().equals(positiveClassification)) {
truePositives += aucData.getWeight();
} else {
falsePositives += aucData.getWeight();
}
}
//iterate through each data point updating all points that are changed by the threshold
for(AUCData aucData : aucDataList) {
if (threshold != aucData.getProbability()) {
aucPoints.add(getAUCPoint(truePositives, falsePositives, trueNegatives, falseNegatives));
threshold = aucData.getProbability();
}
//we are positive but guessing negative
if (aucData.getClassification().equals(positiveClassification)) {
//add a false negative
falseNegatives += aucData.getWeight();
//remove true positive from previous threshold
truePositives -= aucData.getWeight();
} else {//we are negative and guessing negative
//add a true negative
trueNegatives += aucData.getWeight();
//remove a false positive from previous threshold
falsePositives -= aucData.getWeight();
}
}
//add last point
aucPoints.add(getAUCPoint(truePositives, falsePositives, trueNegatives, falseNegatives));
return aucPoints;
}
protected void sortDataByProbability(List aucDataList) {
//order by probability ascending
Collections.sort(aucDataList, new Comparator() {
@Override
public int compare(AUCData o1, AUCData o2) {
if (o1.getProbability() > o2.getProbability()) {
return 1;
} else if (o2.getProbability() > o1.getProbability()) {
return -1;
} else {
return 0;
}
}
});
}
protected AUCPoint getAUCPoint(double truePositives, double falsePositives, double trueNegatives, double falseNegatives) {
double truePositiveRate = (truePositives + falseNegatives == 0) ? 0 : (truePositives / (truePositives + falseNegatives));
double falsePositiveRate = (falsePositives + trueNegatives == 0) ? 0 : (falsePositives / (falsePositives + trueNegatives));
return new AUCPoint(falsePositiveRate, truePositiveRate);
}
protected double getAUCLoss(ArrayList aucPoints) {
//order by false positive rate ascending, true positive rate ascending
Collections.sort(aucPoints, new Comparator() {
@Override
public int compare(AUCPoint o1, AUCPoint o2) {
if (o1.getFalsePositiveRate() > o2.getFalsePositiveRate()) {
return 1;
} else if (o1.getFalsePositiveRate() < o2.getFalsePositiveRate()) {
return -1;
} else {
return o1.getTruePositiveRate() >= o2.getTruePositiveRate() ? 1 : -1;
}
}
});
double sumXY = 0.0;
//Area over curve OR AUCLoss = (2 - sum((x1-x0)(y1+y0)))/2
for(int i = 1; i < aucPoints.size(); i++) {
AUCPoint aucPoint1 = aucPoints.get(i);
AUCPoint aucPoint0 = aucPoints.get(i-1);
sumXY += ((aucPoint1.getFalsePositiveRate() - aucPoint0.getFalsePositiveRate())*(aucPoint1.getTruePositiveRate()+aucPoint0.getTruePositiveRate()));
}
return (2.0 - sumXY) / 2.0;
}
protected static class AUCPoint {
private final double truePositiveRate;
private final double falsePositiveRate;
public AUCPoint(double falsePositiveRate, double truePositiveRate) {
this.truePositiveRate = truePositiveRate;
this.falsePositiveRate = falsePositiveRate;
}
public double getFalsePositiveRate() {
return falsePositiveRate;
}
public double getTruePositiveRate() {
return truePositiveRate;
}
}
protected static class AUCData {
private final Serializable classification;
private final double weight;
private final double probability;
public AUCData(Serializable classification, double weight, double probability) {
this.classification = classification;
this.weight = weight;
this.probability = probability;
}
public Serializable getClassification() {
return classification;
}
public double getWeight() {
return weight;
}
public double getProbability() {
return probability;
}
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/movingAverages/ 0000775 0000000 0000000 00000000000 14142342150 0027236 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/movingAverages/ArithmeticAverage.java 0000664 0000000 0000000 00000000712 14142342150 0033465 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation.movingAverages;
import quickdt.crossValidation.movingAverages.MovingAverage;
import java.util.List;
/**
* Created by alexanderhawk on 4/29/14.
*/
public class ArithmeticAverage implements MovingAverage {
double average = 0;
@Override
public double getAverage(List values) {
for(Double val : values)
average += val;
average /= values.size();
return average;
}
}
HoltWintersMovingAverage.java 0000664 0000000 0000000 00000001613 14142342150 0034760 0 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/movingAverages package quickdt.crossValidation.movingAverages;
import java.util.List;
/**
* Created by alexanderhawk on 4/29/14.
*/
public class HoltWintersMovingAverage implements MovingAverage {
double average = 0;
private double alpha;
private double beta;
public HoltWintersMovingAverage(double alpha, double beta) {
this.alpha = alpha;
this.beta = beta;
}
public void setAlpha(double alpha) {
this.alpha = alpha;
}
public void setBeta(double beta) {
this.beta = beta;
}
public double getAverage(List values) {
double s = values.get(1);
double b = values.get(1) - values.get(0);
for(int i = 2; i < values.size(); i++) {
double s_prev = s;
s = alpha * values.get(i) + (1 - alpha) * (s - b);
b = beta * (s - s_prev) + (1 - beta) * b;
}
return s;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/crossValidation/movingAverages/MovingAverage.java 0000664 0000000 0000000 00000000332 14142342150 0032631 0 ustar 00root root 0000000 0000000 package quickdt.crossValidation.movingAverages;
/**
* Created by alexanderhawk on 4/29/14.
*/
import java.util.List;
public interface MovingAverage {
public abstract double getAverage(List values);
}
sanity-quickdt-808b62c/src/main/java/quickdt/csvReader/ 0000775 0000000 0000000 00000000000 14142342150 0023033 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/csvReader/CSVToMap.java 0000664 0000000 0000000 00000010015 14142342150 0025267 0 ustar 00root root 0000000 0000000 package quickdt.csvReader;
import com.google.common.collect.Sets;
import org.jooq.tools.csv.CSVReader;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.io.*;
import java.util.*;
/**
* Load training data in from redshift.
*/
public class CSVToMap {
private static final Logger LOGGER = LoggerFactory.getLogger(CSVToMap.class);
private String bucketName;
// private S3FileLoader s3FileLoader;
public static final HashSet GOOD_HEADERS = Sets.newHashSet("an_user_id", "an_url",
"an_domain", "an_seller_id", "an_publisher_id", "an_site_id", "an_os", "an_browser", "an_country",
"an_region", "an_city", "an_postal_code", "an_dma", "an_placement_position", "an_reserve", "an_eap", "an_ecp",
"os_account_id", "os_campaign_id", "os_creative_id", "created_at", "an_no_cookies", "an_secure_inventory", "an_ip_address",
"is_click");
public static final String[] HEADERS = new String[]{"an_auction_id", "an_user_id", "an_url", "an_url_domain",
"an_domain", "an_seller_id", "an_publisher_id", "an_site_id", "an_os", "an_browser", "an_country",
"an_region", "an_city", "an_postal_code", "an_dma", "an_placement_position", "an_placement_size",
"an_first_touch_type", "an_first_touch_os_campaign_id", "an_first_touch_os_creative_id",
"os_bd_bid_nobid_outcome", "an_reserve", "an_eap", "an_ecp", "os_bidder_name", "os_bd_our_price_cpm",
"os_bd_customer_price_cpm", "os_bd_raw_click_score", "os_bd_calibrated_click_score",
"os_bd_click_probability", "os_bd_target_cpc", "os_account_id", "os_campaign_id", "os_creative_id",
"created_at", "an_no_cookies", "an_secure_inventory", "an_ip_address", "an_bday_cookie_first_set",
"os_bd_bidding_strategy", "os_bd_bidder_version", "os_bd_campaign_eligibility_reason",
"os_bd_click_probability_adjusted", "an_our_cost_cpm", "an_customer_cost_cpm", "is_click", "randomsample"};
/**
* Load the raw training data.
*
* @return a list of maps
*/
public static List> loadRows(String inputFile) {
List> rawData = new ArrayList<>();
List rowData = new LinkedList<>();
try (CSVReader csvReader = new CSVReader(createReader(inputFile), '|')) {
while (csvReader.hasNext()) {
rowData.add(csvReader.next());
}
} catch (IOException e) {
e.printStackTrace();
System.exit(1);
}
for(String[] row : rowData) {
Map rowMap = convertRowToMap(row);
if (rowMap != null) {
rawData.add(rowMap);
}
}
return rawData;
}
private static InputStreamReader createReader(final String inputFile) {
InputStreamReader inputStreamReader;
try {
inputStreamReader = new InputStreamReader(new FileInputStream(inputFile));
return inputStreamReader;
}
catch(FileNotFoundException e) {
e.printStackTrace();
System.exit(1);
}
return null;
}
private static Map convertRowToMap(final String[] rowData) {
return isValid(rowData) ? convertToMap(rowData) : null;
}
private static Map convertToMap(final String[] rowData) {
HashMap row = new HashMap<>();
if (rowData != null) {
for (int i = 0; i < rowData.length; i++) {
if (GOOD_HEADERS.contains(HEADERS[i]))
row.put(HEADERS[i], rowData[i]);
}
}
return row;
}
private static boolean isValid(final String[] rowArray) {
if (rowArray == null)
return false;
if (rowArray.length != 47) {
LOGGER.warn("Number of elements in redshift row is not valid - {}", rowArray.length);
return false;
}
return true;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/data/ 0000775 0000000 0000000 00000000000 14142342150 0022026 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/data/AbstractInstance.java 0000664 0000000 0000000 00000000740 14142342150 0026122 0 ustar 00root root 0000000 0000000 package quickdt.data;
import java.io.Serializable;
/**
* Created with IntelliJ IDEA.
* User: ian
* Date: 6/27/13
* Time: 1:22 PM
* To change this template use File | Settings | File Templates.
*/
public abstract class AbstractInstance {
public abstract Attributes getAttributes();
public abstract Serializable getClassification();
public abstract double getWeight();
public abstract AbstractInstance reweight(double newWeight);
public int index;
}
sanity-quickdt-808b62c/src/main/java/quickdt/data/Attributes.java 0000664 0000000 0000000 00000000532 14142342150 0025017 0 ustar 00root root 0000000 0000000 package quickdt.data;
import java.io.Serializable;
import java.util.Map;
/**
* Created with IntelliJ IDEA.
* User: ian
* Date: 6/27/13
* Time: 1:09 PM
* To change this template use File | Settings | File Templates.
*/
public interface Attributes extends Map {
public Instance classification(Serializable cls);
}
sanity-quickdt-808b62c/src/main/java/quickdt/data/HashMapAttributes.java 0000664 0000000 0000000 00000005304 14142342150 0026263 0 ustar 00root root 0000000 0000000 package quickdt.data;
import java.io.Serializable;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
public final class HashMapAttributes implements Attributes, Serializable {
private static final long serialVersionUID = 1251740682190367389L;
private HashMap delegatedHashMap;
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("HashMapAttributes{");
sb.append("map=").append(delegatedHashMap);
sb.append('}');
return sb.toString();
}
public static Attributes create(final Serializable... inputs) {
final HashMapAttributes a = new HashMapAttributes();
for (int x = 0; x < inputs.length; x += 2) {
a.put((String) inputs[x], inputs[x + 1]);
}
return a;
}
public HashMapAttributes() {
delegatedHashMap = new HashMap<>();
}
public HashMapAttributes(Map map) {
delegatedHashMap = new HashMap<>(map);
}
@Override
public int size() {
return delegatedHashMap.size();
}
@Override
public boolean isEmpty() {
return delegatedHashMap.isEmpty();
}
@Override
public Serializable get(final Object key) {
return delegatedHashMap.get(key);
}
@Override
public boolean containsKey(final Object key) {
return delegatedHashMap.containsKey(key);
}
@Override
public Serializable put(final String key, final Serializable value) {
return delegatedHashMap.put(key, value);
}
@Override
public void putAll(final Map m) {
delegatedHashMap.putAll(m);
}
@Override
public Serializable remove(final Object key) {
return delegatedHashMap.remove(key);
}
@Override
public void clear() {
delegatedHashMap.clear();
}
@Override
public boolean containsValue(final Object value) {
return delegatedHashMap.containsValue(value);
}
@Override
public Object clone() {
return delegatedHashMap.clone();
}
@Override
public Set keySet() {
return delegatedHashMap.keySet();
}
@Override
public Collection values() {
return delegatedHashMap.values();
}
@Override
public Set> entrySet() {
return delegatedHashMap.entrySet();
}
@Override
public Instance classification(final Serializable cls) {
return new Instance(this, cls);
}
@Override
public boolean equals(final Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
final HashMapAttributes that = (HashMapAttributes) o;
if (!delegatedHashMap.equals(that.delegatedHashMap)) {
return false;
}
return true;
}
@Override
public int hashCode() {
return delegatedHashMap.hashCode();
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/data/Instance.java 0000664 0000000 0000000 00000005410 14142342150 0024435 0 ustar 00root root 0000000 0000000 package quickdt.data;
import java.io.Serializable;
public class Instance extends AbstractInstance implements Serializable {
private static final long serialVersionUID = -932048363529904511L;
private static final double DEFAULT_WEIGHT = 1.0;
private Instance() {
}
public static Instance create(final Serializable classification, final Serializable... inputs) {
return create(classification, DEFAULT_WEIGHT, inputs);
}
public static Instance create(final Serializable classification, final double weight, final Serializable... inputs) {
final HashMapAttributes a = new HashMapAttributes();
for (int x = 0; x < inputs.length; x += 2) {
a.put((String) inputs[x], inputs[x + 1]);
}
return new Instance(a, classification, weight);
}
public Instance(final Attributes attributes, final Serializable classification) {
this(attributes, classification, DEFAULT_WEIGHT);
}
public Instance(final Attributes attributes, final Serializable classification, final double weight) {
this.attributes = attributes;
this.classification = classification;
this.weight = weight;
}
@Override
public Attributes getAttributes() {
return attributes;
}
@Override
public Serializable getClassification() {
return classification;
}
public Instance reweight(double newWeight){
return new Instance(getAttributes(), getClassification(), newWeight);
}
@Override
public double getWeight() {
return weight;
}
private Attributes attributes;
private Serializable classification;
private double weight;
@Override
public boolean equals(final Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
final Instance instance = (Instance) o;
if (Double.compare(instance.weight, weight) != 0) return false;
if (!attributes.equals(instance.attributes)) return false;
if (!classification.equals(instance.classification)) return false;
return true;
}
@Override
public int hashCode() {
int result;
long temp;
result = attributes.hashCode();
result = 31 * result + classification.hashCode();
temp = Double.doubleToLongBits(weight);
result = 31 * result + (int) (temp ^ (temp >>> 32));
return result;
}
@Override
public String toString() {
final StringBuilder builder = new StringBuilder();
builder.append("[attributes=");
builder.append(attributes);
builder.append(", classification=");
builder.append(classification);
if (weight != 1.0) {
builder.append(", weight=");
builder.append(weight);
}
builder.append("]");
return builder.toString();
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/data/NegativeWeightsFilter.java 0000664 0000000 0000000 00000001765 14142342150 0027145 0 ustar 00root root 0000000 0000000 package quickdt.data;
import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import java.util.HashSet;
/**
* Created by alexanderhawk on 5/1/14.
*/
public class NegativeWeightsFilter {
public static Iterable filterNegativeWeights(Iterable trainingData) {
final HashSet instanceLookUp = new HashSet();
for (AbstractInstance instance : trainingData)
if (instance.getWeight() < 0)
instanceLookUp.add(instance.getAttributes());
Predicate predicate = new Predicate() {
@Override
public boolean apply(final AbstractInstance instance) {
if (instanceLookUp.contains(instance.getAttributes()))
return false;
else
return true;
}
};
return Iterables.filter(trainingData, predicate);
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/ 0000775 0000000 0000000 00000000000 14142342150 0023460 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/experiments/ClicksAndImps.java 0000664 0000000 0000000 00000000652 14142342150 0027012 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import quickdt.predictiveModels.downsamplingPredictiveModel.Utils;
public class ClicksAndImps {
double clicks = 0;
double imps = 0;
double ctr = 0;
double correctedCtr = 0;
public void setCtr() {
ctr = clicks/ Math.max(1.0, imps);
setCorrectedCtr();
}
public void setCorrectedCtr() {
correctedCtr = Utils.correctProbability(.99, ctr);
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/CsvReaderExp.java 0000664 0000000 0000000 00000013247 14142342150 0026665 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import com.google.common.collect.Lists;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import quickdt.csvReader.CSVToMap;
import quickdt.data.Attributes;
import quickdt.data.HashMapAttributes;
import quickdt.data.Instance;
import quickdt.predictiveModels.PredictiveModel;
import quickdt.predictiveModels.PredictiveModelBuilder;
import quickdt.predictiveModels.calibratedPredictiveModel.CalibratedPredictiveModel;
import quickdt.predictiveModels.calibratedPredictiveModel.PAVCalibratedPredictiveModelBuilder;
import quickdt.predictiveModels.decisionTree.TreeBuilder;
import quickdt.predictiveModels.downsamplingPredictiveModel.Utils;
import quickdt.predictiveModels.randomForest.RandomForest;
import quickdt.predictiveModels.randomForest.RandomForestBuilder;
import java.io.Serializable;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Created by alexanderhawk on 1/16/14.
*/
public class CsvReaderExp {
private static final Logger logger = LoggerFactory.getLogger(CsvReaderExp.class);
public static void main(String[] args) {
int numTraniningExamples = 40100;
String inputFile = "redshift_training_data.csv";
List> instanceMaps = CSVToMap.loadRows(inputFile);
List instances = convertRawMapToInstance(instanceMaps);
logger.info("got instances");
HashMap uniqueBrowsersRawData = uniqueBrowserData(instances);
RandomForestBuilder randomForestBuilder = getRandomForestBuilder(4, 32);
RandomForest randomForest = randomForestBuilder.buildPredictiveModel(instances);
CalibratedPredictiveModel calibratedPredictiveModel = (new PAVCalibratedPredictiveModelBuilder(randomForestBuilder).binsInCalibrator(5)).buildPredictiveModel(instances);
HashMap uniqueBrowsersRF = uniqueBrowserDataPredicted(randomForest, instances);
HashMap uniqueBrowserPredicted = uniqueBrowserDataPredicted(calibratedPredictiveModel, instances);
int x = 0;
}
private static HashMap uniqueBrowserData(List instances) {
HashMap uniqueBrowsers = new HashMap<>();
for (Instance instance : instances) {
String browser = (String) instance.getAttributes().get("an_browser");
double click = (Double) instance.getClassification();
if (browser != null) {
int count = 0;
if (!uniqueBrowsers.containsKey(browser)) {
uniqueBrowsers.put(browser, new ClicksAndImps());
}
uniqueBrowsers.get(browser).imps++;
uniqueBrowsers.get(browser).clicks += click;
}
}
for (String key : uniqueBrowsers.keySet()) {
uniqueBrowsers.get(key).setCtr();
}
return uniqueBrowsers;
}
private static HashMap uniqueBrowserDataPredicted(PredictiveModel predictiveModel, List instances) {
HashMap uniqueBrowsers = new HashMap<>();
for (Instance instance : instances) {
String browser = (String) instance.getAttributes().get("an_browser");
double clickProb = Utils.correctProbability(.99, predictiveModel.getProbability(instance.getAttributes(), 1.0));
if (browser != null) {
int count = 0;
if (!uniqueBrowsers.containsKey(browser)) {
uniqueBrowsers.put(browser, new ClicksAndImps());
}
uniqueBrowsers.get(browser).imps++;
uniqueBrowsers.get(browser).clicks += clickProb;
}
}
for (String key : uniqueBrowsers.keySet()) {
uniqueBrowsers.get(key).setCtr();
}
return uniqueBrowsers;
}
public static List convertRawMapToInstance(List> rawMaps) {
List instances = Lists.newArrayList();
Attributes attributes;
Instance instance;
int numInstances = 30000;
int count = 0;
for (Map rawMap : rawMaps) {
count++;
if (count < 8000) {
attributes = new HashMapAttributes();
for (String key : rawMap.keySet()) {
if (!key.equals("is_click")) {
attributes.put(key, rawMap.get(key));
}
}
double clickVal = (rawMap.get("is_click").equals("f")) ? 0.0 : 1.0;
instance = new Instance(attributes, clickVal);
instances.add(instance);
// if (count++ > numInstances) break;
}
}
return instances;
}
private static RandomForestBuilder getRandomForestBuilder(int maxDepth, int numTrees) {
TreeBuilder treeBuilder = new TreeBuilder().maxDepth(maxDepth).ignoreAttributeAtNodeProbability(.9);//;.minLeafInstances(20);
return new RandomForestBuilder(treeBuilder).numTrees(numTrees);
}
private static PredictiveModelBuilder getUpdatableRandomForestBuilder(int maxDepth, int numTrees) {
TreeBuilder treeBuilder = new TreeBuilder().ignoreAttributeAtNodeProbability(.7).minLeafInstances(20);
RandomForestBuilder randomForestBuilder = new RandomForestBuilder(treeBuilder).numTrees(numTrees);
// UpdatableRandomForestBuilder updatableRandomForestBuilder = (UpdatableRandomForestBuilder) new UpdatableRandomForestBuilder(randomForestBuilder).rebuildThreshold(2).splitNodeThreshold(2);
return randomForestBuilder;//updatableRandomForestBuilder;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/LearnSimpleVariable.java 0000664 0000000 0000000 00000003311 14142342150 0030202 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import com.google.common.collect.Lists;
import quickdt.data.HashMapAttributes;
import quickdt.data.Instance;
import quickdt.predictiveModels.decisionTree.TreeBuilder;
import quickdt.predictiveModels.randomForest.RandomForest;
import quickdt.predictiveModels.randomForest.RandomForestBuilder;
import java.util.List;
import java.util.Random;
/**
* Created by alexanderhawk on 1/15/14.
*/
public class LearnSimpleVariable {
public static Random generator;
public static void main(String[] args) {
int instances = 100000;
int maxAge = 30;
generator = new Random();
List trainingData = createTrainingData(instances, maxAge);
TreeBuilder treeBuilder = new TreeBuilder().maxDepth(2);
RandomForestBuilder randomForestBuilder = new RandomForestBuilder(treeBuilder).numTrees(100);
RandomForest randomForest = randomForestBuilder.buildPredictiveModel(trainingData);
System.out.println("Probability of a click: "+randomForest.getProbability(HashMapAttributes.create("age", 11),"click"));
}
private static List createTrainingData(int instances, int maxAge) {
List trainingData = Lists.newArrayList();
for (int i=0; i 10 ? .995 : .6;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/OutOfTimeCrossValidatorRunner.java 0000664 0000000 0000000 00000004043 14142342150 0032251 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import quickdt.crossValidation.*;
import quickdt.data.AbstractInstance;
import quickdt.predictiveModels.PredictiveModelBuilder;
import quickdt.predictiveModels.decisionTree.TreeBuilder;
import quickdt.predictiveModels.randomForest.RandomForestBuilder;
import java.util.List;
/**
* Created by alexanderhawk on 1/16/14.
*/
public class OutOfTimeCrossValidatorRunner {
private static final Logger logger = LoggerFactory.getLogger(StationaryCrossValidator.class);
public static void main(String[] args) {
int numTraniningExamples = 40100;
String bidRequestAttributes[] = {"seller_id", "user_id", "users_favorite_beer_id", "favorite_soccer_team_id", "user_iq"};
TrainingDataGenerator2 trainingDataGenerator = new TrainingDataGenerator2(numTraniningExamples, .005, bidRequestAttributes);
List trainingData = trainingDataGenerator.createTrainingData();
int millisInMinute = 60000;
int instanceNumber = 0;
for (AbstractInstance instance : trainingData) {
instance.getAttributes().put("currentTimeMillis", millisInMinute * instanceNumber);
instanceNumber++;
}
logger.info("trainingDataSize " + trainingData.size());
PredictiveModelBuilder predictiveModelBuilder = getRandomForestBuilder(5, 5);
CrossValidator crossValidator = new OutOfTimeCrossValidator(new NonWeightedAUCCrossValLossFunction(), 0.25, 30, new TestDateTimeExtractor()); //number of validation time slices
double totalLoss = crossValidator.getCrossValidatedLoss(predictiveModelBuilder, trainingData);
}
private static PredictiveModelBuilder getRandomForestBuilder(int maxDepth, int numTrees) {
TreeBuilder treeBuilder = new TreeBuilder().maxDepth(maxDepth).ignoreAttributeAtNodeProbability(.7).minLeafInstances(20);
RandomForestBuilder RandomForestBuilder = new RandomForestBuilder(treeBuilder).numTrees(numTrees);
return RandomForestBuilder;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/PredictiveModelOptimizerRunner.java 0000664 0000000 0000000 00000015013 14142342150 0032477 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import org.joda.time.DateTime;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import quickdt.crossValidation.CrossValidator;
import quickdt.crossValidation.DateTimeExtractor;
import quickdt.crossValidation.NonWeightedAUCCrossValLossFunction;
import quickdt.crossValidation.OutOfTimeCrossValidator;
import quickdt.csvReader.CSVToMap;
import quickdt.data.AbstractInstance;
import quickdt.data.Attributes;
import quickdt.data.Instance;
import quickdt.predictiveModelOptimizer.FieldValueRecommender;
import quickdt.predictiveModelOptimizer.PredictiveModelOptimizer;
import quickdt.predictiveModelOptimizer.fieldValueRecommenders.FixedOrderRecommender;
import quickdt.predictiveModelOptimizer.fieldValueRecommenders.MonotonicConvergenceRecommender;
import quickdt.predictiveModels.PredictiveModelBuilderBuilder;
import quickdt.predictiveModels.PredictiveModelWithDataBuilderBuilder;
import quickdt.predictiveModels.randomForest.RandomForestBuilderBuilder;
import java.io.IOException;
import java.io.Serializable;
import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.*;
/**
* Created by chrisreeves on 5/23/14.
*/
public class PredictiveModelOptimizerRunner {
private static final Logger logger = LoggerFactory.getLogger(PredictiveModelOptimizerRunner.class);
public static void main(String[] args) throws IOException {
List builderBuilders = getPredictiveModelBuilderBuilders();
Iterable trainingData = getTrainingData("redshift_training_data.csv");
List configurations = Lists.newLinkedList();
for(PredictiveModelBuilderBuilder builderBuilder : builderBuilders) {
CrossValidator crossValidator = getCrossValidator();
Map parametersToOptimize = getParametersToOptimize();
PredictiveModelOptimizer predictiveModelOptimizer = new PredictiveModelOptimizer(builderBuilder, trainingData, crossValidator,parametersToOptimize);
Map initialConfiguration = getInitialConfiguration();
final Map optimalParameters = predictiveModelOptimizer.determineOptimalConfiguration(initialConfiguration);
Double loss = new Double(0);//predictiveModelOptimizer.getLoss(optimalParameters);
configurations.add(new BidderConfiguration(builderBuilder, optimalParameters, loss));
}
Collections.sort(configurations, new Comparator() {
@Override
public int compare(final BidderConfiguration o1, final BidderConfiguration o2) {
return o1.loss.compareTo(o2.loss);
}
});
logger.info(configurations.get(0).builderBuilder.toString() + " loss:" + configurations.get(0).loss + " " + configurations.get(0).optimalParameters);
logger.info(configurations.get(configurations.size() - 1).builderBuilder.toString() + " loss:" + configurations.get(configurations.size()-1).loss + " " + configurations.get(configurations.size()-1).optimalParameters);
}
private static Map getParametersToOptimize(){
Map parametersToOptimize = Maps.newHashMap();
parametersToOptimize.put("minLeafInstances", new FixedOrderRecommender(40, 60, 70));
parametersToOptimize.put("ignoreAttrProb", new FixedOrderRecommender(0.6, 0.7, 0.8));// 0.95, 0.98, 0.99));
parametersToOptimize.put("numTrees", new MonotonicConvergenceRecommender(Lists.newArrayList(30, 50)));
return parametersToOptimize;
}
private static Map getInitialConfiguration(){
Map initialConfiguration = Maps.newHashMap();
initialConfiguration.put("minLeafInstances", new Integer(30));
initialConfiguration.put("ignoreAttrProb", new Double(.7));
initialConfiguration.put("maxDepth", new Integer(20));
initialConfiguration.put("minScore", new Double(0));
initialConfiguration.put("minCatAttrOcc", new Integer(0));
initialConfiguration.put("bagSize", new Integer(0));
initialConfiguration.put("numTrees", new Integer(30));
initialConfiguration.put("executorThreadCount", new Integer(8));
initialConfiguration.put("rebuildThreshold", new Integer(12));
initialConfiguration.put("splitThreshold", new Integer(2));
return initialConfiguration;
}
private static CrossValidator getCrossValidator() {
return new OutOfTimeCrossValidator(new NonWeightedAUCCrossValLossFunction(), 0.15, 30, new TrainingDateTimeExtractor());
}
private static List getPredictiveModelBuilderBuilders() {
List builderBuilders = Lists.newLinkedList();
builderBuilders.add(new PredictiveModelWithDataBuilderBuilder(new RandomForestBuilderBuilder()));
return builderBuilders;
}
private static Iterable getTrainingData(String filename) throws IOException {
List> instanceMaps = CSVToMap.loadRows(filename);
List instances = CsvReaderExp.convertRawMapToInstance(instanceMaps);
logger.info("Read " + instances.size() + " instances");
return instances;
}
static class BidderConfiguration {
private Map optimalParameters;
private PredictiveModelBuilderBuilder builderBuilder;
private Double loss;
public BidderConfiguration(PredictiveModelBuilderBuilder builderBuilder, Map optimalParameters, Double loss) {
this.builderBuilder = builderBuilder;
this.optimalParameters = optimalParameters;
this.loss = loss;
}
}
public static class TrainingDateTimeExtractor implements DateTimeExtractor {
DateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
@Override
public DateTime extractDateTime(AbstractInstance instance) {
Attributes attributes = instance.getAttributes();
try {
Date currentTimeMillis = dateFormat.parse((String)attributes.get("created_at"));
return new DateTime(currentTimeMillis);
} catch (ParseException e) {
logger.error("Error parsing date", e);
}
return new DateTime();
}
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/ProbDistOfSumOfIndepRandVars.java 0000664 0000000 0000000 00000014163 14142342150 0031736 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import com.google.common.collect.Lists;
import quickdt.data.*;
import quickdt.predictiveModels.decisionTree.TreeBuilder;
import quickdt.predictiveModels.randomForest.RandomForest;
import quickdt.predictiveModels.randomForest.RandomForestBuilder;
import java.io.PrintStream;
import java.util.List;
import java.util.Random;
/**
* Created by alexanderhawk on 1/16/14.
*/
public class ProbDistOfSumOfIndepRandVars {
private int instances;
private int maxDepth;
private int numTrees;
private RandomForest randomForest;
private Random attributeValueGenerator;
private int numPredictiveAttributes;
private int numAttributes;
private Random classificationSampler;
private int classification;
private double classificationVar;
private double stiffness;
private double maxProbabilityOfPositiveClassification;
public ProbDistOfSumOfIndepRandVars(int instances, int maxDepth, int numTrees, int numNoiseAttributes, int numPredictiveAttributes, double maxProbabilityOfPositiveClassification, int stdsAboveTheMeanForRelevance) {
initializeRandomForestProperties(instances, numTrees, maxDepth);
initializeAttributeProperties(numPredictiveAttributes, numNoiseAttributes);
initializeClassificationVariableProperties(maxProbabilityOfPositiveClassification, stdsAboveTheMeanForRelevance);
List trainingData = createTrainingData();
this.randomForest = getRandomForest(trainingData);
}
public void getAverageDeviationInPredictedProbabilities(int samples, double onlyConsiderSamplesAboveThisProbability, boolean print) {
double attributeValue;
Attributes attributes;
double predictedProb;
double actualProb;
double deviation = 0;
for (int i = 0; i < samples; i++) {
attributes = new HashMapAttributes();
classificationVar = 0;
for (int j = 0; j < numAttributes; j++) {
attributeValue = useAttribute(j);
attributes.put(Integer.toString(j), attributeValue);
}
normalizeClassificationVar();
actualProb = getInstanceProbability();
if (actualProb > onlyConsiderSamplesAboveThisProbability) {
predictedProb = randomForest.getProbability(attributes, 1);
deviation += Math.abs(actualProb - predictedProb) / actualProb;
System.out.println("actualProb : predictedProb " + actualProb + " : " + predictedProb);
}
else
i--;
}
// Writer writer = new PrintWriter(System.out);
PrintStream treeView = new PrintStream(System.out); //new WriterOutputStream(writer));
randomForest.dump(treeView);
System.out.println("average deviation" + deviation/samples);
return;
}
private double getInstanceProbability() {
return maxProbabilityOfPositiveClassification * (1 - Math.exp(-stiffness*classificationVar) );
}
// System.out.println("Probability of a click: " + randomForest.getProbability(HashMapAttributes.create("age", 11), "click"));
private void initializeAttributeProperties(int numPredictiveAttributes, int numNoiseAttributes) {
this.attributeValueGenerator = new Random();
this.numPredictiveAttributes = numPredictiveAttributes;
this.numAttributes = numNoiseAttributes + numPredictiveAttributes;
}
private void initializeRandomForestProperties(int instances, int numTrees, int maxDepth) {
this.instances = instances;
this.numTrees = numTrees;
this.maxDepth = maxDepth;
}
private void initializeClassificationVariableProperties(double maxProbabilityOfPositiveClassification,int stdsAboveTheMeanForRelevance) {
this.classificationSampler = new Random();
double standardDeviationOfUniformVariableOn0to1 = Math.sqrt(1.0/12);
double meanOfUniformVariableOn0to1 = 0.5;
double standardDeviationOfClassificationVariable = standardDeviationOfUniformVariableOn0to1 / Math.sqrt(numPredictiveAttributes);
this.stiffness = 1/(meanOfUniformVariableOn0to1 + stdsAboveTheMeanForRelevance*standardDeviationOfClassificationVariable);
this.maxProbabilityOfPositiveClassification = maxProbabilityOfPositiveClassification;
}
private RandomForest getRandomForest(List trainingData) {
TreeBuilder treeBuilder = new TreeBuilder().maxDepth(maxDepth).ignoreAttributeAtNodeProbability(.7);
RandomForestBuilder randomForestBuilder = new RandomForestBuilder(treeBuilder).numTrees(numTrees);
return randomForestBuilder.buildPredictiveModel(trainingData);
}
private List createTrainingData() {
List trainingData = Lists.newArrayList();
double attributeValue;
Instance instance;
Attributes attributes;
for (int i = 0; i < instances; i++) {
attributes = new HashMapAttributes();
classificationVar = 0;
for (int j = 0; j < numAttributes; j++) {
attributeValue = useAttribute(j);
attributes.put(Integer.toString(j), attributeValue);
}
normalizeClassificationVar();
classify();
instance = new Instance(attributes, this.classification );
trainingData.add(instance);
}
return trainingData;
}
private void normalizeClassificationVar() {
classificationVar /= numPredictiveAttributes;
}
private void classify() {
double classProb = getInstanceProbability();
double rand = classificationSampler.nextDouble();
this.classification = rand < classProb ? 1 : 0;
}
private double useAttribute(int attributeNumber) {
double attributeVal = attributeValueGenerator.nextDouble();
incorporateAttributeInClassificationVar(attributeNumber, attributeVal);
return attributeVal;
}
private void incorporateAttributeInClassificationVar(int attributeNumber, double attributeVal) {
if (attributeNumber < numPredictiveAttributes)
classificationVar += attributeVal;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/ProbDistOfSumOfWeightedRandVars.java 0000664 0000000 0000000 00000015350 14142342150 0032436 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import com.google.common.collect.Lists;
import quickdt.data.*;
import quickdt.predictiveModels.decisionTree.TreeBuilder;
import quickdt.predictiveModels.randomForest.RandomForest;
import quickdt.predictiveModels.randomForest.RandomForestBuilder;
import java.io.PrintStream;
import java.util.List;
import java.util.Random;
/**
* Created by alexanderhawk on 1/16/14.
*/
public class ProbDistOfSumOfWeightedRandVars {
private int instances;
private int maxDepth;
private int numTrees;
private RandomForest randomForest;
private Random attributeValueGenerator;
private int numPredictiveAttributes;
private int numAttributes;
private Random classificationSampler;
private int classification;
private double classificationVar;
private double stiffness;
private double maxProbabilityOfPositiveClassification;
public ProbDistOfSumOfWeightedRandVars(int instances, int maxDepth, int numTrees, int numNoiseAttributes, int numPredictiveAttributes, double maxProbabilityOfPositiveClassification, double stdsAboveTheMeanForRelevance) {
initializeRandomForestProperties(instances, numTrees, maxDepth);
initializeAttributeProperties(numPredictiveAttributes, numNoiseAttributes);
initializeClassificationVariableProperties(maxProbabilityOfPositiveClassification, stdsAboveTheMeanForRelevance);
List trainingData = createTrainingData();
this.randomForest = getRandomForest(trainingData);
}
public void getAverageDeviationInPredictedProbabilities(int samples, double onlyConsiderSamplesAboveThisProbability, boolean print) {
double attributeValue;
Attributes attributes;
double predictedProb;
double actualProb;
double deviation = 0;
System.out.println("getting deviations\n");
for (int sample = 0; sample < samples; sample++) {
attributes = new HashMapAttributes();
classificationVar = 0;
for (int attributeNumber = 1; attributeNumber <= numAttributes; attributeNumber++) {
attributeValue = useAttribute(attributeNumber);
attributes.put(Integer.toString(attributeNumber), attributeValue);
}
actualProb = getInstanceProbability();
if (actualProb > onlyConsiderSamplesAboveThisProbability) {
predictedProb = randomForest.getProbability(attributes, 1);
deviation += Math.abs(actualProb - predictedProb) / actualProb;
System.out.println("actualProb : predictedProb " + actualProb + " : " + predictedProb);
}
else
sample--;
}
// Writer writer = new PrintWriter(System.out);
PrintStream treeView = new PrintStream(System.out); //new WriterOutputStream(writer));
randomForest.dump(treeView);
System.out.println("average deviation" + deviation/samples);
return;
}
private double getInstanceProbability() {
double instanceProbability = maxProbabilityOfPositiveClassification * (1 - Math.exp(-stiffness*classificationVar) );
return instanceProbability;
}
// System.out.println("Probability of a click: " + randomForest.getProbability(HashMapAttributes.create("age", 11), "click"));
private void initializeAttributeProperties(int numPredictiveAttributes, int numNoiseAttributes) {
this.attributeValueGenerator = new Random();
this.numPredictiveAttributes = numPredictiveAttributes;
this.numAttributes = numNoiseAttributes + numPredictiveAttributes;
}
private void initializeRandomForestProperties(int instances, int numTrees, int maxDepth) {
this.instances = instances;
this.numTrees = numTrees;
this.maxDepth = maxDepth;
}
private void initializeClassificationVariableProperties(double maxProbabilityOfPositiveClassification, double stdsAboveTheMeanForRelevance) {
this.classificationSampler = new Random();
double standardDeviationOfUniformVariableOn0to1 = Math.sqrt(1.0/12);
double meanOfPredictiveVariable = 0;
for (int i=1; i<=numPredictiveAttributes; i++)
meanOfPredictiveVariable+=(2.0-1.0/i)/2 * 1/i;
double standardDeviationOfClassificationVariable = standardDeviationOfUniformVariableOn0to1 / Math.sqrt(numPredictiveAttributes);
this.stiffness = 1/(meanOfPredictiveVariable + stdsAboveTheMeanForRelevance*standardDeviationOfClassificationVariable);
this.maxProbabilityOfPositiveClassification = maxProbabilityOfPositiveClassification;
}
private RandomForest getRandomForest(List trainingData) {
TreeBuilder treeBuilder = new TreeBuilder().maxDepth(maxDepth).ignoreAttributeAtNodeProbability(.7);
RandomForestBuilder randomForestBuilder = new RandomForestBuilder(treeBuilder).numTrees(numTrees);
return randomForestBuilder.buildPredictiveModel(trainingData);
}
private List createTrainingData() {
List trainingData = Lists.newArrayList();
double attributeValue;
Instance instance;
Attributes attributes;
for (int i = 0; i < instances; i++) {
attributes = new HashMapAttributes();
classificationVar = 0;
for (int attributeNumber = 1; attributeNumber <= numAttributes; attributeNumber++) {
attributeValue = useAttribute(attributeNumber);
attributes.put(Integer.toString(attributeNumber), attributeValue);
}
classify();
instance = new Instance(attributes, this.classification );
trainingData.add(instance);
}
return trainingData;
}
private void classify() {
double classProb = getInstanceProbability();
double rand = classificationSampler.nextDouble();
this.classification = rand < classProb ? 1 : 0;
}
private double useAttribute(int attributeNumber) {
double attributeVal;
if (attributeNumber <= numPredictiveAttributes) {
attributeVal = getPredictiveAttribute(attributeNumber);
}
else
attributeVal = attributeValueGenerator.nextDouble();
return attributeVal;
}
private double getPredictiveAttribute(int attributeNumber) {
double attributeVal;
attributeVal = (attributeValueGenerator.nextDouble())/attributeNumber + (1-1.0/attributeNumber);
incorporateAttributeInClassificationVar(attributeNumber, attributeVal);
return attributeVal;
}
private void incorporateAttributeInClassificationVar(int attributeNumber, double attributeVal) {
if (attributeNumber <= numPredictiveAttributes)
classificationVar += attributeVal/attributeNumber;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/ProbDistOfVarDependentOnCatVars.java 0000664 0000000 0000000 00000020364 14142342150 0032424 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import com.google.common.collect.Lists;
import quickdt.data.*;
import quickdt.predictiveModels.decisionTree.TreeBuilder;
import quickdt.predictiveModels.randomForest.RandomForest;
import quickdt.predictiveModels.randomForest.RandomForestBuilder;
import java.io.PrintStream;
import java.util.List;
import java.util.Random;
/**
* Created by alexanderhawk on 1/17/14.
*/
public class ProbDistOfVarDependentOnCatVars {
private int instances;
private int maxDepth;
private int numTrees;
private RandomForest randomForest;
private Random attributeValueGenerator;
private int numPredictiveAttributes;
private int numAttributes;
private int numAttributeVals;
private Random classificationSampler;
private int classification;
private double classificationVar;
private double stiffness;
private double maxProbabilityOfPositiveClassification;
private double probabilityRangesOfAttributeValue[][];
private double impactOfAttributeValue[][];
public ProbDistOfVarDependentOnCatVars(int instances, int maxDepth, int numTrees, int numNoiseAttributes, int numPredictiveAttributes, int numAttributeVals, double maxProbabilityOfPositiveClassification, double distanceAboveTheMeanForRelevance) {
initializeRandomForestProperties(instances, numTrees, maxDepth);
initializeAttributeProperties(numPredictiveAttributes, numNoiseAttributes, numAttributeVals);
initializeClassificationVariableProperties(maxProbabilityOfPositiveClassification, distanceAboveTheMeanForRelevance);
List trainingData = createTrainingData();
this.randomForest = getRandomForest(trainingData);
}
public void getAverageDeviationInPredictedProbabilities(int samples, double onlyConsiderSamplesAboveThisProbability, boolean print) {
double attributeValue;
Attributes attributes;
double predictedProb;
double actualProb;
double deviation = 0;
System.out.println("getting deviations\n");
for (int sample = 0; sample < samples; sample++) {
attributes = new HashMapAttributes();
classificationVar = 0;
for (int attributeNumber = 0; attributeNumber < numAttributes; attributeNumber++) {
attributeValue = useAttribute(attributeNumber);
attributes.put(Integer.toString(attributeNumber), attributeValue);
}
actualProb = getInstanceProbability();
if (actualProb > onlyConsiderSamplesAboveThisProbability) {
predictedProb = randomForest.getProbability(attributes, 1);
deviation += Math.abs(actualProb - predictedProb) / actualProb;
System.out.println("actualProb : predictedProb " + actualProb + " : " + predictedProb);
}
else
sample--;
}
// Writer writer = new PrintWriter(System.out);
PrintStream treeView = new PrintStream(System.out); //new WriterOutputStream(writer));
randomForest.dump(treeView);
System.out.println("average deviation" + deviation/samples);
return;
}
private double getInstanceProbability() {
double instanceProbability = maxProbabilityOfPositiveClassification * (1 - Math.exp(-stiffness*classificationVar) );
return instanceProbability;
}
// System.out.println("Probability of a click: " + randomForest.getProbability(HashMapAttributes.create("age", 11), "click"));
private void initializeAttributeProperties(int numPredictiveAttributes, int numNoiseAttributes, int numAttributeVals) {
this.attributeValueGenerator = new Random();
this.numPredictiveAttributes = numPredictiveAttributes;
this.numAttributes = numNoiseAttributes + numPredictiveAttributes;
this.numAttributeVals = numAttributeVals;
initializeProbabilityRangesOfAttributeValue();
initializeImpactOfVariableValue();
}
private void initializeProbabilityRangesOfAttributeValue() {
probabilityRangesOfAttributeValue = new double[numAttributes][numAttributeVals];
double normalizationConst = 0;
Random probabilityValueGenerator = new Random();
for (int i=0; i0 )
probabilityRangesOfAttributeValue[i][j] += probabilityRangesOfAttributeValue[i][j-1];
}
}
}
private void initializeImpactOfVariableValue() {
impactOfAttributeValue = new double[numAttributes][numAttributeVals];
Random probabilityValueGenerator = new Random();
for (int i=0; i trainingData) {
TreeBuilder treeBuilder = new TreeBuilder().maxDepth(maxDepth).ignoreAttributeAtNodeProbability(.7);
RandomForestBuilder randomForestBuilder = new RandomForestBuilder(treeBuilder).numTrees(numTrees);
return randomForestBuilder.buildPredictiveModel(trainingData);
}
private List createTrainingData() {
List trainingData = Lists.newArrayList();
double attributeValue;
Instance instance;
Attributes attributes;
for (int i = 0; i < instances; i++) {
attributes = new HashMapAttributes();
classificationVar = 0;
for (int attributeNumber = 0; attributeNumber < numAttributes; attributeNumber++) {
attributeValue = useAttribute(attributeNumber);
attributes.put(Integer.toString(attributeNumber), attributeValue);
}
classify();
instance = new Instance(attributes, this.classification );
trainingData.add(instance);
}
return trainingData;
}
private void classify() {
double classProb = getInstanceProbability();
double rand = classificationSampler.nextDouble();
this.classification = rand < classProb ? 1 : 0;
}
private double useAttribute(int attributeNumber) {
double attributeVal = sampleAttributeValueFromProbabilityDistribution(attributeNumber);
incorporateAttributeInClassificationVar(attributeNumber, attributeVal);
return attributeVal;
}
private double sampleAttributeValueFromProbabilityDistribution(int attributeNumber) {
double attributeVal =0;
double random = attributeValueGenerator.nextDouble();
for (int i=0; i trainingData = createTrainingData();
this.randomForest = getRandomForest(trainingData);
}
public void getAverageDeviationInPredictedProbabilities(int samples, double onlyConsiderSamplesAboveThisProbability, boolean print) {
Instance instance;
double predictedProb;
double actualProb;
double deviation = 0;
System.out.println("getting deviations\n");
for (double val : currentSample) System.out.println("val: " + val);
System.out.printf("sample repsonse0 %f %n", currentSample[currentSample.length - 1]);
for (int sample = 0; sample < samples; sample++) {
instance = sampleInstance("sampleResponseTrue");
System.out.flush();
//System.out.printf("sample repsonse %f %n", currentSample[currentSample.length - 1]);
for (double val : currentSample) System.out.println("val: " + val);
actualProb = getActualConditionalProbabilityOfClick();
if (actualProb > onlyConsiderSamplesAboveThisProbability) {
predictedProb = randomForest.getProbability(instance.getAttributes(), 1.0);
deviation += Math.abs(actualProb - predictedProb) / actualProb;
// if (print)
// System.out.println("actualProb : predictedProb " + actualProb + " : " + predictedProb);
// for (double val : currentSample) System.out.println("val: " + val);
}
else
sample--;
}
PrintStream treeView = new PrintStream(System.out); //new WriterOutputStream(writer));
randomForest.dump(treeView);
System.out.println("average deviation" + deviation/samples);
return;
}
private double getActualConditionalProbabilityOfClick() {
currentSample[variableNumberOfResponse] = numRawResponseStates/2.0 - 0.5;
double jointProbabilityForObservingAttributesWithAClick = variableDistribution.density(currentSample);
double marginalProbabilityForObservingTheAttributes = getMarginalProbabilityForObservingAttributes(currentSample);
double conditionalProbabilityOfAClick = jointProbabilityForObservingAttributesWithAClick / marginalProbabilityForObservingTheAttributes;
System.out.println("margProb " + marginalProbabilityForObservingTheAttributes + " : jointProb " + jointProbabilityForObservingAttributesWithAClick + " conProb : " + conditionalProbabilityOfAClick + "\n" );
return conditionalProbabilityOfAClick;
}
private double getMarginalProbabilityForObservingAttributes(double sample[]) {
double marginalProbabilityForObservingAttributes = 0;
double minRawResponse = -numRawResponseStates/2.0 + 0.5;
for (int i = 0; i < numRawResponseStates; i++) {
sample[variableNumberOfResponse] = minRawResponse + i;
marginalProbabilityForObservingAttributes += variableDistribution.density(sample);
}
return marginalProbabilityForObservingAttributes;
}
private void initializeCurrentSample(int stepsBeforeMixingSetsIn) {
Random initialAttributeVal = new Random();
currentSample = new double[numVariables];
proposedSample = new double [numVariables];
int stateNumber;
for (int i = 0; i < numVariables; i++) {
if (i trainingData) {
TreeBuilder treeBuilder = new TreeBuilder().maxDepth(maxDepth).ignoreAttributeAtNodeProbability(.7);
RandomForestBuilder randomForestBuilder = new RandomForestBuilder(treeBuilder).numTrees(numTrees);
return randomForestBuilder.buildPredictiveModel(trainingData);
}
private List createTrainingData() {
List trainingData = Lists.newArrayList();
Instance instance;
for (globalCount = 0; globalCount < instances; globalCount++) {
instance = sampleInstance("sampleResponseTrue");
trainingData.add(instance);
if (globalCount%1001==0)
System.out.printf("repsonse %f %n", currentSample[currentSample.length - 1]);
}
// System.out.println("instances " + instances );
return trainingData;
}
private Instance sampleInstance(String sampleResponse) {
updateCurrentSample(sampleResponse);
SampleInstance sampleInstance = new SampleInstance(currentSample);
return new Instance(sampleInstance.attributes, sampleInstance.response );
}
private void updateCurrentSample(String sampleResponse) {
getProposedSample();
setProposedSampleToCurrentSampleIfItPassesAcceptanceCriterion(sampleResponse);
}
private void getProposedSample() {
for (int variableNumber = 0; variableNumber < numPredictiveAttributes; variableNumber++) //only get proposal for predictiven attributes
getProposedVariableMove(variableNumber, numAttributeVals);
getProposedVariableMove(variableNumberOfResponse, numRawResponseStates);
}
private void getProposedVariableMove(int variableNumber, int numVariableVals) {
if (probabilityOfMakingAMonteCarloMove.nextDouble() < monteCarloMoveProbability)
return;
else {
if (variableValNotExtrema(variableNumber, numVariableVals))
proposeMoveForNonExtrema(variableNumber);
else if (variableIsMinima(variableNumber, numVariableVals))
proposeMoveFromMinima(variableNumber);
else if (variableIsMaxima(variableNumber, numVariableVals))
proposeMoveFromMaxima(variableNumber);
else {
System.out.println("variable val is out of bounds: varNum: " + variableNumber + ", varVal: " + currentSample[variableNumber]);
System.exit(0);
}
}
}
private boolean variableValNotExtrema(int variableNumber, int numVariableVals) {
return currentSample[variableNumber]>minVal(numVariableVals) && currentSample[variableNumber] 1)
for (int i=0; i < numVariables; i++) {
currentSample[i] = proposedSample[i];
if (i!=variableNumberOfResponse && (currentSample[i] == -2.0 || currentSample[i] == -1.0 || currentSample[i] == 0 || currentSample[i] == 1.0 || currentSample[i] == 2.0))
System.out.printf("currentSample[%d] %f, proposedSample[%d] %f %n", i, currentSample[i], i, proposedSample[i]);
}
}
class SampleInstance {
public Attributes attributes;
public double response;
public SampleInstance(double sample[]) {
attributes = new HashMapAttributes();
for (int attributeNumber = 0; attributeNumber < numAttributes; attributeNumber++)
attributes.put(Integer.toString(attributeNumber), sample[attributeNumber]);
setResponse(sample);
}
private void setResponse (double sample[]) {
double rawResponse = sample[sample.length - 1];
double maxRawResponse = numRawResponseStates/2.0 - 0.5;
response = (rawResponse > maxRawResponse - .0001) ? 1.0 : 0;
if (response ==1 && randomForest == null) {
System.out.println("example of positive response");
System.exit(0);
}
// System.out.println("response" + response + "rawResponse" + rawResponse + "maxRawResponse" + maxRawResponse);
// System.exit(0);
}
}
*/
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/TrainingDataGenerator.java 0000664 0000000 0000000 00000010325 14142342150 0030540 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
/**
* Created by alexanderhawk on 1/16/14.
*/
public class TrainingDataGenerator {
/*
* private Random uniformRandom;
*
* private int instances; private int numPredictiveAttributes;
*
* private double latentVariable; //a latent variable controls
* clickClassification private double decayConstantForNoClickEvent; //the higher
* the value, the less likely a No click event becomes. private double
* maxProbabilityOfClick; private String bidRequestAttributes[];
*
*
* public TrainingDataGenerator(int instances, double maxProbabilityOfClick,
* String bidRequestAttributes[]) { this.uniformRandom = new Random();
* this.instances = instances; this.maxProbabilityOfClick =
* maxProbabilityOfClick; this.bidRequestAttributes = bidRequestAttributes;
* this.numPredictiveAttributes = bidRequestAttributes.length;
* initializeClickProbabilityDistribution(); }
*
* public void getAverageDeviationInPredictedProbabilities(int samples, double
* onlyConsiderSamplesAboveThisProbability, BidderPredictiveModel
* bidderPredictiveModel) { Attributes attributes; double predictedProb; double
* rawPredictedProb; double actualClickProbability; double deviation = 0;
*
* for (int i = 0; i < samples; i++) { attributes =
* getAttributesForAnInstance(); actualClickProbability =
* getClickProbabilityFromLatentVariableValue(); if (actualClickProbability >
* onlyConsiderSamplesAboveThisProbability) { rawPredictedProb =
* bidderPredictiveModel.getProbability(attributes, 1); predictedProb =
* bidderPredictiveModel.calibrator.correct(rawPredictedProb); deviation +=
* Math.abs(actualClickProbability - predictedProb) / actualClickProbability; //
* System.out.println("actualClickProbability : predictedProb " +
* actualClickProbability + " : " + predictedProb); } else i--; } PrintStream
* treeView = new PrintStream(System.out); randomForest.dump(treeView); //prints
* a sample tree for debugging purposes
*
* System.out.println("average deviation" + deviation/samples); return; }
*
* private Attributes getAttributesForAnInstance() { Attributes attributes = new
* HashMapAttributes();
*
* double attrValue; latentVariable = 0; String key; for (int j = 0; j <
* numPredictiveAttributes; j++) { attrValue =
* getAttributeValAndTheEffectOnTheLatentVariable(j); key =
* bidRequestAttributes[j]; // Integer.toString(j); attributes.put(key,
* attrValue); } return attributes; }
*
* private double getClickProbabilityFromLatentVariableValue() { return
* maxProbabilityOfClick * (1 - Math.exp(-decayConstantForNoClickEvent *
* latentVariable) ); }
*
* private void initializeClickProbabilityDistribution() { double
* standardDeviationOfUniformVariableOn0to1 = Math.sqrt(1.0/12); double
* meanOfUniformVariableOn0to1 = 0.5; int stdsAboveTheMeanForRelevance = 16;
* //make this number higher if you want more instances that have high click
* probabilities. double standardDeviationOfClassificationVariable =
* standardDeviationOfUniformVariableOn0to1 /
* Math.sqrt(numPredictiveAttributes); this.decayConstantForNoClickEvent =
* 1/(meanOfUniformVariableOn0to1 +
* stdsAboveTheMeanForRelevance*standardDeviationOfClassificationVariable); }
*
* public List createTrainingData() {
*
* List trainingData = Lists.newArrayList(); double attrValue;
* Instance instance; Attributes attributes; int clickClassification;
*
* for (int i = 0; i < instances; i++) { attributes =
* getAttributesForAnInstance(); clickClassification = setClickValue(); instance
* = new Instance(attributes, clickClassification); trainingData.add(instance);
* } return trainingData; }
*
* private int setClickValue() { double clickProbability =
* getClickProbabilityFromLatentVariableValue(); double rand =
* uniformRandom.nextDouble(); int clickClassification = rand < clickProbability
* ? 1 : 0; return clickClassification; }
*
* private double getAttributeValAndTheEffectOnTheLatentVariable(int
* attributeNumber) { double attributeVal = uniformRandom.nextDouble();
* latentVariable += attributeVal/numPredictiveAttributes; int
* attributeValForPredictiveModel = (int)(attributeVal*10000); return
* attributeValForPredictiveModel; }
*/
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/TrainingDataGenerator2.java 0000664 0000000 0000000 00000011707 14142342150 0030627 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import com.google.common.collect.Lists;
import quickdt.data.*;
import quickdt.predictiveModels.randomForest.RandomForest;
import java.util.List;
import java.util.Random;
/**
* Created by alexanderhawk on 1/16/14.
*/
public class TrainingDataGenerator2 {
private Random uniformRandom;
private int instances;
private int numPredictiveAttributes;
private double latentVariable; //a latent variable controls clickClassification
private double decayConstantForNoClickEvent; //the higher the value, the less likely a No click event becomes.
private double maxProbabilityOfClick;
private String bidRequestAttributes[];
public TrainingDataGenerator2(int instances, double maxProbabilityOfClick, String bidRequestAttributes[]) {
this.uniformRandom = new Random();
this.instances = instances;
this.maxProbabilityOfClick = maxProbabilityOfClick;
this.bidRequestAttributes = bidRequestAttributes;
this.numPredictiveAttributes = bidRequestAttributes.length;
initializeClickProbabilityDistribution();
}
public void getAverageDeviationInPredictedProbabilities(int samples, double onlyConsiderSamplesAboveThisProbability, RandomForest randomForest) {
Attributes attributes;
double predictedProb;
double rawPredictedProb;
double actualClickProbability;
double deviation = 0;
for (int i = 0; i < samples; i++) {
attributes = getAttributesForAnInstance();
actualClickProbability = getClickProbabilityFromLatentVariableValue();
if (actualClickProbability > onlyConsiderSamplesAboveThisProbability) {
predictedProb = randomForest.getProbability(attributes, 1.0);
// predictedProb = randomForest.calibrator.correct(rawPredictedProb);
deviation += Math.abs(actualClickProbability - predictedProb) / actualClickProbability;
// System.out.println("actualClickProbability : predictedProb : rawProb" + actualClickProbability + " : " + predictedProb + " " + rawPredictedProb);
}
else
i--;
}
// PrintStream treeView = new PrintStream(System.out);
// bidderPredictiveModel.clickPredictor.dump(treeView); //prints a sample tree for debugging purposes
System.out.println("average deviation" + deviation/samples);
}
private Attributes getAttributesForAnInstance() {
Attributes attributes = new HashMapAttributes();
double attributeValue;
latentVariable = 0;
String key;
for (int j = 0; j < numPredictiveAttributes; j++) {
attributeValue = getAttributeValAndTheEffectOnTheLatentVariable(j);
key = bidRequestAttributes[j]; // Integer.toString(j);
attributes.put(key, attributeValue);
}
return attributes;
}
private double getClickProbabilityFromLatentVariableValue() {
return maxProbabilityOfClick * (1 - Math.exp(-decayConstantForNoClickEvent * latentVariable) );
}
private void initializeClickProbabilityDistribution() {
double standardDeviationOfUniformVariableOn0to1 = Math.sqrt(1.0/12);
double meanOfUniformVariableOn0to1 = 0.5;
int stdsAboveTheMeanForRelevance = 16; //make this number higher if you want more instances that have high click probabilities.
double standardDeviationOfClassificationVariable = standardDeviationOfUniformVariableOn0to1 / Math.sqrt(numPredictiveAttributes);
this.decayConstantForNoClickEvent = 1/(meanOfUniformVariableOn0to1 + stdsAboveTheMeanForRelevance*standardDeviationOfClassificationVariable);
System.out.println("decay constant " + decayConstantForNoClickEvent );
//System.exit(0);
}
public List createTrainingData() {
List trainingData = Lists.newArrayList();
double attributeValue;
AbstractInstance instance;
Attributes attributes;
double clickClassification;
for (int i = 0; i < instances; i++) {
attributes = getAttributesForAnInstance();
clickClassification = setClickValue();
instance = new Instance(attributes, clickClassification);
trainingData.add(instance);
}
return trainingData;
}
private double setClickValue() {
double clickProbability = getClickProbabilityFromLatentVariableValue();
double rand = uniformRandom.nextDouble();
double clickClassification = rand < clickProbability ? 1.0 : 0.0;
return clickClassification;
}
private double getAttributeValAndTheEffectOnTheLatentVariable(int attributeNumber) {
double attributeVal = uniformRandom.nextDouble();
latentVariable += attributeVal/numPredictiveAttributes;
int attributeValForPredictiveModel = (int)(attributeVal*10000);
return attributeValForPredictiveModel;
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/experiments/TreeTests.java 0000664 0000000 0000000 00000003140 14142342150 0026243 0 ustar 00root root 0000000 0000000 package quickdt.experiments;
import java.io.IOException;
import java.io.Serializable;
import java.util.List;
import java.util.Map;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import com.google.common.collect.Lists;
import quickdt.csvReader.CSVToMap;
import quickdt.data.AbstractInstance;
import quickdt.data.Instance;
import quickdt.predictiveModels.decisionTree.TreeBuilder;
import quickdt.predictiveModels.randomForest.RandomForest;
import quickdt.predictiveModels.randomForest.RandomForestBuilder;
/**
* Created by alexanderhawk on 6/8/14.
*/
public class TreeTests {
private static final Logger logger = LoggerFactory.getLogger(TreeTests.class);
public static void main(String[] args) {
Iterable trainingData = Lists.newArrayList();
try {
trainingData = getTrainingData("redshift_training_data.csv");
} catch (IOException e) {
e.printStackTrace();
}
TreeBuilder treeBuilder = new TreeBuilder().maxDepth(4).ignoreAttributeAtNodeProbability(.7)
.minInstancesPerCategoricalVariable(0);
RandomForestBuilder randomForestBuilder = new RandomForestBuilder(treeBuilder).numTrees(20);
RandomForest randomForest = randomForestBuilder.buildPredictiveModel(trainingData);
randomForest.dump(System.out, 20);
}
private static Iterable getTrainingData(String filename)
throws IOException {
List> instanceMaps = CSVToMap.loadRows(filename);
List instances = CsvReaderExp.convertRawMapToInstance(instanceMaps);
logger.info("Read " + instances.size() + " instances");
return instances;
}
} sanity-quickdt-808b62c/src/main/java/quickdt/inspection/ 0000775 0000000 0000000 00000000000 14142342150 0023270 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/inspection/AttributeImportanceFinder.java 0000664 0000000 0000000 00000011035 14142342150 0031250 0 ustar 00root root 0000000 0000000 package quickdt.inspection;
import com.google.common.base.Function;
import com.google.common.collect.*;
import com.twitter.common.stats.ReservoirSampler;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import quickdt.Misc;
import quickdt.crossValidation.CrossValidator;
import quickdt.crossValidation.StationaryCrossValidator;
import quickdt.data.*;
import quickdt.predictiveModels.PredictiveModel;
import quickdt.predictiveModels.PredictiveModelBuilder;
import quickdt.predictiveModels.decisionTree.TreeBuilder;
import java.io.Serializable;
import java.util.*;
public class AttributeImportanceFinder {
private static final Logger logger = LoggerFactory.getLogger(AttributeImportanceFinder.class);
public AttributeImportanceFinder() {
}
public TreeSet determineAttributeImportance(final Iterable trainingData) {
return determineAttributeImportance(new TreeBuilder(), trainingData);
}
public TreeSet determineAttributeImportance(PredictiveModelBuilder predictiveModelBuilder, final Iterable trainingData) {
return determineAttributeImportance(new StationaryCrossValidator(4, 1), predictiveModelBuilder, trainingData);
}
public TreeSet determineAttributeImportance(CrossValidator crossValidator, PredictiveModelBuilder predictiveModelBuilder, final Iterable trainingData) {
Set attributes = Sets.newHashSet();
for (AbstractInstance instance : trainingData) {
attributes.addAll(instance.getAttributes().keySet());
}
TreeSet scores = Sets.newTreeSet();
LinkedList trainingSet = Lists.newLinkedList();
LinkedList testingSet = Lists.newLinkedList();
for (AbstractInstance instance : trainingData) {
if (Math.abs(instance.getAttributes().hashCode()) % 10 == 0) {
testingSet.add(instance);
} else {
trainingSet.add(instance);
}
}
Map> samplesPerAttribute = Maps.newHashMap();
for (AbstractInstance instance : trainingData) {
for (Map.Entry attributeKeyValue : instance.getAttributes().entrySet()) {
ReservoirSampler sampler = samplesPerAttribute.get(attributeKeyValue.getKey());
if (sampler == null) {
sampler = new ReservoirSampler(1000);
samplesPerAttribute.put(attributeKeyValue.getKey(), sampler);
}
sampler.sample(attributeKeyValue.getValue());
}
}
for (String attributeToExclude : attributes) {
final ReservoirSampler samplerForAttributeToExclude = samplesPerAttribute.get(attributeToExclude);
final ArrayList samplesForAttribute = Lists.newArrayList(samplerForAttributeToExclude.getSamples());
if (samplesForAttribute.size() < 2) continue;
Iterable scrambledTestingSet = Lists.newLinkedList(Iterables.transform(testingSet, new AttributeScrambler(attributeToExclude, samplesForAttribute)));
double score = crossValidator.getCrossValidatedLoss(predictiveModelBuilder, scrambledTestingSet);
logger.info("Attribute \""+attributeToExclude+"\" score is "+score);
scores.add(new AttributeScore(attributeToExclude, score));
}
return scores;
}
public static class AttributeScrambler implements Function {
public AttributeScrambler(final String attributeToExclude, ArrayList attributeValueSamples) {
this.attributeToExclude = attributeToExclude;
this.attributeValueSamples = attributeValueSamples;
}
private final String attributeToExclude;
private final ArrayList attributeValueSamples;
@Override
public AbstractInstance apply(final AbstractInstance instance) {
Attributes randomizedAttributes = new HashMapAttributes();
randomizedAttributes.putAll(instance.getAttributes());
final Serializable randomValue = attributeValueSamples.get(Misc.random.nextInt(attributeValueSamples.size()));
randomizedAttributes.put(attributeToExclude, randomValue);
return new Instance(randomizedAttributes, instance.getClassification());
}
}
} sanity-quickdt-808b62c/src/main/java/quickdt/inspection/AttributeScore.java 0000664 0000000 0000000 00000001562 14142342150 0027076 0 ustar 00root root 0000000 0000000 package quickdt.inspection;
/**
* Created by ian on 3/29/14.
*/
public class AttributeScore implements Comparable {
private final String attribute;
private final double score;
public AttributeScore(final String attribute, final double score) {
this.attribute = attribute;
this.score = score;
}
@Override
public int compareTo(final AttributeScore o) {
return Double.compare(score, o.score);
}
public String getAttribute() {
return attribute;
}
public double getScore() {
return score;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("AttributeScore{");
sb.append("attribute='").append(attribute).append('\'');
sb.append(", score=").append(score);
sb.append('}');
return sb.toString();
}
}
sanity-quickdt-808b62c/src/main/java/quickdt/predictiveModelOptimizer/ 0000775 0000000 0000000 00000000000 14142342150 0026137 5 ustar 00root root 0000000 0000000 sanity-quickdt-808b62c/src/main/java/quickdt/predictiveModelOptimizer/FieldValueRecommender.java 0000664 0000000 0000000 00000000443 14142342150 0033204 0 ustar 00root root 0000000 0000000 package quickdt.predictiveModelOptimizer;
import com.google.common.base.Optional;
import java.util.Map;
/**
* Created by ian on 4/12/14.
*/
public interface FieldValueRecommender {
public Optional