Brainstorming

Data Preprocessing

TODO: for each step evaluate an implementation

• Aggregation of attributes:
  Reduce the number of attributes or objects, change of scale, more “stable” data with less variability

• Sampling:

• sampling: for cardinality of the set
• feature selection: for number of attributes, see PCA projection
• discretization: for cardinality of attribute domain

• Dimensionality Reduction
  To avoid curse of dimensionality (when dimensionality increases, data becomes increasingly sparse in the space ) and help to eliminate irrelevant features or reduce noise. Techniques
  – Principle Component Analysis
  – Singular Value Decomposition
  – Others: supervised and non-linear techniques
• Feature subset selection
  To avoid redundant and irrelevant features
• Feature creation Feature Extraction, Mapping Data to New Space, Feature Construction
• Discretization and Binarization
  To split the domain of a continuous attribute in a set of intervals
• Attribute Transformation: Standardization and Normalization

Data quality

Examples of data quality problems:

• Noise and outliers
• Missing values
• Duplicate data Sol: ?

Features type

The type of an attribute depends on which of the following properties it possesses:

• Distinctness: = !=
• Order: <>
• Addition: +-
• Multiplication: */

There are different types of attributes:

• Nominal (distinctness): ID,
• Ordinal (distinctness & order): rankings, grades
• Interval (distinctness, order & addition): calendar dates
• Ratio (distinctness, order, addition, multiplication): counts, size

Similarity

• Interval/Ratio: based on difference: d = |p-q|
• Ordinal: based on difference divided by numbers of intervals
• Nominal: based on distinction p=q ?

Note: Similarity between binary vectors: SimpleMatching (on 0 and 1), Jaccard (only on 1)
In general if vector represents frequency grater than 1 we use cosine similarity

General Approach for Combining Similarities

1. compute for the kth features a similarity sk in range [0,1]
2. define a indicator variable dk as follows:
   • 0 if kth is a binary attribute and both objects have values 0, or it is a missing value
   • 1 otherwise
3. use weights wk which are between 0 and 1 and sum to 1.
   Compute similarity as the sum( w * d * s ) divided by sum (d)

(w,d,s).zipped.map(_*_*_).sum

Algorithm in multiple space

We divide these features into two classes using the following criterion: given two values of the feature, can the average be computed? The size of the message, or any other numeric feature, is a good example of a feature with a computable average. The message ID, or any other string feature encoding some message traits are an example of features in the latter class (i.e. features without a computable "mean").

A time saving observation is that the layout string as well as the MIME part string vary little within the same cluster. Thus the projection of a cluster in the space is concentrated in a small volume around its virtual mean. This observation leads to the fact that we can assess the mean using a small number of examples. This number, p for instance, can be linked to the level of trust T we have in the feature (which can be the score of a feature selection algorithm (Guyon, 2006)). The higher the trust, the smaller the number of elements needed to accurately determine the cluster average p ~ 1/T

For each center c

• Let cn be the projection of the center in the space Sn that of the features with a computable mean. Set cn as the mean of the equivalent features of the examples classified to c
• Choose a number p of mails that are closest to cn in the space Sn. As specified earlier, p can be smaller than the total number of mails assigned to c.
• Determine the Sm projection of c, cm using k-medoids on the p items chosen above.
• The new center of the cluster will be the sum of its projections cn+cm

Element Representation

Numeric Feature Vector

• v1: content length
• v2: num of urls
• v3: attachments size
• v4:

Non numeric Feature Vector

• s1: text content (Can we compute avg on tf/idf vector?)
• s2: layout structure
• s3: embedded URLs
• s4:

s1: Text clustering

A commonly used term weighting method is tf-idf, which assigns a high weight to a term, if it occurs frequently in the document but rarely in the whole document collection. For calculating the tf-idf weight of a term in a particular document, it is necessary to know two things: how often does it occur in the document (term frequency = tf), and in how many documents of the collection does it appear (document frequency = df).

Distance

To avoid the bias caused by different document lengths, a common way to compute the similarity of two documents is using the cosine similarity measure.

TODO

reweighted tf/idf vector according to a spam dictionary

s2: layout structure

We have focused on two ways to characterize an email’s layout. The first uses directly quantifiable properties such as its size, the total number of new lines, blank lines, links, addresses or parts. The set of values can be regarded as a feature vector that represents the email’s position in the n- dimensional feature space Hn So the text structure of the body of a message like: “Hi, read this: \n http://www.a.com \n a@b.com \n\n\n” could be represented by the string "1 1 3 4 0 0 0" – considering 1 – short line, 3 – link, 4- email address, 0 – blank line. The MIME part structure is treated in the same manner, only with different items and indexes