Interesting! I wonder how it would work on other kinds of data. For example, take a checkerboard image, rotate it (by, say, 15 degrees) and then seriate the result. What will it look like?
Should be easy to try! My expectation is that the TSP approach would recover the original image unless you added a lot of noise to it. Adjacent rows will still end up extremely similar to each other.
My expectation is that it wouldn't, because in a tilted checkerboard image (or any other periodic image) there are many pairs of rows that are more similar than neighbors.
If you truly have unordered table data, and column and row swaps give you a meaningful heatmap data, I suspect the new row and column order probably tell you A LOT. Because before, you just had random labels. Now all of a sudden, your random labels admit a meaningful order. That is a huge deal and suggests underlying structure in your labels!
It's from an introductory course on Algorithms; the dataset is the students' programming assignments, rated for similarity by an off-the-shelf similarity scorer.
This heatmap example is presented in the class on Kruskal's algorithm. We normally think of Kruskal's algorithm as a method for finding a minimum spanning tree, but it can also be thought of as building a classification tree -- which means we can use it for seriation. It's not the best method for seriation by any means, but it's nice just to see it used in this unconventional way.
It's always fun showing this in class, on the coursework that the students submitted just a few weeks ago!
I was a grad student at a major State university. We had a “defensive” grading rubric which caused cheating to be self-defeating. We’d do analyses like this to visualize the cheaters, and try to predict the GPA average of the class (section). Our goal was to speed up or slow down the material to make sure the largest number of students actually learned the core topics of the course and didn’t flunk. (Our worst case scenario was the class of student who’d “get it” at the end of the semester — but too late to pass.)
Is this used in image compression? JPEG, because of the Fourier transform, tends to have waves around edges of flat-colored surfaces. We might have much better compression if we encode images with disordered rows, then leave it up to the decoder to swap them.
No... the ripples you're thinking of are compression artifacts. They aren't present inside large flat-colored areas. Breaking up those flat areas increases detail/entropy/information, from the perspective of a perceptual encoder. So there would be MORE ripples.
This is super cool, so I immediately attempted to try it out.
Unfortunately, the Python package seriate is broken due to an upgrade in its dependency ortools. The update was so long ago a functional version is not available on pypi anymore.
16 comments
[ 2.9 ms ] story [ 49.0 ms ] threadToday's hot topic, TSP solvers.
It's from an introductory course on Algorithms; the dataset is the students' programming assignments, rated for similarity by an off-the-shelf similarity scorer.
This heatmap example is presented in the class on Kruskal's algorithm. We normally think of Kruskal's algorithm as a method for finding a minimum spanning tree, but it can also be thought of as building a classification tree -- which means we can use it for seriation. It's not the best method for seriation by any means, but it's nice just to see it used in this unconventional way.
It's always fun showing this in class, on the coursework that the students submitted just a few weeks ago!
Also compare to DSMs which have the same problem where column and row order can matter a lot to making the diagram clearer: https://web.mit.edu/eppinger/www/SDE-MIT/DSM_Book.html
Unfortunately, the Python package seriate is broken due to an upgrade in its dependency ortools. The update was so long ago a functional version is not available on pypi anymore.
Does anyone have a better way to do this?