Thanks for the PR @StealthyKamereon .

Do I understand correctly that this essentially removes all zeros but one within the column?

If that's the case, then the behaviour won't be equivalent to the dense case:

#dense case 
col_data = np.random.randn(1000)
col_data[:900] = 0

max_bins = 30
percentiles = np.linspace(0, 100, num=max_bins + 1)
percentiles = percentiles[1:-1]

np.percentile(col_data, percentiles, interpolation='midpoint')
# gives
array([-0.32659394,  0.        ,  0.        ,  0.        ,  0.        ,
        0.        ,  0.        ,  0.        ,  0.        ,  0.        ,
        0.        ,  0.        ,  0.        ,  0.        ,  0.        ,
        0.        ,  0.        ,  0.        ,  0.        ,  0.        ,
        0.        ,  0.        ,  0.        ,  0.        ,  0.        ,
        0.        ,  0.        ,  0.        ,  0.5365524 ])

!=

# proposed sparse case
col_data2 = col_data[np.flatnonzero(col_data)]
col_data2 = np.append(col_data2, 0)

np.percentile(col_data2, percentiles, interpolation='midpoint'
# gives
array([-1.59708717, -1.28013648, -1.06639733, -0.93588368, -0.86844474,
       -0.77952759, -0.67911702, -0.61731544, -0.5256898 , -0.32659394,
       -0.19481156, -0.05218316,  0.00542425,  0.0535143 ,  0.1421762 ,
        0.24276456,  0.27940835,  0.36767042,  0.44821144,  0.5365524 ,
        0.64450162,  0.67886618,  0.77848088,  0.87048614,  1.08061173,
        1.25631194,  1.50380088,  1.60707389,  1.88223662])

col_data2 basically corresponds to what this PR does to the sparse case and it's very different from the above dense case.

In any case, it would be good to have a test ensuring the consistency of the output for the dense and sparse cases (with various max_bins, sparsity levels, and number of unique values)

You are right, I naively thought that the output would be the same but it's definitely not the case.
I added some tests as suggested but concerning the computation, does that mean we just want to densify col_data ?

Now that I think more about this, it might actually make sense to not have an equivalence in the bin frontiers computation between the sparse and the dense case.

If a column has tons of zeros, just computing the percentiles would lead to non-informative bin frontiers as most of them would be zeros (see my updated message above with the actual values).

OTOH if we first remove all zeros we'll have better bins frontiers... but we'd be missing 2 important ones: 0 - eps and 0 + eps.

I know that LightGBM manually forces these 2 bins frontiers to exist (whether the matrix is sparse or not BTW, but that's irrelevant).

Maybe a good strat for the sparse case would be to do almost as you did but:

• compute percentiles on the densified non-zero values without re-inserting a 0, and ask for n - 2 midpoints instead of n
• manually insert 0 - eps and 0 + eps (simple binary search would do here) so we end up with the required n mid points.

The equivlence between sparse and dense case would not hold, but it actually looks more sensible this way. Thoughts @StealthyKamereon @ogrisel @lorentzenchr ?

I agree, this is not very visible on our dummy examples but if we look at the sparsity of the matrix generated for #15336, we can imagine that every useful information will be squeezed up.
What do you suggest for eps ? Something like 1e-7 or bigger ?

np.finfo(X_DTYPE).eps should be what we need here

Then what about transform ?
If we computed the bins ignoring all the implicit zeros, it feels wrong mapping those zeros to the actual_bin_zero 🤔

Hm indeed, transform should definitely not use the same code as for the dense case and indeed zeros should be mapped to bin 0. In this case we might not need to insert the 2 additional bin frontiers, and just let the sparse transorm properly deal with the zeros? I guess the sparse transform code would look like:

if x is an implicit 0:
	map to bin 0
else:
	bin = use same binary search as in dense transform
	map to bin + 1

I don't understand why we need the two bins. 🤷
If I sum up, we want col_data to ignore implicit zeros (do we want explicit one ?) and have the same logic as the dense one from there.
For transform we don't want to map implicit zeros to actual_bin_zero so we get rid of the shifting process.
Maybe we want to shift every bin by one so the implicit zeros don't over-populate the bin 0 ?

I agree we don't need the 2 additional bin frontiers. We should just compute the bin frontiers on all non-zeros values, and then pass these bin frontiers to a sparse transform. The sparse transform would be in charge of mapping the zeros to 0, and map the rest of the values into [1, upper_bound] (where upper_bound is usually 255 (or 254, I don't remember, 255 might be reserved for missing values)). This mapping for the non-zero values can use the same binary search algorithm as for the dense case.

From my experience, using lil_matrix to construct medium size matrices and then converting to a tocsr is not great time wise and memory wise.

If we are building a binned matrix, we know for sure that it will have the same nonzero elements as the input sparse matrix. We can construct a the output by copying over the indptr and indices, and setting the data to be the same shape but with the binned dtype.

We can convert into a csc feeding it into _BinMapper and then build the bins from there.