2
$\begingroup$

I have a data integration problem between two data sources (lets call them A and B), I have applied three functions(for the three attributes of every instance) in order to calculate the similarity between two instances a and b of each data source.

Every function returns a similarity coefficient, a number in R between [0.0, 1.0] describing how similiar are an instance a to an instance b.

Example: For the instance a and b we have three different similarity measures

$Sim_{1}(a,b) = 0.6$

$Sim_{2}(a,b) = 0.3$

$Sim_{3}(a,b) = 0.7$

With this values I can calcule the pertinence score (PS) that is the result of multiply every similarity measure for the weight of every attribute. The formule is like this:

$PS\left(a, b\right) = w_{1} Sim_{1}(a,b) + w_{2} Sim_{2}(a,b) + w_{3} Sim_{3}(a,b)$

An example here can be:

Entity1     Entity2     Sim1    Sim2    Sim3    PS
—---------------------------------------------------------------------—
a           b           0.6     0.3     0.7     w1*0.6 + w2*0.3 + w3*0.7
c           c           0.4     0.8     0.9     w1*0.4 + w2*0.8 + w3*0.9

I have in addition three sets that have the same form from above: the valid correspondences (user validation), invalid (again the user says so) and not yet classified (examples in the wild).

Now, I want to calculate the optimal values for w1, w2 and w3 for maximize the value of PS when the correspondence is valid and at the same time reduce its value when the correspondence is invalid.

So, after that I will use those values of w1,w2 and w3 in the not yet classified set and know if an entity is or is not a valid correspondence.

My big problem here is that I don't know how classified this problem. At first, I thought it was a classification problem(a machine learning one), but I want to have the optimal values for three variables, so I discarded the idea. I think it is maybe an optimisation(maximisation or minimization) problem, but I don't know how to set up the correspondence function for the math model.

have some of you an idea for helping me with this problem? I'm a beginner in this domain.

$\endgroup$
1
+50
$\begingroup$

Yes you can define your problem as an optimization in which you maximise (or minimise) a cost function. You could define your cost function simply as

$$\sum_{i} (valid_{i} == True) * PS_{i} - (valid_{i} == False) * PS_{i}$$

However there are a few problems you have to deal with. First one is that there is very little that you can infer analiticaly about convexity/concavity of your function; there is no way to know how many local minima it will have, etc. In consequence, if you used a variant of gradient descent, which would be quite a straightforward choice, you would probably get stuck in a local minimum.

I would recommend something like simulated annealing, which performs random jumps and may find at the end an approximation of a global maximum for your function. Not really sure which tools you use, nor if there are off-the-shelf libraries for the algorithm; anyway it is fairly easy to program it. In your case, you can deduce your neighbours of the state just choosing randomly one of your 3 weights, and adding or removing a delta to it.

Another problem you will have to deal with is overfitting; you might find a global maximum with your data but then it fails to generalise for unseen data. You could do cross-validation to at least test your performance.

$\endgroup$
3
$\begingroup$

A general version of your problem is indeed a classification problem.

Let us suppose you stop at the 3 similarity measures, and for each entry/line you have the correct class (valid or invalid). In this case you have a standard classification problem where the 3 measures are your input and the valid/invalid class is the output. You can use any classification algorithm to learn how to classify your unlabeled data. You have to read some tutorial on how to select the best algorithm (among the tens to hundreds available) to your particular data (in short using cross validation to split your labeled data into train and test and measure in the test set the accuracy of your predictions).

But you seem to require that the algorithm should be a linear classifier - you seems to want to classify the data only based on the pertinence score formula, which is a linear classifier on the attributes (the three similarity measures).

There are basically three different linear classifiers - logistic regression (as @user43849 suggested), linear discriminant analysis and Linear SVM. If your data is linearly separable, that is indeed all valid cases have some high PS and all invalid cases low PS, than the three algorithms are essentially equivalent (linearly separable problems are easy and all algorithms will find one of the possible solutions to the problem) If your problem is not linearly separable then the three algorithms will result in different solutions (w1, w2, w3).

Which one is the best? One solution is to use the same cross validation mentioned above and test which one is the best. I would suggest this alternative. A second alternative is to try to understand how each algorithm models the problem of separating 2 classes of data - and see which one agrees better with your requirement that "the PS should be as high as possible for the valid cases and as low as possible for the invalid cases". If this statement is a correct description of your requirements, than I think linear SVM are the closest (it will try to find the PS definition that will separate the most the valid and invalid PS). But if the statement is only your way of saying that you want the PS to be a good separator of valid and invalid cases, then I think testing the three algorithms is the way to go.

Since you mentioned R, here are the links for the 3 algorithms implemented in R

$\endgroup$
  • $\begingroup$ really interesting answer but I am curious, as I understand, @amaia is trying to find three appropriated values for the PS equation, in order to have high PS for likely correct matches. when you do any of those algorithms to build the classifier you end with a complete math model to classify the input into match or not match, but you don't get the three appropriated values for w1, w2, w3 for the PS equation, is this correct ? or I am missing something ? $\endgroup$ – carpinchosaurio May 3 '17 at 15:07
  • 1
    $\begingroup$ If the models are linear, then "the complete math model to classify.." are the three constants w1 w2 and w3! $\endgroup$ – Jacques Wainer May 3 '17 at 18:42
1
$\begingroup$

This problem looks a lot like logistic (or probit) regression. The three similarity values are the three independent variables, and the valid/nonvalid classifications are the binary response. You want to estimate coefficients w1, w2, and w3 to get a good prediction. If you have a lot of data, or if the similarity measures are not strongly collinear, then fitting this model could be a good way to choose useful weights.

This model can be fit with just about any statistical software.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.