Building machine learning systems with Python, страница 11

That is, let the data describe itself. This is whatwe will do in this chapter, where we consider the challenge of a question and answerwebsite. When a user is browsing our site, perhaps because they were searching forparticular information, the search engine will most likely point them to a specificanswer. If the presented answers are not what they were looking for, the websiteshould present (at least) the related answers so that they can quickly see what otheranswers are available and hopefully stay on our site.The naïve approach will be to simply take the post, calculate its similarity to allother posts and display the top n most similar posts as links on the page. Quickly,this will become very costly. Instead, we need a method that quickly finds all therelated posts.[ 51 ]Clustering – Finding Related PostsWe will achieve this goal in this chapter using clustering.

This is a method ofarranging items so that similar items are in one cluster and dissimilar items are indistinct ones. The tricky thing that we have to tackle first is how to turn text intosomething on which we can calculate similarity. With such a similarity measurement,we will then proceed to investigate how we can leverage that to quickly arrive at acluster that contains similar posts. Once there, we will only have to check out thosedocuments that also belong to that cluster.

To achieve this, we will introduce you tothe marvelous SciKit library, which comes with diverse machine learning methodsthat we will also use in the following chapters.Measuring the relatedness of postsFrom the machine learning point of view, raw text is useless. Only if we manage totransform it into meaningful numbers, can we then feed it into our machine learningalgorithms, such as clustering. This is true for more mundane operations on text suchas similarity measurement.How not to do itOne text similarity measure is the Levenshtein distance, which also goes by the nameEdit Distance.

Let's say we have two words, "machine" and "mchiene". The similaritybetween them can be expressed as the minimum set of edits that are necessary to turnone word into the other. In this case, the edit distance will be 2, as we have to add an"a" after the "m" and delete the first "e". This algorithm is, however, quite costly as it isbound by the length of the first word times the length of the second word.Looking at our posts, we could cheat by treating whole words as characters andperforming the edit distance calculation on the word level. Let's say we have twoposts (let's concentrate on the following title, for simplicity's sake) called "Howto format my hard disk" and "Hard disk format problems", we will need an editdistance of 5 because of removing "how", "to", "format", "my" and then adding"format" and "problems" in the end.

Thus, one could express the difference betweentwo posts as the number of words that have to be added or deleted so that one textmorphs into the other. Although we could speed up the overall approach quite a bit,the time complexity remains the same.But even if it would have been fast enough, there is another problem. In the earlierpost, the word "format" accounts for an edit distance of 2, due to deleting it first, thenadding it.

So, our distance seems to be not robust enough to take word reorderinginto account.[ 52 ]How to do itMore robust than edit distance is the so-called bag of word approach. It totallyignores the order of words and simply uses word counts as their basis. For eachword in the post, its occurrence is counted and noted in a vector.

Not surprisingly,this step is also called vectorization. The vector is typically huge as it contains asmany elements as words occur in the whole dataset. Take, for instance, two exampleposts with the following word counts:WordOccurrences in post 1Occurrences in post 2disk11format11how10hard11my10problems01to10The columns Occurrences in post 1 and Occurrences in post 2 can now be treated assimple vectors. We can simply calculate the Euclidean distance between the vectorsof all posts and take the nearest one (too slow, as we have found out earlier). And assuch, we can use them later as our feature vectors in the clustering steps according tothe following procedure:1.

Extract salient features from each post and store it as a vector per post.2. Then compute clustering on the vectors.3. Determine the cluster for the post in question.4. From this cluster, fetch a handful of posts having a different similarity to thepost in question. This will increase diversity.But there is some more work to be done before we get there. Before we can do thatwork, we need some data to work on.[ 53 ]Clustering – Finding Related PostsPreprocessing – similarity measured as asimilar number of common wordsAs we have seen earlier, the bag of word approach is both fast and robust.

It is,though, not without challenges. Let's dive directly into them.Converting raw text into a bag of wordsWe do not have to write custom code for counting words and representing thosecounts as a vector. SciKit's CountVectorizer method does the job not only efficientlybut also has a very convenient interface. SciKit's functions and classes are importedvia the sklearn package:>>> from sklearn.feature_extraction.text import CountVectorizer>>> vectorizer = CountVectorizer(min_df=1)The min_df parameter determines how CountVectorizer treats seldom words(minimum document frequency). If it is set to an integer, all words occurring lessthan that value will be dropped. If it is a fraction, all words that occur in less thanthat fraction of the overall dataset will be dropped.

The max_df parameter worksin a similar manner. If we print the instance, we see what other parameters SciKitprovides together with their default values:>>> print(vectorizer)CountVectorizer(analyzer='word', binary=False, charset=None,charset_error=None, decode_error='strict',dtype=<class 'numpy.int64'>, encoding='utf-8',input='content',lowercase=True, max_df=1.0, max_features=None, min_df=1,ngram_range=(1, 1), preprocessor=None, stop_words=None,strip_accents=None, token_pattern='(?u)\\b\\w\\w+\\b',tokenizer=None, vocabulary=None)We see that, as expected, the counting is done at word level (analyzer=word) andwords are determined by the regular expression pattern token_pattern.

It will,for example, tokenize "cross-validated" into "cross" and "validated". Let's ignore theother parameters for now and consider the following two example subject lines:>>> content = ["How to format my hard disk", " Hard disk formatproblems "][ 54 ]We can now put this list of subject lines into the fit_transform() function of ourvectorizer, which does all the hard vectorization work.>>> X = vectorizer.fit_transform(content)>>> vectorizer.get_feature_names()[u'disk', u'format', u'hard', u'how', u'my', u'problems', u'to']The vectorizer has detected seven words for which we can fetch the counts individually:>>> print(X.toarray().transpose())[[1 1][1 1][1 1][1 0][1 0][0 1][1 0]]This means that the first sentence contains all the words except "problems", whilethe second contains all but "how", "my", and "to".

In fact, these are exactly the samecolumns as we have seen in the preceding table. From X, we can extract a featurevector that we will use to compare two documents with each other.We will start with a naïve approach first, to point out some preprocessingpeculiarities we have to account for. So let's pick a random post, for which we thencreate the count vector. We will then compare its distance to all the count vectors andfetch the post with the smallest one.Counting wordsLet's play with the toy dataset consisting of the following posts:Post filename01.txtPost content02.txtImaging databases can get huge.03.txtMost imaging databases save images permanently.04.txtImaging databases store images.05.txtImaging databases store images. Imaging databases store images.Imaging databases store images.This is a toy post about machine learning.

Actually, it contains not muchinteresting stuff.[ 55 ]Clustering – Finding Related PostsIn this post dataset, we want to find the most similar post for the short post"imaging databases".Assuming that the posts are located in the directory DIR, we can feedCountVectorizer with it:>>> posts = [open(os.path.join(DIR, f)).read() for f inos.listdir(DIR)]>>> from sklearn.feature_extraction.text import CountVectorizer>>> vectorizer = CountVectorizer(min_df=1)We have to notify the vectorizer about the full dataset so that it knows upfront whatwords are to be expected:>>> X_train = vectorizer.fit_transform(posts)>>> num_samples, num_features = X_train.shape>>> print("#samples: %d, #features: %d" % (num_samples,num_features))#samples: 5, #features: 25Unsurprisingly, we have five posts with a total of 25 different words.