3
$\begingroup$

Say I have a tagging system on an electrical circuit:

Name          Description
-------       --------------
BT104         Battery. Power source
SW104         Circuit switch
LBLB-F104     Fluorescent light bulb
LBLB104       Light bulb
...           ...

I have a hundreds of tags created by people who should have followed my naming conventions but sometimes they make mistakes add unnecessary additional characters to tag names (i.e. BTwq104 etc.).

Up until now I used regular expressions, that I built over time whilst observing various inconsistencies that users introduce whilst naming different parts of their circuits, to parse the names and tell me what the different elements are. For example: name 'BT104' would tell me it's a battery on circuit 104.

I would like to investigate or use a machine learning technique to identify what a tag name is (same way I used regular expressions). Any suggestions and approaches are welcome.

So far I tried Named-entity recognition suggested technique "Bag of words". Followed a few tutorials here and here (latter being the most useful in learning). None of them produced wanted results if any. I think that "Bag of words" are mostly used for real word rather than made up words.

$\endgroup$
  • $\begingroup$ I would train a is-it-made-up classifier using the hashed n-grams. This is something you would run only for unrecognized terms, since much of your content seems to be in English. $\endgroup$ – Emre Mar 20 '18 at 16:59
  • $\begingroup$ @Emre Could you expand your answer a bit on "is-it-made-up classifier" $\endgroup$ – Neil Varnas Mar 21 '18 at 9:27
  • $\begingroup$ I mean train a binary classifier using feature hashing on the character n-grams of the word to be evaluated. $\endgroup$ – Emre Mar 21 '18 at 17:49
  • $\begingroup$ How frequent are the numbers (e.g. the '104' in 'BT104'). In the most simple approach you could just return a count of instances, and if the numbers are frequent, then 'BT104' should occur many times, while 'BTwq104' should occur only once. Not quite the method you are looking for, but maybe useful. BTW you could also use regex to drop the numbers and the just look for 'BT'. $\endgroup$ – Eulenfuchswiesel Aug 2 '18 at 6:31
  • $\begingroup$ Hey, there could be a variant number of numbers, but not more than 10 or so. Ive been using RegEx up till now but for example everytime there is an edge case I need to update the regex and its massive, its not pretty... Hence I thought maybe ML could help me here. $\endgroup$ – Neil Varnas Aug 2 '18 at 12:11
-1
+50
$\begingroup$

You could try a recurrent model to identify the part, such that it reads the strings "letter by letter". I would extract the circuit number and parse that by hand, then feed the textual part into the network. In TensorFlow a basic example could look something like this:

import tensorflow as tf

# Words used by people
TAGS = [
    'BT',
    'SW',
    'LBLB-F',
    'LBLB',
    # ...
]
# "Component id"
LABELS = [
    0,  # 0 => Battery
    1,  # 1 => Circuit switch
    2,  # 2 => Fluroescent light bulb
    3,  # 3 => Light bulb
    # ...
]

# Number of different components
NUM_CLASSES = 4

NUM_LAYERS = 1
LAYER_SIZE = 64
BATCH_SIZE = 100
NUM_EPOCHS = 100

# Inputs must be strings of the same size padded with '\0'
input_tags = tf.placeholder(tf.string, [None], name='Input')
# Convert to ascii values
tag_ascii = tf.decode_raw(input_tags, tf.uint8)
# Get actual lengths
mask = ~tf.equal(tag_ascii, 0)
tag_length = tf.reduce_sum(tf.cast(mask, tf.int32), axis=1)
# Convert to one-hot encoding
tag_1h = tf.one_hot(tag_ascii, 256, dtype=tf.float32)
# RNN
cells = [tf.nn.rnn_cell.BasicLSTMCell(LAYER_SIZE) for _ in range(NUM_LAYERS)]
rnn = tf.nn.rnn_cell.MultiRNNCell(cells)
rnn_output, _ = tf.nn.dynamic_rnn(rnn, tag_1h, sequence_length=tag_length, dtype=tf.float32)
# Get last RNN output
last_rnn_indices = tf.stack([tf.range(tf.shape(rnn_output)[0]), tag_length - 1], axis=-1)
rnn_last_output = tf.gather_nd(rnn_output, last_rnn_indices)
# Output layer
output_weights = tf.get_variable('OutputWeights', (LAYER_SIZE, NUM_CLASSES))
output_logit = rnn_last_output @ output_weights
# Final output as distribution and highest-scoring class
output_dist = tf.nn.softmax(output_logit)
output_class = tf.argmax(output_logit, axis=-1)
# Loss and training
input_labels = tf.placeholder(tf.int32, [None], name='Class')
loss = tf.losses.sparse_softmax_cross_entropy(labels=input_labels, logits=output_logit)
# Choose optimizer and hyperparameters
train_op = tf.train.AdamOptimizer().minimize(loss)
# Variable initialization
init_op = tf.global_variables_initializer()

# Preprocess words so all have the same size
max_tag_len = max(len(tag) for tag in TAGS)
tags_padded = [tag + '\0' * (max_tag_len - len(tag)) for tag in TAGS]

num_examples = len(tags_padded)
with tf.Session() as session:
    session.run(init_op)
    # Train
    for i_epoch in range(NUM_EPOCHS):
        for idx_batch in range(0, num_examples, BATCH_SIZE):
            tags_batch = tags_padded[idx_batch:idx_batch + BATCH_SIZE]
            labels_batch = LABELS[idx_batch:idx_batch + BATCH_SIZE]
            session.run(train_op, feed_dict={input_tags: tags_batch, input_labels: labels_batch})
    # Check results
    predictions, dist = session.run([output_class, rnn_output], feed_dict={input_tags: tags_padded})
    for tag, label, prediction in zip(TAGS, LABELS, predictions):
        print('Tag {} is class {} and was predicted to be class {}.'.format(tag, label, prediction))
    # Test for an unknown tag: 22LBLB-T should be class 3
    tag = '22LBLB-T'
    prediction = session.run(output_class, feed_dict={input_tags: [tag]})[0]
    print('Tag {} was predicted to be class {}.'.format(tag, prediction))

Output:

Tag BT is class 0 and was predicted to be class 0.
Tag SW is class 1 and was predicted to be class 1.
Tag LBLB-F is class 2 and was predicted to be class 2.
Tag LBLB is class 3 and was predicted to be class 3.
Tag 22LBLB-T was predicted to be class 2.

Which basically takes each string, converts it into vectors of numbers, converts these to one-hot encoding and feeds them to a recurrent network (plus an output layer). In this particular case it pads the strings with null characters at the end so all have the same length.

I added a test at the end for an unseen tag 22LBLB-T that should be classified as light bulb. In this case the model failed and said it's a fluorescent light bulb, although to be fair it didn't have many clues to figure out the right answer, given the data (in fact, that tag is in this case more similar to the fluorescent light bulb, since it has a hyphen - you could consider filtering filtering characters like hyphens and others if you think they are going to "confuse" the model). In any case, the prediction by the model "makes sense" with respect to the provided data (it didn't predict it to be a battery or circuit switch, which would not make any sense).

$\endgroup$
  • $\begingroup$ Uhm, some reason for the downvote? $\endgroup$ – jdehesa Aug 2 '18 at 19:19
  • $\begingroup$ not sure who down voted this, but it certainly sounds interesting. Youre absolutely right about the idea of separating numbers and letters, because the numbers dont mean too much its the letters that matter the most which identify the element type. Will try to set up your example, but could you clarify (give an example dataset) the data format that needs to be fed in? $\endgroup$ – Neil Varnas Aug 2 '18 at 19:56
  • $\begingroup$ @NeilVarnas I've extended the snippet to actual runnable code that trains on the four given examples. In principle you just need the tags that people use and the component that they should be assigned to. $\endgroup$ – jdehesa Aug 2 '18 at 21:23
  • $\begingroup$ @jdhesa used your answer and looks liek its working, although there are bits that Im not sure what they do will go through it more thoroughly. Also, just make your answer more complete Id include a skewed term in your data set, like 22LBLB-T, which in theory should be recognised as a light bulb. Thanks for your input, much appreciated. $\endgroup$ – Neil Varnas Aug 8 '18 at 7:15
  • 1
    $\begingroup$ @jdehese sorry, maybe I didnt explain it right. At the moment only the term name is used to determine on what it is, but in the future in addition I would like to supply the description as well (I have the data, just didnt want to complicate the question initially and its good to start simple). So both NAME and DESCRIPTION fields could be used to recognise what the term is. The current output is perfect its just an additional field to help the recognition process. Hope this clears thing, if you read my previous comment again the example should be clearer now. $\endgroup$ – Neil Varnas Aug 10 '18 at 6:05
2
$\begingroup$

You could treat this as a spelling error identification problem. The "Name" column should be a set of unique keys. You can calculate the Levenshtein distance, which finds the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other, between each key. Then set a similarity threshold. Any two keys that are greater than the similarity threshold are merged together.

You can write your own based on Peter Norvig's Spelling Corrector or use Python's FuzzyWuzzy package. The code would be something like this:

from fuzzywuzzy import process

names  = set("BT104 SW104 LBLB-F104 LBLB104".split())
threshold = 85

for name in names:
    leave_current_out = names - {name}
    for match, score in process.extract(name, leave_current_out, limit=1):
        if score >= threshold:
            print(f'Potential misspelling: {name} with {match}')
$\endgroup$
1
$\begingroup$

My suggestion assumes you know the list of correct possible terms beforehand.

Given the list of possible terms:

correct_terms = [
    "BT104",
    "SW104",
    "LBLB-F104",
    "LBLB104",
]

You can define a function to pick the term from correct_names that is the most similar to the term_to_find_a_match_for.

This function splits your terms into characters and compares the effort to transform the term_to_find_a_match_for into one of the terms in the list. It then returns the most similar one. The assumption is that the order of the characters is important to be compared.

from fuzzywuzzy import process, fuzz
import re

def get_correct_term(term_to_find_a_match_for: str, correct_terms: list) -> (str, int):
    """
    Find the most similar entry in correct_terms to term.
    :param term_to_find_a_match_for: The term of interest
    :param correct_terms: The list of possible terms
    :return: The most similar term from the the list and matching score [0,100]
    """

    # Split all terms in sequence of characters
    correct_terms = [re.sub('', ' ', t).strip() for t in correct_terms]
    term_to_find_a_match_for = re.sub('', ' ', term_to_find_a_match_for).strip()

    # Calculate transformation effort based on the character ordered sequence
    matched_term = process.extractOne(term_to_find_a_match_for, correct_terms, scorer=fuzz.token_sort_ratio)
    matched_term_name = re.sub(' ', '', matched_term[0])
    matched_term_score = matched_term[1]

    print("'{}' matched to '{}' with a score of {}.".format(term_to_find_a_match_for, matched_term_name, matched_term_score))

    return matched_term_name, matched_term_score

You can then use the function per term that you have.

term_to_find_a_match_for = 'BTwq104 '
matched_term_name, matched_term_score = get_correct_term(term_to_find_a_match_for, correct_terms)

>> 'BTwq104 ' matched to 'BT104' with a score of 82.
$\endgroup$
  • $\begingroup$ I do know, say a 100, of correct terms but the plan is to run unknown ones that might be a bit skewed or follow a slightly different naming convention. The ones which are recognised say with 70% certainty to add into training model for the future. Will give this a go and come back to, thanks bud. $\endgroup$ – Neil Varnas Aug 4 '18 at 12:53
  • $\begingroup$ @NeilVarnas, I assumed you knew all the possible values because you said that the naming convention was yours... So you knew exactly which ones followed and which ones did not follow your convention. Then the task is to figure out how the wrong names should have been. $\endgroup$ – Bruno Lubascher Aug 4 '18 at 13:01
  • $\begingroup$ The very first sentence in the question : "I have a hundreds of tags created by people who should have followed my naming conventions but sometimes they make mistakes add unnecessary additional characters to tag names (i.e. BTwq104 etc.)." $\endgroup$ – Neil Varnas Aug 8 '18 at 7:12
  • $\begingroup$ @NeilVarnas exactly my point! You created a naming convention. So identifying the true positives should be easy for you. I don't know how your convention, but I guess that a couple of regular expressions should get all the tags that are complying to your convention. Then you would need to be able to figure out what the tags that don't comply to your convention should be. Please correct me if I'm wrong, but you can identify if a tag complies to your convention? $\endgroup$ – Bruno Lubascher Aug 8 '18 at 7:33
  • $\begingroup$ I think you might be missing a point, yes I have created a convention but it doesnt mean that other people will necessarily follow it. It also doesnt make them completely wrong. Of course it would be easier if everyone just followed it but they dont. Hence the "additional characters" in their terms, which might mean something to them but are meaningless to me. Although there are extra characters the term still means something, hence the question. $\endgroup$ – Neil Varnas Aug 8 '18 at 7:58

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.