Python: Removing similar strings in column

user_11074397 0
Viewed 1209

I have a dataframe, where one column consists of strings:

d = pd.DataFrame({'text': ["hello, this is a test. we want to remove entries, where the text is similar to other texts",
                           "hello, this is a test. we want to remove entries, where the text is similar to other texts because",
                           "where are you going",
                           "i'm going to the zoo to pet the animals",
                           "where are you going jane"]})

Question: Some of these strings can be very similar and only differ in, e.g., one or two words. I want to remove all "duplicates", i.e. remove all articles that are similar to each other. In the above example, since the 1. and 2. row are alike, I want to only keep the first. Likewise, row 3 and 5 are similar and I want to keep only row 3. The actual dataframe has around 100k rows.

My attempt: I figured a good starting point is to convert the strings into sets for easy and efficient comparison:

d["text"].str.split().apply(set)

Next, I'd write a function that compares each row to all the others and removes it if it is at least 90% similar to the others. Here is how I have done it: 

def find_duplicates(df):
    df = df.str.split().apply(set)
    ls_duplicates = []
    for i in range(len(df)):
        doc_i = df.iloc[i]
        for j in range(i+1, len(df)):
            doc_j = df.iloc[j]
            score = len(doc_i.intersection(doc_j)) / len(doc_i)
            if score > 0.9:
                ls_duplicates.append(i)
    return ls_duplicates

find_duplicates(d['text'])

This works for my purposes, but runs very slow. Is there a way to optimize it?

pandas python
2 Answers

Comparing texts is a broad topic, but for choosing best matches from list of strings, You may try:

import difflib

phrases =  ["hello, this is a test. we want to remove entries, where the text is similar to other texts",
      "hello, this is a test. we want to remove entries, where the text is similar to other texts because",
      "where are you going",
      "i'm going to the zoo to pet the animals",
      "where are you going jane"]

difflib.get_close_matches('where are you going', phrases)

Result is sorted by similarity score:

['where are you going', 'where are you going jane']

Method get_close_matches performs fuzzy string matching.

You can also apply function to dataframe:

d['text_similar'] = d.text.apply(lambda row: difflib.get_close_matches(row, list(d[d.text!=row].text), cutoff = 0.8))

Output:

                                                text                                       text_similar
0  hello, this is a test. we want to remove entri...  [hello, this is a test. we want to remove entr...
1  hello, this is a test. we want to remove entri...  [hello, this is a test. we want to remove entr...
2                                where are you going                         [where are you going jane]
3            i'm going to the zoo to pet the animals                                                 []
4                           where are you going jane                              [where are you going]

In above example i'm going to the zoo to pet the animals has no good enough similar string, when cutoff = 0.8.

user_28050830

you can use difflib.SequenceMatcher and filter the text rows based on the percentage similarity( thr) associated with other info

import difflib
# Threshold filter based on Percentage similarity
thr = 0.85
df['Flag'] = 0
for text in df['text'].tolist():
    df['temp'] = [difflib.SequenceMatcher(None, text1,text).ratio() for text1 in df['text'].tolist()]
    df.loc[df['temp'].gt(thr),['Flag']] = df['Flag'].max()+1
df.drop('temp',1)

df.loc[~df['Flag'].duplicated(keep='first')]

Out:

    text                                                 Flag   
0   hello, this is a test. we want to remove entri...   2   
2   where are you going                                 5   
3   i'm going to the zoo to pet the animals             4

Actually this problem has to be treated with Clustering model and Filtering the text information based on the distance nearer to the center.

If you are concern to reduce the time complexity, need to complicate the problem by applying cluster on one-hot encoded vectors of text info.

user_82080060
Related