cp2025 1.0.0

Depersonalization algorithms for course project 2025

Общее описание

Проект состоит из следующих элементов:

• docs - файлы с документацией
• static - статические файлы
• tests - тесты к классам, реализующм алгоритмы обезличивания
• utility - модули с функциями, использующимися несколькими алгоритмами обезличивания
• класс Depersonalizator и классы с алгоритмами обезличивания расположениы в корневой директории
• классы с алгоритмами обезличивания

Методы оценки качества обезличивания

Методы оценки рисков деобезличивания

• оценка максимального k, при котором выполняется k-анонимность
• оценка максимального l, при котором выполняется l-разнообразие
• оценка минимального t, при котором выполняется t-близость
• adversarial knowledge gain, описанный в пункте 4.4 статьи https://desfontain.es/PDFs/PhD/TheCostOfPrivacyDestructionOfDataMiningUtilityInAnonymizedDataPublishing.pdf
• adversarial accuracy gain, описанный в пункте 4.4 статьи https://desfontain.es/PDFs/PhD/TheCostOfPrivacyDestructionOfDataMiningUtilityInAnonymizedDataPublishing.pdf
• оценка accuracy деобезличивания при помощи градиентного бустинга

Методы оценки полезности обезличенных данных

• решение задач классификации и регрессии при помощи градиентного бустинга на изначальном и обезличенном датасетах и сравнение качества работы моделей
• средний размер класса эквивалентности
• отношение количества уникальных записей к общему числу записей (distinctness)
• доля изменившихся отдельных значений в датасете
• неоднородная энтропия (non-uniform entropy)
• потеря информации на основе энтропии (entropy-based information loss)
• оценка расстояния между исходными и получившимися данными поэлементно (my_by_element_distance)

Оценка расстояния между исходными и получившимися данными поэлементно (my_by_element_distance)

• представляет собой среднее поэлементных расстояний
• поэлементное расстояние вычисляется по следующим принципам
  • вычисляется для пары элементов
  • лежит на отрезке от 0 до 1
  • если один элемент - nan, а другой нет, равно 1
  • если оба nan - 0
  • если столбец имеет тип числовых значений
    • обозначим m - минимальное значение в столбце, M - максимальное
    • обозначим первый элемент a, если он - значение и [a1, a2], если это дипапазон
    • аналогично b и [b1, b2] - для второго
    • если оба элемента значения, то расстояние вычисляется по формуле abs(a-b)/(M-m)
    • если один элемент - диапазон (пусть второй), то ((a-b1)^2+(a-b2)^2) / (2 * (M-m) * (b2 - b1))
  • если столбец имеет тип порядковых значений
    • r(x) - функцию получения ранга элемента в столбце, n - количество элементов в столбце
    • обозначим первый элемент за a, если он - значение и за [a1, a2], если это дипапазон
    • аналогично b и [b1, b2] - для второго
    • если оба элемента значения, то расстояние вычисляется по формуле abs(r(a)-r(b))/(n-1)
    • если один элемент - диапазон (пусть второй), то ((r(a)-r(b1))^2+(r(a)-r(b2))^2) / (2 * (M-m) * (r(b2) - r(b1)))
  • если столбец имеет номинальный тип, то
    • обозначим |X| мощность множества X
    • обозначим \in отношение включения
    • обозначим \union оператор объединения
    • обозначим \intersection оператор пересечения
    • обозначим первый элемент за a, а второй - за b (могут быть элементами или множествами возможных элементов)
    • если оба элемента значения, то расстояние вычисляется по формуле int(a!=b)
    • если один элемент - множество (пусть второй), то int(a /in b) / |b|
    • если оба - множества, то |a \intersection b| / |a \union b|, то есть IOU

Интерфейс классов обезличивания:

• параметры алгоритмов задаются в конструкторах классов
• для обезличивания датасета необходимо передать его методу depersanolize
• для того чтобы указать колонки-идентификаторы, необходимо передать в параметр identifiers_ids списток индексов этих колонок
• для того чтобы указать колонки-квазиидентификаторы, необходимо передать в параметр quasi_identifiers_ids списток индексов этих колонок
• для того чтобы указать колонки с чувствительной информацией, необходимо передать в параметр sensitives_ids списток индексов этих колонок
• для того чтобы указать, что все оставшиеся колонки относятся к данному типу, необходимо передать в соответствующий параметр значение 'left'
• по умолчанию quasi_identifiers_ids = 'left'
• только один из данных параметров может иметь значение 'left'

Класс Depersonalizator:

• от данного класса наследуются все классы с алгоритмами обезличивания
• данный класс преобразует данные из входного формата, описанного выше, в формат, удобный для обработки (разбивает на идентификаторы, квазиидентификаторы и чувствительную информацию), а также преобразует выходные данные алгоритмов в единый датасет

В проекте представлены следующие классы с алгоритмы (классы) обезличивания:

• AggregationKAnonymityTimeOptimal - агрегация с разбиением на группы с взятием k-1 ближайших к данной строке с использованием описанного ниже расстояния между элементами
• AggregationLDiversityTimeOptimal - алгоритм аналогичен AggregationKAnonymityTimeOptimal, но строки отбираются до тех пор, пока датасет не станет k-анонимным и l-разнообразным
• Datafly - реализация алгоритма Datafly (https://www.cerias.purdue.edu/assets/pdf/bibtex_archive/2005-134.pdf) с автоматически создаваемым VGH
• DistributedDataKAnonymityDepersonalization - алгоритм обмена данными между двумя владельцами с соблюдением k-анонимности, представленный в статье https://www.cerias.purdue.edu/assets/pdf/bibtex_archive/2005-134.pdf, но вместо DataFly используется groupjoin (см. ниже)
• GeneralizationGreedyByOneEqualSizedGroups - обобщение, при котором каждый столбец делится на группы с одинаковым для каждого столбца минимальным количеством элементов в столбце
• GeneralizationKAnonymityTimeOptimal - обобщение с разбиением на группы с взятием k-1 ближайших к данной строке с использованием описанного ниже расстояния между элементами
• GeneralizationLDiversityTimeOptimal - алгоритм аналогичен GeneralizationKAnonymityTimeOptimal, но строки отбираются до тех пор, пока датасет не станет k-анонимным и l-разнообразным
• GroupJoin - алгоритм объединения групп строк, функция потерь для которых изменяется меньше всего, объединение происходит, пока не будет достигнута необходимая метрика (k-анонимность, l-разнообразие, t-близость)
• TestIdentifierHasher - алгоритм хеширования идентификаторов
• RandomizationDepersonalizator - добавляет к каждому значению случайную величину с распределением, задаваемым относительно исходных данных
• Shuffler - переставляет строки в заданных столбцах
• ShufflerInBatches - переставляет строки в каждой группе отдельно в заданных столбцах
• SuppressionKAnonymityBaseline - перебирает все варианты подавления значений в датасете, в поиске варианта, достигающего k-анонимности с наименьшим количеством подавлений
• SuppressionLDiversityBaseline - алгоритм, аналогичный SuppressionKAnonymityBaseline, но достигается l-разнообразие
• SuppressionKAnonimityTimeOptimal - алгоритм, аналогичный GeneralizationKAnonymityTimeOptimal, но используется расстояние Хэмминга и подавление
• SuppressionLDiversityTimeOptimal - алгоритм, аналогичный GeneralizationLDiversityTimeOptimal, но используется расстояние Хэмминга и подавление
• SuppressionTClosenessBaseline - алгоритм, аналогичный SuppressionKAnonymityBaseline, но достигается t-близость

Типы столбцов:

• real - количественные данные
• ordered - порядковые данные
• unordered - номинальные данные

Класс GeneralizationRange:

• класс хранит обобщение нескольких номинальных значений или отрезок порядковых или количественных значений
• для порядковых или количественных значений хранятся минимум и максимум отрезка
• для номинальных - список уникальных значений
• класс поддерживает сравнение на равенство, а для порядковых или количественных значений - отношение порядка
• предполагается, что отношение порядка применяется только к непересекающимся отрезкам, иначе - неопределённое поведение

Описание алгоритмов обезличивания

AggregationKAnonymityTimeOptimal

Краткое описание алгоритма

Агрегация с разбиением на группы с взятием k-1 ближайших к данной строке с использованием описанного ниже расстояния между элементами

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• quasi_identifiers_types - тип каждого столбца (массив размера равного количеству квазиидентификаторов со значениями 'real', 'ordered', 'unordered'); по умолчанию значения считаются номинальными

Результат работы алгоритма

• K-анонимный датасет
• количество значений-квазиидентификаторов K-анонимного датасета, отличных от соответствующих значений изначального датасета

Принцип работы алгоритма

• все идентификаторы подавляются
• все действия далее проводятся над квазиидентификаторами
• если размер датасета меньше k, но не 0 возвращается None, то есть невозможность провести k-анонимизацию
• прозводится расчёт расстояния для всех пар строк по следующему принципу:
  • расстояние между строками представляет собой сумму расстояний между соответствующими элементами
  • расстояние между двумя значениями лежит на отрезке от 0 до 1
  • расстояние между двумя номинальными значениями равно 0, если они равны, и 1 иначе
  • расстояние между двумя порядковыми значениями равно модулю разности их рангов среди всех элементов столбца, делённому на количество строк
  • расстояние между двумя вещественными значениями равно 0, если они равны, или модулю их разности, делённому на разность максимального и минимального значений, в ином случае
• затем производится группировка значений по следующему принципу
  • берётся первая по списку не отнесённая ни к какой группе строка
  • она группируется с k-1 самыми близкими к ней несгруппированными строками
  • эти действия повторяются пока не останется менее k строк
  • оставшиеся строки присоединяются к последней группе
• для каждого столбца в каждой группе считается агрегированное значение
  • для столбцов с номинальными значениями - мода
  • для столбцов с порядковыми значениями - медиана
  • для столбцов с числовыми значениями - среднее
• из агрегированных значений составляются агрегированные строки
• каждая строка группы заменяется на агрегированную строку

AggregationLDiversityTimeOptimal

Краткое описание алгоритма

Алгоритм аналогичен AggregationKAnonymityTimeOptimal, но строки отбираются до тех пор, пока датасет не станет k-анонимным и l-разнообразным

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• l - параметр l-разнообразия (целое число больше либо равное 1)
• quasi_identifiers_types - тип каждого столбца (массив размера равного количеству квазиидентификаторов со значениями 'real', 'ordered', 'unordered'); по умолчанию значения считаются номинальными

Результат работы алгоритма

• L-разнообразный датасет
• количество значений-квазиидентификаторов K-анонимного датасета, отличных от соответствующих значений изначального датасета

Принцип работы алгоритма

• все идентификаторы подавляются
• все действия далее проводятся над квазиидентификаторами
• если размер датасета меньше k, но не 0 возвращается None, то есть невозможность провести k-анонимизацию
• прозводится расчёт расстояния для всех пар строк по следующему принципу:
  • расстояние между строками представляет собой сумму расстояний между соответствующими элементами
  • расстояние между двумя значениями лежит на отрезке от 0 до 1
  • расстояние между двумя номинальными значениями равно 0, если они равны, и 1 иначе
  • расстояние между двумя порядковыми значениями равно модулю разности их рангов среди всех элементов столбца, делённому на количество строк
  • расстояние между двумя вещественными значениями равно 0, если они равны, или модулю их разности, делённому на разность максимального и минимального значений, в ином случае
• затем производится группировка значений по следующему принципу
  • берётся первая по списку не отнесённая ни к какой группе строка
  • она группируется с необходимым количеством самых близких к ней несгруппированных строк для того, чтобы группа стала содержать хотя бы k строк и для каждого чувствительного столбца - l различных значений
  • эти действия повторяются пока не останется менее k строк
  • оставшиеся строки присоединяются к последней группе
• для каждого столбца в каждой группе считается агрегированное значение
  • для столбцов с номинальными значениями - мода
  • для столбцов с порядковыми значениями - медиана
  • для столбцов с числовыми значениями - среднее
• из агрегированных значений составляются агрегированные строки
• каждая строка группы заменяется на агрегированную строку

Datafly

Краткое описание алгоритма

Реализация алгоритма Datafly (https://www.cerias.purdue.edu/assets/pdf/bibtex_archive/2005-134.pdf) с автоматически создаваемым VGH

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• quasi_identifiers_types - тип каждого столбца (массив размера равного количеству квазиидентификаторов со значениями 'real', 'ordered', 'unordered'); по умолчанию значения считаются номинальными
• k_suppressed_lines - максимальное количество строк, которые можно подавить (в Datafly, описанном в статье = k-1), по умолчанию = k-1

Результат работы алгоритма

• K-анонимный датасет
• количество значений-квазиидентификаторов K-анонимного датасета, отличных от соответствующих значений изначального датасета

Принцип работы алгоритма

• все идентификаторы подавляются
• все действия далее проводятся над квазиидентификаторами
• если размер датасета меньше k, но не 0 возвращается None, то есть невозможность провести k-анонимизацию
• выбирается столбец с наибольшим количеством различных значений
• для этого столбца производится обобщение по следующим принципам
  • если значения столбца номинальные, то 2 наиболее редких значения объединяются в одно при помощи класса GeneralizationRange
  • если значения столбца порядковые или числовые, то наиболее редкое значение объединяется с наиболее редким из соседних с ним по порядку при помощи класса GeneralizationRange
• данные действия повторяются до тех пор, пока число строк, которые не относятся ни к одной группе из равных строк из хотя бы k элементов, не станет меньше k_suppressed_lines
• оставшиеся строки подавляются

DistributedDataKAnonymityDepersonalization

Краткое описание алгоритма

Алгоритм обмена данными между двумя владельцами с соблюдением k-анонимности, представленный в статье https://www.cerias.purdue.edu/assets/pdf/bibtex_archive/2005-134.pdf, но вместо DataFly используется groupjoin (см. ниже)

Параметры алгоритма

• Алгоритм не наследуется от Depersonalizer
• Алгоритм запускается методом exchange_data
• Для запуска алгоритма необходимо создать 2 объекта класса DistributedDataOwnerKAnonymityDepersonalizator, представляющие собой двух владельцев данных, и сообщить им друг о друге при помощи метода set_other_data_owner
• Конструктор класса имеет следующие параметры:
  • quasi_identifiers - квадиидентификаторы данного владельца (матрица numpy)
  • sensitives - чувствительные столбы этого владельца (матрица numpy)
  • k - параметр k-анонимности
  • encryption_key - секретный и отдельный для каждого ключ шифрования
  • quasi_identifiers_types - тип каждого столбца матрицы квазиидентификаторов (массив размера равного количеству квазиидентификаторов со значениями 'real', 'ordered', 'unordered'); по умолчанию значения считаются номинальными
  • seed - сид генератора случайных чисел (по умолчанию не задаётся)

Результат работы алгоритма

Объединённый массив, из которого каждый из владельцев может узнать не больше, чем позволяет k-анонимность. Порядок объединения следующий:

• квадиидентификаторы первого (того, у кого запускается метод exchange_data)
• чувствительные значения первого
• квадиидентификаторы второго
• чувствительные значения второго

Содержится в атрибуте joined_data каждого владельца

Принцип работы алгоритма

• изначально данные обезличиваются локально (у каждого владельца отдельно до k-анонимности)
• вычисляются параметры шифрования (публичный ключ - точка на эллиптической кривой)
• каждый вычисляет статистики датасетов для удобства обезличивания при помощи groupjoin
• обмен информацией о группах, на которые производится обезличивание, осуществляется следующим образом:
  • все индексы групп шифруются алгоритмом передающего владельца
  • зашифрованные индексы групп ещё раз шифруются алгоритмом принимающего владельца
  • в результате, если индексы равны, их итоговое представление у обоих владельцев будет одинаковым, так как используется коммутативное шифрование на эллиптических кривых
• на каждом шаге (цикл):
  • производится обмен информацией о группах
  • производится проверка на "равенство" по следующему принципу: если у первого и у второго существует хотя бы по одной группе, мощность пересечения которых не равна нулю, но меньше k, то разбиения на группы не равны, иначе - равны
  • если равны - завершение цикла
  • если нет - обезличивание на 1 шаг при помощи groupjoin (см. ниже)
• как только разбиения равны, можно производить обмен обезличенными датасетами, что соответственно и происходит, и объединённый датасет становится значением атрибута joined_data каждого владельца

GeneralizationGreedyByOneEqualSizedGroups

Краткое описание алгоритма

Обобщение, при котором каждый столбец делится на группы с одинаковым для каждого столбца минимальным количеством элементов в столбце

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• quasi_identifiers_types - тип каждого столбца (массив размера равного количеству квазиидентификаторов со значениями 'real', 'ordered', 'unordered'); по умолчанию значения считаются номинальными

Результат работы алгоритма

• K-анонимный датасет
• минимальный размер группы (смотри принцип работы алгоритма)

Принцип работы алгоритма

• все идентификаторы подавляются
• все действия далее проводятся над квазиидентификаторами
• если размер датасета меньше k, но не 0 возвращается None, то есть невозможность провести k-анонимизацию
• производится перебор минимального размера группы (group_size) от k до размера датасета
• group_size одинаково для каждого столбца
• для каждого размера группы строится обобщённый датасет:
  • для количественных и порядковых столбцов от начала отсортированного столбца берутся по group_size значений
  • для номинальных столбцов в случайном порядке набираются уникальные значения, пока общее количество взятых элементов столбца не достигнет k
  • если после данных k значений идут значения равные последнему взятому значению, они тоже берутся в группу
  • в случае, если в конце остаётся менее k значений, они добавляются в последней сформированной группе
• перебор останавливается, как только обобщённый датасет стал анонимным
• анонимность всегда достижима, так как при group_size, равном размеру датасета, он будет k-анонимным
• бинарный поиск не используется, так как не гарантировано, что для всех group_size больших подходящего group_size обобщённый датасет k-анонимен

GeneralizationKAnonymityTimeOptimal

Краткое описание алгоритма

Обобщение с разбиением на группы с взятием k-1 ближайших к данной строке с использованием описанного ниже расстояния между элементами

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• quasi_identifiers_types - тип каждого столбца (массив размера равного количеству квазиидентификаторов со значениями 'real', 'ordered', 'unordered'); по умолчанию значения считаются номинальными

Результат работы алгоритма

• K-анонимный датасет
• число обобщений

Принцип работы алгоритма

• все идентификаторы подавляются
• все действия далее проводятся над квазиидентификаторами
• если размер датасета меньше k, но не 0 возвращается None, то есть невозможность провести k-анонимизацию
• прозводится расчёт расстояния для всех пар строк по следующему принципу:
  • расстояние между строками представляет собой сумму расстояний между соответствующими элементами
  • расстояние между двумя значениями лежит на отрезке от 0 до 1
  • расстояние между двумя номинальными значениями равно 0, если они равны, и 1 иначе
  • расстояние между двумя порядковыми значениями равно модулю разности их рангов среди всех элементов столбца, делённому на количество строк
  • расстояние между двумя вещественными значениями равно 0, если они равны, или модулю их разности, делённому на разность максимального и минимального значений, в ином случае
• затем производится группировка значений по следующему принципу
  • берётся первая по списку не отнесённая ни к какой группе строка
  • она группируется с k-1 самыми близкими к ней несгруппированными строками
  • эти действия повторяются пока не останется менее k строк
  • оставшиеся строки присоединяются к последней группе
• для каждого столбца в каждой группе считается обобщённые значения объединением всех значений столбца в группе при помощи класса GeneralizationRange
• из обобщённых значений составляются обобщённые строки
• каждая строка группы заменяется на обобщённую строку

GeneralizationLDiversityTimeOptimal

Краткое описание алгоритма

Алгоритм аналогичен GeneralizationKAnonymityTimeOptimal, но строки отбираются до тех пор, пока датасет не станет k-анонимным и l-разнообразным

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• l - параметр l-разнообразия (целое число больше либо равное 1)
• quasi_identifiers_types - тип каждого столбца (массив размера равного количеству квазиидентификаторов со значениями 'real', 'ordered', 'unordered'); по умолчанию значения считаются номинальными

Результат работы алгоритма

• l-разнообразный датасет
• число обобщений

Принцип работы алгоритма

• все идентификаторы подавляются
• все действия далее проводятся над квазиидентификаторами
• если размер датасета меньше k, но не 0 возвращается None, то есть невозможность провести k-анонимизацию
• прозводится расчёт расстояния для всех пар строк по следующему принципу:
  • расстояние между строками представляет собой сумму расстояний между соответствующими элементами
  • расстояние между двумя значениями лежит на отрезке от 0 до 1
  • расстояние между двумя номинальными значениями равно 0, если они равны, и 1 иначе
  • расстояние между двумя порядковыми значениями равно модулю разности их рангов среди всех элементов столбца, делённому на количество строк
  • расстояние между двумя вещественными значениями равно 0, если они равны, или модулю их разности, делённому на разность максимального и минимального значений, в ином случае
• затем производится группировка значений по следующему принципу
  • берётся первая по списку не отнесённая ни к какой группе строка
  • она группируется с необходимым количеством самых близких к ней несгруппированных строк для того, чтобы группа стала содержать хотя бы k строк и для каждого чувствительного столбца - l различных значений
  • эти действия повторяются пока не останется менее k строк
  • оставшиеся строки присоединяются к последней группе
• для каждого столбца в каждой группе считается обобщённые значения объединением всех значений столбца в группе при помощи класса GeneralizationRange
• из обобщённых значений составляются обобщённые строки
• каждая строка группы заменяется на обобщённую строку

GroupJoin

Краткое описание алгоритма

Алгоритм объединения групп строк, функция потерь для которых изменяется меньше всего, объединение происходит, пока не будет достигнута необходимая метрика (k-анонимность, l-разнообразие, t-близость)

Структура алгоритма

• для формирования класса деперсонализации требуются ещё 2 класса:
  • класс, отвечающий за метрику (k-близость, l-разнообразие, t-близость)
  • класс, отвечающий за метод обобщения (подавление, обобщение, агрегация)
• класс, отвечающий за метрику, значет о классе, отвечающем за метод обобщения

Параметры класса, отвечающего за метрику

• параметры метрики (k, l, t)
• loss_function - функция, определяющая, как подсчитывается итоговая функция потерь, принимает:
  • loss - расстояние между обобщённым объединением групп и теми же строками из изначального датасета, рассчитываемое аналогично my_by_element_distance
  • size1 - размер первой объединяемой группы
  • size2 - размер второй объединяемой группы
  • параметры метрики (k, l, t)
  • k_sens - количество отдельных чувствительных значений в каждом столбце (для l-diversity)
  • t_sens - текущее значение t для каждого столбца в группах с чувствительными значениями
  • для k-анонимности по умолчанию = loss
  • для l-разнообразия по умолчанию = loss / sum(k_sens)
  • для t-близости по умолчанию = loss * sum(t_sens)
• always_use_entropy - использовать ли только энтропию для t-близости, или расстояние Вассерштейна для вещественных значений
• sensitives_types - типы чувствительных столбцов (real, ordered, unordered) для t-близости
• seed - сид для генератора случайных чисел (по умолчанию не задаётся)

Параметры класса, отвечающего за метод обобщения

• quasi_identifiers_types - типы квазиидентификаторов (real, ordered, unordered)

Результат работы алгоритма

Датасет удовлетворяющий метрике и обезличенный при помощи выбранного метода

Принцип работы алгоритма

• изначально производится предподсчёт параметров столбцов, для упрощения вычисления расстояние
  • минимум и максимум для каждого вещественного столбца
  • отображение из элементов в их ранги и общее число элементов для каждого порядкового столбца
• изначально каждый элемент находится в своей группе
• затем случайно берётся группа, не удовлетворяющая метрике
• далее рассматриваются все пары, состоящие из данной группы и какой-либо из оставшихся (в том числе удовлетворяющих метрике)
• для каждой пары производится подсчёт разности функции потерь относительно изначального датасета для объединения групп (двух) и аналогичной функции потерь для каждой группы отдельно:
  • loss_final(g1, g2) = loss(g1 \join g2) - loss(g1) - loss(g2), где
  • loss_final - искомое
  • loss - функция потерь из параметров класса, отвечающего за метрику
  • g1 - первая группа
  • g2 - вторая группа
  • \join - объединение
• выбирается пара с наименьшим расстоянием и объединяется
• процесс повторяется, пока не достигнута метрика
• затем производится обезличивание и полученными группами с применением выбранного метода (подавления, обобщения, агрегации)

IdentifierHasher

Краткое описание алгоритма

Алгоритм хеширования идентификаторов

Параметры алгоритма

Нет

Результат работы алгоритма

Датасет с захешированными алгоритмом SHA256 идентификаторами

Принцип работы алгоритма

Производит поэлементное хеширование алгоритмом из hashlib

RandomizationDepersonalizator

Краткое описание алгоритма

Добавляет к каждому значению случайную величину с распределением, задаваемым относительно исходных данных

Параметры алгоритма

• min_rand - минимальное значение для всех столбцов (или список минимальных значений для каждого столбца) для задания добавляемого значения равномерным распределением (None, если не задано)
• max_rand - максимальное значение для всех столбцов (или список минимальных значений для каждого столбца) для задания добавляемого значения равномерным распределением (None, если не задано)
• seed - сид генератора случайных чисел
• rand_add - функция для генерации добавляемого случайного значения для всех столбцов (список функций для каждого столбца) (None, если не задано)
• quasi_identifiers_types - тип каждого столбца (массив размера равного количеству квазиидентификаторов со значениями 'real', 'ordered', 'unordered'); по умолчанию значения считаются номинальными
• scale - величина задающая разброс значений при генерации методом по умолчанию (на неё умножается сдвиг по индексу для порядковых значений и вещественный сдвиг для численных значений)

Результат работы алгоритма

Датасет с добавленными случайными значениями

Принцип работы алгоритма

• все идентификаторы подавляются
• добавочные функции примеряются только к столбцам с численными значениями, ко всем остальным - методом по умолчанию
• к каждому значению соответствующего столбца прибавляется значение добавочной функции
• если для столбца функция для генерации добавляемого случайного значения не задана, но задано минимальное и максимальное значение, генерация производится из равномерного распределения с соответствующими максимальным и минимальным значениями
• если для столбца функция для генерации добавляемого случайного значения не задана и не заданы минимальное и максимальное значение, то генерация производится методом по умолчанию
• генерация методом по умолчанию производится по следующим принципам:
  • для номинальных значений новое значение выбирается равновероятно из списка (с повторениями) всех значений столбца
  • для порядковых значений генерируется сдвиг (целочисленный, приведением к типу int значения из стандартного нормального распределения) и берётся значение из упорядоченного массива (с повторениями), индекс которого равен сумме индекса изначального значения и сдвига
  • для численных значений строится гистограмма, из неё выбирается (с повторениями) количество значений, равное количеству строк, а затем генерация происходит аналогично генерации для порядковых значений, но сдвиг вещественный, но затем производится линейная интерполяция имеющегося упорядоченного массива (как функции от индекса) и берётся значение, соответствующее сдвигу

Shuffler

Краткое описание алгоритма

Переставляет строки в заданных столбцах

Параметры алгоритма

• columns_ids_to_shuffle - номера столбцов для перемешивания
• seed - сид генератора случайных чисел

Результат работы алгоритма

Датасет с перемешанными строками в заданных столбцах

Принцип работы алгоритма

• производится перемешивание каждого столбца отдельно

ShufflerInBatches

Краткое описание алгоритма

Переставляет строки в каждой группе отдельно в заданных столбцах

Параметры алгоритма

• columns_ids_to_shuffle - номера столбцов для перемешивания
• seed - сид генератора случайных чисел

Результат работы алгоритма

Датасет с перемешанными строками в заданных столбцах, при этом строки меняются местами только с другими строками, входящими в одну группу

Принцип работы алгоритма

• производится перемешивание срок каждой группы каждого столбца отдельно для

SuppressionKAnonymityBaseline

Краткое описание алгоритма

Перебирает все варианты подавления значений в датасете, в поиске варианта, достигающего k-анонимности с наименьшим количеством подавлений

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)

Результат работы алгоритма

• k-анонимный датасет
• число подавлений

Принцип работы алгоритма

• производится перебор всех возможных вариантов подавления отдельных значений
• выбирается первый найденный вариант с наименьшим числом подавлений

SuppressionLDiversityBaseline

Краткое описание алгоритма

Алгоритм, аналогичный SuppressionKAnonymityBaseline, но достигается l-разнообразие

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• l - параметр l-разнообразия (целое число больше либо равное 1)

Результат работы алгоритма

• l-разнообразный датасет
• число подавлений

Принцип работы алгоритма

• производится перебор всех возможных вариантов подавления отдельных значений
• выбирается первый найденный вариант с наименьшим числом подавлений

SuppressionKAnonimityTimeOptimal

Краткое описание алгоритма

Алгоритм, аналогичный GeneralizationKAnonymityTimeOptimal, но используется расстояние Хэмминга и подавление

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)

Результат работы алгоритма

• k-анонимный датасет
• число подавлений

Принцип работы алгоритма

• все идентификаторы подавляются
• все действия далее проводятся над квазиидентификаторами
• если размер датасета меньше k, но не 0 возвращается None, то есть невозможность провести k-анонимизацию
• прозводится расчёт расстояния Хэмминга для всех пар строк
• затем производится группировка значений по следующему принципу
  • берётся первая по списку не отнесённая ни к какой группе строка
  • она группируется с k-1 самыми близкими к ней несгруппированными строками
  • эти действия повторяются пока не останется менее k строк
  • оставшиеся строки присоединяются к последней группе
• для каждого столбца в каждой группе определяется, есть ли в данном столбце в данной группе разные значения; если есть, производится подавление всех значений столбца в этой группе

SuppressionLDiversityTimeOptimal

Краткое описание алгоритма

Алгоритм, аналогичный GeneralizationLDiversityTimeOptimal, но используется расстояние Хэмминга и подавление

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• l - параметр l-разнообразия (целое число больше либо равное 1)

Результат работы алгоритма

• l-разнообразный датасет
• число подавлений

Принцип работы алгоритма

• все идентификаторы подавляются
• все действия далее проводятся над квазиидентификаторами
• если размер датасета меньше k, но не 0 возвращается None, то есть невозможность провести k-анонимизацию
• прозводится расчёт расстояния Хэмминга для всех пар строк
• затем производится группировка значений по следующему принципу
  • берётся первая по списку не отнесённая ни к какой группе строка
  • она группируется с необходимым количеством самых близких к ней несгруппированных строк для того, чтобы группа стала содержать хотя бы k строк и для каждого чувствительного столбца - l различных значений
  • эти действия повторяются пока не останется менее k строк
  • оставшиеся строки присоединяются к последней группе
• для каждого столбца в каждой группе определяется, есть ли в данном столбце в данной группе разные значения; если есть, производится подавление всех значений столбца в этой группе

SuppressionTClosenessBaseline

Краткое описание алгоритма

Алгоритм, аналогичный SuppressionKAnonymityBaseline, но достигается t-близость

Параметры алгоритма

• k - параметр k-анонимности (целое число больше либо равное 1)
• t - параметр t-близости (вещественное неотрицательное число)

Результат работы алгоритма

• удовлетворяющий t-близости датасет
• число подавлений

Принцип работы алгоритма

• производится перебор всех возможных вариантов подавления отдельных значений
• выбирается первый найденный вариант с наименьшим числом подавлений