3
$\begingroup$

I am looking at a number of algorithms in Data Mining and some are described as being greedy. My issue is that they seem to be using the term greedy in different ways, which seems contradictory.

For example, with Hierarchical Clustering the decision to merge clusters is described as greedy. However, a filter attribute selection method where we select a subset of the attributes which possess the highest Information Gain is also described as greedy because it does not cope well with the interaction of attributes.

What does the term greedy mean in terms of Data Mining?

$\endgroup$
3
$\begingroup$

I'm not a Data Mining expert, but from what I understand, it means the same thing as it does outside of data mining: to improving the solution in a locally optimal way, rather than one that is guaranteed globally optimal. (And, as Raphael comments, to not backtrack on that decision).

For example, if you are training a graphical model, the process of repeatedly adding the edge that improves your model's fit the most, until no changes improve the model, is a greedy process. at each stage, you've taken the action which has the most incremental improvement over your current model, but the result may not be globally optimal.

Likewise, in the clustering example, to say that the clusters are merged greedily means that they are merged in the way that provides the best incremental improvement over other merges, but may not lead to the optimal clustering at the end.

$\endgroup$
  • $\begingroup$ So, to make sure I understand, being greedy means to improve in the best immediately possible way without thought for the overall solution? If we apply greedy to a different area, does this mean that best-first search could be classed as greedy? Because we choose the next best move in a graph without thought for the overall problem. $\endgroup$ – Haych May 5 '16 at 22:51
  • 1
    $\begingroup$ Yes, exactly! Greedy and best first are similar (synonymous?) concepts $\endgroup$ – jmite May 5 '16 at 22:56

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.