Skip to content

Instantly share code, notes, and snippets.

@MajorGressingham

MajorGressingham/gist:7876252

Created December 9, 2013 17:20
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save MajorGressingham/7876252 to your computer and use it in GitHub Desktop.
Save MajorGressingham/7876252 to your computer and use it in GitHub Desktop.
Download ZIP
Fuzzy String Strategy Pt. 2
Raw
gistfile1.txt
{
"metadata": {
"name": ""
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": [
"Developing A Fuzzy String Strategy Pt. 2 - Clustering"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Image(r'C:\\Users\\rcreedon\\Dropbox\\Rory Notes\\Notes\\JellyFish\\StringStrategy\\clusters.png')"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"png": "/9j/4AAQSkZJRgABAQAAAQABAAD/2wCEAAkGBxQTEhQUExQUFBUWGBkVFBcWGBgZFhcXHBgYFxcX\nGBgYHSggGBslHhcVIjEhJSkrLi4uGh80ODMsNygtLisBCgoKDg0OGxAQGzImICYsLDQsLCwvLyws\nLCwvLywsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLCwsLP/AABEIAQUAwQMBEQACEQED\nEQH/xAAcAAAABwEBAAAAAAAAAAAAAAAAAgMEBQYHAQj/xABLEAABAwIDBQQFCAcFBwUBAAABAgMR\nAAQSITEFBkFRYRMicYEHMpGhsRQjQlJywdHwYnOCkqKy4RUkMzRDU2OTs8LS8SVEdIOUFv/EABoB\nAAIDAQEAAAAAAAAAAAAAAAABAgMEBQb/xAA5EQACAQIDAwsCBgICAwEAAAAAAQIDEQQhMRJBUQUT\nIjJhcYGRobHwFDNCUsHR4fEjNBViU3KyJP/aAAwDAQACEQMRAD8A2+gAUACgDhoGFoA4RSGcIpgc\nApAA0AcoA5QAKABFAwUCBTANSAFAAoAFAAoAFMQKABQB2mAKBC1IDlAAoGcoA5QM4aAOUAcpDOGg\nAtAAoAFAAoAFAAoA6KAO0CBQAKABQAKYgUACgAUAdpiFqQDPau027dHaOkhGIJkAmCTAyGdRnNQV\n2W0aM6stmGpDK35s/wDaKPew5IV+9p6vv6VU8TTW81rkzEPd6nDvxaQTjVkQIwGSPrDp7+lL6qnr\ncl/xWJusvU4rfm0z7yzBgdw97qOnjBpfV0uI1yVicsl5iw3utTMLJiI7p73h/WKf1NPiJcl4nLo+\nod3em2TMrOQnJKs+gy1oeKpLeC5MxL/D6oQ//s7SYxqGUyUqj7Omvu60vqqXEb5LxNur6oTO+lpl\n31CRPqKy6GBrQsVS4h/xeJ/L6o41vrZqj5wiZ1QrKOeXwprFUuIPkzEr8PqhRO91rAPaHMx6qsup\ny0pfVUuIf8Xify+qDDe20ie14x6i/bppR9VS4i/4zE/l9V+5w732efzwyMeqvXplmOtP6ml+Yj/x\n2JvbZ9hRe9FoAol5Pd1yV7oGflT+opcRf8fifyMIN7bPvf3hHdEnXToYzPQZ0+fp8RfQ4j8jDt70\n2ZmLhrJOM5xA8+P6OvShVqb/ABIi8HXX4GOGNv2y4wvtGRiHeGg110460+ehxRH6WuvwMXRtNk4Y\ndbOISnvJzA1jOmqkXvIvD1Ve8Xl2B0X7Rww42cU4YUnONYzzimpx4idGor3i8uwOi5QYhaTi9WFD\nONY501JcSLpyV7p5BkvJMQpJmYgjONY507kXFrcGBoFYFMR2gDtFwF6BFc39H9zV9pHCfpCsuM+y\nzpclf7K7n7GYEDkP+HHvGtce+X8nqUsxNX57tLT+yYQ/nKi/y4wBRGk+yi/y4HXXFFJzVNO9wEW1\nggGDnnSBHFnx91SQMbvO4dZ8oqVrsg3YAv0wJK/4fwqOyw2kOO3ThmVkDlh/ChLPMd8gzCULTKSr\nzj8KVmNWYV5lQBiT4ifvouFiLK0g5ZeR/Gm9reV3QUQDkPbSzDJB0PkZiBHSiw7j35UZmRPgRSt2\nE7nPlE5nB++R91K3f6CuKi4EQQ1/xgPimi1uPkJyYVLKCQcpGXdumwfKU1YrrS/kVSuwP2KSZT2o\nMFIw3LJgHVMcAc8uNT25JKzfkVuCk3den7mw7mN4bG3AnJHEgnU8Rka6+H+3HuPMY7/Yn3k1VxkB\nFADigRXd/v8AJr+0j+YVlxv2X4HS5J/2o+PsZas+Hvrio9aJk+HvoGFkdPfTzA5I6ew0swB7PYae\nYDdr1R+FMS0ElqzFMRKr2QVWyXwCsB7A4B9FGGZPiSB/5q+NO9Pb7TNKulX5p8L9+YjfoaZQFJab\nWCc8QKjHtpOTjkreJOdO+d2u4ZJ3hIySxbAfqx+NDqvgvIp5rhKXmPrXaspyYtwrXJuB10NLn+xe\nRZHD5daXmOU7TSokFpuOBGMH3LpuqtLIcaLX436fsRe2LRvAXG5SoEBSZkGQcxxGlKycb2sDUlKz\nd7kWDIB8vyapaZYdQr84qLX/AKAdlfWP24+6o27PQlf5c4HFjRQ/eH3im0uHoGYu2+viT5Ka+8VH\nZS3ejAcIxHgs/wD126qe7+yuw6bsp1Qr/wDMyfgqpN/MyDdv7f7Gr7rpi0ZHJMeqE8T9EZDwrt4f\nOlHuPK4378+8lavMoKBC9Aiu7/f5Jz7SP501mxn2WdHkr/aj4+xlaj+ZriHrhPF199L5oM4T4e2n\n80AE+Htp2+WA4VfmTQAg0O6KbQloDsASPGlcLEhbbUdYJLK1InIxofEHI1OFScOqyqtQp1cpxuR+\n2dquvCFqBEyYSgE+JSAalKpKepGNGFPqr1f7kSW4qslYlNnogE0nqWR0EUXywO7hA+wkn2qBNTjk\nVtbWZy4vCuA4qQNAAEiecJAE9aUnJqwRjFMJbsdo4htBzWpKAeAKjA+NKEXJ2e8JyUYuXBMnXtz3\nUdpLiDgCTxlWLFAEjI9w68xWp4Vq+Zhhj4StZPO/Ddb9xO92ApIchxKy1AWlOUKKgjDKkgHM6zwq\nEsPa9np3l0MUpbOTSemnC45Tui5iCQ4gmVJVqcK0gEojDKjn9GdDUvpHpf3K/r4WvZ8d2j39niFt\n92XlBonCkOlUSgHDAUoFWX0gkxFKOFlk+PayUsdTTkvy93YvS4ordlaXEIPZErWpAPY5d0JVJPIh\nQik8NJSSvq+LEsbBwc7aK/6foNLi3DaynCk4cpDCwD4GaoqR2Xb9TRTltRUv1NV3O/ybPgrhH01c\nDpXawv2onluUP9mfzciaFaDGdpCFqYiD3zaCrRYKggEolR0HziczFUYlJ02mbeTpOOIi0r65eDM/\nGxWsQHytuO0KJ6AGDy70eHXhXL5infrrU9F9XV2b809L/O7z7BFOyGsIPylE9mVx+kPoaa+/kDS5\nmna+1uJ/U1dq3NvVLw4/PEUXsVkT/ekwCgTHBQGJXgCYj2xT5mkvxcBLFVsv8T3+mi+eBwbGZkTd\nJ9ZwaaBPqdO9z06mjmKT/Fvf8C+qrW+29F66+XmJHZbOGflKZ7MK0PrFRCk8+6M+Z5UuapW624n9\nRWvbm3rbwtr4+R0bGYBj5UiAtKJj6JRiKz55dOMVLm6d+tv9CKxNa323o/O9rfr7BP7LZgf3lEw4\nSI4o9VPiefsmkqVP83H0H9TW/wDG93rq/D+wruzGIP8AemzAbIyOeJQCusJnTXoKfNU/zcA+pq3z\npvV+iy8/IL/YjBWB8qbguFGYPqgEhXLPgdOvCnzVP828g8TWtfm3pf8Ajw37xFvYbOEK+UNg9mXM\nMH1s+5ny1PE8Aai6cGruW4lz9RO3NvVLw4/PEcr2QwMSflbcYkCY+ipIJVlwEx8Yp81TvlLgCxNa\n323v9NF88Bu3sa2ED5UjV0afU9UTpKuenKaOZhfrcSP1Fa323u9dfLzEXtkWpBPytE4EK0V6yl4V\nCNe6M416CnzcLdbcN16rf23q/K2Xn5CjOyLVLiSm9Skh0JCgnMJCcQWD1IEHQcTNCp00+vvIOtWc\nXenu07dLeXixy2hJbj5erNpSlJwnMgqhvyknmZMVK8bdfc/6I2ntfa3rPLz+abx2tIxH/wBRXqhE\n4FHuKSFKV1AOUcONScof+TgRSnb7C3vdqtPm/cEykK+XrJCXQO6qRhjCgH9KAZ4wIqO1DV1OO/5r\nxHadrcyt3Dfq/Dh5nAlKZIvzMNQezc490mJ0SkkYdeeVC2FnznAfTeTo8eHf68dBVLoBj5fljcOj\nn0IwGZiVQO9plAqXR3VPYg1K32FovXXy4akvu9sxgw/iS+4rMr70A9En1T4515rF4irKTjLL5xM2\nKrVF/jtsrgXexHcHn8TXqeSv9SHj7s41XrMcCuiVnaLiFaBEXvOP7q79nlPEVRivtSNeA/2Id5la\n0HqP2Z9uWdefU3e57GyGzyHQdMQ5hKfhFTU1oFosI2+dChQ/Z/pT2u1DtEOlQ4yPEf0pbS7CWyhQ\nrTzT5hPLwp33i2UzjZGuXA6DgPhTQ9lB0uJyzHDUDh5UabhbKChaRlI4cBznlR4BshFEzqIz4DnN\nK26w9lCgdB5ZzwHGjvQtlBivnHH3iKHnuDYRxRPSP6R/Wk2uAbHaDGnkn8iP60Za2DY7TsJ5JOmo\n/OtPLgLY7TgA5J4cOX40lbgGx2gSB9VB8vbxoy4BsPiCB9Rv908/HypXXANh8QEp+o37Dz8fKneP\nD1Fzb/MEN0gZYGieWY4+PKm7cCLpy/MJ2m8ZaViDWA5g4VKAmcgQTEZe+lKnTkrWKalDbVpu/eal\nudfqftG3VgBSscx0WoD4V2sHCMKMVHQ8xjaap1nFdnsTYrUZAUCFaBEXvQgm0fjXAT7M/uqnEK9K\nXca8C7YiHeY9jVzNeePaoOLhQ4T5n8ai0FkKJuQcuzJP2lU0Rasr3Ere4adUWwyoLESFEjUxx68d\nI41fKk4raTMqrq7UmTTW68pnCEqjQg5eJqhzltWzIPGwi8s0Q+0NkKaVhlMDQiYI6TVkpWZpo1VU\nimhmoEZE0lK5cIqXGvwFSuK4E3I01/ZTT7xXDFY4iP2U0bxnUqSfpAfsCk78AFAkfWQf2BScrbgE\nzg+u3+4KL9gshRDKfrI/cpbQwjqmwpKStqVHIFIE++rIQnOO0ou3YQdSEXZtXHCdnKOnZ/uj/uqp\n1ESDf2W5+h7D9yqW2hbSE3LR1PBJ8Cr8aldDWYj2L06R1BXReNv6CzFDs99Se6hS+E90T4TQmt5X\nKUY6s1rci3LdiwlWRAVPiVqJ+Nd3C/aieTx7viJv5oTtaDGCKQhSmIa7URLLo5oUPcarq9SXcy7D\nu1WL7UZZ8kHKvN2vkj2fOWFW9l9xKjxqTi1qV/U9JxRKbK2Wn1okz5CPvqmbadkZMTiZdVDvaOxU\nLTOFPaD1TGvQ8x46VdRqKm89DnupKTyDbHvgtGZ9UwZ15FJniIp4mTurDnTe7eLu2ra84SocfyKy\nc5JZE41akN9mRlxsO2XICSmZzBOR88qmpPW5ojiq8es7lf2zsbsSlKZOKYUqOkgwMtfzrWyk9pNo\nuji3N5kLc7NORB6HLj0ioSdmbabchuSpOokUJl2aCB0HpUmK4stqU9aQ7ZDZCVlSEDDiWtDaSqYB\nUoJBMZxnRGMLty0zbt2K5nxFZ0qbkloSu8G7d1aIDuIXDYHzvZoKVN/pBMkqRzOo8KhSxGHry2Ip\nxe67un2dj4bjmUuUp7X+TTs3Ens/Z6HdjBbTSO2cKTigYlKF0IlWsZCrqdeosdzVST2VF5bl0c8j\nnznartrjf1JNvdthtxtl1u5uHHBK3k4wy3rHqqASJGgBOhOtQeKm6TqUpRilpFpOT7Xcc8TVm7yb\nEdo7ASm3uEW4Pypg4kKxEqWkjGmQTBJSVJ0zKTUqePlzsHX+3NZqyst2XDPPuZGNaae0mKbU3XVi\ntAyVAYwi6OIkrRhxlRJPdJKCMo9eqqXKikqnOJcYZLLcu/8Agkq9SN7S1KrvW6i3vFobCsCUoSU9\nosjHBUpXeJ+sBH6NdvC4GeKwkJ1ZWk7u9lo+6xfhcXKk23mn2mobmtpct0Ep4IInUShJI9s1nlg+\nZnzc/Mz42u3Lajle/uT9gBgy+ssfxqrZh/toxVut4L2Q5q4qO0xB6BCN4QEKJ0wmfCKhU6j7idNN\nzVuJm6XkkGvP0rNnq6sZJCu7ALiDizgD2zVtSxjqzcGWSxaCQRGfDw/PwrHVVmY60nN33Bb9RCSU\nxJyzqqNPaJUUnK0irqsVDQGtGydlVojnZT5aUQsHCfcecVGcNpFWJpqrG8dUPzcIgKSYPUGqdiW8\nyqnO7TRDX75W4Fa4ch/4rTBuMbGylh4xWYdNwFZKbEDlkabz1JOk45xkGOymV6Ap50bJH6mrDXMY\nXW6bZ0XHlQrpkljL6xGO193nbVCFKhSFaKHA8lDhVjjJJN7y3D4ynWbjHVFcdu0puLZM94vskDp2\nqMz7Ktp0JTjKSWSjL2ZTyjWhGm4PVmmbf3mbtLhlt4Q28lXzmuBQKR3hxScWvD4crCcmyxWHlUp9\nZPTire/ucC+Y62sEMWLq2EpCUIU+gJ9QkK7WRHAnPLnTwMZVMWo1L3d0+OjRFlX2pvdYXbaFG8ur\nePWaZ7VKj+irAgg+INdChg8XhW4pQa4u39+A1Fy0RCbs7dQ3tFx1tt5Nq42GzjJW4SgSlwySSSZy\nnRXlWjHUo18OoTqJzTve2XasvmRfDCVrZRJ3ZO+AbubpbiHFNOKCmwmCQUgISIJyxJCZ6iq8ThcN\nUp0oxlZxVnk815cb+ZL6Kvbq+xn1+XXHFuuJMrUVq5STJ8s69LQxeHsoRkvYTw1SCzibnuZ3WgP0\nW/8AlorDyi7Yjw/czYjNImNlKlB+25/zFVXhXemvH3KsSrTXdH2Q9rQZztAB6YhlttUW7x5NrP8A\nCahV6j7i/Cq9eHevcyW1fzE6ca8ym4u57WpDajYk9l3im4QgJOLTgddasbl1mYq1Gnq3oTVzdOoK\nVJwQAUkrUoDpkEmfdRTnRn9y64WV7nNlGLTSV/0Kc56SHcakFCUqSSkj1swYMHjXqcNybhNlOzfj\nYyOSvZIl7Xea4UAVN4RzVhQPauK3RweDWkP1Db7B81tgGZeZTn/tUH4TU3g8Luh6D2+wP8pbX/7h\ngxwxonymKreDwzydL0LFXktBQKQNVN+OUfver76plyXhZZqLXcyf1M+IVzaNujJcInQ5ieoOh8qz\ny5DpS6kvYPqXfUT/ALUsf9vh/ZJ+FY6vIlWOcWmP6yfBMVZ2/ZozbX26h4ADy1rBLDuk+mn46E4w\nq4jLaSXY7sZbQ2wbhKgrQ8OA5VGv1DoYfDQotbJnO0mou0qSknsy2rIciF10ME4LCPbdr3/YyY+L\nqV2oq+SLBvffHaC2yGy2lvEBKsSlYsOsCExh61gwlengYOEOk3veRGjybN5zfkR42S4Ww0XVlsaN\nlSigTn6sx7qhPHzk29L8PlzoQ5OpR3Diy3eROYmszqykzTzdOC0H67ZSBGHCPCB7TRGhUk+in5BK\nvShrJDcLRxdZ/wCI3/3VoXJ2Ieagyl4/Dr8XoxVtkLyQUOfYUlZHkkk1XPB14LOLHHGUJuykvY0H\nZjuBSxyDX/KR99WOpLatLccWtTU4prjL/wCmS+765bV+sc/mn766WDd6XizDjVaov/WPsSlajGCg\nA9MRHbxn+6XH6pf8pqFXqPuNGE+/DvXuef8Aau2g2tDSTClKSFHXCkkcBxrkYfC84nOWnuelxeNV\nKSpx1evYixWnaOvkJ9QcQNI1J5aVTUlGEbPUcpRjeTeRNXO2vlHzFuCtZOERmSeSeGXM5CuvyXyR\nGMOexD7l+5xa1Wz7Bq3uqwypZXjddTm72S0tMtE5/O3K88XROfSutJ36qst3HwRkdVvQrrlta3Tz\ntu0gtPpQpbTiLhb7LpQgrKFFxIUJAPeHEceNm3OGb9rDcpLMruwmn31FDDXbKCC4U8cIgEgSJPeG\nQzrRKqo6k3JR1JG+2W+zbh99tLOJeBttYWl1cCVLCeCRkJPOnGspSshKabyIkbSUnNKlIPQ5VbtX\nJbQva7xOpOeFST66FCUL8U8D+kINQklLv4ieY721aDsm7pgq7BwlBSTKmXRmW1HiIzB4iq4zbvGW\nvuQvuK0p8gyCQRx41lqtPJlTk07on9lbzOtiFQ4P0tf3vxmuTisJTnpkzfhuUqtPKXSXbr5kzbbd\nYdgKPZmZhWQJ09YZe2uVUwlWGmfzgdqjyjh6uTyfb+5IXF600O8pI5DifACqaWGq1eqjZUxFKkuk\nyHud606NoJ6qy9wro0+TEvuS8EcuryullTXmds9vPnRQRP1QJ9pzHlXVw+CoRd1HxeZgqYytV6zH\nbrfaZrJUeaiSfaa7NKmtCtIaO2iROVXSpxSE1YinUlKwRIIMgjIjwNZJRVyBph3pSDhfyUUMlLo1\nMtpJCxxznvVhxvJcasdqGT/supVObkl+HgXLc9yWV/rFe8JP31ysEnGm4vc2R5TS51W/KierWc07\nQAamIjd5P8pcfqXP5DUKnVZfhnatB9qPKKryXw6rOHAsjmAoGPYKioWp7C4Fsq21W5yXE1fefb6P\n7OCrYj51WBSgIOXrA5TOXGuVydgnLFNVPw5/sbK9Ta6UXkKej8/JtmXF9/qqV2LR+qJSmR+0T+6K\n9QrzqRpvQ503eSQ63o2K+/bWgt0KcaU0FnBnLys1qX16nTMVfSqQUpubs7+hGMrN3IvY27XyXtS8\n4lD5ZWF4SFfJWCIccWRkXSDhQgcVeyupPba2Vl7v9iTlfQU3e3cat9oMvNqfQ22LcYFYS6X7gH5p\nWGAEhBKlcgDFRnNuDT1z8kEpXiSV1sVi9RbtOrdStCGVpfKlLxi4fdlqDlJCclHSBwEGCnKF2u30\nIptBrTZFvbuMrVbtsi4U80Uuk5pcXgQ1CjKYZbUST9JwDjQ5ykmr6W+eYNt7yLAtWLRxxtxlTrDb\n5WhsAhN0+pLIIVEdmhJKUc4J4VO8pTs1w8l8zHm2V3ZrRGx38X+vco7EHj2SSXFjoBlNXLOsu4na\n8impZJV51jqu8sip5s1Dd/0WOO2xeec7IlGJtESo5SCrPug8tc+GlZ5tJPeShs7SiylvWDSEgyXF\nnURCUnlzUfdVtOC2VIu2FF56kU+4T+AqM5EJSuKWrUmq46kUW7ZOw33EYm2lrTITISYxEwBP5iti\nqRhqXJpGkK3ASi2JxrW+E4sj3MQzwhMacJql4yrF7UfIjSrdKz0E2NzLZlsO3zmZ1SFYUJ6SM1Hr\nlU6+OlJ5ZC251H0EIb5blWotF3Ft3ChOMQoqQtP7ROo4g1n+pnBp3J0ZuUtiSzzM/wB4XJ7M82WD\n/AB91dt9VEqhpnojuSuzWDnhdKfLAgj41ycRBRqNrfmU1pOWzfcv1ZeaoKDtAg9MRH7wibW4/VOf\nyGoz6rLsP92PejyZfWxTnGRJg8MtRVsobNnusSqx2ZMmbSyuewUrs19gVBeKMpAw4ucRx0ow9Smq\n2y30rE6als6ZF73C2tbu2b2zrhwNY1Y2HDknEcJgk5SFCeEgkVrqJwqKcc+JCaae0iXtt2r1hJSL\nptpnUrD6koI5gDjV6r0ZO7jd9xW5JiJ2rYstusFLryVltS3UwFPrQrFgVi9VrIDic1VOpQrSaqZL\ns4fyCTbIu+9IBIcLds2lx2FqWSVFLwb7LtGwfV7kgDhJzNQWFta709iagVNe8F0WWbcOrwMqCmgn\nJSVCcMKGZiTHKas5qN27ak9lCF3bOKly6cVJlWFaipxROpwk92eZimrbkSsP93tlrWhSHCW2HVIW\npIA7V3s8WENg/R75lSoSNeFVykr9HUjbPIlttXRew29ugd1IbSEH5tlsGSkKOpJzUs6kcqhZxT4/\nPiQ9myy1Gg2RastqSVKublYwoDWTTajkM4xOq6ARWV02s2V7NtT0EwkqZSCCkqQAQRmCU5iOlZWr\nqxVGWzK5RdtWmy9nMrStKHHVJIGOFuEka55I8oqEptrm45v27zVTjJyVWeSvfv7FxK3sLcK3ZZF3\ntJRSgwUMiQYOYxxnJ+qIjieAsnNRst/qyuKdRtR/okt8t17MWjd1aICAcJETCkq0MKzBopyaqJPf\n/f6E6T2rxeq3l3dX2Wzpb7uFgFMZR3BVVVuzK6KUqqTK/sb0isdi0l4q7WUtuGMuALhPhmfOrJRk\nnZLIbop3d/Am989gfLWAlCoUk4kGe6ctPPnUU7SUkKjNRvGWjMyfubwI+RPEpbRqkjMichPEVsw2\nHjXqKXD37jXCLWiXfxRA7fMhro0hP7siupUySI1DSPQz/lXv1v8A0gfdXMxWsTNV3GhVkKjtAg9M\nQy20Jt3h/ul/yGoy6rLaH3Y969zzGxe9mtaVIS42VSptWhIORB+irr5EEZVupxVSlG/A11lapJdr\nNa2LtZh71VAEJAwxBGXqkaD4cia8ryhyfWw8nLVcd/ia4Vk1stfsUjeTdpBuHQ24hAPewKCsidQI\nByrrYDlFOkud14kXg5t3iQtlYvtiCgqSPpJ7yY55ffXcw2LpyyTMs6M49ZEgl0KTXVUlKJl0YxuG\n6okTTC24cJhvF1wAz/CJqDdtSxMkrHZZHfUkJzPedISZSYV60nIg5gDxrHWxFKLs3d8FmTjDazGj\nu1ypakYhhJjuYu+dBJV3l+dJVEs2rCbSND2R6NHnGgXXQxiz7NKcSv2ziAnpnVM8Vuiih1tyHVtu\nw7slw3acN02lJDicOBxCSQStGZBIj2E1kq1pPNko7NXo6MvW7+2EXluh9uQleIAHUYVFJmPCo57y\niSUXZGDbtbNNzthDThKgHlqXOfdbxLgzwOEDzpUko01bgasU3zkn2l/9KLLtxdWls2CcQKgOEkwV\nHoAJop25xt7l7/0EGo0L8X7JW9xxv6tLNtb2beZASI4kJECepNSpdKrfh7v+Lio5RcnvLs9Yzbln\n/d9n/DFVzV4tFFOezNS7TBrqyAKkkQpJIPQgwa6lKFOrTUlqzZKmldEtu1vrcWhShXzrIywK4D9B\nXDw0rJUotP5Yqkk8peZoe+TLb9kLpGqEh1CuJQYJSfEcKphVlRqKot2vcPCyansd/mYjtjaKFRBz\n73xkfGu1UqqSTRbNps0z0HPYmLkcnE+9Jrm4mV5JGatojTazlB2gA1MQ32imWnBzQofwmlLQnT66\n70eUb9QDrn2ifvrXg5/4Y9xvxWVea7SYbfSjCsHvQMxIIyFdF7Fs0Qy1Cq2+vEcYxA6kHCr2jL3V\nx8RhKU3eKsThipweWhJbE3ltGlDGp9KSZVKQQT4pVMeQrmVsFXWcGr+Rp+vg4OLjqXC22/ssoCQt\nrDEBJaWIHjgnzmaIPlPa2tr1y8jK6mHtaxHXG07NvJl3uwcg2sqn7SkifM6V0WsdXzm0u55Dp4ih\nBW2bjNrfAMIUm2aSlSjKnFgSTAHqJyHt586nPkyVdrn6jaW5ZebKpVk23FWK3tHaTr6sTq1LPCTk\nOgGgrpUMPSoq1ONvnEjtN6kh6OLVCtq2uOMOJSgDpjS2tSP4gD5VlxKtmQqaG5b57QeYs3nWE4nE\nCRAkgTmqOMCsEr2I0FFztLw7XuM22f6XEKsXW7kKVcFK0JISMKwoEAnkRMdYFE4tx2Vv3ltPYVRT\nbtZ3tnu4fyyY9BG0sdo8ydWncQH6DiQR/EldWzM89bkdu5Z9hvE6k5Yu1KOuJOMe4Gq4dW3BsvxG\naUuKXtZ+qL7vbtcWaQ+Gca1Dswv6o9aCdQJ+FQablaOr393uRow24vaeS3d5R902XL6+DzuYQe0V\nyEeqkeceQNaIxUKeW/42SqTy9jSNmbTS65cIBktLCT4FIIPtxDyqiLbVyqpDZt3FO3n3ZQ7tFlOP\nCl/EXAmMUoSSSJ5wBVtKtKneC7+4vU3zSlwy7/n7DV/0ZLxwl1BaJ1UDjA8BkT5itCxbcHGauJ1o\nNaEn6Rbtux2SppJ1QGGgdTpJ/POsVTpO3Fhhb7bm9yfrkjzm8cvP7hXUatFA2bf6Amotrg83E+4E\nViqvp27ERqq0I+P6Gq1WZwUAGpiE30ylQ5gj3UMcdUeTNrN/PLHUfAVdglekvm86ONX+eQ5KtJ5D\n8PurdJldxB1EmBxrPMqmrF73d9EFxcJC7hYtknMJKcTpHVMgI8zPQVmckVOSEt9vRsrZ7IebdLzY\nIC5ThUmdDkTIojPOzJxipxdtV7EJu3sS4u14GGyuPWOiUjmpRyHx5VshNRV5FA83q3dcsXUtuqQp\nSk45RMDOIzA5VZSrqo2luLrdFS4/p/ZB1obsSRYNobqXlow3eqhqFoKBPzqTqlREQPCZ5iubWrxk\n9niSj0723Z/oaxuPv4zfIShZS3cAQps5BR+s3OoPLUe+sryyZVKnvj/Q23q9F1ndYltp+TvHPEgd\nxR/SRp5iDQstAVW/Xz7d5TdxrV7ZO1Es3AwouAWgoeoozLagfHuxqMdNzTXaTnC8brNFp9IGznGr\ny0v2EFZQtKHEpEkgnCPaFKT5ioLKXf7ji9uls717P9n7l9vLRDqChxIUk6g02iiMnF3RB379ts23\nVgARPqiZUpXDXM0TnKTtvLYRdR7UtPmRlezdv3Fu8t1oypycYIkGTOY6VodBuKii6XSldq4Z7bL7\nbqL1xWJxKpg6Ry8CJHnVrwjp0tp79ePeSnF7N5acOBO3PpsZCMrdZXyKhhnx191YWp7rFKp0t8n5\nfyZbvRvW/tB3tHjCRkhA9VI6detXUKVpXebLdpNbMVZfM2QZE+38K3z1Kje/QW3Fm4ea/wDurm1H\nerLw9ieIypw8fc0mkZAUAGpiOKoA8tbwW2G4V5fh91aOTOlS8WdfHxtW8EIBPdH54mt0kZGap6Id\n0AQL55MmYtkngBkXfEmQOUTxFc6tO7siipK5btpb9W7V41aDE44taW1YYhBUYEzrrmKzpt6Im6Fo\nbUnbgvmgX0pPoTsy4xkd5ISnqoqER7DRLd3r3DDdZvdZ38mJ+iWzDezGDGbmJxXWVED+EJHlV1R3\nkUPUrW2djjaW2XGlKKWmUDGU+tAgFI5EqVrymp0pbEHLtLamUYx7Pf8AixUfSNsZuzu+zYBSjAla\nQSVQeOZz4VdQqympRkTstiL439zS/Sa4HdkKcGig24PAwR8awS1j3oMNrJf9X+5jGwt27i8Lht0Y\nuyTiWqQkDWBJ1UYMDpWms42uw/EknZk1uz6SLy0UEuKL7QyKFnvAccK9QehkVTsb4hPN2mvHf/Js\nG1rZnalgFp0WjtGV6KQsaeBBBBqEtL7yNKWxOz0evzs3EPur6SGHGQm6X2b6O6vI4VkZYkkDjy50\nbWV0r9w5UHtNJrzK/vNvg44+VW61IQBhESJ4yfbRGnleSzfouGRZdQjsrMrNzcuOqxOrUs9TWilB\nILuWpJWmzilHauQ03qFOHCD9kaq8ga3UpRjmyyLSzZX9oXqXyvCskIjhCQDMa5nTpWfFY+MXxJr/\nACPIrm0bEBONJxTy+/lXP+t2na1hOhZXEDZlC8Jg6ySSBA1zp08Y7XFKi4uwu5YgJJBzBlSTqAYh\nQP0hmJ4iRW7D4qNXLeVSg46m6+hluLE9VD+UH76xXvVn3/oTxqtGmv8Ar+rL/FTMB2kAKYAoA867\n42cO4+ZUk+IJj89KlyNUu50+256DlGn0YT7LEXsy27XA19Jaw2nxUvD99daq1GDZy5W2T0Ft25TZ\nWDimwAGWsLY5QAlP3VxJN2KaEVKok9NX3LM8yJvnA72wUe0CsYVOYUDIPtq1R2VZaEpTcpOTJDeb\ne66vQkPuYkp0SAEpnnA41BRSd945VLx2YpJdm89Dej9MbMsv/jtH2oB++py1ZnlqUD0cbXx7YuZ/\n1g7HilSVD3A1NK9BP5mXYhWqNcMvJWG3pstyLtlXBTUeYUf6VPCdeS7F+pJP/HHvf6FusrY3ewEN\njNRtglPUt90fyVmrK17bn7EaLSq56O688hr6EkgWbwKClXbEkkEBQwIAg6GCCI4VOTu7kKialmQe\n3PRC6u4Uph5oMrUVHHixoBMkAAQv2iowbjHZLZ1oz6W8te39psbJ2elhKpWlvs2kn1lEzKyBpmSf\nGqqjcuitX6doUIdLnJdVer4L5kjFdl2+JWI+JrTGCsPrNyZarHYqlp7RSkssj/UcySeiBq4ron3U\nrEWxZzabLOVsiVDV94Ar8UN+qjxMnrU0xopO8W2VuKJUpSjxKiST5mlJt6hJ3K2LxSSYOR1HA1VO\nkpahCpKGhP2qkXDbaJwLmDynWT0yPma5soSoyb1RtjLnIriOrQ6pcwzjgKETllmDwGtQcFe8Se03\nqEutlk4lJOacRgcU5mfZFaKFdwqR7ympG6ubh6KW4s/2/wDoRVtB3c3/ANmLlJWlTX/VfqXStBzQ\nUACgAUAYtvHZdoHU8cSinxCj/wCK5WFxHMYnbel2n3HsalLnsMo9it5EBunbhN1blWRRcNz4YxB9\n4NerrpSpNo81OPRZr/pLZKtm3AH1QfIKBNcZ6rvXuV4frNdj9mebXW60NZENxYN0dx7jaGMtYEpR\nEqWSE4jmEiAZPHp5ioaK7DLeb/sW2Wxs5ptYhbNslCgMwFIbgweIkVXOWTYRSdVLtPP27O1/k143\nccEOyr7BlK/4VKrbTjejbs/YlWzqSfazYPSvsBd1bNuspLi2jihOZUhQziNeBis9KexNSCk8nF96\n70PN1bgbP2Swq6lsJBK5BlONxREp10UJGtQqzW1cjGDqSaXyxD7/AG/tsm0i0uUl4qSUdmc055k8\nvA86ql0mkuPcX0qbheU7aZaPP1M5uPSXtIpw9vHUJQD7QKtdF8X5gpJfgXz0K+HXbhzE4pTi1HVR\nk+01OFJLJCk5TfSZd9ndhbIGQuHjnn/go8Rq6fYnxq2TUcvnmDyyEb68cfVicUVHQcgOSQMkjoKr\nSchJEDte7gYR51dsbhtbivpty5iMwExJ1JJnCkDiTFV1ZKmsxxhcVf2EoKwoIciCqMinLiCaopYm\nE+tl3kpUWgyLXBkMiNfGt06EJIrzWgV3ETJM8aySwySsshbcr3eY4Y2wtKMCUgzl3s4zMxH3nhWR\n4ZbW035E+fdrJHob0cN4bSP0z/KkUsJnBvtZfytlWS4RRaa1HMBQAKABQBk9+PnHPtq/mNeeq9d9\n57ih9uPcvYrW2bXB86jJQ9f291Y8DAP7PWvT8l4lTo81LWxxeUaOxU2tz9zYdkXiL+ySoxDrZS4P\nqqjCseRn3VRKNm0cZN05pmJbW3EvEvFpLDi84SpKSUKHA4tB5kRV+2pLPIsmo6p5G0bsbLRs6xSh\nZAwJLjyuBWc1HrwA6AVROSzbKoxdSajHeL7ubVF7aB2IDnaJgcgtSPgBSSdukOdoVOhotCi7Q9GN\nra2dy6tS3nAhSkKJwpQdRCUnM8MyfKpurKMEluLINVaumTuMNwvSehllFveBUIAS26kYu6NErGuW\nkjh7atqUms0ipRUt9mRfpV3/AG7xtNvbYuznEtREYiNAByqhQlKSbVrF6UacWk7t+SX8mXgZ1o2S\nKiS+ztjOOkZYRzP591Zq+Kp0ut5GzD4OpWeWnE0ndjc1laSlU6Zr+lPTgPCuXLH1ZzyyXD9zbicN\nSoU7Wu+Ihtbdxy3OYxI4LAy8xwNdTDzjUst5zHS4EHtS7S0mB6x91dNRUFbeFrFPu35NCVsyLJLd\nl9KA6VxmElAIJOIYoI8JrBjsPUqxioK+foW0ZqN7hX3JViBVpBJ9pMUUMBJLpkZ1G3kJLQrDiCVE\ncwCRlrnW+UorK5SyOVe9KzykQbJTdvZ5eeSY7qTiV7ZA8zXOxlbm4PizbyfhnWqp7lmz0XuKmLUd\nVq+MfdUMF9peIuV3fEvuRYa1nMBQAKABQBlO0B8459tX8xrz9Xry7z21D7ce5ew0es8YHnV9GpKm\n1JCrQhUThILu7ePbNUtSR2jCjiW3OY4YkngqPaK70ZwxMdqD6W9HnsRhHDKWm5l1Z9I1iUYi4pJ4\npKTi8MsvfVLUluZj+nfFefxmb+kLf9V2CywChnjOq/HkOlEYNu8vL9yzajTTjDNvV/ohX0a+kFqy\nYWxcheHEVtlImJAxJInmJnqalO+qzKlTUt9u+/6XI/fz0oLvUm3YQW2T6xUZWvxjIDpShCUpLa8v\n3LI7EE1DNvf+y/X0KSmuvGKtYq2SUa3dcUApQ7JJzGId9Q5pRrHUwOtYsVXpUo5mmjQlVdoL9vMl\n9mbvZgNNqUoyAdSSIJE6DUZCNc5rh1cbUq5U8jr0sDSpLaqu/t/Jbtk2DbPapeCSsoSGwnOCoYgQ\nYjLKfd1y2jDa5zN2y8TTOU6mw6WSTd92m4t2w2AhoHnrUaEd5zsZU26lhTaV0lCCVkBJBHMkxkIr\nTPJXk7Iqo05VJWjqZHtzZaXVFQOEnlp7OFTw/KdSnlPpL1OpX5NhLOOTI613JfWQe5HMq08RFdeH\nKWG60m/I4s8PJSsOU7tLBIxNkjI+tzj6vStMeVMN2+QnSkjiNhKCwl0FKeJT3p5RE/CivyhSUNqD\nuxKm2yRsr1DILbcqSgjXiSTJOQ4wK4OIlKpLblvLo7KWyQlxu6p5zG2kIClHGJBCDkSRHAzMePCt\nEcXCEOm81p2kYYKVafQ039hbNl7PSy2EJHieJPM1x61V1ZbTPR0KEKENiP8AZqe5iYtEdSr+Y11s\nH9lHmOVX/wDql4eyJytRzgUACgAUAZVf/wCI59tX8xrz9XrPvZ7Wh9uPcvY6gwB1qaeQ3m2Lsshe\nKTACZOUzmBpyzk9BV1PW6drFFWTjZWvcg9q7rtqP1DkQRmMxOhrasfUWVRbXv5mWWDo1c45Ffudz\n3PoKQoeYNWxxlGWt187DJPkya6rRGPbp3H1U/vCp/U0Pzej/AGK1ybXb09RsrddwZqwgdDn8KhLl\nGjHq3ZfHkqrvsi07vbHBKQ0gBWUrgkp4SVGcHiIrPLlKtWezFWRpfJ9ClHbqO/Zp6bywM2iWFg3G\nFWWLDOLPGlJn6xjtMv0axNbM9qq7+vzeadt1KezQVlpw3N/t5iDm34AbtkBpOpUQMRJSEkgZgSBx\nnnkajPEWVoKwRwm1Laqu79Nb/NB5sPZ6nFYiCRxUfxNUwpym8izE140oWWvAt12+lpGIkd0wPLl+\ndDwrW5RpRyzZxKdOVaduJQdq7QU6qSZ4AVjcnJ3Z6KjRjSjsxEbazkgq55dKUc2OrNQi5DzaV92a\nSUQXCISNSVR7yNa1whfXQ4MnbMYbHKmwgOE43DBBGk6fnrU52u7FaTtmNt7rQqw4CMs40JGk51Kn\nOMXmRqQk45EExYPBIXMSYMnIRzNXuVNuxTGM9Sx7Gt1oTmpPelXCPIViquM3obKFWpT0ZJYY11rK\n7XyO5Sm5wUmaVumItGv2v51V3ML9qJ5TlJ3xM/D2RL1oMIKABSAFAGU3p+cX9tXxNefqdd97PbUf\ntx7kBBkQeFTg7qwSuncfv2akEqQZTPdKZnjy5QRNXypuOcTJTrxqLZnrvuHY2moZKCVjrrEyB8ac\naz3q4p4SLd4uwO1YJEoI0xHPTOSIOZJjhzp7dNvQWxiEnaXd8Yi32QSSZK4UADmASFAGIj6vHWel\nQTgo9pZJVXOy0y+e4zuFMJA+axyIVOvqkZEkicRBmNAKjtU1uuWbFed25W4cNfDK3bqR9xvC6s4E\npShMyhIElJgJGE8OOg+kajLETeUQp4SEM5O73/z83BGmHH+8ZjEhvEeasgBzPE+PWq7Sn0u5foXO\ndOl0V2u3dmO9nbMaaehZ7XuzAkQvFBSYPIcYyOnAyap05Wlnl6lEqlWpTvDo5+ltfnmWlW0G2kwo\n5xECNBJGkDidIpSr3yRzlh6lWV4lU2ttAury0+iKpebzOzQoKlG28RYtozOtF7lrYuuQCoAmM6sp\np3MeLqRUNl6sru1b0A9oFCQR2YggxHeCutdCEdrJHFc7IdMo+UlDgUB2ZBkazqAoEgDMVHON4sbs\n7NCFwpTSsBT2gWThwCVJzjhqk0nFSzva3Em5WCv3pRPdS24gSkApOIAZ5AYSCMjnUVC7STuhXsnd\nC2zH7hw4jCEZR3YVhme7nn8Krq83HLeaaFCdTO1kTZ51jOylZWRpu7aYtmfsz7STXfw32o9x47HO\n+In3klV5kBQAKQAoAym7/wARf2lfE15+p133ntqXUj3Ijbq4UlWmVO1kWDyy2iRMGJyI4Gpwm0Qn\nRjPUlGr5pallaIxKThI+gnPEctTodOdXKpCTe0jJKhWhGOxLRPxe7XcO1WTCpwOj6RExnkiBnHEr\n4cKs5qk+qyhV8RHrw4frnv7Drmx0ycLyY73LQAkZzHwpPDrdIUcbO2cHu+aEe1ZNqSkrcCQfWGUj\nNQyzk6J4fSqlU4tJtmqVepGTUY34en7vfuGzt1bW4lLalqxJUMXBQn6WUa8jNSU6dNdFZkZUsRVf\nSdlmsu3sz9yJ2rttx4RklMgpSkaQIEHWByqipXlUy3GijhYUs1m+L+WJfY+xVJQHHD2aR62LIx3Y\nIJyE4jryNShhm+lLJFNbGK/NwV358RptJSFufNThAAkzmeJzqups7XR0NWHU4w/ya3CtMgeNVljY\npTELMPwCCJGusZ1JStoZa+GVV3vZjK5tG1nNAjkc/Pxp85JaBDCU0ulmIt7OQhCktpCcXU66damq\n8pO8iE8FC3QyErLZhbbKMeIkyZEgdB0qU8Qm72IwwCiutmGt9mhMYyFgaApEA9KrlV4KxdTwsU88\nx9NU3VzVYFMZqOwxFuz+rT8BXoKKtTj3HisW71597H1WmcFAApAcoAym59dX2j8TXn59Z957en1F\n3IK+wFCrLApWIxxhSDlUbFl+BY9hR2UpwhwkhRIBKc04cicgRizHHWtVFLZy1Obi3LnOl1eGl9b+\nOnhoPHdjqKl6yMOEADvnBKspEZxpzqUqF22UwxsVGPjfPRXy+dhGu2S05lB5+Xl4Gs0qUo6o2xxF\nOWjFWdmrMEwAYzkHI6ZTNSjQnLUhPFwjpmwj2zW8ZS4oFKYP2hiiPZrGfCjmoqdpPQaxE5U04Rzf\npl8tuGynm2smWSSRmtRzTIzCVAzGgiBodZodSnBdBZgqNWo/8ksuHHvWnv6Dd9xbhlw9YEADnAGQ\nrPKUpZs106cKatBHUpjSlmSO0gOUgOE8yB1JgU0r5IjOahHaYRu6bVOFUwJ4g+0/CtDpJHN+tqdg\nazcS44pElJSASQJyOmXOlKCSTEsbNJoOV4swIzI8Y1NVTVnka8LVc07sIarNgXDQFw1FgNV2YmGW\nhyQn+UV6On1F3Hh67vVk+1+46qZUCgDlRAE0DMpf9ZXifjXAl1n3ntodVdwgu4UlUESOFT0Gopom\nraySptKiCtSsykKCcKc8xOpy99aqVGMo3ZzMRi5wqOMdwq7sFv8A3g4iQFD3U/po7mEeUKm9L2EU\n2mE4UvwQYAONGc6e4e6jmKi0YPGU5daHsxS7YfSlWJYIVkRiJnjx8KhJVUrNkqc8PKScY2a7CMWp\nZGZJHjy+NZ3tPU2R5vcIYqgy+xykMFDQHKTAFAX3BUupIUQpJKdQDn+HlU+adrsyzxdOMtkSSvu4\n3OzDR7sKSVEk5SMM5jlxqyEUslqYK+IlU10C2Wx0EE9rjGHvJShTajnKQJkjqelWydncy3bCWe2U\nW6lW6milSlQZOZTEDva6RT2Xba1FZXJS8bICXIwjMGDkoFPKMjr7azNXNMK0kkluGaFSAYIngRnr\nH3VVJbLsdijU5yO0cddCc1EAdaIxbeROU4xV5OwaaW8kszWrQQhA5JA9wr0cdEeFqO8m+0WqRAFA\nBTURhZpDMccuVJcUFaYjw4YiK4E8qjtxPbU86a7kP8iAam8wzTsPbC4AICg2QM0lYJgzoCMxxNX0\nazjlfIxYnDqfSSd+z+R38sbEQAn7DqhrE5EVo5/uMn0b7fL+Tvy8RktzU/TQo8IAnXQxzmnzyF9H\nJf0wt8rEiXCpIyEuYZPexRhTwOQOmQqMnntPIlCn+CLu+wh22Ckg421CCFGcyJnSABoPCVHjSlUg\n0ycKVSMkJuLE/nzNYpLM6sFlmFxVGxMGKkwsNby8KDkkqymOeYAHhnnVkIKWbMWMrunZR1Y3e21h\nSlwJBVELSO6g65kceOkVojDM5Uq0nncOyhxLQgJ7VwktNIzCYBkq+ikwR1obi3rkQTa3EO8zcBJW\nMigmUHhGpHA+VSWxfZYNytcPsTeJxBJDhk+sCYB89ac4uOhCMlLUkrja6iVLcX2jRgKBGJI5DMVX\n0paalmSHGztutmG+yAExKlK0OmXCoOLtmO63MWurlIk/RHnlyrNs3kdqn0aCcdbERdILysYUgJBA\nCCSAofSIlOcGMxWlNQVreJypupUdtSVth3UjPIAZxPnFZpZyOzRi4U0mbG2IA8K9CjxL1DVIQKAC\nGoDCE0Eio7a3XBJWz6xklJjjyVWKrhVJ3idrC8puNo1FlxRXbhhbeSkkR+eFZ3hpnSjjKUs/0GK7\ntI1McpBE+E60uYnwJ/VU1vG7u02xqtI8SB8aXMyW4ksRTejQa12ylKgttxIUNCCKa2ou6CfN1I7M\ns0C42gXFFSl4ieM1FuUs2TpwhBWjkhEXIpakw/yoUWFc78rTzFLZDaCm/R9YDzFPYFziEHb9B/1U\nDzTTUHwK5OMt6Ia9daVrcNGOBWn7tK0QbW6xgq4aD3oI3toI/wANxocPXnLlkafNRebuZebmtLBj\nt5USXETwVJyHspqkk94nCW9oiULaJ/x0dYxfcKm27WsyKoRvfbQ/SG1JCS+MPIJVn486h0k7qJfG\nhTesx+w3bgyXCo9Z+4VTLnXklY1U6GGjm3fvJRvaLIEBQ9h/CqHRqcDcq9NLUUb2gzwI8h/SlzNR\n7g5+kt5M7IsFvkdmklMiTyBOudWwwdS6bRnrY+jCLzzszVa7J5E7QIFMApFRsMTUk0rEk0JONGlZ\nk1JETfbLx6iai4mmFZIg7rdQK0FQdM0LFIjntzTwmlzbH9RB6kVfejJLoOIQT9IQFf186ahJClWg\n0R7PoiWNH1QDlCAMvI69aTptlkMZs2SJa39GhTkXHSPEe8jWhUiuWLk3qKO+i5tfrFfkoj4U+bIP\nEdoi16IWRqXFfaV+AFPYY/qUOEeia3H0PaomjYYvqULI9FjA/wBNNHNsPqkhZHowZ+oj2Uc0+Ivq\n0OEejZrkkeVHM9ovrFwFk+jln8ijmUL618BRHo6Y/Ip8yiP1j4C7fo+thwPuo5mIvrJDpvce1H0J\npqlEi8XMcI3PtR/pJp81HgQeLqcRy3u1bDRlHsqShFbiLxNR7yQtrNDfqJCfAVIqlOUtRemRBQAK\nABQAKABQByKAOFNIdznZiiwbTB2dA9oHZ0WDaBgoC4MFArncFFguDDRYLncNAXBFMR2gAUACgAUg\nBTAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAAoAFAA\noAFAH//Z\n",
"prompt_number": 2,
"text": [
"<IPython.core.display.Image at 0x38485b0>"
]
}
],
"prompt_number": 2
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Author: Rory Creedon\n",
"\n",
"Date: 5 December 2013\n",
"\n",
"Purpose: Building upon a previous notebook (Fuzzy Strategy Part 1), this notebook continues to look at how we might match fuzzy style data strings (and by extension any set of strings). In particular the previous notebook looked at how to strip out generic components of strings in order that matching may happen on a less generic core ID substring. This notebook starts where we left off with the next step which is clustering the strings into matched 'groups'.\n",
"\n",
"The question of clustering is somewhat technical in nature, and I had never looked into it before writing this notebook. Therefore the potential for error is quite large. If you find mistakes please do notify me. It seems possible that this notebook will become as much about clustering as it is about matching strings. \n",
"\n",
"A good primer, that got me understanding the language of clustering is the following student dissertation:\n",
"\n",
"http://members.tripod.com/asim_saeed/paper.htm\n",
"\n",
"A lot of this notebook may be pretty much directly plagerised from that paper. \n",
"\n",
"As ever this notebook has been developed for my work, and so the issues may not be totally intelligible to all readers (if there are any). However, I take pains to explain what I am doing, and so a careful reading will help those facing similar issues. \n",
"\n",
"Comments/Questions - rcreedon@poverty-action.org"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import pandas as pd\n",
"import numpy as np\n",
"import datetime\n",
"import os\n",
"from pandas import DataFrame\n",
"from numpy import nan as NA\n",
"from IPython.core.display import HTML\n",
"from IPython.core.display import Image\n",
"from IPython.display import Math\n",
"from IPython.display import Latex\n",
"import collections\n",
"import jellyfish as jf\n",
"import re\n",
"import random\n",
"import itertools\n",
"%qtconsole"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 1
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Introduction to Clustering"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Meaning of Clustering**<br />\n",
"From Wikipedia:<br />\n",
">\"Cluster analysis or clustering is the task of grouping a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each other than to those in other groups (clusters).\"\n",
"\n",
"So in the context of string matching, where more than one match may be possible per string this means clustering the data into groups of strings that are all potential matches for each other. \n",
"\n",
"**Clustering Methods**<br />\n",
"There are many different types of clustering method, and it is hard to know which is most appropriate for strings (hard at least for me to divine at this stage). Before looking at any particular methods for clustering I plagerise a brief introduction to the techniques that seem relevant to this particular problem (drawn from above referenced paper and wikipedia). \n",
"\n",
"Clustering methods vary in their approach to partitioning. Partitioning refers to how a data set of N observations is partitioned into clusters. There are at least four different types of partitioning:\n",
"\n",
"1. *Strict Partitioning* - each object belongs to exactly one cluster\n",
"2. *Strict Partitioning with Outliers* - as above but outliers can belong to no cluster and are therefore considered outliers\n",
"3. *Overlapping* - (sometimes referred to as *clumping*) - objects may belong to more than one cluster\n",
"4. *Hierarchical* - objects that belong to a child cluster also belong to the parent cluster\n",
"\n",
"In all methods, an object is a member of the cluster(s) with which it is most similar (however that is to be defined). Generally each cluster has a centroid that represents the cluster. Typically this will be some summary description/statistic. The form of this statistic will be dependent upon the nature of the object being clustered. \n",
"\n",
"When deciding upon which method is to be used, clearly the structure of the problem is the most pertinent factor. \n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Single Pass Partitioning Method"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is the simplest method I could find, and could well be sufficient for my purposes. It partitions the data strictly. The program can be described as follows:\n",
"\n",
"1. Make the first object the centroid for the first cluster\n",
"2. For the next object, calculate the similarity with each existing cluster centroid\n",
"3. If the highest calculated similarity is over some threshold value then add the object to the relevant cluster and re-determine the centroid of that cluster, otherwise use the object to initiate a new cluster. If any object remains to be clustered then return to step 2. \n",
"\n",
"This method only requires a single pass through the data set which is desirable from a computational power point of view. One issue is that the clusters are not independent of the order in which the data are processed, which leads me to conclude that that data should be randomly shuffled before being processed. \n",
"\n",
"In the method as applied here the similarity between objects is calculated as the Jaro-Distance. \n",
"\n",
"Below is a function that I believe implements the partitioning method as described above. There are comments that are numbers that link to explanations below the code\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def SLINK(SList, Threshold):\n",
" #1\n",
" random.shuffle(SList)\n",
" Clusters = []\n",
" Centroid = []\n",
" Scores = []\n",
" \n",
" for string in SList: \n",
" SPScores = []\n",
" Matched = 0\n",
" \n",
" #2\n",
" if len(Clusters) == 0:\n",
" Clusters.append([string])\n",
" Centroid.append([string])\n",
" Scores.append([])\n",
" continue\n",
" \n",
" #3\n",
" for ClustNum in xrange(len(Clusters)):\n",
" Dist = jf.jaro_distance(string, Centroid[ClustNum][0])\n",
" SPScores.append(Dist)\n",
" \n",
" #4\n",
" MaxVal = max(SPScores)\n",
" MaxInd = SPScores.index(max(SPScores))\n",
" \n",
" #5\n",
" if MaxVal >= Threshold:\n",
" Clusters[MaxInd].append(string)\n",
" \n",
" #6\n",
" if len(Scores[MaxInd]) == 0:\n",
" Scores[MaxInd].append(MaxVal) \n",
" else:\n",
" #7\n",
" if MaxVal > Scores[MaxInd][0]:\n",
" Scores[MaxInd][0] = MaxVal\n",
" Centroid[MaxInd][0] = string \n",
" Matched = 1\n",
" \n",
" #8\n",
" if Matched ==0: \n",
" Clusters.append([string])\n",
" Centroid.append([string])\n",
" Scores.append([])\n",
" \n",
" return Clusters"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 3
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The function accepts two arguments: Firstly a list of strings to be clustered, secondly the threshold which must be reached in order to consider a string matched. It returns a list of lists, where each list represents a cluster.\n",
"\n",
"\n",
"Comments are as follows: <br />\n",
"\n",
"1. The shuffle command randomly orders the list of strings passed as the argument to the function. The objects 'Clusters' 'Centroid' and 'Scores' are list objects that will store information about the clusters created. The information will be stored as lists, which means these objects will ultimately be lists of lists. By ensuring that these objects are modified in the same manner at all stages of the function, it is possible to ensure that for cluster $i$ the Cluster itself, the cluster centroid, and the cluster centroid score will be located within the Cluster, Centroid and Scores objects (respectively) at index position $j$. \n",
"2. This is the behaviour when the string being evaluated is the first such string. I.e. the length of the Clusters object is 0. In this case the first string is used to initialize the first cluster. \n",
"3. Loop through the clusters and calculate the jaro-distance between the string being evaluated, and the centroid of each cluster and store the distance measures in a list object names SPScores\n",
"4. Find the max value of the calculated jaro-distances, and the index position of that value in the SPScores list. This index value will also be the index value for the corresponding cluster, centroid and score in the list objects as discussed above\n",
"5. If the max value is above a given threshold, then append the string being evaluated to the relevant cluster. \n",
"6. If the length of the corresponding list item in the Scores object is equal to zero, then this is the first match that has been made with centroid of the relevant cluster. In that case, append the max value of the jaro distance to the empty list within Scores. \n",
"7. If the length as discussed above is not zero, then this is not the first such match. If then the max jaro score for the string being evaluated is larger than the previous scored match, then the relevant list item is updated to reflect the increase in score, and the centroid for that cluster is set as the string being evaluated. This is an attempt to have the centroid as the 'truest' version of that string. However, this method is totally arbitrary with respect to the order that that strings are evaluated. \n",
"8. If Matched = 0 then no jaro distance score was above the threshold for the string being evaluated. In this case the string then becomes the initializer of a new centroid.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, let's see this at work with some real data. The following are (modified) style names as observed in some work conducted here in Bangladesh. The above function will be used to group those style names into clusters of strings that potentially represent the same style, but have minor differences in the string value assigned to them. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Read in some data"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Styles = list(pd.Series(pd.read_csv(r'C:\\Users\\rcreedon\\Dropbox\\GIZSupervisor\\DATA\\Production_Data\\STP_Data\\Data_Sets\\Wave1\\1005\\1005_all_merged.csv')['style'].unique()))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 4
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Delete missing values, remove multiple white spaces, make lower case, remove special characters"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"del Styles[Styles.index(np.nan)]\n",
"Styles = [re.sub('[^A-Za-z0-9 ' ']+', '', style) for style in Styles]\n",
"Styles = [style.lower() for style in Styles]\n",
"Styles = [\" \".join(style.split()) for style in Styles]\n",
"Styles"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 5,
"text": [
"['denim jacket',\n",
" 'denim vest',\n",
" 'jonas long',\n",
" '2618 longer denim',\n",
" 'lilen trs',\n",
" 'ride',\n",
" 'tye dye jean',\n",
" 'jonas short',\n",
" 'jacket 2002',\n",
" 'dobby short',\n",
" 'parker chino',\n",
" '550 pant',\n",
" 'ride 510',\n",
" 'chambrey117',\n",
" 'space treggins',\n",
" 'jhonny boxer',\n",
" 'new skinny',\n",
" 'clint',\n",
" 'todd jkt',\n",
" 'jacket 2001',\n",
" 'back to school',\n",
" 'jacket 2001',\n",
" 'reidun parka',\n",
" 'mixmatch',\n",
" 'reidun parkalining',\n",
" 'parko chino',\n",
" 'camden jkt',\n",
" 'cb32405510',\n",
" 'bomber jkt',\n",
" '5 pkt cord',\n",
" 'shairt615',\n",
" 'shairt537',\n",
" 'shairt564',\n",
" 'love trs340',\n",
" '1zb153tpant',\n",
" '1zb153tjkt',\n",
" 'jacketswear',\n",
" 'jacketbk to schoolboys',\n",
" 'jacketbk to schoolgirls',\n",
" 'jacket253ke',\n",
" '14011876']"
]
}
],
"prompt_number": 5
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Create a clusters object"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Clusters = SLINK(Styles, 0.8)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 6
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Sort clusters object according to size of the elements"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Clusters.sort(lambda x,y: cmp(len(y), len(x)))\n",
"Clusters"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 7,
"text": [
"[['jacket 2002', 'jacket 2001', 'jacket 2001'],\n",
" ['shairt615', 'shairt537', 'shairt564'],\n",
" ['jacketbk to schoolboys', 'back to school', 'jacketbk to schoolgirls'],\n",
" ['1zb153tjkt', '1zb153tpant'],\n",
" ['parker chino', 'parko chino'],\n",
" ['reidun parkalining', 'reidun parka'],\n",
" ['ride 510', 'ride'],\n",
" ['denim jacket', 'denim vest'],\n",
" ['jacketswear'],\n",
" ['tye dye jean'],\n",
" ['love trs340'],\n",
" ['14011876'],\n",
" ['bomber jkt'],\n",
" ['2618 longer denim'],\n",
" ['5 pkt cord'],\n",
" ['todd jkt'],\n",
" ['jacket253ke'],\n",
" ['camden jkt'],\n",
" ['lilen trs'],\n",
" ['jonas short'],\n",
" ['mixmatch'],\n",
" ['chambrey117'],\n",
" ['jonas long'],\n",
" ['550 pant'],\n",
" ['clint'],\n",
" ['jhonny boxer'],\n",
" ['cb32405510'],\n",
" ['dobby short'],\n",
" ['space treggins'],\n",
" ['new skinny']]"
]
}
],
"prompt_number": 7
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It appears to have worked rather well. Admittedly I began with a prior that that threshold should be 0.85 (based on work done in previous notebooks), but this had to be lowered to achieve the above somewhat sensible clusters. Sensible, only in that they conform to what I would think of as potentially matched. \n",
"\n",
"In fact this method seems to be pretty decent for what I am trying to do, therefore I am going to pause with the clustering methods, and move on to how the above method could be used in combination with the stripping of generic components method previously discussed. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Combining this Method with Generic Component Stripping"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As discussed in the previous notebook, I believe that for the type of string I am working with, it is beneficial to strip out the generic components of the strings being work with. A recapitulation of that method is not going to be given here, but I will now combine the methods. \n",
"\n",
"One of the somewhat unfortunate side effects of stripping away generic components, is that it is theoretically possible that the resulting list of strings will have multiple entries that are exactly the same. In order for the clustering to be useful it is important that after the clustering has happened, the original string can be identified in order that it can be modified if thought necessary. This means, some unbreakable link needs to be be formed between the original string and its stripped counterpart.\n",
"\n",
"It is possible that this can be done using a hash table, however the method I prefer to explore here is of creating a new class of object that contains both the original string and the stripped version. This is achieved below:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"class Stripped:\n",
" 'Common base class for all stripped stings'\n",
" \n",
" def __init__(self, original, GenericAll, GenericWhite = None, DelWhite = False):\n",
" # Class attribute that is the string in its original format\n",
" \n",
" self.original = original\n",
" StrVal = original.lower()\n",
" StrVal = re.sub('[^A-Za-z0-9 ' ']+', ' ', StrVal)\n",
" \n",
" #strip out all occurences of sub-strings from GenericAll list that appear anywhere in the string\n",
" for word in GenericAll:\n",
" RegEx1 = re.compile('' + word)\n",
" StrVal = re.sub(RegEx1, '', StrVal)\n",
" \n",
" # If provided as argument strip out all occurences of sub-string when that sub string is surrounded by \n",
" # whitespace (i.e. is not part of another substring-sequence)\n",
" if not GenericWhite == None:\n",
" for word in GenericWhite:\n",
" RegEx2 = re.compile(r'\\b' + word + r'\\b')\n",
" StrVal = re.sub(RegEx2, '', StrVal)\n",
" \n",
" # Removes special characters, removes all whitespace\n",
" if DelWhite == True:\n",
" StrVal = StrVal.replace(' ', '')\n",
" \n",
" # Class attribute that is the stipped string\n",
" self.stripped = StrVal\n"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 8
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's look at the components of this class object. Each time an instance of the class Stripped is created, the following arguments must be passed:\n",
"\n",
"+ Original - this is the original string that is to be manipulated and stored as an attribute of the Stripped Class\n",
"+ GenericAll - this is a list of the words (i.e. sub-strings) that are to be stripped out of the string before the clustering occurs. These sub-strings will be stripped out no matter where they appear in the string sequence of characters (i.e. possibly from the middle of words/sub-strings) For information about to derive this list from the data, then see the previous notebook. In theory, this could all be done totally automatically, and this may be something I explore toward the end of this notebook. \n",
"\n",
"The following arguments are optional:\n",
"\n",
"+ GenericWhite - this is a list of the words (i.e sub-strings) that will be stripped out. Unlike the GenericAll list these sub strings will only be stripped out if they are surrounded by whitespace (i.e. they are not part of another sub string)\n",
"+ DelWhite - set DelWhite equal to True if it desired to compare strings that have no whitespace. \n",
"\n",
"The StippedClass object has two attributes.\n",
"\n",
"1. The original string\n",
"2. The stripped string\n",
"\n",
"The stripped string is the original string in lower case with special characters removed, and all instances of the sub-strings listed in GenericAll removed. If GenericWhite is passed as an argument then those sub-strings are also removed (when standalone sub-sqtrings). If DelWhite = True then all whitespaces are also removed."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In order to use the SLINK function on this Stripped Class, some modifications are necessary:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def SlinkSC(ClassList, Threshold):\n",
" #1\n",
" random.shuffle(ClassList)\n",
" \n",
" \n",
" Clusters = []\n",
" ClustersStripped = []\n",
" Centroid = []\n",
" Scores = []\n",
" \n",
" for StrippedClass in ClassList: \n",
" SPScores = []\n",
" Matched = 0\n",
" \n",
" if len(Clusters) == 0:\n",
" Clusters.append([StrippedClass.original])\n",
" ClustersStripped.append([StrippedClass.stripped])\n",
" Centroid.append([StrippedClass.stripped, StrippedClass.original])\n",
" Scores.append([])\n",
" continue\n",
" \n",
" for ClustNum in xrange(len(Clusters)):\n",
" Dist = jf.jaro_distance(StrippedClass.stripped, Centroid[ClustNum][0])\n",
" SPScores.append(Dist)\n",
" \n",
" MaxVal = max(SPScores)\n",
" MaxInd = SPScores.index(max(SPScores))\n",
" \n",
" if MaxVal >= Threshold:\n",
" Clusters[MaxInd].append(StrippedClass.original)\n",
" ClustersStripped[MaxInd].append(StrippedClass.stripped)\n",
" \n",
" if len(Scores[MaxInd]) == 0:\n",
" Scores[MaxInd].append(MaxVal) \n",
" else:\n",
" if MaxVal > Scores[MaxInd][0]:\n",
" Scores[MaxInd][0] = MaxVal\n",
" Centroid[MaxInd][0] = StrippedClass.stripped\n",
" Centroid[MaxInd][1] = StrippedClass.original\n",
" Matched = 1\n",
" \n",
" if Matched ==0: \n",
" Clusters.append([StrippedClass.original])\n",
" ClustersStripped.append([StrippedClass.stripped])\n",
" Centroid.append([StrippedClass.stripped, StrippedClass.original])\n",
" Scores.append([])\n",
" \n",
" return [Clusters, ClustersStripped, Centroid]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 9
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The function now accepts rather than a list of strings, a list of StrippedClass objects. The matching is done on the 'stripped' attribute of each object (i.e. the stripped strings). However, two cluster lists are now created and returned. The first one is a list of the clusters where the original string values are reported. It is primarily this one that will be of use. The second one is list of the cluster where the stripped string values are reported. This is primarily for information purposes. \n",
"\n",
"The function returns a list of three lists, the first as noted above is the list of clusters that reports the original string names, the second is the list of clusters that reports the stripped string names, the third is the list of centroids in list format, the first element being the stripped version, the second the original string (to be used in setting naming conventions)\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The method, including the stripping of generic components is now demonstrated with the same style data as above:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Step 1: Read Data & Determine Generic Components** <br />\n",
"NB for the sake of convenience I strip out special characters and make lower case at this stage, this is not strictly necessary as this will done when creating the Stripped Class objects\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Read in some data, stip special characters etc. (as above)"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Styles = list(pd.Series(pd.read_csv(r'C:\\Users\\rcreedon\\Dropbox\\GIZSupervisor\\DATA\\Production_Data\\STP_Data\\Data_Sets\\Wave1\\1005\\1005_all_merged.csv')['style'].unique()))\n",
"del Styles[Styles.index(np.nan)]\n",
"Styles = [re.sub('[^A-Za-z0-9 ' ']+', '', style) for style in Styles]\n",
"Styles = [style.lower() for style in Styles]\n",
"Styles = [\" \".join(style.split()) for style in Styles]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 10
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Create dictionary to determine generic components"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"WordDict = {}\n",
"for style in Styles:\n",
" for word in style.split(' '):\n",
" if word not in WordDict:\n",
" WordDict[word] = 1\n",
" else:\n",
" WordDict[word] +=1\n",
"for word, value in WordDict.iteritems():\n",
" if value > 1:\n",
" print word, value"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"denim 3\n",
"reidun 2\n",
"2001 2\n",
"jacketbk 2\n",
"to 3\n",
"jkt 3\n",
"jonas 2\n",
"chino 2\n",
"short 2\n",
"ride 2\n",
"jacket 4\n"
]
}
],
"prompt_number": 11
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Step 2: Create Lists of Generic Words to be Stripped Out**<br />\n",
"NB in this instance I do not wish to create a GenericWhite list\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"GenericAll = ['denim', 'jkt', 'chino', 'short', 'jacket']"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 12
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Step 3: Create list of Stripped Class Objects**"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ClassList = [Stripped(elem, GenericAll, DelWhite = True) for elem in Styles]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 13
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Step 4: Apply the SlinkSC Function to the list of Stripped Class Objects** <br />\n",
"NB I also separate out the lists, and sort them according to the length of the sub-lists"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Clustered = SlinkSC(ClassList, 0.8)\n",
"ClustersOriginal = Clustered[0]\n",
"ClustersOriginal.sort(lambda x,y: cmp(len(y) , len(x)))\n",
"ClustersStripped = Clustered[1]\n",
"ClustersStripped.sort(lambda x,y: cmp(len(y) , len(x)))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 14
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Step 5: View the Clusters**"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"#Original Clusters\n",
"ClustersOriginal[:8]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 15,
"text": [
"[['jacket 2001', 'jacket 2001', 'jacket 2002'],\n",
" ['shairt564', 'shairt537', 'shairt615'],\n",
" ['parker chino', 'parko chino'],\n",
" ['reidun parkalining', 'reidun parka'],\n",
" ['1zb153tpant', '1zb153tjkt'],\n",
" ['jonas short', 'jonas long'],\n",
" ['ride 510', 'ride'],\n",
" ['jacketbk to schoolboys', 'jacketbk to schoolgirls']]"
]
}
],
"prompt_number": 15
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"#Stripped Clusers\n",
"ClustersStripped[:8]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 16,
"text": [
"[['2001', '2001', '2002'],\n",
" ['shairt564', 'shairt537', 'shairt615'],\n",
" ['parker', 'parko'],\n",
" ['reidunparkalining', 'reidunparka'],\n",
" ['1zb153tpant', '1zb153t'],\n",
" ['jonas', 'jonaslong'],\n",
" ['ride510', 'ride'],\n",
" ['bktoschoolboys', 'bktoschoolgirls']]"
]
}
],
"prompt_number": 16
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The clusters as above have been recreated, but the threshold was raised to 0.8 (this is not\n",
"\n",
"So this system could be useful it seems. However, in order to investigate further, a more complex data set if needed. This is looked at below:"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"A More Complex Data Set"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Read in some data"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Bstyles = list(pd.read_csv('ExampleData.csv')['style'].unique())"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 17
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"List generic components to be removed (as per previous notebook)"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"GenericRemoveAll = ['bottom', 'boys', 'long', 'topb', 'tank', 'basic', 'polo', 'shorts', 'ssivts', \\\n",
" 'top', 'sslvts', 'mens', 'nightware', 'lslvts', 'nightwear', 'msp', 'lsivts', 'tee', 'large', 'slv']\n",
"\n",
"GenericWhiteSpace = ['l', 'pj', 's']"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 18
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Create list of Stripped Class obejcts from the Bstyles data"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# uses list comprehension\n",
"BClassList = [Stripped(elem, GenericRemoveAll, GenericWhiteSpace, True) for elem in Bstyles]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 19
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Apply function to the list of Stipped Class objects"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"BClustersSC = SlinkSC(BClassList, 0.85)\n",
"# Give separate names to each list in the ClusterSC object\n",
"BClustersOriginal = BClustersSC[0]\n",
"BClustersOriginal.sort(lambda x,y: cmp(len(y) , len(x)))\n",
"BClustersStripped = BClustersSC[1]\n",
"BClustersStripped.sort(lambda x,y: cmp(len(y) , len(x)))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 20
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Display first 5 clusters in original format"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"BClustersOriginal[:5]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 21,
"text": [
"[['SR-560 SR-564 S-Siv-T-S',\n",
" 'SR-542 SR-565 S-Siv-T-S',\n",
" 'SR-560 S-Siv-T-S',\n",
" 'SR-567 S-Siv-T-S',\n",
" 'SR-568 L-Siv-T-S',\n",
" 'SR-562 S-Siv-T-S',\n",
" 'SR-564 S-Siv-T-S',\n",
" 'SR-561 S-Siv-T-S'],\n",
" ['PJ-49131B Pj-49131 Nightware Bottom',\n",
" 'PJ-49131B PJ-49131 Nightware Bottom',\n",
" 'PJ-49131Tb Pj-49131 Nightware Top_b',\n",
" 'PJ-49131Tb PJ-49130/ PJ-2912 Nightware Top_b',\n",
" 'PJ-49131Tb PJ-49130/2913 Nightware Top_b',\n",
" 'PJ-49131Tb PJ-49130 Nightware Top_b',\n",
" 'PJ-49131Tb Pj-49131/2916 Nightware Top_b',\n",
" 'PJ-49131B Pj-49131 /pj-2913 Nightware Bottom'],\n",
" ['UWC-931-006 194 L-Slv-T-S',\n",
" 'UWC-931-008 194 L-Slv-T-S',\n",
" 'UWC-933-006 194 L-Slv-T-S',\n",
" 'UWC-931-006 194/192 L-Slv-T-S S-Slv-T-S',\n",
" 'UWC-933-006 192/194 S-Slv-T-S L-Slv-T-S',\n",
" 'UWC-931-008 194 S-Slv-T-S/ L-Slv-T-S',\n",
" 'UWC-931-008 194/192 L-Slv-T-S/ S-Slv-T-S',\n",
" 'UWC-931-008 192/194 S-Slv-T-S L-Slv-T-S'],\n",
" ['UWC-932-010 192/194 S-Slv-T-S L-Slv-T-S',\n",
" 'UWC-931-008 194/192 L-Slv-T-S S-Slv-T-S',\n",
" 'UWC-932-010 192 /M.S.P S-Slv-T-S /L-Slv-T-S',\n",
" 'UWC-931-008 192/194 S-Slv-T-S/ L-Slv-T-S',\n",
" 'UWC-933-006 194/192 L-Slv-T-S S-Slv-T-S',\n",
" 'UWC-932-010 192 S-Slv-T-S',\n",
" 'UWC-932-010 192/Serafeno S-Slv-T-S L-Slv-T-S',\n",
" 'UWC-931-008 192 S-Slv-T-S'],\n",
" ['674262 Ronny S-Slv-T-S',\n",
" '674265 Ronny S-Slv-T-S',\n",
" '674263 Ronny S-Slv-T-S',\n",
" '674262 Ronny S-Siv-T-S',\n",
" '674261 Ronny S-Siv-T-S',\n",
" '674262 Ronny Cocoon S-Siv-T-S Bottom',\n",
" '694265 Ronny S-Slv-T-S',\n",
" '674268 Ronny S-Siv-T-S']]"
]
}
],
"prompt_number": 21
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Display first 5 clusters in stripped format"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"BClustersStripped[:5]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 22,
"text": [
"[['sr560sr564sivt',\n",
" 'sr542sr565sivt',\n",
" 'sr560sivt',\n",
" 'sr567sivt',\n",
" 'sr568sivt',\n",
" 'sr562sivt',\n",
" 'sr564sivt',\n",
" 'sr561sivt'],\n",
" ['49131b49131',\n",
" '49131b49131',\n",
" '49131tb49131b',\n",
" '49131tb491302912b',\n",
" '49131tb491302913b',\n",
" '49131tb49130b',\n",
" '49131tb491312916b',\n",
" '49131b491312913'],\n",
" ['uwc931006194t',\n",
" 'uwc931008194t',\n",
" 'uwc933006194t',\n",
" 'uwc931006194192tt',\n",
" 'uwc933006192194tt',\n",
" 'uwc931008194tt',\n",
" 'uwc931008194192tt',\n",
" 'uwc931008192194tt'],\n",
" ['uwc932010192194tt',\n",
" 'uwc931008194192tt',\n",
" 'uwc932010192mptt',\n",
" 'uwc931008192194tt',\n",
" 'uwc933006194192tt',\n",
" 'uwc932010192t',\n",
" 'uwc932010192serafenott',\n",
" 'uwc931008192t'],\n",
" ['674262ronnyt',\n",
" '674265ronnyt',\n",
" '674263ronnyt',\n",
" '674262ronnysivt',\n",
" '674261ronnysivt',\n",
" '674262ronnycocoonsivt',\n",
" '694265ronnyt',\n",
" '674268ronnysivt']]"
]
}
],
"prompt_number": 22
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Interim Conclusions ###"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So how useful does this prove?\n",
"\n",
"I think the answer to that depends to a great deal on the nature of the data being examined. If deviations from the 'true' string are expected to be small, the size of the clusters small etc. then this system could work quite smoothly. When the data are simple I think this system will get good results. Also, the clusters in small data sets can be viewed with the eye and judges as to suitability.\n",
"\n",
"When the data are more complex, as above, the results are somewhat more debatable. For example, it seems likely that the 'polo' cluster above truly represents the same style. However it is not clear that the small differences in the ID component (such as a different digit) are not representative of genuine differences. \n",
"\n",
"One possible strategy to deal with this is to simply increase the threshold of what is considered a matched string as below:\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"BLClustersSC = SlinkSC(BClassList, 0.95)\n",
"# Give separate names to each list in the ClusterSC object\n",
"BLClustersOriginal = BClustersSC[0]\n",
"BLClustersOriginal.sort(lambda x,y: cmp(len(y) , len(x)))\n",
"BLClustersStripped = BClustersSC[1]\n",
"BLClustersStripped.sort(lambda x,y: cmp(len(y) , len(x)))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 23
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"BLClustersOriginal[:5]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 24,
"text": [
"[['SR-560 SR-564 S-Siv-T-S',\n",
" 'SR-542 SR-565 S-Siv-T-S',\n",
" 'SR-560 S-Siv-T-S',\n",
" 'SR-567 S-Siv-T-S',\n",
" 'SR-568 L-Siv-T-S',\n",
" 'SR-562 S-Siv-T-S',\n",
" 'SR-564 S-Siv-T-S',\n",
" 'SR-561 S-Siv-T-S'],\n",
" ['PJ-49131B Pj-49131 Nightware Bottom',\n",
" 'PJ-49131B PJ-49131 Nightware Bottom',\n",
" 'PJ-49131Tb Pj-49131 Nightware Top_b',\n",
" 'PJ-49131Tb PJ-49130/ PJ-2912 Nightware Top_b',\n",
" 'PJ-49131Tb PJ-49130/2913 Nightware Top_b',\n",
" 'PJ-49131Tb PJ-49130 Nightware Top_b',\n",
" 'PJ-49131Tb Pj-49131/2916 Nightware Top_b',\n",
" 'PJ-49131B Pj-49131 /pj-2913 Nightware Bottom'],\n",
" ['UWC-931-006 194 L-Slv-T-S',\n",
" 'UWC-931-008 194 L-Slv-T-S',\n",
" 'UWC-933-006 194 L-Slv-T-S',\n",
" 'UWC-931-006 194/192 L-Slv-T-S S-Slv-T-S',\n",
" 'UWC-933-006 192/194 S-Slv-T-S L-Slv-T-S',\n",
" 'UWC-931-008 194 S-Slv-T-S/ L-Slv-T-S',\n",
" 'UWC-931-008 194/192 L-Slv-T-S/ S-Slv-T-S',\n",
" 'UWC-931-008 192/194 S-Slv-T-S L-Slv-T-S'],\n",
" ['UWC-932-010 192/194 S-Slv-T-S L-Slv-T-S',\n",
" 'UWC-931-008 194/192 L-Slv-T-S S-Slv-T-S',\n",
" 'UWC-932-010 192 /M.S.P S-Slv-T-S /L-Slv-T-S',\n",
" 'UWC-931-008 192/194 S-Slv-T-S/ L-Slv-T-S',\n",
" 'UWC-933-006 194/192 L-Slv-T-S S-Slv-T-S',\n",
" 'UWC-932-010 192 S-Slv-T-S',\n",
" 'UWC-932-010 192/Serafeno S-Slv-T-S L-Slv-T-S',\n",
" 'UWC-931-008 192 S-Slv-T-S'],\n",
" ['674262 Ronny S-Slv-T-S',\n",
" '674265 Ronny S-Slv-T-S',\n",
" '674263 Ronny S-Slv-T-S',\n",
" '674262 Ronny S-Siv-T-S',\n",
" '674261 Ronny S-Siv-T-S',\n",
" '674262 Ronny Cocoon S-Siv-T-S Bottom',\n",
" '694265 Ronny S-Slv-T-S',\n",
" '674268 Ronny S-Siv-T-S']]"
]
}
],
"prompt_number": 24
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This makes what may in the end turn out to be more sensible clusters, but possibly increasing the threshold means that it is possible that too many clusters are created, thereby creating a situation where true matches are not clustered together. Notice the difference in the number of clusters at the different thresholds below:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"# Number of clusters with threshold at 0.85\n",
"print len([elem for elem in BClustersOriginal if len(elem) > 1])\n",
"\n",
"# Number of clusters with threshold at 0.95\n",
"print len([elem for elem in BLClustersOriginal if len(elem) > 1])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"101\n",
"101\n"
]
}
],
"prompt_number": 25
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A second strategy that could prove useful is to use another data point to verify the clusters. This will be particularly useful when clustering strings that have other attributes that are consistent when the strings may be inconsistent. One possible strategy would be to set the threshold iteratively until such time as the maximum number of matches can be made within cluster by verifying with an alternative data point. \n",
"\n",
"For the data currently being studied, the SMV would be a good candidate. For name matching for example, age or similar would be a sensible candidate.\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Confirming Clusters with Alternate Varible"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Read in some data"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"DF = DataFrame(pd.read_csv('ExampleData.csv'))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 26
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Before proceeding to look at possible functions, let's look at an example. Within the second cluster of the data, the unique SMVs for each of the styles that have been clustered together are as follows:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"#Example 1\n",
"for style in BClustersOriginal[1]:\n",
" print DF[DF.style == style]['smv'].unique()\n",
"print BClustersOriginal[1]\n",
"print BClustersStripped[1]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[ 8.97]\n",
"[ 8.97]\n",
"[ 8.02]\n",
"[ 8.02]\n",
"[ 8.02]\n",
"[ 8.02]\n",
"[ 8.02]\n",
"[ 8.97]\n",
"['PJ-49131B Pj-49131 Nightware Bottom', 'PJ-49131B PJ-49131 Nightware Bottom', 'PJ-49131Tb Pj-49131 Nightware Top_b', 'PJ-49131Tb PJ-49130/ PJ-2912 Nightware Top_b', 'PJ-49131Tb PJ-49130/2913 Nightware Top_b', 'PJ-49131Tb PJ-49130 Nightware Top_b', 'PJ-49131Tb Pj-49131/2916 Nightware Top_b', 'PJ-49131B Pj-49131 /pj-2913 Nightware Bottom']\n",
"['49131b49131', '49131b49131', '49131tb49131b', '49131tb491302912b', '49131tb491302913b', '49131tb49130b', '49131tb491312916b', '49131b491312913']\n"
]
}
],
"prompt_number": 27
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"#Example 2\n",
"for style in BLClustersOriginal[0]:\n",
" print DF[DF.style == style]['smv'].unique()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[ 17.05]\n",
"[ 10.27]\n",
"[ 17.05]\n",
"[ 18.61]\n",
"[ 12.96]\n",
"[ 24.61]\n",
"[ 17.05]\n",
"[ 22.28]\n"
]
}
],
"prompt_number": 28
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"It seems clear to me that the example drawn from the higher threshold clustering (example 2) represents the same style.\n",
"\n",
"The first example is a bit trickier. Within this cluster, it appears that the cluster has been formed such that in fact it captures strings that relate to two underlying 'true' styles. The question is, should the threshold be raised such that these styles are grouped separately (and would this even be possible?), or should I accept the overlap in the cluster an separately claim that within cluster there may be multiple styles?\n",
"\n",
"\n",
"I think the first thing to try would be to iteratively set the threshold to maximize the number of groupings that have consistent SWVs within each cluster.\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def maxClusters(ClassList, startThreshold, stopThreshold, step):\n",
" \n",
" Threshold = startThreshold\n",
" ConsistentClusters = []\n",
" \n",
" while Threshold <= stopThreshold:\n",
" ConsistentCount = 0\n",
" TotClusters = SlinkSC(ClassList, Threshold)\n",
" MultiClusters = [elem for elem in TotClusters[0] if len(elem) > 1]\n",
" for elem in MultiClusters:\n",
" MultiSMV = list(itertools.chain(*[DF[DF.style == style]['smv'].unique() for style in elem]))\n",
" if len(set(MultiSMV)) == 1:\n",
" ConsistentCount +=1\n",
" ConsistentClusters.append(ConsistentCount)\n",
" Threshold += step\n",
" \n",
" return ConsistentClusters\n",
"\n",
" \n",
" "
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 29
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The above function will effectively iteratively call the SlinkSC function on the list of Stripped Class objects using different threshold values, that fall between startThreshold, and stopThreshold, and move in steps as specified by the user in the function arguments. \n",
"\n",
"For the clusters that are produced at iterations, the unique SMVs are pulled from the underlying DF and placed in a list. If all of the unique SMVs in the cluster form a set of length 1, then they are the same, and the cluster is therefore correctly specified (i.e. all strings in fact represent the same underlying style). In this case, then the ConsistentCount is incremented by one. \n",
"\n",
"After each iteration the ConsistenCount variable is append to a list and after the iterations are complete this list is returned. \n",
"\n",
"The returned list allows the user to identify at which threshold value the most number of consistent clusters are identified.\n",
"\n",
"Let's see an example, in fact let's see three examples"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print maxClusters(BClassList, 0.7, 0.95, 0.025)\n",
"print maxClusters(BClassList, 0.7, 0.95, 0.025)\n",
"print maxClusters(BClassList, 0.7, 0.95, 0.025)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[27, 27, 32, 35, 42, 47, 60, 50, 43, 48]\n",
"[25, 32, 31, 43, 42, 53, 58, 55, 42, 42]"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"[21, 26, 32, 43, 43, 53, 57, 54, 46, 41]"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n"
]
}
],
"prompt_number": 30
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What is intriguing about the above is that even though the exact same commands were issued, the results were different. The reason for this is that the list of Stripped Class objects is shuffled in a different way upon each iteration, and as was noted above, the clusters this method generates are not independent of the way in which the data are sorted. \n",
"\n",
"So, this is not necessarily a problem that can be dealt with. However, it would be sensible to run the above analysis a number of times in order to gauge where to best set the threshold. This is now done below\n",
"\n",
"NB the computer is doing a lot of work here so it may take some time to compute!\n",
"!"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Optimum = []\n",
"for x in xrange(10):\n",
" L = maxClusters(BClassList, 0.7, 0.95, 0.025)\n",
" Ind = L.index(max(L))\n",
" Val = 0.7 + (Ind*0.025)\n",
" Optimum.append(Val)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 31
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Optimum"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 32,
"text": [
"[0.875, 0.85, 0.85, 0.825, 0.85, 0.85, 0.85, 0.85, 0.85, 0.85]"
]
}
],
"prompt_number": 32
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"So it seems pretty clear that the optimum for this data is somewhere around 0.85. But where exactly? Well let's narrow the search:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Optimum2 = []\n",
"for x in xrange(10):\n",
" L = maxClusters(BClassList, 0.82, 0.88, 0.01)\n",
" Ind = L.index(max(L))\n",
" Val = 0.82 + (Ind*0.01)\n",
" Optimum2.append(Val)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 33
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print Optimum2\n",
"print np.mean(Optimum2)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[0.86, 0.86, 0.87, 0.85, 0.84, 0.87, 0.85, 0.86, 0.86, 0.86]\n",
"0.858\n"
]
}
],
"prompt_number": 34
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For this data set, it appears that 0.85 is the threshold that maximises the consistency of the clusters."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now, let's run the analysis again, but this time to actually identify the clusters which are consistent, and their centroid name. These will be eligible for automatic renaming.\n",
"\n",
"NB as this function is refined below, the arguments are described below rather than here. "
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def IdentifyClusters(ClassList, Threshold, df, col1, col2):\n",
"\n",
" ClustersDict = {}\n",
" Clusters = SlinkSC(ClassList, Threshold)\n",
" ClustersOriginal = Clusters[0]\n",
" ClustersCentroid = Clusters[2]\n",
" \n",
" IndList = [x for x in xrange(len(ClustersOriginal)) if len(ClustersOriginal[x]) > 1]\n",
" \n",
" MultiClusters = [ClustersOriginal[Ind] for Ind in IndList]\n",
" MultiCentroid = [ClustersCentroid[Ind] for Ind in IndList]\n",
" \n",
" for cluster in xrange(len(MultiClusters)):\n",
" MultiSMV = list(itertools.chain(*[df[df[col1] == elem][col2].unique() for elem in MultiClusters[cluster]]))\n",
" if len(set(MultiSMV)) == 1:\n",
" ClustersDict[MultiCentroid[cluster][1]] = MultiClusters[cluster]\n",
" \n",
" return ClustersDict\n",
" "
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 35
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Create a dictionary of matched clusters uding the IdentifyClusters function"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MatchedDict = IdentifyClusters(BClassList, 0.85, DF, 'style', 'smv')"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 36
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Display the length of th dictionary"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"len(MatchedDict)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 37,
"text": [
"60"
]
}
],
"prompt_number": 37
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Count the number of clustered strings"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Count = 0\n",
"for key, value in MatchedDict.iteritems():\n",
" for elem in value:\n",
" Count +=1\n",
" \n",
"Count"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 38,
"text": [
"174"
]
}
],
"prompt_number": 38
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Display the first ten cluster names and associated cluster"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"for Key in MatchedDict.keys()[:10]:\n",
" print 'The cluster name is ' + Key \n",
" print MatchedDict[Key]\n",
" print "
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"The cluster name is 345750 Samira/Bruce Tee Samira nightgown\n",
"['345750 Samira/Bruce Tee Samira nightgown', '345750 Samira nightgown']\n",
"\n",
"The cluster name is 615950 Benny-j / SR-561 Bottom S-Siv-T-S\n",
"['615950 Benny-J SR-541 Bottom S-Siv-T-S', '615950 Benny-J SR-560 Bottom S-Siv-T-S', '615950 Benny-j / SR-561 Bottom S-Siv-T-S', '615951 Benny-j/ SR-542 Bottom/ S-Siv-T-S']\n",
"\n",
"The cluster name is PJ-2912 PJ-2912/2922 Top\n",
"['PJ-2912 PJ-2912/2922 Top', 'PJ-2912 PJ-2922 Top']\n",
"\n",
"The cluster name is Nightwear s slv top (PJ-0405)\n",
"['Nightwear s slv top (PJ-0405)', 'Nightwear l slv top (PJ-0405)']\n",
"\n",
"The cluster name is PJ-50307TV PJ-50306 /Nap-56/100 LSV\n",
"['PJ-50307TV PJ-50306 /Nap-56/100 LSV', 'PJ-50307TV PJ-50306 LSV']\n",
"\n",
"The cluster name is PJ-2913T PJ-2923 Top\n",
"['PJ-2913T PJ-2913 Top', 'PJ-2913T PJ-2313 Top', 'PJ-2913T PJ-2923 Top']\n",
"\n",
"The cluster name is 674262 Ronny B.P.D S-Slv-T-S\n",
"['674262 Ronny B.P.D S-Slv-T-S', '674262 Ronny S-Slv-T-S']\n",
"\n",
"The cluster name is 979650 Art Tee/Art tank S-Siv-T-S Tank Top\n",
"['979650 Art Tee/Art tank S-Siv-T-S Tank Top', '979650 Art Tee S-Siv-T-S']\n",
"\n",
"The cluster name is 436002 Vito/ Superman S-Siv-T-S Tank Top\n",
"['436002 Vito/ Superman S-Siv-T-S Tank Top', '436002 Vito S-Siv-T-S']\n",
"\n",
"The cluster name is 674262 Cocoon pj/ Ronny Bottom S-Siv-T-S\n",
"['674262 Cocoon pj/ Ronny Bottom S-Siv-T-S', '674262 Ronny Cocoon S-Siv-T-S Bottom']\n",
"\n"
]
}
],
"prompt_number": 39
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To my mind this is pretty successful. Based upon the initial running of the program (which will change with subsequent runs due to changing nature of the clusters) this reduces 145 style names and condenses them into 52.\n",
"\n",
"It seems natural that once this stage has happened, then the analysis should be re-run with the new group of strings, until no more clusters are identified. I am not yet sure about this, so will investigate further. In any case it should be decided what to do with the clusters that show multiple SMVs. \n",
"\n",
"Let's actually look at the failed clusters (i.e. those with multiple SMV measures). This may help in guiding future action. "
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ForFailed = SlinkSC(BClassList, 0.85)\n",
"Potential = [elem for elem in ForFailed[0] if len(elem) > 0]\n",
"\n",
"# Print a selection of the failed clusters\n",
"for elem in Potential[:15]:\n",
" SMVs = list(itertools.chain(*[DF[DF.style == style]['smv'].unique() for style in elem]))\n",
" if len(set(SMVs)) != 1:\n",
" print elem\n",
" print SMVs\n",
" print"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"['SR-560 S-Siv-T-S', 'SR-560 SR-564 S-Siv-T-S', 'SR-541 S-Siv-T-S', 'SR-561 S-Siv-T-S', 'SR-562 S-Siv-T-S', 'SR-564 S-Siv-T-S', 'SR-568 L-Siv-T-S', 'SR-567 S-Siv-T-S']\n",
"[17.050000000000001, 17.050000000000001, 12.960000000000001, 22.280000000000001, 24.609999999999999, 17.050000000000001, 12.960000000000001, 18.609999999999999]\n",
"\n",
"['825211T Daniella Top', '825211B Daniella Bottom']\n",
"[6.4500000000000002, 6.75]\n",
"\n",
"['185480Ba Cocoon Coocon Bottom', '354750B Cocoon Pj Coocon Bottom', '185480Bb Cocoon Pj Coocon Bottom', '185480Tb Cocoon Coocon Top_b', '185480Ta Cocoon Coocon Top_a', '185480Ba Cocoon Pj Coocon Bottom']\n",
"[4.9500000000000002, 5.4500000000000002, 5.4500000000000002, 5.7400000000000002, 5.2400000000000002, 4.9500000000000002]\n",
"\n",
"['Randy shorts btm (820880)', 'Randy tank top (820880)']\n",
"[6.9500000000000002, 4.4400000000000004]\n",
"\n",
"['UWC-932-010 192/194 S-Slv-T-S L-Slv-T-S', 'UWC-932-010 192 S-Slv-T-S', 'UWC-932-010 192 /M.S.P S-Slv-T-S /L-Slv-T-S', 'UWC-931-006 194/192 L-Slv-T-S S-Slv-T-S', 'UWC-933-006 192/194 S-Slv-T-S L-Slv-T-S', 'UWC-933-006 194/192 L-Slv-T-S S-Slv-T-S']\n",
"[26.030000000000001, 26.030000000000001, 26.030000000000001, 26.559999999999999, 26.559999999999999, 26.559999999999999]\n",
"\n",
"['PJ-49131B Pj-49131 Nightware Bottom', 'PJ-49131Tb PJ-49130 Nightware Top_b', 'PJ-49131Tb Pj-49131/2916 Nightware Top_b', 'PJ-49131B PJ-49131 Nightware Bottom', 'PJ-49131Tb Pj-49131 Nightware Top_b', 'PJ-49131Tb PJ-49130/ PJ-2912 Nightware Top_b', 'PJ-49131B Pj-49131 /pj-2913 Nightware Bottom', 'PJ-49131Tb PJ-49130/2913 Nightware Top_b']\n",
"[8.9700000000000006, 8.0199999999999996, 8.0199999999999996, 8.9700000000000006, 8.0199999999999996, 8.0199999999999996, 8.9700000000000006, 8.0199999999999996]\n",
"\n",
"['BS-1105 PJ-1105 Top', 'BS-1106 Pj-1106 Top', 'BS-1105 PJ-1105/49130 Top', 'BS-1106 Pj-1106/49131 Top']\n",
"[16.350000000000001, 18.149999999999999, 16.350000000000001, 18.149999999999999, 18.149999999999999, 18.149999999999999]\n",
"\n",
"['674262 Ronny B.P.D S-Slv-T-S', '674262 Ronny S-Siv-T-S', '674262 Ronny S-Slv-T-S', '674262 Ronny Cocoon S-Siv-T-S Bottom', '674263 Ronny S-Slv-T-S', '674261 Ronny S-Siv-T-S', '674268 Ronny S-Siv-T-S', '674265 Ronny S-Slv-T-S', '674269 Ronny S-Slv-T-S', '694265 Ronny S-Slv-T-S']\n",
"[5.7800000000000002, 5.7800000000000002, 5.7800000000000002, 5.7800000000000002, 5.7800000000000002, 5.7800000000000002, 6.4000000000000004, 5.7800000000000002, 6.4000000000000004, 5.7800000000000002]\n",
"\n"
]
}
],
"prompt_number": 40
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Let's look at the output (may have changed due to changing nature of the data). Observe the following:\n",
"\n",
" Cluster: ['332860Pb M.w.P /M.S.p/194 Polo', '332860Pc M.w.P /M.S.p Polo'] \n",
" SMVs: [17.949999999999999, 18.140000000000001]\n",
"\n",
"Here the cluster has two style names in it, and two SMVs. Quite clearly these cannot be thought of as representing the same style. NB I am not sure what is going on with the floating points here. \n",
"\n",
"However, now look at the following:\n",
"\n",
" Cluster: ['PJ-2913T PJ-2913 Top', 'PJ-2913T PJ-2313 Top', 'PJ-2913B PJ-2913 Bottom', 'PJ-2913B pj-2913 Bottom', 'PJ-2913B PJ-2923 Bottom']\n",
" SMVs: [9.1600000000000001, 9.1600000000000001, 7.8700000000000001, 7.8700000000000001, 7.8700000000000001]\n",
" \n",
"In this case it seems like the cluster has picked up two underlying styles one related to the top half of a pijama set, and the other the bottom half. That these were clustered together is a by-product of stripping out the generic components. I think that it is pretty clear that within this cluster there are two separate clusters of styles, that are cleaning identified by the SMVs.\n",
"\n",
"How then to proceed?\n",
"\n",
"I think given the high string matching threshold, I can be pretty comfortable that these stings represent, if not the same exact product, then at least the same product family. Therefore, a rule I propose to use, is to cluster within groups based upon the unique SMV being observed more than once. An attempt to do this is demonstrated below:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def ClustersRemainders(ClassList, Threshold, df, col1, col2):\n",
" #1\n",
" ClustersDict = {}\n",
" Clusters = SlinkSC(ClassList, Threshold)\n",
" ClustersOriginal = Clusters[0]\n",
" ClustersCentroid = Clusters[2]\n",
" \n",
" #2\n",
" IndList = [x for x in xrange(len(ClustersOriginal)) if len(ClustersOriginal[x]) > 1] \n",
" MultiClusters = [ClustersOriginal[Ind] for Ind in IndList]\n",
" MultiCentroid = [ClustersCentroid[Ind] for Ind in IndList]\n",
" \n",
" #3\n",
" for cluster in xrange(len(MultiClusters)):\n",
" MultiSMV = list(itertools.chain(*[df[df[col1] == elem][col2].unique() for elem in MultiClusters[cluster]]))\n",
" if len(set(MultiSMV)) == 1:\n",
" ClustersDict[MultiCentroid[cluster][1]] = MultiClusters[cluster]\n",
" else:\n",
" \n",
" #4\n",
" if len(MultiSMV) == len(MultiClusters[cluster]):\n",
" for smv in list(set(MultiSMV)):\n",
" if MultiSMV.count(smv) >= 2:\n",
" BoolList = [True if elem == smv else False for elem in MultiSMV]\n",
" StrList = [MultiClusters[cluster][x] for x in xrange(len(BoolList)) if BoolList[x] == True]\n",
" StrList.sort(lambda x, y: cmp(len(x), len(y)))\n",
" ClustersDict[StrList[0]] = StrList\n",
" \n",
" \n",
" return ClustersDict"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 41
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"I think this will be the final identification function and so the workings are explained here.\n",
"\n",
"The function is for use in identifying correctly specified clusters of strings based upon verifying the cluster using some additional data source. The function only works if the strings being clustered and the additional data point are drawn from the **same pandas data frame**. \n",
"\n",
"The function accepts five arguments: <br />\n",
"\n",
"1. ClassList - a list of Stripped Class objects representing the strings to be clustered\n",
"2. Threshold - the threshold Jaro-distance score on which the clusters are formed\n",
"3. df - the data frame from which the strings being clustered ar drawn and from which the additional data is drawn\n",
"4. col1 - the column name in the data frame from where the strings being clustered were drawn\n",
"5. col2 - the column name in the data frame from where the additional data are drawn. \n",
"\n",
"The function returns a dictionary where the key is the centroid name of the cluster and value is a list of the strings that form the cluster. Within each cluster the SMVs associated with evry style name are identical. \n",
"\n",
"**Comments:**\n",
"\n",
"1. Here the SlinkSC function is called on the ClassList, and the relevant objects are created according to the output of that function\n",
"2. The IndList represents the index points of the clusters that have length of above 1 (meaning that the cluster is in fact a cluster, not a lone string) Lists of clusters and their centroids are then created using this IndList.\n",
"3. For each cluster a list of the unique SMVs associated with each of the strings (style names) is created. If the length of the set of the list is one, then all SMVs are the same, and the centroid and cluster are added to the dictionary of verified clusters. \n",
"4. If the length of the set is not one, then if the number of SMVs found in the data exactly matches the length of the cluster, then there is one unique SMV per style name. For each SMV in that set, if the count of each SMV in the smv list is more than 2, then a cluster is formed by taking the shortest style name in the sub-cluster and making it the centroid, and then clustering all the strings that have the same unique SMV.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Create a dictionary of matched clusters uding the ClustersRemainders function"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"MatchedDict2 = ClustersRemainders(BClassList, 0.85, DF, 'style', 'smv')"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 42
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Display length of the dictionary"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"len(MatchedDict2)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 43,
"text": [
"94"
]
}
],
"prompt_number": 43
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Count the number of clustered strings"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Count = 0\n",
"for key, value in MatchedDict2.iteritems():\n",
" for elem in value:\n",
" Count +=1\n",
" \n",
"Count"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 44,
"text": [
"260"
]
}
],
"prompt_number": 44
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Based upon the way the code ran as I write this, this method has taken 258 style strings and clustered them in 97 style clusters, thus reducing the number of unique style names by c.150, which is a pretty big imporovement. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Modifying the String Values"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Now that the string have been clustered, I can use the dictionary generated to map the clustered strings the centroid value of each cluster. "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Create a dictionary for mapping"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"StringMap = {}\n",
"for key, value in MatchedDict2.iteritems():\n",
" for elem in value:\n",
" StringMap[elem] = key"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 45
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Display current number of unique strings"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"len(DF.style.unique())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 46,
"text": [
"454"
]
}
],
"prompt_number": 46
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Map the string clusters to the data"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"DF['style_new'] = DF.style\n",
"for row in DF.index:\n",
" try:\n",
" DF['style_new'][row] = StringMap[DF.style[row]]\n",
" except KeyError:\n",
" pass\n",
" "
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 47
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Display new number of unique strings"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"len(DF.style_new.unique())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 48,
"text": [
"288"
]
}
],
"prompt_number": 48
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The number of unique strings has been greatly reduced. \n",
"\n",
"Due to the non-perfect nature of the clustering, it might be that some strings were clustered into different clusters when they in fact represent the same underlying reality. Therefore, once this first clustering has occurred, it seems like it could be sensible to go through the process again, in order to see if more clusters can be generated. \n",
"\n",
"This is now explored:\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"A Second Clustering Pass"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Repeat the above process a second time"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SecondPass = list(DF.style_new.unique())"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 49
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SecondClassList = [Stripped(elem, GenericRemoveAll, GenericWhiteSpace, DelWhite = True) for elem in SecondPass]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 50
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SecondClusters = SlinkSC(SecondClassList, 0.85)\n",
"\n",
"# Give separate names to each list in the ClusterSC object\n",
"SecondClusOrig = BClustersSC[0]\n",
"SecondClusOrig.sort(lambda x,y: cmp(len(y) , len(x)))\n",
"SecondClusStrip = BClustersSC[1]\n",
"SecondClusStrip.sort(lambda x,y: cmp(len(y) , len(x)))"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 51
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"SecondMatchedDict = ClustersRemainders(SecondClassList, 0.85, DF, 'style', 'smv')"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 52
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"len(SecondMatchedDict)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 53,
"text": [
"8"
]
}
],
"prompt_number": 53
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"Count = 0\n",
"for key, value in SecondMatchedDict.iteritems():\n",
" for elem in value:\n",
" Count +=1\n",
" \n",
"Count"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 54,
"text": [
"16"
]
}
],
"prompt_number": 54
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"for key, value in SecondMatchedDict.iteritems():\n",
" print key, value\n",
" print"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"PJ-2913T PJ-2913 Top ['PJ-2913T PJ-2913 Top', 'PJ-2913T PJ-2913/2923 Top']\n",
"\n",
"354750Ta Cocoon Coocon Top_a ['354750Ta Cocoon Coocon Top_a', '185480Ta Cocoon Coocon Top_a']\n",
"\n",
"SR-541 S-Siv-T-S ['SR-541 S-Siv-T-S', 'SR-541 /SR-542 S-Siv-T-S']\n",
"\n",
"BS-1105 PJ-1105/49130 Top ['BS-1105 PJ-1105/49130 Top', 'BS-1106 Pj-1106/49131 Top']\n",
"\n",
"239851B Daniella Bottom ['239851B Daniella Bottom', '825211B Daniella Bottom']\n",
"\n",
"UWC-931-007Ta 192 Top large ['UWC-931-007Ta 192 Top large', 'UWC-931-007Ta 194 Top large']\n",
"\n",
"PJ-49131B PJ-49131 Nightware Bottom ['PJ-49131B PJ-49131 Nightware Bottom', 'PJ-49131B Pj-49131 /pj-2913 Nightware Bottom']\n",
"\n",
"SR-565 SR-542 S-Siv-T-S ['SR-565 SR-542 S-Siv-T-S', 'SR-565 SR-542/SR-565 S-Siv-T-S']\n",
"\n"
]
}
],
"prompt_number": 55
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"What the above demonstrates is that clearly there is a benefit to running the clustering a second time. This would seem to call for a recursive function that continues to perform the clustering until no more clusters are possible. When I ran the program, this would have clustered 33 style names into 16 clusters."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"A Recurcive Identifaction Function"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In order to achieve a recurcive function unfortunatley some modifications will necessary, but in fact this may actually make calling the function somewhat simpler"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def ClustersRecursive(Threshold, df, col1, col2, GenericAll, GenericWhite = None, DelWhite = False):\n",
" Styles = df[col1].unique()\n",
" ClassList = [Stripped(style, GenericAll, GenericWhite, DelWhite) for style in Styles]\n",
" ClustersDict = {}\n",
" Clusters = SlinkSC(ClassList, Threshold)\n",
" ClustersOriginal = Clusters[0]\n",
" ClustersCentroid = Clusters[2]\n",
" IndList = [x for x in xrange(len(ClustersOriginal)) if len(ClustersOriginal[x]) > 1] \n",
" MultiClusters = [ClustersOriginal[Ind] for Ind in IndList]\n",
" MultiCentroid = [ClustersCentroid[Ind] for Ind in IndList]\n",
" \n",
" if len(MultiClusters) == 0:\n",
" print 'Finished1'\n",
" return \n",
" else:\n",
" Counter = 0\n",
" for cluster in xrange(len(MultiClusters)):\n",
" MultiSMV = list(itertools.chain(*[df[df[col1] == elem][col2].unique() for elem in MultiClusters[cluster]]))\n",
" if len(set(MultiSMV)) == 1:\n",
" ClustersDict[MultiCentroid[cluster][1]] = MultiClusters[cluster]\n",
" Counter +=1\n",
" else:\n",
" if len(MultiSMV) == len(MultiClusters[cluster]):\n",
" for smv in list(set(MultiSMV)):\n",
" if MultiSMV.count(smv) >= 2:\n",
" BoolList = [True if elem == smv else False for elem in MultiSMV]\n",
" StrList = [MultiClusters[cluster][x] for x in xrange(len(BoolList)) if BoolList[x] == True]\n",
" StrList.sort(lambda x, y: cmp(len(x), len(y)))\n",
" ClustersDict[StrList[0]] = StrList\n",
" Counter +=1\n",
" \n",
" StringMap = {}\n",
" for key, value in ClustersDict.iteritems():\n",
" for elem in value:\n",
" StringMap[elem] = key\n",
" \n",
" \n",
" if Counter == 0:\n",
" return \n",
" else:\n",
" for row in DF.index:\n",
" try:\n",
" df[col1][row] = StringMap[df[col1][row]]\n",
" except KeyError:\n",
" pass\n",
" \n",
"\n",
" ClustersRecursive(Threshold, df, col1, col2, GenericAll, GenericWhite = None, DelWhite = False) "
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 56
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The function accepts arguments that should now be familar. \n",
"\n",
"The innovation here is that the function not only creates a dictionary of clustered strings, but it maps the dictionary to the underlying data frame from where the strings are drawn, thereby modifying the string names according to the centorid of the cluster they have been placed in. The function then recusively calls itself on the (now) modified string data. This will continue until no more clusters are formed that can be verified as matched according to the method already enumerated at length."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"DF['style_new2'] = DF.style"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 57
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Call the function on the data"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"ClustersRecursive(0.85, DF, 'style_new2', 'smv', GenericRemoveAll, GenericWhiteSpace, True)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 58
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Display number of unqiue strings in the data"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"len(DF.style_new2.unique())"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 59,
"text": [
"265"
]
}
],
"prompt_number": 59
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In testing this function iterated through four rounds of clustering. As can be seen from the above output it has reduced the number of unique strings to 259 (numbers may change when program is re-run). It seems possible that by recursively clustering the strings could also stabilize the clusters that are actually formed. Whereas with one round of clustering the number of strings clustered seemed to vary quite sizably, here the number of unique strings after clustering seems quite stable. \n",
"\n",
"I am quickly going to test how stable it is by seeing how many unique strings are left after multiple runs through the recursive function.\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"LenList = []\n",
"for x in xrange(20):\n",
" DF['style_new2'] = DF.style\n",
" ClustersRecursive(0.85, DF, 'style_new2', 'smv', GenericRemoveAll, GenericWhiteSpace, True)\n",
" LenList.append(len(DF.style_new2.unique()))\n",
" "
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 62
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print LenList"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[262, 259, 256, 260, 259, 260, 257, 258, 258, 257, 261, 259, 257, 258, 258, 253, 260, 257, 254, 256]\n"
]
}
],
"prompt_number": 63
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As the above output shows, the method is not perfect and does not generate the same results each time it is run, although within a fairly small window."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br />"
]
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Conclusions"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Efficacy** <br />\n",
"The string clustering method described here, seems to work relatively well. With the data provided a list of 450+ string has been reduced to a group of strings nearly half that size. \n",
"\n",
"If there is no alternative data available to the user by which the clusters can be verified, then some others means will have be sought. It is possible that using the SlinkSC function in a recursive manner (as displayed above in relation to the ClusterRecursive function), sensible clusters can be formed even without verifying data. Th threshold can be manipulated to ensure greater accuracy (at the cost of potentially missing true clusters). With small data sets where the data can be verified either by eye, or by some other method, this will work well.\n",
"\n",
"For large more complex sets of fuzzy strings it is likely that some verifying data will be necessary or some other method of exploring the veracity of the clustered data. \n",
"\n",
"**Caveats**<br />\n",
"The clustering method described here is not perfect. In particular the clusters that are generated are not independent of the order that the data are evaluated. The effects of this can be mitigated (or at least randomized) by shuffling the list of data to be clustered.\n",
"\n",
"There are doubtless many more problems of a technical nature that are somewhat beyond my limited understanding of clustering. \n",
"\n",
"**Use in the Future**<br />\n",
"Provided we can live with imperfect nature of the clustering, I am happy to move forward with using this method for matching strings into clusters in my work. \n",
"\n",
"It is possible that this notebook is too unwieldy in size to be useful to anyone but me, possibly I will create an example notebook that just goes through the final method (without the workings), possibly I can't be bothered though.\n"
]
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment