I think this is what is called classes_ in most classifiers

*columns

(Oops, sorry about that)

Not sure what this means

Essentially it's the number of columns of X that is put into the fit() function
Then when transform is called on another X2, we verify that X2 has the same number of columns as X, if the number of columns are different, an error is thrown

Since you're always accessing all layers of the defaultdict's nesting, why not just use a tuple of (X, output_idx, y[output_idx]) as a key to a single Counter?

You might want to use a Counter here. A difference which may be valuable is that looking up a key in a defaultdict sets that key. Looking it up in a Counter will return 0 but not expand the dict.

For similar reasons you should not use a defaultdict with an active default_factory at transform time.

Sorry, you should not use a default with an active default_factory when the keys are likely to be sparsely found.

If I were you, I would benchmark having a prefabricated dict, or an array of counts, for all possible classes. Then just copy as needed, and at test time don't copy at all. That way for X values that are seen, you will get correctly-sized dicts from the outset. A bit more memory for X values that are exclusive to some values of y, but perhaps a valuable saving in time. I'm not certain, but I think there's some potential for experimenting with the correct data structure here.

Maybe we should consider producing a working estimator but keeping these count dicts private until we're happy with the data structure.

Yes. I agree, we should experiment with data structures to find the right one.
Currently I am leaning towards just making my own "default" dict that checks if key in my_dict: every time.
I did a benchmark on this, testing the time to build counts when no key exists, when the key already exists, and lookup into dict

import time
from collections import defaultdict
from collections import Counter

loop_count = 10000000

t = time.time()
a = {}
for i in xrange(loop_count):
	if i in a:
		a[i] += i
	else:
		a[i] = i

for i in xrange(loop_count / 2):
	if i in a:
		a[i] += i
	else:
		a[i] = i

for i in xrange(loop_count * 2):
	if i in a:
		x = a[i] + 5
	else:
		x = 5

print "time take for {}:", (time.time() - t)


t = time.time()
b = defaultdict(int)
for i in xrange(loop_count):
	b[i] += i

for i in xrange(loop_count / 2):
	b[i] += i

for i in xrange(loop_count * 2):
	x = b[i] + 5

print "time take for defaultdict:", (time.time() - t)

t = time.time()
c = Counter(xrange(loop_count)) + Counter(xrange(loop_count / 2))

for i in xrange(loop_count * 2):
	x = c[i] + 5

print "time take for counter:", (time.time() - t)


t = time.time()
c2 = Counter()
for i in xrange(loop_count):
	c2[i] += i

for i in xrange(loop_count / 2):
	c2[i] += i

for i in xrange(loop_count * 2):
	x = c2[i] + 5

print "time take for counter version 2:", (time.time() - t)

And the results were kind of surprising:

time take for {}: 7.626983881
time take for defaultdict: 9.94141697884
time take for counter: 58.303508997
time take for counter version 2: 15.7543189526

You mean list of lists, not 2d. Needn't be rectangular array.

Changed to lists of lists:
- 'all' (default) : Every feature is concatenated and counted
- 'each' : Each feature will have its own set of counts
- list of indices : Only the given list of features is
concatenated and counted
- list of lists of indices : The given list of lists of features is
concatenated and counted, but each list in the
list of lists has its own set of counts

hanging indent, please

Handled

hanging indent, please

Handled

not clear that these are counted together, i.e. these features are concatenated and counted.

Changed to

    - 1D list of indices : Only the given list of features is
                           concatenated and counted
    - 2D list of indices : The given list of lists of features is
                           concatenated and counted, but each list in the
                           list of lists has its own set of counts

not clear that these are counted together, i.e. these features are concatenated and counted.

Changed to "- 'all' (default) : Every feature is concatenated and counted"

why don't you just reshape y at the top?

Now reshapes y at the top if it is 1D

do this out of the j loop

Also, tuple(my_array) is slower than tuple(my_array.tolist())

make this a local variable if you're going to overwrite it below. but you could just consider using something like LabelEncoder.

Changed to classes_unsorted
I am unsure about using LabelEncoder because I won't make good use of everything in there and there will be additional overhead in calculating the things that I won't be using

why don't you just set y to 0s when it's None

Changed to np.zeros(len(X))
Was unsure about it before because it would create len(X) additional elements in memory that wouldn't really have that much use, but it certainly did make the code a lot cleaner.

If you have arrays instead of single counts in your cache you don't need this loop.