last day (17 days later) » 

10:13 PM
Hi
Let me know when you are here, also I will remove my second comment from the question. It is advisable to don't fill the comments with an extended discussion, for that are the chats. Thus, I would recommend you to delete your comments too.
 
hello mr. Luis,thanks for helping us
 
No problem :)
 
Hello mr Luis, we are working on a project for university in a Data Mining course
 
and we have no clue what the data actually means for what you are asking,just that we have to identify the "outliers" based on a distance metric
 
The purpose is to find the outliers by calculating the distance of every point from every other point in the dataset
 
10:23 PM
and we are first timers in scala and spark and things are a bit stiff so far :P
 
Ok so, first things first. I would like to understand better your problem in an abstract way of course. I was going to say that for avoid legal issues (thinking it was for work), but now that it is for university it stays abstract as the idea is you to learn! - Am I a teacher so cheats :D
Also, I'm not a native english speaker so excuse me if I made any grammatical mistake of I am too slow writing.
 
we are neither native speakers so no problem !
 
The purpose of the project is to try to identify outliers without using any clustering techniques like k-means
 
Ok, so maybe it is about finding data that is very unusual so you may remove them ?
 
-3
Q: Finding outliers in clustered data without using any clustering algorithm using Spark

thelawI have a txt file that includes data into 5 clusters. Following is a scatter plot that shows what they look like : I want to find the outliers in this dataset but without using any clustering algorithms first (e.g. k-means). Are there any ways that this can be accomplished? I am programming in ...

 
10:25 PM
we don't need to remove them,we just have to identify them and presend them
present^
 
If you want check out this question to better understand
 
Ok, I just read it.
So it is two dimensional data - meaning it only has X and Y axis. Am I correct?
 
Yes sir!
 
And every line of the txt file is just one point?
 
Yeah, there are null entries but we have taken care of them
Every line is essentially a point
 
10:29 PM
Also, are all points (of all clusters) in a single file?
 
Yes
 
Ok, for now I will assume only one cluster.
To simplify things
latter we can talk about how the problem changes with many clusters.
 
We are all ears!
 
So I assume the K-Means you made first was from mllib
And that is why you are using Vectors.dense
 
Yes
 
10:31 PM
But, are you obliged to use it too in this second exercise?
 
No we are not obliged to use it
We can do whatever we want
 
Also, has the code to be general enough to work with any kind of data?, or can you made it specific ?
 
No it only has to work with the points given
x, y points
and we can't use k-means or any clustering algorithm
 
O.k. I love "easy" things :D
 
So we thought of computing the euclidean distance to solve this
 
10:33 PM
Well what I would do, will be
 
or mahanalobis distance,but its harder to implement we think
 
"easy" :P
For us it's very hard :D
 
we are used to working with arrays and flexible data structures,so RDD are too stiff for us so far :P
 
the purpose of the " was to show that :D
Yeah, yeah I know, my first experience with Scala & Spark was a bit fuzzy too. But anyways returning to the main conversation.
1. Read the data as an RDD[(Double, Double)]
And RDD is just like any other linear collection, but immutable (that is the hard part at first) and distributed in many machines. But you can always forget that and think it is just any normal scala List or java.util.LinkedList.
 
yeah,we wanted many times to access specific points,but it seems it's all or nothing with RDDs
 
10:37 PM
For doing so, something like points = data.map(line => line.split(",").map { case Array(x, y) => (x.toDouble, y.toDouble) })
> "yeah,we wanted many times to access specific points,but it seems it's all or nothing with RDDs"

yep, it is how it works in the FP world.
 
FP world?
 
I'm assuming data is an RDD[String] which each entry is a line of the txt file.
 
So mr Luis this maps the data to an array?
 
FP = Functional Programming
Oh no, points is a RDD[(Double, Double)] a tuple. A tuple is a data structure which have two elements which can be of different type, in this case both are Doubles (x, y).
Python and Scala has tuples, they are great for manipulating data.
let me explain that first line better
 
{ case Array(x, y) => (x.toDouble, y.toDouble) }
I don't understand this line mr Luis
 
10:42 PM
Yes, that is called pattern matching, I assumed you already saw that, sorry for that.
What it says is
take the argument and make sure it looks like an Array of two elements
name the first element x and the second y.
Then, we use that x and y in the function body to cast them to Doubles and making a tuple (x, y)
 
And so we end with a points RDD that contains two elements x and y?
 
yes
every element of the RDD is a point
each point has an x and a y
 
I understand
 
you may think the tuple like class
that has and x and y fields
with which programming languages are you comfortable?, maybe Java ?
 
so the RDD in my question was a tuple or a vector?
the one which I used a Vectors.dense
 
10:45 PM
I am very comfortable with Java mr Luis
 
it was a RDD of Vectors
remember that the RDD is a container, a collection.
So the important is what it has on the inside
think of it as a Java array or a Java LinkedList.
So, what I say is. It does not make sense to have an Array of Arrays to store points.
because you now that a point always has two entries X and Y
 
Are vectors in scala like vectors in c++?
Cause in java I don't know vectors
 
A vector in c++ is like (emphasis in like) a java LinkedList
 
Yeah or like an arraylist :D
 
but the Vectors of Spark, because the vectors that you used are from Spark not from Scala are very different.
ArrayList and LinkedList are very different
as far as I remember a C++ vector is a linkedlist
but, I think this only brings more confusion to the matter.
What I really want is that you think about the RDD just as a collection.
of any kind.
 
10:50 PM
We understand
 
The important is to understand that it stores many elements. So when you see RDD[T] the T is the type of the elements inside the RDD.
 
And now we store points in it?
 
points = data.map(line => line.split(",").map { case Array(x, y) => (x.toDouble, y.toDouble) })
 
Remember also, that because RDD are immutable (in really almost anything in scala is immutable), every transformation we perform on they return a new copy, they don't change.
This can also be written like
 
10:53 PM
like filtering into a new RDD etc
 
So the next step is to do the cartesian product with itself?
 
points = data.map(line => line.split(",").map(array => (array(0).toDouble, array(1).toDouble)))
Yes
2. Create the product.
val cartesianProduct: RDD[((Double, Double), (Double, Double))] = points.cartesian(points)
As you can see, the cartesian returns an RDD[(T, U)] of tuples, where the first element of the tuple is an element of the first RDD and the second is from the second.
 
And now starts the hard part mr Luis :D
 
In your case it becomes a tuple of tuples, because each element of the first RDD is a Point (a tuple) and the second RDD is the same, also a Point (also a tuple).
Yes, so to make the things more clear. Let me make sure you have the right mental image of the cartesian.
 
Then we need to find the distance for each cell?
For each cell of the RDD calculate the distance of the two tuples and then store them to a new RDD?
 
10:58 PM
if we have rdd1 = [a, b, c] and rdd2 = [1, 2, 3] then cartesian = rdd1.cartesian(rdd2) = [(a, 1), (a, 2), (a, 3), ..., (c, 2), (c, 3)]
Yes mr thelaw, you are correct
each element is a tuple of two points
and you can compute the distance
but, you also need to have a notion of origin, destination
 
How can this be implemented is the hard part? :D
 
and you need to compute the sum of all distances of each destination.
that is the hard part
the distance is somewhat simple.
 
can we use this for distance Vectors.sqdist?
 
def euclidianDistance(p1: (Double, Double), p2: (Double, Double)): Double = (p1, p2) match { case ((x1, y1), (x2, y2)) => sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2)) }
as I said before, I haven't used mllib so no idea.
But, I would suggest you to try to implement everything and use only things available in vanilla scala / spark.
Your objective is to learn, not to make the best implementation.
 
ok mr. Luis, you are right!
 
11:04 PM
are you two ok with the above implementation of the euclidianDistance ?
I hope it is very clear.
 
Of course it is
 
yes it's very clear
 
Ok, hope you get more familiar with pattern matching it is very useful in Scala / Spark.
now you can make something like
val distances: RDD[Double] = cartesianProduct.map { case (p1, p2) => euclidianDistance(p1, p2) }
You can also put all the implementation of the euclidean distance there, instead of creating a new function.
But, here comes the problem.
 
I think it's better to have a function
 
Now, you have lost the information of the origin (p1)
And now you can't sum all distances for each point.
 
11:08 PM
that's pretty confusing :P
 
(BTW, is euclidean, no euclidian - probably you already noticed it, sorry about that)
 
we are not used to working like this with data structures :P
or collections for that matter
 
Yes yes I know.
 
so distances is now an RDD that contains the distance for every point?
Can't we sum it's rows some way?
 
That is whay is better to first study FP before Spark, but nobody wants to haha
No you can't
Well you can
But that will give you only the summation of all distances.
which is no what you want.
 
11:09 PM
we would study it extensively if we didn't have many other courses :P
 
Yeah, I'm no baling you, but universities in general.
 
Wouldn't each row give us the summation for a single point?
 
remember that each row
 
For example the first row for the first point?
 
is only a pair of points
not all points for first point
was that clear?
 
11:11 PM
I mean each row from the distances RDD
 
each row in distances is just the distance of one pair
look at the type signature
RDD[Double]
That means each cell, row, entry is just one double
Not a collection of doubles.
 
Oh it's not two dimensional
 
ohhh right
so we don't know what's what?
 
Can't we make it two dimensional?
 
11:12 PM
Well you can
but is a bad idea
 
Ok mr Luis
So how do you suggest we solve this problem
 
remember that Spark is intended for gigabytes even terabytes of data
so, how spark work.
An RDD is splitted in many machines
but one machine must have atleast one element.
spark is not able to split elements
that is why is not advisable to have big collections of elements inside an RDD
but simple values instead, so it can be distributed easily.
That is why cartesian return an RDD of tuples instead of an RDD of collections
 
I understand!
 
oh,got it
 
Cartesian could have been implemented to return something like RDD[(T, Array[U])]
ok
 
11:15 PM
So how can we solve our problem now mr Luis?
 
sorry for talking too much haha, I just want to make sure you get what is happening under the hood.
 
No mr Luis you are the best!
 
no problem sir,if we don't waste your time
 
So, because the general idea of your problem is very common (I want to group many values by a key and do computations on the group).
Spark provides an special kind of RDD
a PairRDD
that is intended for Key, Value pairs.
 
So we can pass as key the points and as value the distance in this PairRDD
 
11:18 PM
The great thing about Scala / Spark is that you don't have to cast not create this RDD, if your RDD is of the form (K, V) (note a Tuple again) all those functions become available.
Yes mr thelaw
you get the idea
what a PairRDD is
is that instead of grouping all values with the samin key
it replicates the key, the idea is that there is the same key multiple times
and it provides functions to operate in all values that share the same key
for example reduceByKey
 
For example for all the distances of a single point?
 
Wow this is amazing news!
 
look at the signature an explanation of reduceByKey
and tell me, what would you do given an RDD[(Point, Distance)]
 
Merge the values for each key using an associative and commutative reduce function.
 
11:21 PM
(Point will be a tuple (X, Y) which is a tuple of Doubles and Distance is Double too)
yes
what is that function you want
 
We perform reduceByKey?
 
yes yes
but what you can pass to that reduceByKey
or more precisely what will you pass for your problem.
 
reduceByKey(partitioner: Partitioner, func: (V, V) ⇒ V): RDD[(K, V)]
What is partitioner in the above mr Luis?
 
ham, is how to partition the keys that is to increase performance
 
can we skip it?
 
11:23 PM
don't bother for it yet.
There is a version of reduceByKey that only takes a function
 
def
reduceByKey(func: (V, V) ⇒ V): RDD[(K, V)]
Like this?
 
Yes
So what does it does. It applys the reduce function to each pair of elements that have the same key, until there is only one element per key.
 
We are trying to figure it out :D
 
we use the euclidian function?
as an argument?
so that it calculates distance?
and feed the result to reduce? Or did I say nonsense :P
 
haha nop sorry -1 point in the exam.
jokes aside
as the name says, it reduces values to one
it works like, given 3 values that share the same key
 
11:27 PM
reduceByKey(func: (distance, distance) ⇒ distance): RDD[(point, distance)]
 
it applies the function to the first two to merge them in one, then it applies it to the result of the previous application and to the third one to have only one
 
I'm not sure mr Luis
 
you have the signature ok, you receive two "distances" and return another "distance"
How will you merge this two distances to make it only one.
 
I'm kinda lost because of the abstract way of thinking,can we do a specific example?
 
reduceByKey(func: (distance, distance) ⇒ summedDistance): RDD[(point, fullSummedDistance)]
Like this mr Luis?
 
11:29 PM
yes
you pass the sum function
val distancesPerPoint: RDD[(Point, Distance)] = pairRdd.reduceByKey(_ + _)
 
(_ + _) what is this mr Luis?
 
given that, you can sort that RDD by distance to have which are the farthest points.
it is only an easy way to type
{ case (distace1, distance2) => distance1 + distance2 }
 
Wow this is mindblowing!!!
 
i have no clue how we were supposed to figure this out
 
haha yes, Scala is mindblowing when learning.
 
11:32 PM
when our lecture is just theory and not even scala/spark tutoring
 
yes... that happens sometimes and is the kind of things I against to.
anyways
now you have to figure out how to build the PairRDD
remember that as long as and RDD is of form (K, V) it is a PairRDD.
You don't have to instantiate it.
 
Isn't it already built ?
 
distancesperpoint isn't already?
 
now distancesPerPoint is the result
points
you have
cartesian
 
So it's a tuple of points?
 
11:34 PM
pairRDD - (I didn't showed how to built it)
and distancePerPoints
no, cartesian is a tuple of points
pairRDD is RDD[(Poin, Distance)]
You have to figure that by yourselves.
 
Isn't it the same as distancesPerPoint though?
 
And for each point it contains the summed distance ?
 
no no no wait
it does have the same type as distance per point
but distance per point only has one value per key
whereas pairRDD has many values per key, all distances for a given point
 
And what is that value mr Luis?
I am confused
 
and you build distancesPerPoint by reducing PairRDD by key with sum (+)
 
11:37 PM
So you mean that distanceperPoint isn't summed up?
 
In distancesPerPoint for example our first point in a dataset of 10 points what would the value be?
 
the opposite distancesPerPoint is the summed one
 
So why do we need the new RDD,since we only need to show a Point(tuple) and a Distance?
 
is not new
is the input
 
Oh but mr Luis isn't the distancesPerPoint enough for our problem?
 
11:38 PM
the pipeline goes data -> points -> cartesian -> pair -> distancePerPoint -> sorted
yes
 
so you just want us to sort distancePerPoint?
 
distancePerPoint is the output of your problem (well you can sort it to have the farthest more easily).
Now, I want you to build pair
I didn't showed you two how to build pair - that is the homework ;)
 
Oh we got confused :D
 
Now the other problem is how to do that for every cluster
I mean, the idea is to find which are far to each cluster
 
Yes that's a big problem I think
 
11:41 PM
So for now guys I would say, create a sample dataset with only one cluster
 
If we do it like it's one huge cluster the results would be messed up?
 
yes... because each cluster is far away to each other
so is difficult to find outliners.
 
How could we handle this many clusters?
Where do we begin?
 
so as I was saying, create a sample dataset with one cluster and try to solve it.
Latter think in many datasets, because I'm thinking the best way would be to split it up per cluster.
But that can be latter
for now I have to go.
Feel free to write here again when you had it solved for one cluster
 
Can we do that through Spark someway?
 
11:43 PM
or make a new question in so.
 
Ok mr Luis
You are the best
Gracias :D:D:D
 
Ok mr Luis thank you so much for your time
We would like to ask if we could use standard deviation for clustered data to define outliers,but you can answer it another day.
 
I suppose so, but to be honest I'm not really sure how... because for finding each cluster you may need to do kmean or other clustering technique.
 
Thank you very much for the help !
 
Yes but the professor has forbid us from using it
So maybe he wants us to pretend its one huge cluster
 
11:45 PM
I would ask the professor how does it expect to work with out using clustering
 
Our professor is a little crazy
 
or maybe, doing it with the full dataset will show points which are really too far away to everything
maybe that is what he wants
 
I guess this is what he wants yeah
 
I think so too
 
11:46 PM
or maybe he doesn't care for accurate data,just for practice
 
Otherwise it's too hard
 
Mr Luis are you a teacher?
 
because segregating clusters, without clustering is well... stupid.
I'm planning to be, for now I give extra courses in the university, like Spark and FP :D
 
Well,thank you very much for your patience and your time sir
 
11:47 PM
Oh amazing!
 
anyway, really need to go
See y'all
 
Take care mr Luis!
 
Cya !
 
You are welcome
:D
 

  last day (17 days later) »