Levenshtein distance and search for controllers

Probably, in every city in Belarus where there are trolleybuses, there are VK groups or chats on Telegram in which people track the location of the controllers. This is mainly done in order not to pay for travel and travel for free, although the description of the groups almost always contains the “Pay for travel” postscript.



In VC, it usually looks like this:







A typical comment looks like this:







The structure is extremely simple. In the commentary there are names of the stop where the controllers were currently noticed, there is also the direction they are standing:







The comment, as a result, is an object with a stop, time and date, as well as a unique id by which we can identify it. With this, you can calculate the most likely location of where the controllers are now.

Training

First you need to determine the target public, from which we will parse the data. The group should have quite a lot of activity in the comments, otherwise we risk getting too little data



In my case, this is the “Control Gomel” group.



We will parse comments using the official VKontakte API for Python



We authenticate with the user's access key, as some groups may be closed, and access to their comments can only be obtained if you were accepted into the group.

After that, you can begin to extract comments:

Receive comments

To get started, we get the last available post in the group to pull out comments through vk.wall.getComments, and initialize the DataFrame, into which we will save the data.



Each commentary post has the inscription “Have a nice day, pay the fare and do not fall under control”, so download the comments, check the contents of the post and get an array of comments from which you can take data.



I took comments from posts over the past 3 months, given that 1 post is posted every day (now the end of November, the school year begins in September, and the supervisors most likely take this into account and change their ordinary places). In principle, other signs can be taken into account, such as, for example, the time of year.



Some comments are clogged with messages like “Is there anyone on Barykin?” If you look at such (unnecessary) comments, you can highlight some signs:

• The text contains the words “clean”, “left”, “nobody” and the like
• The words “tell me”, “who”, “what”, “how”
• Symbols, such as emoticons, for example

After that, we go through an array of comments and pull out a unique id, text, time, date and day of the week from them, which we put in the already created DataFrame.





Thus, we received a DataFrame with the text of comments, their id, day of the week, hour and minute in which the comment was written. We need only the day of the week, the hour of writing and the text. It looks something like this:

Data cleansing

Now we need to clear the data. It is necessary to remove the direction from the commentary in order to make less mistakes when searching for the Levenshtein distance. We find the expressions “to the side”, “go”, “how”, “near”, as they are usually followed by the name of the second stop, and delete them along with what comes after them, as well as replace some jargon names of the stops with the usual ones .

Converting using Levenshtein distance

We directly proceed to the Levenshane distance. A little help: Levenshtein distance - the minimum number of operations to insert one character, delete one character and replace one character with another, necessary to turn one line into another.



We will find it using the fuzzywuzzy library. It helps you quickly and easily calculate the Levenshtein distance. To speed up the work, the authors of the library also recommend installing the python-Levenshtein library.



In order to get stops from comments, we need a list of stops. It was kindly provided to me by the developer of the GoTrans application, Alexander Kozlov.



The list had to be expanded, adding there some stops that were not there, and changing part of the names so that they were better located.





Using .map and fuzzywuzzy.process.extractOne, we find the stop with the minimum Levenshtein distance in the list, after which we replace the comment text with the name of the stop, which allows us to get a dataset with the names of the stops.



The resulting dataset looks something like this:

Data output

Now we can guess where the controllers will most likely be at the given hour.



We are looking in the resulting data records for a specific hour and day of the week. For example, on Tuesday, 9 a.m.:

 <code>data[(data["day_in_week"] == day) & (data["hour"] == hour)]</code>
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

(this is not all data)



After that, we find the number of unique stops, and display only the stops, and their number:

 df[(df["day_in_week"] == 2) & (df["hour"] == 9)]["text"].value_counts()
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Now we can say that at 9 o’clock in the morning, on Tuesdays, the controllers will most likely be spotted at the stops Myasokombinat, ul. Lugovaya, BelGUT, TD “Oma”.



The main flaw in this method is the lack of data. Not for all days and hours there are entries in the comments given during rush hour, when people use public transport more than the data in less popular hours, but if you add data, for example, not only from the comments of one group, but also from alternative groups, or telegram chats, with the number of entries everything will become easier.

Bot with VK LongPoll API

To give the opportunity to receive data on the location of the controllers, depending on the time, and without being tied to a computer, I made a bot for a group on VKontakte that responds to any message by sending the number of stops in the records, given the current hour and day of the week.

Conclusion

The quality of such hypotheses has been tested by me more than once in practice, and everything works fine. It turned out that the controllers, basically, are at the same stops, although absolutely correct forecasts cannot be given, and the probability of success is not 100%. The Levenshtein distance has dozens of different applications, from correcting errors in a word, to comparing genes, chromosomes and proteins, but it also has potential in such applied problems.



Have a nice day, and pay the fare.



All bot code and data manipulations are published here .