Brainstorming

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: ?

Feature types

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

Embedded URLs and IP

The spam mails from the same group of spammers often arrive in burst

To find the similarity between two emails, we need to find the similarity of all the associated attributes. However, the email attributes are not exactly like the attributes in scientific papers. For example, the title of a paper always indicates the topic of the paper, while an email subject may say nothing about the email content. In this research, we decided to cluster spam domains instead of emails because we wanted to target the hosting places of spam domains and there were too many near-identical emails sent to different recipients. We developed algorithms to compute the similarity for email subjects and the IP addresses of the URLs.

Derived attributes, those that cannot be directly acquired from emails but can be derived from inherent attributes by looking them up in additional sources, are also important, for example, the WHOIS data from the Domain Name Registrar and fetched web pages of URLs.

We will define the similarity between two IP addresses. Because each domain may correspond to multiple IP addresses and are associated with many email subjects, similarity coefficients will be used to compute similarity between two sets of IP addresses and email subjects

Therefore, the comparison of IP addresses between two domain names becomes a set operation. The Kulczynski coefficient is used to measure the similarity between two IP address sets. The Kulczynski coefficient on sets A and B is defined by: Kulczynski (A, B) = (|A∩B|/|A| + |A∩B|/|B|) / 2, where |A| and |B| are the size of set A and B. It yields a value between 0 and 1. When matching two IP addresses, a little fuzziness is allowed. Two IP addresses can be partially matched if they belong to the same subnet, which is recognized by matching the first three octets. For example, 1.2.3.4 partially matches 1.2.3.5 and a score of 0.5 is assigned.

Kulczynski coefficient

The Kulczynski coefficient accomplishes this but is defined for sets instead of strings. The Kulczynski coefficient on sets A and B is defined by: Kulczynski (A, B) = (|A∩B|/|A| + |A∩B|/|B|) / 2 where |A| and |B| are the size of set A and B, |A∩B| is the size of the intersection. It yields a value between 0 and 1. The Simpson coefficient allows a smaller sub-set match to a bigger set. The Jaccard coefficient favors toward sets with equal sizes. the Kulczynski coefficient, which takes the average of two sets.

Host IP Similarity between two clusters:

An intuitive way to compute the IP similarity is to find common IP addresses from the two clusters and then use a similarity coefficient.

The similarity between two entities depends on how many other attributes are common to both entities. In our case, the similarity between two spam domains is measured based on the similarity of related email subjects and hosting IP addresses. We can calculate the pair-wise similarity between two entities but cannot define a cluster centroid and shape. Therefore, a graph based clustering algorithm is developed to link entities that are similar to each other and extract connected components as clusters.

Graph based clustering algorithm

This research also proposed an algorithm to measure the similarity between two entities, which cannot be represented by vectors. In traditional clustering research, a data point is represented by a vector, containing a series of numerical or binary values. Normal distance functions can calculate the distance between two data points. Statistical data can describe a cluster of data points, such as mean and standard deviation. However, if the data point cannot be represented by a multi-dimensional coordinate, normal distance and statistical functions cannot apply. The similarity between two entities depends on how many other attributes are common to both entities. In our case, the similarity between two spam domains is measured based on the similarity of related email subjects and hosting IP addresses. ** Because the data points have no coordinates, traditional centroid-based, distance- based or density-based clustering algorithms cannot be applied to this kind of problem. We can calculate the pair-wise similarity between two entities but cannot define a cluster centroid and shape. Therefore, a graph based clustering algorithm is developed to link entities that are similar to each other and extract connected components as clusters. A bi-connected component algorithm ensures that there are no weak breakpoints in the clusters. **