3
$\begingroup$

I have a huge data set (4-5 million entries). The data is indexed by 10 values (v1, v2, ..., v10) = IDENTIFIER.

The Identifier is not unique, there are many repetitions. The indexes are numbers, letters or dates.

Does there exist any tool or algorithm or idea to find some correlations which cover a big-enough span of identifiers?

For instance, just to make sure I explained myself:

╔═══╦════════════╦═════════════╦═════════════╗
║ID ║ V1         ║ V2          ║ V3          ║ 
╠═══╬════════════╬═════════════╬═════════════╣
║ 1 ║ 5          ║ a           ║ string      ║
║ 2 ║ 8          ║ b           ║ string      ║
║ 1 ║ 567        ║ c           ║ string      ║
║ 2 ║ 8          ║ d           ║ string      ║
║ 2 ║ 8          ║ e           ║ string      ║
║ 2 ║ 8          ║ f           ║ string      ║
║ 9 ║ 656        ║ g           ║ string      ║
╚═══╩════════════╩═════════════╩═════════════╝

Given the above, the output I am looking for would be something like: if v1==8 then ID is 2 because there are many IDs which correlate to that, while I wouldn't necessarily care about if firstdigit(v1)==5 then ID is 1 as I have few of them.

EDIT: I am looking for a deterministic output. What I mean is that for the existing set of data (without any new addition) I cannot allow any false positive.

EDIT2: My objective is to speed up lookup of an "ID", given the v's. Right now I basically have a look up table which hashes the v's and gets the corresponding "ID". If I were to cover a portion of my data by some kind of algorithm which wouldn't require any DB/disk/lookup operations, I would optimize my workflow. All my v's are discrete (some are like one of 10 values, or one of 100, or one of 10000, etc). There are relations between them, for instance v1 is a date (only 100 dates are present), while v2 is a type of event (one or more) during that date, etc.

$\endgroup$
  • $\begingroup$ Is it correct to assume that your "ID" is the dependent variable and that $(v_1,...,v_10)$ are the independent variables? Do you know if there is any correlation between your $v_i$ variables? Finally, is "ID" a numerical (discrete or continuous) or categorical variable? $\endgroup$ – user77876 Sep 28 '17 at 18:39
  • $\begingroup$ The "ID" is, in its current form, an MD5 but could easily become a number 1,..,n. Given v1..v10, I get an "ID", not viceversa (not sure if this answer your question). Lastly, yes, there is a little of correlation between the "v's". Like: for vi="x", then vj could be only something or something else. ..hope this helps! Thanks! $\endgroup$ – JoeSlav Sep 28 '17 at 19:37
  • $\begingroup$ If you have one of the V's which is of interest to compare to the 9 other ones, classification or regression is your best bet. If you want to compare all or most of them among each other and if they are mostly categorical, you may look into frequent item set mining. More information about your data and your objective would help us. $\endgroup$ – David Ernst Oct 1 '17 at 9:48
  • $\begingroup$ @DavidErnst: thanks. I've added some info in the question. $\endgroup$ – JoeSlav Oct 1 '17 at 10:03
  • $\begingroup$ Ah that's entirely something else. So the IDs are unique. Does the data-set grow regularly or is it fixed in the number of lines. You will be looking for a search algorithm, perhaps a tree based search that splits on the v variables and quickly narrows down the number of candidate lines. $\endgroup$ – David Ernst Oct 1 '17 at 10:22
3
+100
$\begingroup$
  • Machine Learning algorithms learn from data and make predictions on new unseen data. As your dataset is fixed, the hardest part in supervised learning "to reduce overfitting" does not exist. No need to generalize - it's only about training a model, not testing it.

  • Data Mining focuses more on exploratory data analysis (unsupervised learning), generating association rules (e.g. apriori algorithm) and things like that. Actually I would remove that tag. Your problem definition makes it much easier than that.

Given $\vec{v} = (v_1,...v_{10})$: Find rules that return the right $ID$ for a given feature vector.

I would recommend Tree-based Systems (human readable and easy to train/use).

The first step would be to (fully) grow a Decision Tree on your data. 
Each path, from root node to leaf, translates to one rule:

if (v1 < 12 and v1 > 5 and v2 == 44 and ...):
    then id = 8.

To take False Positives into account, use an impurity measure at each leaf node. You should only consider those rules that lead to leaves that do not have any false positives at all.

E.g if you correctly classify the IDs of 200.000 instances in one leaf, you can extract that rule to optimize your workflow.

About ANNs.. They are much slower (for training and classification) and useless if it is important to you what the model is doing (black box model). So unlike trees, you cannot simply analyze the ANN after it is trained and discover how (and why) it works.

Btw, a decision tree algorithm is basically what you want to code yourself (mentioned in one of your comments). It searches through a hypothesis space, trying to find the simplest rules to classify instances.

$\endgroup$
  • $\begingroup$ Thanks @mlvalidated, do you have any suggestions on which tool to try Tree-based Systems with? thanks! $\endgroup$ – JoeSlav Oct 2 '17 at 11:26
  • $\begingroup$ Id3 decision trees will do. You could go for WEKA (gui) or scikit learn in python. I dunno what youd like to use but pretty sure a basic tree is supported in almost any language. $\endgroup$ – mlvalidated Oct 2 '17 at 12:53
0
$\begingroup$

I have two suggestions for approaches that you might try: Naïve Bayes and Neural Networks.

Naïve Bayes

From Wikipedia, Naïve Bayes classifiers apply Bayes's Theorem to determine the probability that a given instance belongs to each class. In your case, given the feature vector $\vec{v} = (v_1,...v_{10})$ and you want to predict one of $k$ classes $ID$, a Naïve Bayes classifier would compute:

$$P(ID_k | \vec{v}) = \frac{P(ID_k) \times p(\vec{v}|ID_k)}{P(\vec{v})} $$

One limitation to this approach is that it assumes complete independence between the variables (that's the "naïve" part), but in practice you can still get good results if your variables are mostly independent.

Neural Networks

Another approach would be to train a neural network with one neuron per variable $(v_1,...v_{10})$ in the input layer, a certain number of hidden layers and then an output layer that gives you $ID$. You might want to do some data preparation to encode the IDs in an "easy-to-represent" format for the neural network, but a lot of the tuning like that is problem dependent. Depending on how in depth your knowledge is of Neural Networks, Geoff Hinton's series of videos on them are quite illuminating and accessible.

$\endgroup$
  • $\begingroup$ Thanks a lot for your answer. A quick followup: would the output of these two approaches be 100% correct or will they be mostly correct? (probability, etc). Thanks a lot. $\endgroup$ – JoeSlav Sep 29 '17 at 12:45
  • $\begingroup$ @JoeSlav I certainly can't guarantee that any technique will provide you 100% correct answers, but a big part of that will be the data that you have. Are your patterns really easy to spot and really separable with absolutely no "borderline" cases or exceptions? If so, machine learning techniques will be able to do well. The messier your data and more the assumptions of your chosen technique are violated, the lower quality your results will be. It may just be a hard problem, though - is there any reason to believe that you could find a 100% correct answer? $\endgroup$ – user77876 Sep 29 '17 at 16:07
  • $\begingroup$ Got it thank. Having learned a little but more about NN I now understand that my question was more "is the approach deterministic", and I think the answer is no, as there is always a probability associated with it. I am going to try NN! But I'll also start a bounty here for curiosity :) Thanks again! I was also thinking of writing a simple algoritm to run through my data, find most popular ID, see if there is any combination of vs which is unique to them, and iterate. $\endgroup$ – JoeSlav Oct 1 '17 at 8:45
  • $\begingroup$ @JoeSlav I think there is a distinction to be made about what process you are looking to ensure is deterministic. For example, the initial weights for a NN may be randomly selected, but once trained the NN's output will be deterministic. $\endgroup$ – user77876 Oct 2 '17 at 16:16
  • $\begingroup$ Thank you. Yes, I understand. What I mean is: I can't have false positives, i.e. I must arrive at a point where if I bypass actual lookup, i must be certain to get the same result. $\endgroup$ – JoeSlav Oct 2 '17 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.