The “state of TLV” is a widely used phrase in Israel. Ask the average Israeli and he’ll tell you that everyone in TLV are left wing voters and we all eat sushi all day. That, of course, is far from the truth, but gives an opportunity to look at this theory from a more mathematical approach.

While many infographics were made on the different voting trends in Israel (per area, per socio-economic decile, …), I wanted to see whether the best partition of the country to cantons will result in a canton that surrounds Tel Aviv or is it small enough to be absorbed in the “general center of Israel”. In a way, I’m looking on the same problem from the opposite direction - instead of comparing statistics and showing that Tel Aviv is different from the surrounding cities (which is true and easy to observe), I want to find the best clustering of the country and see if Tel Aviv gets its own cluster. If so, I’ll consider it as a strengthening to the argument that the “state of TLV” exists.

One can think of many approaches for this clustering problem. For the purpose of this post I’ll try to cluster the points with a greedy algorithm. Both because it’s easier and in order to have a benchmark for other techniques that will follow later.

Thanks and credits

The last Knesset (parliament) elections were just a week ago and surprisingly a file with detailed data on the ballots and vote counts was published a few hours after the ballots closed (and was updated live for the next few days). Way to go!! The raw data and some statistics are available in the votes20.gov.il website.

The whole idea came from a data-hackathon that was organized by the Data Science Tel Aviv meetup group. While we had some time constraints during the hackaton and only managed to scratch the surface of this problem, I allowed myself to wait for the real results and spend a few weekends on that. Special thanks go to my group members: Ido Hadanny, Shay Tsadok and Hila Kantor for a great Friday morning, to Yair Chuchem for helping me with finding a file with ballots exact addresses and to Yuval Gabay for many ideas along the way.

The data

Generally, data files used in this post can be found in this GitHub repo and the code is shared through this iPython notebook.

As mentioned before, the election results, broken down by ballots, can be downloaded here. The downloaded file had some UTF problems, but after overcoming these, I’ve created a valid tab-delimited file (raw-votes-19.txt). In addition, I’ve added some calculated columns to make work easier.

Geo-location

The Google Geocoding API helped me with the extra mile to the ballots_locations.txt file that has a geo-location (long,lat) for every ballot. Another file with geo-locations for each city in the data file is cities_geo.txt.

Some ballots are “external votes” (votes of people that didn’t vote at their original ballot, mainly because they are soldiers, were on duty on the elections day or have an official position abroad (diplomats)). These are around 3% of the ballots and 5% of the valid votes. For all those, since we can’t have a “real” geo-location, I’ve randomly assigned a location of another ballot so they should be spread all over.

Calculating the “side-score”

For the simplicity of this post, I’ve assigned all parties to a Right/Center/Left group. Every ballot is then given a score between 0.0 to 1.0 that represents it’s location on that axis (0.0 represents left parties, 0.5 is the center and 1.0 goes to right wing parties). The mapping of parties to ‘sides’ is in the parties_mapper.txt file.

This is an obvious misrepresentation of reality. We have around 25 parties in Israel and they can’t all be projected on a single axis. Two parties might share the same opinions on the country’s foreign relations strategy but hold opposite opinions on economical issues. A future post will probably rate all parties on many axes and try to find clusters based on that data. For now, we’ll stay with a single score per point, representing the range between left and right.

Columns

• City name
• City ID
• Ballot ID
• Number of registered voters
• Number of actual votes
• Number of invalid votes
• Number of valid votes
• Number of votes every party got - multiple columns (per party)
• long/lat - the geo-location of the city
• votes_L/votes_C/votes_R - votes count per side
• side_score - an aggregated score (0.0-1.0) per ballot

Visualizing the data

Just for a general orientation, I went with the American color scheme (Republicans=red, Democrats=blue) so the red color represents right wing parties (score close to 1.0) and the blue goes for the left wing parties (score close to 0.0). Score of 0.5 (center parties) are represented with a white circle.

The simplest scatter of the ballots on a map will show us some expected results - Jerusalem and the “Judea and Samaria” villages tend to be significantly right-wings, that also applies for Ashdod and Ashkelon on the coastline and the Shfela area. We can also see clear red areas around Kiriat-Gat, Sderot, Netivot, Ofakim and Beer-Sheva. Not much of a surprise for the Israeli readers. Left wing areas are around the triangle villages, the Galilee and the Bedouin tribes around Beer-Sheva.

A 3D visualization will discover some more interesting observations:

1. The city of Tel Aviv. We can see an indication that supports the initial hypothesis that it behaves differently from its surroundings. The cities on its right are Rishon-Lezion, Rehovot and the whole Shfela area, and they clearly tend to the upper parts of the map while the Tel Aviv “ballots cloud” is pulled down a bit (having its mass around the center and certainly contains blue dots that the other don’t have).

2. Areas of homogeneous votes. Both in the Jerusalem and Judea and Samaria area to the right, and in the desert, the triangle villages and the Galilee to the left (as we’ve seen before).

Defining the problem

If we get out of the ballots and elections world, what we actually have here is a set of points with (long,lat) and a score attached to each one. We are trying to assign each point to a cluster such that:

1. Every cluster is homogeneous (as much as we can) - the average standard deviation of the cluster scores is minimal.
2. Clusters are “geographically close” - we can give some mathematical constraints on that, but I’ll keep it simple and use this as a guideline while designing the greedy algorithm. Other approaches (that will come in future posts), might treat this constraint differently.

Generally speaking, we could define an objective function based on these two measures and approach the whole problem as an optimization problem, looking for the clusters assignment that will minimize the function. I wanted to start with a greedy approach for this post, but going forward, I’ll will probably spend some time on other approaches as well.

The more clusters we break the dataset into, the smaller AVG(STD) we’ll get. Eventually, if every point is in its own cluster, we get AVG(STD)=0. So, in order to agree on some basic rules - I’ll define a valid solution to have at most 8 clusters (rule of thumb, you could run the same experiment with more or less clusters).

Benchmark - A simple KMeans clustering (geographical only)

Before introducing the greedy algorithm let’s measure some statistics on the data and use a simple KMeans clustering on the (long,lat) space to have a benchmark for comparison.

Statistics

avg/std is weighted by the number of votes per ballot

• side_score mean - 0.579
• side_score std - 0.284

KMeans results

I’ve used KMeans with K=8, without adding the side_score as another dimension. I did however test 2 different spaces for the points. One is the regular (long,lat) space, the other is the distance-from-major-cities space where every (long,lat) point is converted into the distance from Tel Aviv, Jerusalem and Haifa. Hopefully that would give more “natural” clusters.

The plot above shows the KMeans results. The background color is the average score in each cluster. From the two options above, I think I like the ‘major-cities-distances’ space more, although I agree the difference isn’t that big. I’ll run the rest of the exercise on both spaces to see if that makes any difference.

While we didn’t take the side_score into account while clustering, we do know that tendency to left/right wing parties is, among other factors, geographically based so we can expect some improvement in the average STD of side_scores in the clusters. The results are:

Our worst STD (without clustering) was 0.284 so even pure geographical clustering seems to help.

The greedy algorithm

For efficiency, I’ve run this part on a 20% random sample of the ballots.

The greedy algorithm will try to cluster the points in an iterative process, where in every step, boundaries between clusters can “migrate” to the adjacent cluster if it’s more similar to their side_score. By migrating, they will obviously affect the average side_score of the cluster, and might cause others to join or leave the cluster in the next round. The whole process stops when it converges (no-one moved) or after a maximum of 75 iterations. We’ll also start with a high number of clusters and then slowly reducing their number, forcing small clusters to join bigger ones.

- Start with a random assignment of K points as clusters centers
- Assign the rest to the closest center
- While we didn't converge (max=75 iters):
	- Identify clusters boundries (explained later)
	- Assign every edge-point to either its current cluster or the one it's
	  adjacent clusters based on the average side_score and the
	  distance from it (explained later)
	- Vanish small clusters, assigning their points to one of the adjacent
	  clusters (explained later)
	- Check if we converged

Identifying cluster boundaries

To identify boundaries between clusters, every point is assigned with the closest point that is in a different cluster. Then, for every ordered pair of clusters, we take the top X points with the minimal distance.

Points migration between clusters

At every iteration, we assign every point to one of its potential clusters. The potential clusters for a point are:

• It’s original cluster (meaning - no migration)
• An adjacent cluster - If the point was one of the boundary points between two clusters

d(P,CLUSTER) is the distance between P to a CLUSTER. It’s defined as the average distance from P to the closest 10% points in CLUSTER. I’ve used this metric rather than distance from the center because I wanted clusters to be more flexible in growing.

SPACE_DIST_TO_KM is the distance in Kms that equals one unit in our space. In Israel, and with (long,lat) space, it’s roughly 102 Km. The distance-from-major-cities space makes this more complicated but I’ll use this as a number of thumb although it won’t be very accurate.
NORMAL_RADIUS is the distance from the cluster for which we’ll compare based on the score difference only. If the point is double that radius, we’ll consider the score difference to be doubled. If it’s half the way, we’ll consider the score difference as half.

Vanishing small clusters

The number of clusters reduces as we iterate. That was inspired by Simulated Annealing. We first choose (randomly) a large number (K_START) of random clusters, let them “stabilize” for a while (INCUBATION_PERIOD) and then start reducing their number to K_END. When we’re done, the algorithm will continue iterating with K_END clusters until it converges (or the max number of iterations is reached).
I’ve chosen a logistic function to get this kind of graph: \[ f(i) = \frac{ \verb|K_START| - \verb|K_END| }{ 1 + e^{0.35(i - \verb|INCUBATION_PERIOD|)} } + \verb|K_END| \]

Notice that since we start with a random assignment of clusters, the final outcome might differ between runs. I’ve found the changes to be relatively minor, but they do exist. Starting with a large number of clusters helps reducing the differences as we are then less prone to a “bad random” at the beginning.

Clustering the ballots

First, you can move the slider below to see the “cluster-formation” process, starting from many random clusters and gradually reducing to 8. The left plot are the ballots themselves (color indicating the side_score). The background is the cluster’s average side_score. On the right plot, for easier orientation, there is a plot with the same clusters but the background goes according to the cluster_id. The cluster_id itself is also annotated on that graph.

Clustering on the (long,lat) space

Final AVG(STD(side_score)) was 0.189