How to specify important attributes?

Question

Assume a set of loosely structured data (e.g. Web tables/Linked Open Data), composed of many data sources. There is no common schema followed by the data and each source can use synonym attributes to describe the values (e.g. "nationality" vs "bornIn").

My goal is to find some "important" attributes that somehow "define" the entities that they describe. So, when I find the same value for such an attribute, I will know that the two descriptions are most likely about the same entity (e.g. the same person).

For example, the attribute "lastName" is more discriminative than the attribute "nationality".

How could I (statistically) find such attributes that are more important than others?

A naive solution would be to take the average IDF of the values of each attribute and make this the "importance" factor of the attribute. A similar approach would be to count how many distinct values appear for each attribute.

I have seen the term feature, or attribute selection in machine learning, but I don't want to discard the remaining attributes, I just want to put higher weights to the most important ones.

Answer 1

A possible solution is to calculate the information gain associated to each attribute:

$$I_{E}(f) = - \sum \limits_{i = 1}^m f_ilog_2f_i$$

Initially you have the whole dataset, and compute the information gain of each item. The item with the best information gain is the one you should use to partition the dataset (considering the item's values). Then, perform the same computations for each item (but the ones selected), and always choose the one which best describes/differentiates the entries from your dataset.

There are implementations available for such computations. Decision trees usually base their feature selection on the features with best information gain. You may use the resulting tree structure to find these important items.

Answer 2

Actually there are more than one question to answer here:

1. How to work on schemaless/loose/missing data
2. How to label a person (from what I understand unsupervised) and create an identifier
3. How to train your system so that it can tell you which attributes you should use in order to identify the person

As Rubens mentioned, you can use decision tree methods, specifically Random Forests for calculating the most important attributes based on information gain if you have already found a way to identify how to label a person.

However, if you do not have any label information maybe you can use some expert view for preliminary attribute selection. After that you make unsupervised classification in order to retrieve your labels. Lastly, you can select the most important fields using Random Forest or other methods like Bayesian Belief Networks.

In order to achieve all that, you also need complete data set. If your data set is loose you have to manually or heuristically find a way to couple attributes indicating same thing with different names. What is more, you can use imputation techniques such as Expectation Maximization method and complete your data set. Or you can also work with Bayesian Networks and can leave missing fields as they are.

Answer 3

Lots of techniques out there. If your information system has a decision attribute or labels attached, the best way I found is to use rough set based attribute reduction. Check out the quick reduction algorithm by Qiang Shen and Richard Jensen.

If you have unlabeled data, check Principal Component Analysis (PCA).

Answer 4

Just for the sake of it, after almost 5 years, I thought I might share what I actually used in my PhD to solve this problem, which is not new, or a contribution of my PhD, in case it helps someone else.

The measure that we used for selecting important attributes is the harmonic mean (aka F-measure) between support and discriminability.

The support of an attribute p is intuitively how often the entities in our dataset contain values for this attribute:

support(p) = |instances(p)|/ |D|, 

where instances(p) is the set of entities that have a value for p, and |D| is the number of entities in the dataset D.

discriminability(p) = |values(p)| / |instances(p)|, 

where values(p) is the set of (distinct, since it's a set) values that the attribute p can have in our dataset. That's normalized by the number of entities that actually have a value for this attribute.

In other words, support measures the frequency in which p appears in the dataset and discriminability indicates how close to being a "key" this attribute is.

For more details, you can read my dissertation (Section 4.3.2), or you can find a shorter version in our EDBT 2019 paper (Section 2).

Thank you all for your constructive answers!