In one of my earlier articles, "Filtering Mail with
News::Gateway", (TPJ 5.2) we discussed a relatively simple way to
help manage email, by filtering into mail folders and gatewaying to
private news groups. This article discusses the "next generation" of
mail handling, mail mining, and demonstrates the utility of a
Mail::Miner set up.
The "formal" definition of data mining from the Free Online Dictionary of Computing states that it is "analysis of data in a database using tools which look for trends or anomalies without knowledge of the meaning of the data". However, when we use it in this article, we use it in a much looser sense - data mining is the automated extraction of core pieces of information from a mass of data, and its filing such that querying and retrieval is made relatively easy.
One convenient source of a massive corpus of data suitable for data mining is the mass of email that arrives at our system every day.
Email is a surprisingly interesting data format. It contains a lot of structured, regular data, in the form of mail headers, which is easy for a computer to parse. Unfortunately, the utility of the mail headers is pretty hit and miss. While things like "To" and "Subject" are always going to be important, in the vast majority of cases, many of the headers are almost useless when the message has been delivered, filed and read.
The structure of the body is also relatively easy to parse; there may be binary or textual attachments, which may or may not contain useful data. Finally, there’s usually one reasonably large unstructured part, the textual body of the message.
Just like the mail headers, this is pretty hit and miss too. There could be things that we will want to remember later: phone numbers, dates, place names, addresses, snippets of code, and so on. But interspersed with that, we find line after line of small talk, signature files, flames, and all kinds of other non-information whch is almost useless when the message has been delivered, filed and read.
The idea behind mail mining is to provide a means for separating the wheat from the chaff. I want to be able to find out where and when I’m meeting someone, without much concern for the state of the weather in western Japan one particular Friday afternoon. So our goal, then, is to produce a mechanism for extracting useful information from both the structured and unstructured portions of a mail message, preferably without human intervention, and provide a means for retrieving that information quickly and easily.
To put it in extremely human terms, I want a tool which lets me say "Show me the mail I got around three weeks ago from Nat which was something to do with web services and had an interesting snippet of code in it".
And this is precisely what the
Mail::Miner module does.
Mail::Miner, as its name implies, is a module, rather than a
complete application. To be precise, it’s a collection of modules,
arranged in the following framework:
EDITOR: Insert http://ddtm.simon-cozens.org/~simon/mailminer.png here. I can provide it in alternative formats if needed.
The mail comes in at the top of the diagram, and is converted by your
Mail::Audit filter into a
MIME::Entity, which is handed to
Mail::Miner::Message by whatever your delivery process happens to
be. Right at that moment, an entry is created for the email in a
relational database, storing the from address, subject, and other
useful but trivial metadata. Any attachments are stripped off and
filed separately in the database, associated with the mail message in
question. A notification is added to the body of the email, of the
[ text/x-perl attachment test.pl detached - use mm –detach 821 to recover ]
Notice the format of this text: to retrieve the attachment, I just cut
and paste the middle line onto a shell prompt, and the attachment will
be dumped into the current directory. (If there’s already a test.pl
Mail::Miner command line utility, will prompt
Mail::Miner locates and calls any Mail Miner
Recognisers. We’ll come back to those in a second.
After this point, the mail, with its newly flattened body, can be filed into the database. Once that’s done, the message can leave the Mail Miner system, ready for delivery to the user’s inbox.
Notice that here, even with no cleverness, we have a system for managing attachments, plus a searchable database of old email. However, the real power of Mail Miner comes in its recognisers.
Recognisers are, simply, modules that look for things that may be considered interesting in an incoming message, ("assets") file them away for later, and provide an interface to query for them.
Let’s take a tour of the currently implemented
The first recogniser isn’t really a recogniser at all, but it does
provide a query mechanism - the
Mail::Miner::Message module itself
can be used to query the From address of messages in the
database. Recognisers declare command line options that they can
fulfill, so I can now say
% mm –from ddj.com –summary 26 matched 766:2002-03-29: Kevin Carlson
:Dr. Dobb’s Journal 768:2002-03-29: Kevin Carlson :Re: Dr. Dobb’s Journal 769:2002-03-29: Kevin Carlson :Re: Dr. Dobb’s Journal 770:2002-03-29: Kevin Carlson :Re: Dr. Dobb’s Journal 783:2002-04-03: Kevin Carlson :Re: Dr. Dobb’s Journal 825:2002-04-17: Rosalyn Lum :Dr. Dobb’s Journal …
If I hadn’t specified the summary option,
mm would have returned a
dump of all of the above messages in a Unix mailbox format - this
gives us virtual folders, a la Evolution.
Let’s add some more intelligent recognisers. Now, I’m a firm believer in 80% solutions; most of the time, the effort required to make an algorithm "perfect" isn’t worth it. Edge cases are, well, edge cases, and if you don’t expect the algorithm to get things right, 80% of the time is just fine.
So when I say "intelligent" recognisers, I’m not referring to artificial intelligence; in fact, what the recognisers do is more along the lines of artificial stupidity, leaving the human (who is supposed to have some sort of natural intelligence) to do some elementary top-level filtering. Computers are good at grinding data, so we’ll leave them to do that, and humans are good at top-level filtering, so we’ll leave them to do that.
Think of the recognisers, then, as a production line of trained monkeys. When these monkeys find something interesting or shiny, they file it away in the database, as an "asset". Assets know which mail message they were found in, and which monkey discovered them.
For instance, when a recogniser attempts to discover any phone numbers in a message, it throws up anything that it can find that looks even remotely like a phone number. This naturally produces one or two false positives - although not that many, since most of the long sequences of numbers, parentheses and hyphens found in mail messages turn out to be phone numbers anyway - but that’s Officially OK by the Mail Miner design philosophy. After all, if you can very quickly scan through 500 megabytes of email and produce three candidate phone numbers for someone, two of which are obviously bogus, I’d call that a sufficiently big win.
The phone number recogniser is actually a slightly interesting
example, because using it alters the output format of
mm. Essentially, there are two types of recogniser: those which
help to find particular messages, and those which actually store
"hard" information. The former type of recogniser produces a mailbox
full of messages that match; the latter type of recogniser just dumps
out the "asset" in question.
What does this mean in practice? Well, when you’re asking
phone numbers, it’s more than likely that you don’t want
messages containing phone numbers, but you actually want to get at
the numbers themselves. So, for instance, if I ask
Mail::Miner for Tim
O’Reilly’s phone number:
% mm –from "Tim O’Reilly" –phone Phone numbers found in message 2863 from "Tim O’Reilly"
: (555) 123-4567
(Notice there that I’ve used both the simple "From" query tool and the query tool provided by the phone number recogniser to form an additive filter.)
Of course, if I want to check this out, I can get a copy of the message in question:
% mm –id 2863 From mail-miner-2863@localhost Thu Oct 31 18:58:53 2002 Received: from rock.oreilly.com ([22.214.171.124] helo=smtp.oreilly.com) …
Or just find out what the mail was actually about:
% mm –id 2863 –summary 1 matched 2863:2002-08-31: "Tim O’Reilly"
:Re: Mail::Miner update
And speaking of what mails are about, let’s move on to another recogniser, the keywords recogniser.
One interesting aspect of
Mail::Miner from my point of view is that
it’s sparked the development of a few other neat little modules. The
first was taking note of the fact that, as discussions tend to drift,
Subject: line is now completely irrelevant to a
particular email. How do I find important details about a forthcoming
business trip if they’re hidden in a thread entitled
Return from caller?
To solve this problem, I came up with the amazingly simple
Lingua::EN::Keywords module to extract a set of salient keywords
from a block of text. The keywords recogniser runs this module over a
mail message, files each keyword returned from
as an asset attached to the message, and provides the (synonymous)
–keyword command line query functions.
The other recogniser which is currently implemented is
Mail::Miner::Recogniser::Address; this recognises physical
addresses, by looking for something that looks a bit like a postcode
or US zip code and state, and filing the entire paragraph.
There now follows a technical digression that you may skip if you’re not particularly interested in reading a rant about relational databases.
As we’ve seen above with
–from … –address, queries can be
combined. As an interesting technical point, I wanted each query to be
represented by a single SQL statement for efficiency. How this works
in practice is that we generate
SELECT * FROM messages WHERE and
each recogniser takes its argument, generates a suitable
clause, and all the
WHERE clauses get
SELECT statement returns a set of messages, another
function in each of the recognisers is called to allow them to
post-process and filter out inapplicable messages on a more fine
grained basis than can be achieved with raw SQL alone.
This is an elegant and efficient design.
Unfortunately, most of the interesting recognisers are looking for
messages which contain assets of a particular form. Hence, the
WHERE clause that they return is actually a subselect along the
EXISTS ( SELECT * FROM assets WHERE message = message.id AND recogniser = "me" AND asset LIKE ‘%something%’ )
Of course, the most popular open source relational database does not
support subselects. Hence, for the moment,
Mail::Miner requires the
second most popular open source relational database, PostgreSQL, until
either MySQL gets its act together or I am persuaded that there’s an
equally elegant design that doesn’t use subselects.
In the grand tradition of this sort of article, I shall talk at length about currently unimplemented features as though they were up and running.
The other module sparked by the
Mail::Miner project came out of the
need to express timeframes in a human manner. As well as being a big
fan of 80% solutions, I’m also a big fan of fuzzy input. Fuzzy input
means that the computer, which has an awful lot of processing power
when it comes to precise operations, tries its best to understand the
human, who isn’t all that great at precise operations. This requires
admitting that computer programs are there for the user’s benefit and
not the programmers, but that’s a different story and will be told a
So, given that the whole premise of
Mail::Miner is that I only vaguely
know what I’m looking for, I don’t want to have to specify explicit
dates and times in order to narrow down searches. If I knew the date
and time of the email, I wouldn’t need
Mail::Miner in the first
Instead, I want to be able to say "find me the email I got from Adam
sometime around a week ago". The
Date::PeriodParser module was
written to solve this problem: given a "fuzzy" date expressed in
English, produce a pair of Unix time values which are likely to
bracket the date.
For instance, as I write this on a Thursday night:
% perl -MDate::PeriodParser -le ‘print scalar localtime $_ for parse_period("around the morning of the day before yesterday")’ Mon Oct 28 22:00:00 2002 Tue Oct 29 14:00:00 2002
"Around" the morning of the day before yesterday translates to between
very late on Monday evening to early Tuesday afternoon. Mail Miner’s
–date option will give an interface to this.
So far in our explorations of
Mail::Miner, we’ve seen how it can be
used to extract salient information from the incoming email of a
single user. However, if the system was to be deployed across an
organisation with multiple users, this would require each use to have
their own database.
Or would it? The natural extension to filing information about how you communicate by email is to file information about how an organisation communicates internally and with its clients.
A planned future phase of
Mail::Miner is to have it sit on the main
mail gateway to a company and file every single incoming and outgoing
email. From this simple idea, we can develop a customer relationship
management utility - now you know where your clients live, what they
do, and, more importantly, who’s been speaking to them about what.
The future of
Mail::Miner lies in three distinct developments: the
first is the development of more specific recognisers; the second, in
developing this idea of
Mail::Miner as an organisation-wide tool;
thirdly, the extension of
Mail::Miner from being purely a search
and retrieval tool to being an integrated part of an email client.
In the first category, I intend to work on recognisers that detect and extract place names, dates and times, code snippets, human languages used in an email, and much more.
In the second, I see far more possiblities. Adding a user-defined asset recogniser and asset management tool will allow you to specify more accurately the details that you want to record from an email; combine this with the idea of restructuring the assets system so that it can be applied either to a particular email or a particular recipient, and you have a system which can store the fact that a particular client has expressed an interest in playing golf, or is going on holiday for the next two weeks, or many other things which a computer cannot pick out, no matter how many monkeys are involved.
Similarly, there could be recognisers which attempt to divine the
relationships between correspondents on an email message - if I always
Cc Joe when I email Amy, then
Mail::Miner should take notice of this.
This ties in with the third category, which combines the data
retrieval capabilities of
Mail::Miner with the ordinary email
client. I’ve already intimated that
Mail::Miner can be used to
generate virtual mail folders - imagine if your favourite email client
could search read mail based on language or a vague description of
when you read it! On this front, I expect to work on IMAP proxies
which can use an ordinary mail client to perform
searches, as well as integration with some of the more common Unix
However, for me,
Mail::Miner is and always has been a way to make
sure I never need to remember anything again - now, who do I have to
send this article do? I’m sure I got an email from someone at
ddj.com a week or so ago…