2
$\begingroup$

I obtain a 'group' of numbers every day. Each number is associated with a 'term'. eg 35 is Big Data. 42 is Hadoop, 82 is Zebra, 89 is Python, 3 is Machine Learning, and 6 is Waterfall, etc. I want a non-supervised Machine Learning way to detect numbers that are usually not part of the group. I will highlight in the following examples groups that should not be in the set:

  1. { 35, 42, 82, 89, 3, 6}
  2. { 35, 42, 89 } [no false number in this group]
  3. { 35, 42, 89 } 4

So in my example, as the sets are usually obtained over time, the numbers 35 (Big Data), 42 (Hadoop), 89 (Python) will be usually together. But 82 (Zebra) and 6 (Waterfall) are unlikely to be usually in a set. Occasionally, they may come as a set. but usually they will not be there. since they are usually not there. i need a way to filter those out.

Some points to note:

a. Sometimes false numbers will not be present

b. Numbers go from 1-30,000, and they represent an 'alpha-numeric term'

c I am okay if the algorithm is not 100% accurate. 75% detection is better than having the false terms always present.

d. I'd prefer a non-supervised learning, but i am willing to compromise this.

e. The repository of sets will grow as 1000's of new sets are added each day.

f. lets say we see the following numbers always together as a set {1,2,3,4,5,6,7,8,9} and as such a density cluster is established. But we also see {6,7,8} appear by themselves frequently a lot too just by themselves. So in that case, if i have a set : {1,6,7,8} I need the algorithm to filter out the {1} since in this case {2,3,4,5,9} is missing in the original set of {1,6,7,8} So its a cluster within a cluster.

My question is: are there existing Machine Learning algorithms out there that can help me achieve this result set with a reasonable level of confidence? If yes, which ones? How does the database/algorithms change as 'new' sets are added that start showing new numbers being added to a group.

$\endgroup$
4
  • $\begingroup$ There are also semi-supervised learning algorithms. Btw, why 82 and 6 does not fit 35, 42, 82, 89, 3, 6 ? What is the meaning of numbers? $\endgroup$
    – Tim
    Jan 30, 2016 at 21:18
  • $\begingroup$ I didn't add the words associated with each number. But basically each number is associated with a 'term'. eg 35 is Big Data. 42 is Hadoop, 82 is Zebra, 89 is Python, 3 is Machine Learning, and 6 is Waterfall. So in my example, as the sets are usually obtained, the numbers 35, 42, 89 will be usually togther. But 82 and 6 are unlikely to be usually in a set. Occasionally, they may come as a set. but usually they will not be there. since they are usually not there. i need a way to filter those out. $\endgroup$
    – LAlearner
    Jan 30, 2016 at 21:44
  • $\begingroup$ But this is very important detail, because this makes many of the methods described by @anantary invalid. For example, if you use k-means than you look for distances between means of clusters and it makes no sense at all to take average of numbers that are labels of words! Please edit your question to add such information since otherwise your question is misleading and you'll receive answers that are totally unrelated to the problem behind your question. $\endgroup$
    – Tim
    Jan 31, 2016 at 8:43
  • 1
    $\begingroup$ Thanks Tim. I added clarity that the numbers actually stand for a 'term'. $\endgroup$
    – LAlearner
    Jan 31, 2016 at 19:47

1 Answer 1

2
$\begingroup$

In your case I would go with hierarchical or density based clustering.

However, this is not a trivial question and you will certainly need to do some heavy thinking with regards to your dataset and which of the methods here portrayed might be definitely appropriate. Please see my comments in the code for some important points about each algorithm.

library(fpc)

# How your data could look like, most true values and some false outliers.
set.seed(1234)
records = 500
mydata <- matrix(ncol=2, nrow=records)
x <- rnorm(n=records, mean=50, sd=5)
y <- rnorm(n=records, mean=50, sd=5)
mydata[,1]<-x
mydata[,2]<-y
mydata[499,]<-c(10,90)
mydata[500,]<-c(90,90)
mydf<-data.frame(x=mydata[,1],y=mydata[,2])
myplot<-ggplot(as.data.frame(mydf),aes(x=x,y=y,xmin=0, xmax=100, ymax=100, ymin=0, colour = x*y ))
myplot + geom_point(pch=19,size=5,)

# Using partitioning based clustering, PAM
# Cons: 
#   - Supervised, K required
#   - Cluster shapes limited to spheres
#   - REALLY sensitive to outliers, less sensitive than K-means
# Pros: 
#   - Pamk can be used to determine a plausible K

mypamk <- pamk(mydf)
plot(mypamk$pamobject)

# Using partitioning based clustering, K-Means
# Cons: 
#   - Supervised, K required
#   - Cluster shapes limited to spheres
#   - REALLY sensitive to outliers

mykmeans <- kmeans(mydf,3)
plot(mydf, col=mykmeans$cluster)

[1]

K-means and PAM didn't do well, we now have a look at hierarchical clustering, DBSCAN and Gaussian Mixture models.

    # Using density based clustering, DBSCAN
# Pros: 
#   - Unsupervised, no K required
#   - Cluster shapes not limited to spheres
#   - Non-cluster-like points are not clustered and hence easily identifiable
# Cons: 
#   - Arbitrary non-convex shapes are likely not desired in your scenario.
#   - DBSCAN requires an index for good performance, R implementation lacks indexing capabilities.

mydbscan <- dbscan(mydf,showplot = 2,eps = 10);
mydbscan$cluster


# Using hierarchical clustering
# Pros:
#   - Pruning point arbitrary
#   - Not sensitive to clusters with varying density
#   - Less sensitive to outliers
# Cons:
#   - K for pruning, can eventually be not needed if other way is found to prune the dendrogram.

myhclust <- hclust(dist(mydf))
plot(myhclust)
cuthclust=rect.hclust(myhclust,k=3)
groups<- cutree(myhclust,k=3)
groups

myplot<-ggplot(as.data.frame(mydf),aes(x=x,y=y,xmin=0, xmax=100, ymax=100, ymin=0, colour = rainbow(3)[groups] ))
myplot + geom_point(pch=19,size=5,)



# Pros:
#   - Probabilistic framework
#   - Flexible, sensitivity to outliers can be overcome by identifying potential noise
# Cons:
#   - Theoretical framework less intuitive
#   - Outliers can become clusters of themselves

library(mclust)
myBIC <- mclustBIC(mydf)
myBIC <- mclustBIC(mydf, G = 1:20, x = myBIC)
myEM <- summary(myBIC, data = mydf)
mclust2Dplot(data = mydf, what = "density", identify = TRUE, parameters = myEM$parameters, z = myEM$z)
myBIC

[2]

Edit, see comments:

A scenario DBSCAN would have problems with:

$\endgroup$
4
  • $\begingroup$ thanks for your response. I read up on all of your methodologies. It seems DBSCAN at this stage is making more sense for me. My question is: how does DBSCAN handle a group-with-in a group. for example, lets say we see the following numbers always together 1,2,3,4,5,6,7,8,9 and as such a density cluster is established. But we also see 6,7,8 appear by themselves frequently a lot too. So in that case, if i have set come out: 1,6,7,8, will the DBSCAN algorithm filter out the 1 since in this case 2,3,4,5,9 are missing? thanks for your help. $\endgroup$
    – LAlearner
    Jan 31, 2016 at 2:26
  • $\begingroup$ DBSCAN is a powerful tool but it has problems with clusters of varying density. I've added such an example scenario to the answer. Furthermore, in the scenario you mention, DBSCAN will filter {1} from {1,6,7,8} but not for the reasons you mentioned. Given a minpts value of 3 and an epsilon of 4, while checking point {1} one will find out that neither does the point have minpts points in its vicinity nor is it within an epsilon distance from {6}, the closest point from to the only cluster found. It will filter {1} because it's not density reachable. $\endgroup$
    – jdsalaro
    Jan 31, 2016 at 10:02
  • $\begingroup$ In case of clusters with varying density OPTICS might be the best option, I do not know, however, of an R implementation of the algorithm. If you want your algorithm to filter events which occur or don't occur together often, that's a different question altogether. That's called frequent pattern matching and there different algorithms which address it. Mark this question as answered if this solved your doubts. $\endgroup$
    – jdsalaro
    Jan 31, 2016 at 10:04
  • $\begingroup$ Thanks @anantary. I think i am 'conveging' towards a solution. I have re-written the original problem statement to provide more clarification from the questions that you and Tim have asked. Do you have any other algorithms in mind given the re-written question? I am looking into the OPTICS algorithm that you mentioned. $\endgroup$
    – LAlearner
    Jan 31, 2016 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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