Как написать алгоритм группировки, который группирует элементы в наборе данных, имея 3 или более одинаковых свойства - PullRequest
Новая
       11

Как написать алгоритм группировки, который группирует элементы в наборе данных, имея 3 или более одинаковых свойства

0 голосов
/ 03 октября 2019

Я создаю инструмент для своего клиента, который группирует ключевые слова на основе 10 самых популярных поисковых запросов Google. Ключевое слово представлено в виде объекта JavaScript, содержащего массив URL-адресов. Критерием группировки является то, что два ключевых слова принадлежат к одной группе, если они имеют 3 или более общих URL . Кроме того, должно быть без дублирования ключевых слов в сгенерированных группах, и общее количество сгенерированных групп не предопределено перед группировкой. Я был бы признателен за любые советы по логике части этой проблемы, спасибо!

До сих пор мне удавалось разработать алгоритм, представленный ниже, но он все еще делает дубликаты и не группирует ключевое слово 100% справа (некоторые ключевые слова должны быть в той же группе, но это не так). 

function makeKeywordGroupsNew(results: Result[], uid: string): Group[] {
  let dataset = results;
  let groups: any[] = [];

  // loop thru all records in dataset
  dataset.forEach((current: Result) => {
    // initialize the group with the current keyword in it
    const group = { volume: 0, items: [current] };
    // remove the current keyword from the dataset
    dataset = dataset.filter(el => el.keyword !== current.keyword);
    // loop thru the new dataset and push the other keyword into the group if it has >=3 urls in common with current keyword
    dataset.forEach((other: Result) => {
      const urlsInCommon = _.intersection(current.urls, other.urls);
      if (urlsInCommon.length >= 3) {
        group.items.push(other);
      }
    });

    // sum the keyword volumes to form the group volume - not important for the core logic
    // @ts-ignore
    group.volume = _.sum(group.items.map(item => item.volume));
    // sort keywords in the formed group by volume - not important for the core logic
    // @ts-ignore
    group.items = group.items
      .sort((a, b) => {
        if (a.volume < b.volume) return 1;
        if (a.volume > b.volume) return -1;
        return 0;
      })
      .map(el => el.keyword);
    // add the newly formed group to the groups array (the result)
    groups.push(group);
  });

  // exclude the groups with only one keyword inside
  groups = groups.filter(group => group.items.length > 1);
  // delete keyword duplicates inside of the group
  groups = groups.map(group => ({ ...group, items: _.uniq(group.items) }));
  // form the correct result object shape - not important for the core logic
  return groups.map(group => ({
    uid,
    main: group.items[0],
    keywords: group.items.slice(1, group.length),
    volume: group.volume
  }));
}

Я ожидал, что результат input.json будет output.csv , но мое решение либо помещает меньше ключевых слов в группу, либо создает неправильные группы.

Ответы [ 3 ]

1 голос
/ 03 октября 2019

Глядя на результат, я не думаю, что это правильно, потому что это приводит к 135 "группам", и ожидаемое число равно 87, а исходный код выдает 88

Iдумаю, что ваша проблема в самом верху вашего кода 

  let dataset = results;
  let groups: any[] = [];

  dataset.forEach((current: Result) => {
    const group = { volume: 0, items: [current] };
    dataset = dataset.filter(el => el.keyword !== current.keyword);

Вы мутируете dataset внутри функции dataSet.forEach

Я думаю, это должно быть 

  //let dataset = results; remove this
  let groups: any[] = [];

  results.forEach((current: Result) => {
    const group = { volume: 0, items: [current] };
    const dataset = results.filter(el => el.keyword !== current.keyword);
1 голос
/ 03 октября 2019

Это можно упростить в один reduce fn-вызов, чтобы избежать побочных эффектов и путаницы: 

const out = data.reduce((acc, current, index) => {
  const maybeGroup = acc.findIndex(
    el => _.intersection(current.urls, el.urls).length > 3
  );
  if (maybeGroup !== -1 || maybeGroup === 0) {
    if(!acc[maybeGroup].searches.includes(current.keyword)) {
      acc[maybeGroup].searches.push(current.keyword);
      return acc;
    }
    return acc;
  } else {
    acc.push({
      mainKeyword: current.keyword,
      searches: [],
      urls: current.urls
    });
    return acc;
  }
}, []);
console.log(out.map(x => _.pick(x, ['mainKeyword', 'searches'])))

Это, конечно, игнорирует логику подсчета и сортировки, но ее можно легко добавить в существующуюкод.

1 голос
/ 03 октября 2019

Одной из возможных проблем может быть то, как вы фильтруете массив dataset, который проходит через него и фильтруется внутри его собственного цикла. Вы можете отфильтровать dataset и удалить текущее ключевое слово и поместить его в другую переменную, а затем использовать его вместо foreach вместо изменения самого dataset.

...