# Regression with variable containing multiple entries per observation - clustering right approach?

Setting and Data

I would like to run a 2-stage Hurdle regression with various variables describing the funding activity of companies (number of rounds, amount, etc). Some information on the data set:

• 60,000+ rows (i.e. companies)
• 20+ variables (numerical, integer, categorical, binary)

I have the feeling that one key control variable of my regression would be the industry of the company.

Unfortunately such information is not readily available but rather the variable named "company category" that consists of ~850 different category tags (e.g., 3D printing, greentech, fintech, etc). Each company has n assigned category tags that collectively shall describe the type of business they are running (~94% of companies have 5 or less tags - min is 1; max is 48). Unfortunately the category tags are not reported in the order as the author assigned them, but alphabetically.

Exemplary data - alternatively also in long format

   company_name                                             company_category_list
(chr)                                                             (chr)
1     Jurnal.id                                               Accounting|Software
2      Magicpin                                                            Retail
3       MoneyMe                                                Financial Services
4    ScoopWhoop                                                        Publishing
5 Stride Travel Adventure Travel|Online Travel|Reviews and Recommendations|Search


What I am trying to achieve

To be able to include this information in a meaningful way into my regression as a categorical variable I need one element/value per company (i.e. row)

-> Is this assumption true? Or is it actually possible to include a variable with multiple categorical values per observation in a regression without having to create 850 dummy variables (one for each category tag)?

To generate one element per company I thought of identifying industry clusters.

Below is a snapshot of the company/category tag information converted into a binary matrix (rownames are the company IDs). The real matrix only contains ~0.3% of 1s - the rest are 0s (i.e., highly sparse matrix)

  3d 3d printing 3d technology accounting active lifestyle [...]
1  0           0             0          1                0
2  1           0             0          0                0
3  1           1             0          0                0
4  0           0             1          0                0
5  0           0             0          0                1
[...]


I tried so far the following clustering algorithms (based on suggestions in other threads):

• DBSCAN -> seems not applicable as not really suitable for sparse, binary data
• ROCK -> despite running it on a small server (128 GB RAM, 12 cores) R session gets terminated when running rockLink within rockCluster (after computing distances)
• k-modes: did not return any meaningful clusters

What I tried besides clustering

• Reducing the number of category tags by similarity/frequent co-occurance (based on cramer's v), string distance and tf idf. This reduced the number of tags to around 600 -> still way too high

• Treating the category tags collectively per company as a sentence, splitting everything into single words, erasing stop words and reducing then the number of words in the same way as above - wasn't much of an improvement compared to bullet (1)

My questions

• As mentioned above, is clustering actually the way to go or are their other ways to reach my goal of including the category data into my regression?

• If clustering is the way to go, do you have any concrete recommendations which approachs/algorithms I should try considering my input data (binary/categorical, very large)?

• This sort of question was asked several times here, I expect. Did you try first a search of clustering binary sparse? – ttnphns Apr 8 '16 at 7:35
• I did (you can also see "related" questions on the right). However those questions (3-4) where either in a different context, differed on one key dimension (e.g., my matrix is extremely sparse) or didn't provide any helpful solution. – JNWHH Apr 8 '16 at 7:50
• Check additionally stats.stackexchange.com/q/44640/3277, stats.stackexchange.com/q/89535/3277, stats.stackexchange.com/q/105838/3277. If these didn't help you then please say it in your question - why; what makes your problem different or what dissatisfied you in the recipes already given. – ttnphns Apr 8 '16 at 7:58
• Thanks for challenging my question - I reframed my question and included my overall goal since maybe clustering overall is not the right approach – JNWHH Apr 8 '16 at 9:59

I agree that clustering is not the right approach. It does sound like dimension reduction in terms of the sheer number of industries is a goal.

Chances are that many of these industries are so sparse in your data that they could be eliminated based on judgement alone. For instance, based on a minimum threshold of mentions, the most infrequently named industries could be tossed, further reducing the burden of sparsity.

You've indicated that 94% of your companies have five or fewer industries assigned to them. One obvious question is whether or not the industries mentioned for each company are ordinally arranged. By this, I mean that companies will have a distribution of involvement, from high to low, across the industries they are concentrated in. So, going across the industry field, is the first named industry the primary focus of a company's activity? If so, then you could ignore industries 6-48 and create five fields that capture the first five named industries, spanning ~94% of the possibilities.

It looks like the industries do not correspond to any standard industry classification system such as SIC or NAICS but if they can be classified along those lines, that would be another approach to dimension reduction. The beauty of these systems is that, once a code is assigned, then the hierarchical nesting enables a roll up to as few as 15 or so very high level sectors, e.g., Consumer, Retail, Manufacturing, etc.

Another approach would be to use a robust PCA algorithm as discussed in this paper by Xie and Xing (http://www.cs.cmu.edu/~pengtaox/papers/cpca.pdf). They propose a range of techniques for modeling sparse matrices.

Principal Component Analysis (PCA) aims to learn compact and informative representations for data and has wide applications in machine learning, text mining and computer vision. Classical PCA based on a Gaussian noise model is fragile to noise of large magnitude. Laplace noise assumption based PCA methods cannot deal with dense noise effectively. In this paper, we propose Cauchy Principal Component Analysis (Cauchy PCA), a very simple yet effective PCA method which is robust to various types of noise. We utilize Cauchy distribution to model noise and derive Cauchy PCA under the maximum likelihood estimation (MLE) framework with low rank constraint. Our method can robustly estimate the low rank matrix regardless of whether noise is large or small, dense or sparse. We analyze the robustness of Cauchy PCA from a robust statistics view and present an efficient singular value projection optimization method. Experimental results on both simulated data and real applications demonstrate the robustness of Cauchy PCA to various noise patterns.

They have Matlab code available but the core of the algorithm can be readily written up in any software which allows matrix manipulation.

• Thanks for your suggestions. I will explore them in the coming week. I additionally updated my question with more information based on your questions/suggestions. – JNWHH Apr 9 '16 at 15:27

Usually, on such data, you cannot expect clusters in the traditional sense.

The reason is that the data lacks resolution. See, if a company has 1 tag only, you essentially have companies that also have this tag, and companies that don't. But nothing inbetween.

You can run hierarchical clustering or DBSCAN e.g. with Jaccard metric, or cosine. Look at the dendrogram of HAC to see if you csan spot convincing clusters (probably not). If you add the dendrogram to your question, we could help you with that.

k-means etc. suffer from the problem that they attempt to put every object into k clusters. On such data, you will want something that recognizes outliers, and that allows instances to belong to multiple clusters.

Probably a meaningful approach is frequent itemset mining instead. Instead of thinking about where to put every object, this directly searches for typical combinations of features. So you may see that e.g. "3d printing" and "plastics" is a frequent combination.

• Thanks for the answer. r/ frequent itemset mining: I thought about this approach as well, but I am not sure whether this actually helps me achieving my goal. If I find certain association rules I might be able to combine certain tags and by that reducing complexity. However, I am not sure that this actually enables me to arrive at 25-100 "tags" with each company assigned to 1 at most. – JNWHH Apr 10 '16 at 13:58
• Association rules aren't what you need. Frequent items are. But no; this will not give you 1 tag per company (which may not be a good idea anyway! why would every company be only allowed to have 1 tag?) Consider you have the tags "makes_cars" and "makes_trucks". There will be companies that do both, and companies that do only one of them. Reality is, patterns are not disjoint. It may be better to adjust your aims then. – Has QUIT--Anony-Mousse Apr 10 '16 at 14:44
• For sure I would loose some details but grouping companies that have the tags "makes_cars" and "makes_trucks" under a more high-level tag resp. industry such as "automotive" (which may or may not exist) would be fine for me. – JNWHH Apr 11 '16 at 1:35
• The algorithm may decide to ignore that one company belongs to both, too. It definitely won't care that a huma ginds "automotive" reasonable. But it might decide that car makers and airlines are the same, because they buy engines from rolls royce. – Has QUIT--Anony-Mousse Apr 11 '16 at 5:58